ON HRUSHOVSKI FUSIONS FOR PREDICATES AND THEIR ENVELOPES

S.V. Sudoplatov^{∗}

Sobolev Institute of Mathematics, 4, Acad. Koptyug avenue, Novosibirsk, 630090, Russia; Novosibirsk State Technical University, 20, K.Marx avenue, Novosibirsk, 630092, Russia e-mail: sudoplat@math.nsc.ru

E.Hrushovski [1] showed that, for any predicate symbol R, taking a linear prerank function of form

y_{R}(A) = |A| − α · e_{R}(A),

(where A is a structure ⟨A; R⟩, α ∈ ℝ^{+}, e_{R}(A) is a number of tuples in R, being interpreted in A) and a class K_{R} of finite structures A with y_{R}(A) ≥ 0, one get a saturated countable K_{R}-generic (in the sense of [2, 3]) structure M_{R} = ⟨M_{R}; R⟩ with a stable theory.

For predicate symbols R_{1}, …, R_{n}, …, taking a prerank function

y_{R_{1},...,R_{n},...}(A) = |A| − ∑_{i} α_{i} · e_{R_{i}}(A),

and a class K_{R_{1},...,R_{n},...} of finite structures A of language {R_{1}, …, R_{n}, …} with y_{R_{1},...,R_{n},...}(A) ≥ 0, one again get a saturated countable K_{R_{1},...,R_{n},...}- generic structure M with a stable theory and such that M ↾ R_{i} = M_{R_{i}}. That structure M is called the Hrushovski fusion of structures M_{R_{i}} (cf. [3, 4, 5]). Considering M itself, M and the restrictions M ↾ {R_{i_{1}}, …, R_{i_{k}}, …} are called the Hrushovski structures. If for a Hrushovski structure M, arities for all relations R_{i} are at most r, coefficients α_{i} are chosen in Herwig style [6] (cf. [3, Chapter 4]) and additionally with α_{i}·(k_{p})^{r} < ε_{p}, as well as the special b_{n}^{p} are lower bounds for p-approximations of y_{R_{1},...,R_{n},...} (with ∑_{i=1}^{p} instead of

∗The work is supported by RFFI (grant 09-01-00336-a), by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-3669.2010.1, and by the grant of Novosibirsk State Technical University.

∑_{i}), then M is called a Hrushovski–Herwig structure.

Notice that each Hrushovski structure is countable. Notice also that, by construction, the Hrushovski structures in [3] are Hrushovski–Herwig structures.

The following definition generalizes the notion of (binary) envelope in [3], being used for constructions of generic Ehrenfeucht theories.

Definition. Let R(x_{1}, …, x_{n}) be an atomic formula, x̄ be a tuple with coordinates in {x_{1}, …, x_{n}}. The formula ∃x̄ R(x_{1}, …, x_{n}) (as well as the correspondent relations in structures) is called the x̄-projection or the x̄- envelope of R(x_{1}, …, x_{n}). A tuple (Q_{1}, …, Q_{m}) is an envelope of the relation R or R-envelope if, for each coordinate x_{i} in R(x_{1}, …, x_{n}), there is a tuple x̄ without x_{i} such that some Q_{j} is an x̄-envelope of R. The envelope (Q_{1}, …, Q_{m}) is k-ary if each Q_{j} is a k-ary relation. Any 2-ary envelope is called binary. If (Q_{1}, …, Q_{m}) is an envelope of R, the relation R is called the bush in (Q_{1}, …, Q_{m}).

Since

R(x_{1}, …, x_{n}) ⊢ ∃x̄ R(x_{1}, …, x_{n}),

any envelope (Q_{1}, …, Q_{m}) forms a formula

φ(x_{1}, …, x_{n}) ⇌ ⋀_{j=1}^{m} ∃x̄^{j} R(x_{1}, …, x_{n}),

where ∃x̄^{j} R(x_{1}, …, x_{n}) corresponds to Q_{j}, such that

R(x_{1}, …, x_{n}) ⊢ φ(x_{1}, …, x_{n}).

Now we consider an influence of bushes R and their envelopes (Q_{1}, …, Q_{m}) with respect to Hrushovski construction, as well as Hrushovski fusions for R and (Q_{1}, …, Q_{m}).

A bush R (an envelope (Q_{1}, …, Q_{m})) is a Hrushovski(–Herwig) bush (a Hrushovski(–Herwig) envelope) if its structure M is a generic Hrushovski(– Herwig) structure.

The following examples show that an existence of K_{R}-generic Hrushovski structure can not guarantee that envelopes of R are Hrushovski envelopes.

Example. Let R(x, y_{1}, …, y_{n}) be an infinite bush (with a K_{R}-generic Hrushovski structure) for a binary envelope (Q_{1}, …, Q_{n}), where

∃y_{1}, …, y_{i−1}, y_{i+1}, …, y_{n} R(x, y_{1}, …, y_{n}) ≡ Q_{i}(x, y_{i}),

i = 1, …, n, Q_{j} = Q_{k} for some j ≠ k, and Q_{j} satisfies the pairwise intersection property [3], i. e.,

⊧ ∀x, y∃z(Q_{j}(z, x) ∧ Q_{j}(z, y)).

Then the binary R-envelope (Q_{1}, …, Q_{n}, Q_{n+1}), where Q_{n+1} corresponds to the formula

∃x, y_{1}, …, y_{j−1}, y_{j+1} …, y_{k−1}, y_{k+1}, …, y_{n} R(x, y_{1}, …, y_{n}),

has the coordinate Q_{n+1} that forms a complete graph (having \frac{n(n−1)}{2} edges for n-element subgraphs). Thus there is no Hrushovski structures with respect to the class K_{Q_{n+1}}, being generated by finite restrictions of a Q_{n+1}-structure. If n > 2 one can replace Q_{j} and Q_{k} by Q_{n+1} and again get an non-Hrushovski R-envelope. □

Modifying Example one can get a K_{R}-generic Hrushovski structure with a binary envelope (Q_{1}, …, Q_{n}), not having the pairwise intersection property but with O(k^{2}) edges for k-element subgraphs with respect to some Q_{i} producing a non-Hrushovski generic structure.

Recall [1, 3] that a finite substructure A in a Hrushovski structure M is strong or self-sufficient if y_{·}(A) ≤ y_{·}(B) for any finite B with A ⊆ B ⊆ M.

A Hrushovski relation R is self-sufficient any tuple (a_{1}, …, a_{n}) in R forms a self-sufficient set {a_{1}, …, a_{n}}.

Theorem. If (Q_{1}, …, Q_{m}) be a Hrushovski-Herwig envelope for an nary bush and consisting of self-sufficient relations, then (Q_{1}, …, Q_{m}) has a Hrushovski-Herwig bush R forming a Hrushovski fusion of generic structures M_{Q_{i}}, i = 1, …, m, and M_{R}.

Proof. Let

y_{Q_{1},...,Q_{m}}(A) = |A| − ∑_{i=1}^{m} α_{i} · e_{Q_{i}}(A),

be the prerank function for a generic model M_{Q_{1},...,Q_{m}}. Take α_{m+1}, being in Herwig construction [3, 6] and additionally with α_{m+1} · (k_{p})^{n} < ε_{p}, allow to permutate coordinates of tuples in R, preserving R, and to put (a_{1}, …, a_{n}) in R if that tuple belongs to a bush of (Q_{1}, …, Q_{m})).

Now we consider the prerank function

y_{Q_{1},...,Q_{m},R}(A) = |A| − ∑_{i=1}^{m} α_{i} · e_{Q_{i}}(A) − α_{m+1} · e_{R}(A).

By choice of α_{m+1} for any n-element restriction A_{0} of structure in K_{Q_{1},...,Q_{m}} there is a bush R of a copy of a restriction of (Q_{1}, …, Q_{m}) such that papproximations of y_{Q_{1},...,Q_{m},R}(A) have lower bounds b_{n′}^{p} for any non-empty restrictions A of A_{0}.^{1} Thus, a class K_{Q_{1},...,Q_{m},R} of finite (Q_{1}, …, Q_{m}, R)- structures A with that lower bounds b_{n′}^{p} for p-approximations is generic. Since each Q_{i} is self-sufficient, for each tuple ā_{i} ∈ Q_{i}, i = 1, …, m, the structure A_{i} with the universe A_{i}, consisting of all elements in ā_{i}, admits (using standard arguments of Amalgamation Lemmas in [3]) the free amalgamation B ∗_{A_{i}} A′ inside the class K_{Q_{1},...,Q_{m},R}, where A′ is a copy of A_{0} such that A_{i} is a strong restriction of A′ to a tuple in Q_{i}, and A_{i} is a strong substructure of B. Thus, in that amalgams, ā belongs to the according projection of R. Taking a K_{Q_{1},...,Q_{m},R}-generic structure M, we get the small stable theory Th(M) and a required Hrushovski fusion with a bush R for the envelope (Q_{1}, …, Q_{m}). □

References

[1] Hrushovski E. A stable ℵ_{0}-categorical pseudoplane / E. Hrushovski. — Jerusalem : Hebrew University, 1988. — (Preprint).

[2] Sudoplatov S. V. Syntactic approach to constructions of generic models / S. V. Sudoplatov // Algebra and Logic. — 2007. — Vol. 46, No. 2. — P. 134–146.

[3] Sudoplatov S. V. The Lachlan problem / S. V. Sudoplatov. — Novosibirsk : NSTU, 2009. — 336 p. [in Russian]

[4] Hrushovski E. A new strongly minimal set / E. Hrushovski // Ann. Pure and Appl. Logic. — 1993. — Vol. 62, No. 2. — P. 147–166.

[5] Sudoplatov S. V. On the finite closure property for fusions of generic classes / S. V. Sudoplatov // Algebra and Model Theory 7. Collection of papers / eds.: A. G. Pinus, K. N. Ponomaryov, S. V. Sudoplatov. — Novosibirsk : NSTU, 2009. — P. 131–140. [in Russian]

[6] Herwig B. Weight ω in stable theories with few types / B. Herwig // J. Symbolic Logic. — 1995. — Vol. 60, No. 2. — P. 353–373.

1The coefficients (k_{p})^{n} allow to add to R some or all permutations of any tuple in the bush R, if it is necessary, staying in the class K_{Q_{1},...,Q_{m},R} with lower bounds b_{n′}^{p}.