1 Introduction
The subject of this article is the first-order theory of a class of combinatorial structures called free Steiner triple systems (STSs). An STS of order
$\lambda $
is a pair
$(M, \mathcal {B})$
, where M is a set with
$\lambda $
elements, and
$\mathcal {B}$
is a collection of 3-element subsets of M (the blocks) such that any two
$x, y \in M$
are contained in exactly one block. A set M with a collection of 3-element subsets is a partial STS (PSTS) if any two elements of M belong to at most one block.
Varying the parameters 2 and 3 gives the more general notion of a Steiner
$(t,k)$
-system, where blocks have size k and every t-subset is contained in exactly one block.
Steiner systems are well-known structures, widely studied in the finite case. Recently, certain infinite incarnations have appeared in the model-theoretic literature, e.g., as examples of strongly minimal structures [Reference Baldwin and Paolini4], or as specific constructions such as Fraïssé amalgamations [Reference Barbina and Casanovas6]. These constructions exhibit a range of stability behaviours: the structure in [Reference Barbina and Casanovas6] is
$\mathrm {TP}_2$
and
$\mathrm {NSOP}_1$
, and thus it lies at the opposite end of the stability spectrum from its counterparts in [Reference Baldwin and Paolini4].
An interest has emerged, more broadly, in the model theory of incidence structures—see, for example, [Reference Conant and Kruckman11] for generic incidence structures, [Reference Hyttinen and Paolini21] for projective spaces, [Reference Baldwin and Paolini4] and [Reference Baldwin2] for Steiner systems, and [Reference Ammer and Tent1] for generalised n-gons. In [Reference Ammer and Tent1, Reference Baldwin2, Reference Conant and Kruckman11, Reference Hyttinen and Paolini21], the structures involved are described as either two-sorted or bipartite, with one sort (resp. part) for points and one for lines. In [Reference Baldwin and Paolini4], the vocabulary is relational and one-sorted. As we shall see, here (and in [Reference Barbina and Casanovas6]) STSs are one-sorted structures, which means our methods are generally different.
A notable construction method that applies to incidence structures and, more generally, to algebras, generates free structures. Universal algebra gives a standard characterization of free constructions, which, in the case of STSs, captures the intuition that an infinite STS can be obtained from an initial set A containing
$\lambda $
vertices with no blocks defined among them by adding, for each pair of vertices
$a_1, a_2 \in A$
, a new point that gives the unique block to which
$a_1$
and
$a_2$
belong. Iterating this process
$\omega $
times gives an STS. The template example in [Reference Chicot, Grannell, Griggs and Webb9] is, essentially, the result of this construction for
$\lambda =3$
.
Standard universal-algebraic tools tell us that such free constructions are uniquely determined up to isomorphism by the cardinality of the generating set A. A series of natural questions then arises, such as which first-order properties, if any, are shared by two free constructions where the sizes of the initial generating sets are different.
Questions of this kind have been addressed, for example, for projective planes [Reference Hyttinen and Paolini21] and for generalised polygons [Reference Ammer and Tent1]. Towards the completion of the write-up of our results, we became aware of [Reference Paolini and Quadrellaro26]—see the end of this section for the connection with our work.
In these papers, free structures are characterised via the existence of specific constructions in stages, rather than through the universal algebraic definition. Our choice of a one-sorted, functional language (see below) for STSs makes the connection with universal algebra rather natural, and distinguishes our methods.
A PSTS can be regarded as a first-order structure in the language containing a ternary relation symbol R and satisfying the axioms:
-
• for all permutations
$\sigma \in S_3$
,
$ \forall x_1 x_2 x_3 \, (R(x_1, x_2, x_3) \rightarrow R(x_{\sigma (1)}, x_{\sigma (2)}, x_{\sigma (3)} )$
; -
•
$\forall x y z ( R(x,y,z) \rightarrow y\neq z )$
; -
•
$\forall x y w z ( R(x,y,w) \wedge R(x,y,z) \rightarrow w=z )$
.
The relation R is interpreted as the set of blocks: three elements
$x, y,$
and z are in a block if and only if
$R(x,y,z)$
. A PSTS that satisfies the additional axiom
-
•
$\forall x y ( x \neq y \rightarrow \exists z \,R(x,y,z))$
is an STS. With this choice of language, a substructure of an STS is a PSTS.
An STS can also be described as a Steiner quasigroup, that is, a structure with a single binary operation symbol
$\cdot $
, interpreted as an operation that satisfies the following axioms:
-
1.
$\forall x y \, (x \cdot y= y\cdot x);$
-
2.
$\forall x \, (x\cdot x =x);$
-
3.
$\forall x y \, (x\cdot (x\cdot y)=y)$
.
Thus, Steiner quasigroups are an equational class (see [Reference Ganter and Werner15, Reference Ganter, Werner, Linder and Rosa16]). This is what makes it possible to employ universal algebraic tools.
A quasigroup M determines an STS whose blocks are the elements of the graph of the operation
$\cdot $
without the diagonal, that is,
$$\begin{align*}\mathcal{B} = \{ \{x,y,z \} \subseteq M : x \cdot y = z \} \smallsetminus \{ \{x \} : x \in M \} \, .\end{align*}$$
It is easy to see that each STS determines a quasigroup and each quasigroup determines an STS, where
$$ \begin{align*}x \cdot y = z \text{ iff } R(x,y,z) \text{ or } x=y=z.\end{align*} $$
In fact, as noted in [Reference Ganter and Werner15, Reference Ganter, Werner, Linder and Rosa16], this shows that each STS is bi-interpretable with a Steiner quasigroup, and justifies our choice to use the term STS to cover both the functional and relational structures from the end of this section onwards.
A detailed account of the relation between Steiner quasigroups and Steiner systems can be found in [Reference Baldwin3], where the author shows that each strongly minimal Steiner
$(2,k)$
-system constructed in [Reference Baldwin and Paolini4] can be coordinatised by a quasigroup when k is a prime power. In particular, in Section 3 STSs are shown to be bi-interpretable with, rather than simply coordinatised by, Steiner quasigroups. Instead, when
$k \neq 3$
the strongly minimal Steiner
$(2,k)$
-systems constructed in [Reference Baldwin and Paolini4] can be interpreted in appropriate quasigroups, but no interpretation can be found in the other direction. This confirms that treating STSs as quasigroups makes algebraic tools available that are not applicable when they are described as incidence structures.
Since the quasigroup axioms are universal, it is clear that a substructure of a Steiner quasigroup is a Steiner quasigroup. Moreover, if N is a Steiner quasigroup and
$A \subseteq N$
, there is a natural notion of substructure of N generated by A, namely,
$$\begin{align*}\langle A \rangle_N = \bigcap \{ M\subseteq N : M \text{ is a substructure that contains } A \}.\end{align*}$$
The subscript N may be omitted when clear from the context.
Remark 1.1. Let M be a Steiner quasigroup generated by
$A\subseteq M$
. Then
-
• for every
$b \in M$
there is a term
$t(\bar {x})$
such that
$b=t(\bar {a})$
, where
$\bar {a}$
enumerates A; -
•
$M=\bigcup _{n<\omega } S_n$
for a chain of sets
$S_n$
such that
$S_0 =A$
and
$S_{n+1}= \{a\cdot b\mid a,b\in S_n\}$
. Note that
$S_n\subseteq S_{n+1}$
since
$a\cdot a = a$
.
Notation. Below we write
$S_{<n}$
for
$\bigcup _{i<n} S_i$
.
Definition 1.2. Let M be a Steiner quasigroup generated by
$A\subseteq M$
. The sets
$S_n$
in Remark 1.1 are called the levels of M over A. An element
$a\in M$
has level n over A if
$a\in S_n\smallsetminus S_{<n}$
.
As remarked above, in what follows the term STS is used for Steiner quasigroups, too; we rely on the context to clarify the usage.
In Section 2 we characterise free STSs as those that are freely generated by a subset in the sense of universal algebra, and we recall some standard universal-algebraic results. Section 3 introduces certain linear orderings for STSs and PSTSs that are an essential tool in our treatment of the theory of free STSs. Moreover, we show that the existence of an HF-ordering on an STS is equivalent to its unconfinedness, a first-order condition that is satisfied by all infinite free STSs and will essentially axiomatise their theory. In Section 4 we show that the amalgamation property fails for the class
$\mathcal {C}_{{\mathrm {un}}}$
of finite unconfined PSTSs. We also show that the obvious choice of a predimension function does not yield a fruitful definition of strong substructure for the construction of a Hrushovski amalgam. An appropriate notion of strong substrcuture is formulated in Section 5 and it involves HF-orderings. We show that the countable free STS with
$\omega $
generators is the generic object for
$\mathcal {C}_{{\mathrm {un}}}$
with respect to this notion. We also give appropriate definitions of n-strong substructure and n-amalgamation and use the setup in [Reference Wagner, Kaye and Macpherson29] to show that the generic is not saturated. In Section 6 we show that infinite unconfined STSs always contain certain binary trees that are an essential ingredient in the proof of our main result in Section 7, where we prove that the theory of infinite unconfined STSs is complete and it is the theory of infinite free STSs—so, in particular, any two free infinite STSs are elementarily equivalent. We also show that the theory is stable and that it has a model which is not free.
Our elementary equivalence result appears to be a special case of the main theorem in [Reference Paolini and Quadrellaro26], developed independently, where the completeness and strict stability are asserted for the theories of a range of open incidence structures that includes free Steiner systems (hence free STSs). The results in [Reference Paolini and Quadrellaro26] generalise those in [Reference Ammer and Tent1, Reference Hyttinen and Paolini21]. As previously noted, a two-sorted language is chosen in [Reference Paolini and Quadrellaro26]. This allows for a uniform treatment of the range of incidence structures considered in the article. Since here we restrict our attention to STSs, we can adopt the more natural choice of a one-sorted language, which leads to different methods and considerable simplifications.
2 Free Steiner triple systems: Universal algebra
We give a universal algebraic characterisation of free STSs as those that satisfy a universal mapping property (UMP).
Definition 2.1. Let
$\mathcal {C}$
be a class of STSs. An STS M generated by A has the UMP over A for
$\mathcal {C}$
if for every
$N \in \mathcal {C}$
, every map
$$\begin{align*}\varphi : A \to N \end{align*}$$
extends to a homomorphism
$ \hat {\varphi } : M \to N $
.
A standard argument (see, e.g., [Reference Grätzer17, Section 24, Corollary 1]) ensures that the extension
$\hat {\varphi }$
is unique.
Definition 2.2. If M is an STS, a subset
$A \subseteq M$
is independent if
$\langle A \rangle _M$
has UMP over A for the class of all STSs.
M is said to be freely generated by A if:
-
(i) A is independent;
-
(ii)
$\langle A \rangle _M = M$
.
If M is freely generated by
$A \subseteq M$
then M is a free STS, and A is a free base of M.
The next proposition formalises the intuition that an STS freely generated by a subset A can be constructed from A in stages by adding, at each stage, a new vertex as the product of two existing vertices whose product is still undefined. This construction was first described in [Reference Siebenmann28] as the result of a free extension process, and later generalised in [Reference Funk, Strambach and Buekenhout14] to various classes of incidence geometries that include, among others, projective and affine planes, generalised n-gons, k-nets, and Steiner
$(t,k)$
-systems. For convenience, we state a version for STSs that lists explicitly the properties we require in the rest of the article.
Proposition 2.3. Let M be an STS and let
$A\subseteq M$
. The following are equivalent:
-
1. A is a free base of M.
-
2. M is generated by A with levels
$(S_n\mid n<\omega )$
, where
$S_0=A$
and-
(a) if
$a,b\in S_n\smallsetminus S_{<n}$
and
$a\neq b$
, then
$a\cdot b\not \in S_n$
. -
(b) if
$a\in S_{n+1}\smallsetminus S_n$
, there is a unique pair
$\{b,c\}\subseteq S_n$
such that
$b\neq c$
and
$a= b\cdot c$
.
-
Moreover, property (b) implies that if
$a\in S_{n+1}\smallsetminus S_n$
, and
$b, a\cdot b\in S_n$
, then
$\{b,a\cdot b\}$
is the unique pair given by (b) for a.
Proof. See [Reference Barbina and Casanovas7, Proposition 3.1].
Notice that each set
$S_{n+1}\smallsetminus S_n$
in the construction above generates a subsystem of M that satisfies condition 2, so
$S_{n+1}\smallsetminus S_n$
is a free base for
$\langle S_{n+1}\smallsetminus S_n \rangle $
, and in particular an independent set. It follows that M contains independent sets of finite unbounded cardinality. In fact, M also contains an independent set of cardinality
$\omega $
—a proof for Steiner loops in [Reference Markovski and Sokolova24] is easily adapted to STSs.
Definition 2.4. Let M be an STS with a free base
$A\subseteq M$
. The sequence
${(S_n\mid n<\omega )}$
of levels described in Proposition 2.3 will be called a standard free construction of M over A.
Standard techniques for any variety in universal algebra show that the cardinality of a free base A determines the STS freely generated by A up to isomorphism.
Proposition 2.5. Let
$M,N$
be STSs freely generated by
$A\subseteq M$
and
$B\subseteq N,$
respectively. Then
$M\cong N$
if and only if
$|A|=|B|$
. In fact, every bijection between A and B can be extended to an isomorphism between M and N.
Proof. This follows from Theorem I in [Reference Fujiwara13], and Lemma 2.6 and Theorems 1 and 2 in [Reference Jónsson and Tarski22]. See [Reference Barbina and Casanovas7, Corollary 2.11] for a self-contained version of these arguments in the case of STSs.
The elementary equivalence of any two infinitely generated free STSs follows from a standard argument for infinitely generated free algebras.
Lemma 2.6. Let
$M,N$
be free STSs and assume A is an infinite free base of M that can be extended to a free base B of N. Then
$M\preccurlyeq N$
.
Proof. See [Reference Grätzer17, Chapter 6, Section 38, Theorem 4].
Theorem 2.7. If
$M,N$
are free STSs with infinite free bases, then
$M \equiv N$
.
Proof. See [Reference Grätzer17, Chapter 6, Section 38, Corollary to Theorem 5].
3 HF-orderings and confined configurations
The idea of free and hyperfree extension processes appears in the context of free projective planes in [Reference Siebenmann28] and has subsequently been generalised to a wider range of incidence structures that includes STSs in [Reference Funk, Strambach and Buekenhout14]. Such processes yield well-founded constructions of incidence structures from existing ones by adding new elements one at a time, with suitable restrictions on the number of incidences. In [Reference Hyttinen and Paolini21], the related notions of HF- (hyperfree) and F- (free) orderings are formulated for projective planes to dispense with the well-foundedness assumption. These orderings have natural parallels for partial and complete STSs, respectively. Their properties are proved below by adapting arguments that appear in [Reference Funk, Strambach and Buekenhout14, Reference Hyttinen and Paolini21] for two-sorted incidence structures.
Definition 3.1. A free ordering (or F-ordering) of an STS M over
$A\subseteq M$
is a linear ordering
$<$
of M such that for every
$a\in M$
there is a unique pair
$\{a_1,a_2\}\subseteq M$
with
$a=a_1\cdot a_2$
, and, for each i, either
$a_i\in A$
or
$a_i<a$
. Notice that when
$a\in A$
, the only possibility is
$a_1=a_2=a$
.
In our discussion of linear orderings we use standard operations as defined, for instance, in [Reference Rosenstein27]. In particular, if
$(A,<_A)$
and
$(B,<_B)$
are linear orderings and
$A\cap B=\emptyset $
, then their sum is the linear order
$$\begin{align*}(A\cup B, <)= (A,<_A) + (B,<_B) \, ,\end{align*}$$
where
$<$
is defined as
$<_A\cup <_B \cup \, (A\times B)$
.
Remark 3.2. Let M be an STS with standard free construction
$(S_n\mid n<\omega )$
over A. Let
$<_n$
be a linear ordering of
$S_n\smallsetminus S_{<n}$
and for
$a,b\in M$
define
$$ \begin{align*}a<b \text{ iff for some } n,\; b\in S_n\smallsetminus S_{<n} \text{ and either } a\in S_{<n} \text{ or } a\in S_n\smallsetminus S_{<n} \text{ and } a<_n b.\end{align*} $$
Then
$<$
is an F-ordering of M over
$A=S_0$
, which is an initial segment, and
$<$
is in fact the generalized sum
$\sum _{n<\omega }(S_n\smallsetminus S_{<n}, <_n)$
. If every
$<_n$
is a well-order,
$<$
is a well-order.
Remark 3.3. Let M be an STS. If there is an F-ordering of M over A, there is another one where A is an initial segment. If the original order is a well-order, so is the new order; moreover,
$M=\langle A\rangle $
.
Proof. If
$<$
is an F-ordering of M over A, then the sum
$(A,<\restriction A)+(M\smallsetminus A, <\restriction (M\smallsetminus A))$
defines an F-ordering of M over A with initial segment A.
Definition 3.4. A hyperfree ordering (or HF-ordering) of a PSTS A is a linear ordering
$<$
of A such that for every
$a\in A$
there is at most one pair of smaller elements
$\{a_1,a_2\}\subseteq A$
with
$a=a_1\cdot a_2$
, that is, there is at most one block
$\{a,a_1,a_2\}$
with
$a_1,a_2<a$
.
The next proposition explains the connection between free bases and F-/HF-orderings.
Proposition 3.5. Assume M is an STS and
$A\subseteq M$
. The following are equivalent:
-
1. A is a free base of M (as a Steiner quasigroup).
-
2. There is a well-founded F-ordering of M over
$A.$
-
3. There is a well-founded HF-ordering of M and A is the set of points that are not a product of smaller elements.
Proof. See [Reference Barbina and Casanovas7, Proposition 3.7].
Free STSs satisfy a property which can be expressed through infinitely many first-order universal sentences.
Definition 3.6. A finite PSTS A is confined if every element of A belongs to at least two blocks.
A PSTS
$A\neq \emptyset $
is unconfined, or contains no confined configuration, if no finite
$A^\prime \subseteq A$
is confined.
Equivalently,
$A\neq \emptyset $
is unconfined if for all finite
$A^\prime \subseteq A$
there is
$a \in A^\prime $
that belongs to at most one block in
$A^\prime $
, that is, a is either not a product of any elements in
$A^\prime $
, or the product of exactly one pair of elements of
$A^\prime $
.
Note that being unconfined is stronger than not being confined: an unconfined PSTS is hereditarily not confined.
In [Reference Hall18], confined partial projective planes are those where every line contains three or more points, and there are three or more lines through every point. If a finite partial plane is not confined, then it is open. These notions are later used in [Reference Siebenmann28] and they are central in [Reference Hyttinen and Paolini21]. Analogues are defined in [Reference Funk, Strambach and Buekenhout14] for the range of incidence structures treated in the article, including Steiner systems. Our definition of unconfined PSTS is equivalent to that of open PSTS in [Reference Funk, Strambach and Buekenhout14].
Proposition 3.7.
-
1. Free STSs are unconfined.
-
2. Finitely generated unconfined STSs are free.
-
3. A PSTS is unconfined if and only if it has an HF-ordering.
Proof. See [Reference Barbina and Casanovas7, Propositions 3.10, 3.11, 3.13] for (1), (2), and (3), respectively.
Definition 3.8. Let
$A\subseteq B$
be PSTS. An HF-ordering
$<$
of B is over A if for every
$a\in B\smallsetminus A$
there is at most one pair
$\{a_1,a_2\}$
of distinct elements of B such that
$\{a,a_1,a_2\}$
is a block and for every i, either
$a_i<a$
or
$a_i\in A$
.
Note that if B is an STS, any F-ordering of B over
$A\subseteq B$
is an HF-ordering over A, but even if an HF-ordering over A is an F-ordering (over some subset of B), it is not necessarily an F-ordering over A, since elements of A can be a product of smaller elements of A.
Lemma 3.9. Let
$A\subseteq B$
be PSTS. There is an HF-ordering of B over A if and only if there is an HF-ordering of B, where A is an initial segment. In fact, given any HF-ordering
$<$
of B over A, the sum
$(A,<\restriction A)+(B\smallsetminus A, <\restriction (B\smallsetminus A))$
is an HF-ordering of B with initial segment A.
Proof. On the one hand, if
$<$
is an HF-ordering of B with initial segment A, it easy to see that it is an HF-ordering over A. On the other hand, assume
$<$
is an HF-ordering of B over A. Then the only way in which the sum can fail to be an HF-ordering is for some
$a\in B \smallsetminus A$
to be a product of two different pairs of smaller elements, and each element is either smaller than a in
$<$
or belongs to A, contradicting that
$<$
is an HF-ordering over A.
Definition 3.10. Given an HF-ordering
$<$
of the PSTS B and a subset
$A\subseteq B$
, we define the
$<$
-closure of A (in B) as the smallest subset C of B containing A and such that whenever
$b\in C$
and
$b_1,b_2 < b$
and
$\{b,b_1,b_2\}$
is a block, then
$b_1,b_2\in C$
. We denote C by
$\operatorname {\mathrm {cl}}_<(A)$
.
It is clear that the
$<$
-closure is a finitary closure operator on subsets of B. Moreover,
$$\begin{align*}\operatorname{\mathrm{cl}}_<(A_1\cup A_2)= \operatorname{\mathrm{cl}}_<(A_1) \cup \operatorname{\mathrm{cl}}_<(A_2).\end{align*}$$
Lemma 3.11. If
$<$
is an HF-ordering of B and
$A=\operatorname {\mathrm {cl}}_<(A)\subseteq B$
, then
$<$
is an HF-ordering of B over A.
Proof. If not, there is some
$b\in B\smallsetminus A$
and there are distinct
$b_1,b_2,b_3,b_4$
, such that
$\{b,b_1,b_2\}$
and
$\{b,b_3,b_4\}$
are blocks and, for each i, either
$b_i < b$
or
$b_i \in A$
. Without loss of generality,
$b_2 <b_1$
. We claim that
$b_1 < b$
. If not, then
$b_1\in A$
and
$b <b_1$
, and since
$A=\operatorname {\mathrm {cl}}_<(A)$
, we get
$b \in A$
, a contradiction. Hence,
$b>b_1>b_2$
. By a similar argument,
$b> b_3,b_4$
. But then
$<$
is not an HF-ordering.
Lemma 3.12. Assume
$<$
is an HF-ordering of B,
$A=\operatorname {\mathrm {cl}}_<(A)\subseteq B$
and
$C\subseteq B$
is an initial segment such that
$c<a$
whenever
$c\in C$
and
$a\in A$
. Then we can interpolate A between C and the rest of the order of B in such a way that we obtain an HF-ordering. In other words,
$$ \begin{align*}(C, <\restriction C) +(A, <\restriction A) + (B\smallsetminus (A\cup C), <\restriction B\smallsetminus(A\cup C))\end{align*} $$
is an HF-ordering of B. Moreover, we can change the ordering of A by any other HF-ordering of A and still have an HF-ordering of B.
Proof. Notice that
$(C, <\restriction C) +(A, <\restriction A)= (A\cup C,<\restriction (A\cup C))$
. Since
$\operatorname {\mathrm {cl}}_<(A\cup C)=A\cup C$
, Lemma 3.11 ensures that
$<$
is an HF-ordering of B over
$A\cup C$
. For the moreover clause, note that no element of A is a product of elements of C nor a product of an element of C by an element of A.
Lemma 3.13. If
$<$
is an HF-ordering of M,
$A\subseteq M$
and
$\operatorname {\mathrm {cl}}_<(A)=A$
, then
$\operatorname {\mathrm {cl}}_<(\langle A\rangle )= \langle A \rangle $
.
Proof. Let
$\langle A\rangle = \bigcup _{n<\omega }A_n$
, where
$A_0=A$
and
$A_{n+1}$
is the set of elements of
$\langle A\rangle \smallsetminus (A_0\cup \cdots \cup A_n)$
which are a product of two elements of
$A_0\cup \cdots \cup A_n$
. It is enough to prove by induction that, for every n,
$\operatorname {\mathrm {cl}}_<(A_0\cup \cdots \cup A_n)= A_0\cup \cdots \cup A_n$
. This is clear for
$n=0$
. Assume
$a\in A_{n+1}\smallsetminus (A_0\cup \cdots \cup A_n)$
. There are
$b,c\in A_0\cup \cdots \cup A_n$
such that
$a=b\cdot c$
. If
$b>a$
or
$c>a$
, then
$a\in \operatorname {\mathrm {cl}}_<(A_0\cup \cdots \cup A_n)= A_0\cup \cdots \cup A_n$
, a contradiction. Otherwise,
$a>b,c$
and
$\{b,c\}\subseteq A_0\cup \cdots \cup A_n$
is the unique pair of elements such that
$a>b,c$
and
$a=b\cdot c$
.
4 Some remarks on predimension
In [Reference Hall18], a notion of rank for projective planes is defined whose analogue for STSs coincides with a natural choice for a predimension function. As we shall see, though, this predimension function is not suitable for defining a notion of strong substructure that would lead to the construction of a Hrushovski-style amalgam—in fact, this is what motivates the different choice of predimension to build the uncountably many strongly minimal Steiner systems in [Reference Baldwin and Paolini4].
We show that the amalgamation property fails in the class of finite partial unconfined STSs with respect to both the substructure relation, and the obvious definition of strong substructure via predimension. This is why, in Section 5, our construction of a generic object requires a rather different, and possibly not as natural, notion of strong substructure.
We also include a comparison with a class of finite PSTSs, defined in [Reference Evans12] in a wider context, that properly contains the unconfined ones and where predimension works well instead. While these results have no direct application in subsequent sections, they clarify the context and may have independent interest.
Definition 4.1. Let A be a finite PSTS and let
$\operatorname {\mathrm {b}}(A)$
be the set of blocks in A. Then the rank, or predimension, of A is
$$\begin{align*}\delta(A)= |A|-|\operatorname{\mathrm{b}}(A)| \, .\end{align*}$$
Remark 4.2. It is well known (see, e.g., Subsection 1.1.1 in [Reference Colbourn and Rosa10]) that in a finite STS M of cardinality
$n:$
-
• any point lies in
$\frac {n-1}{2}$
blocks; -
• there are
$\frac {n(n-1)}{6}$
blocks.
It follows that:
-
1. an unconfined STS M is infinite, or
$|M|=3;$
-
2. if M is an STS of cardinality
$\geq 3$
then
$\delta (S)\leq 0$
.
For 1, let M be a finite STS such that
$|M|> 3$
. Then M is a PSTS contained in M such that any
$p \in M$
lies in
$\frac {n-1}{2}$
blocks. Since
$n>3$
,
$\frac {n-1}{2}>1$
.
For 2, let M be a finite SMS of cardinality
$n \geq 3$
. Then
$$\begin{align*}\delta(M) = n - \dfrac{n(n-1)}{6} \end{align*}$$
and
$\delta (M) \geq 0$
if and only if
$0 \leq n \leq 7$
. In fact, the predimension of the Fano plane (the unique STS of order 7) is 0, and the predimension of all other finite, non-trivial STS is negative.
Nevertheless, suitable subclasses of the class of finite PSTSs characterised in terms of non-negative dimension. The next lemma is an adaptation of the corollary to Lemma 1 in [Reference Siebenmann28].
Lemma 4.3. The predimension of a finite PSTS A that contains no confined configuration is non-negative.
Proof. Suppose
$|A|=n$
. Since A is unconfined, we can find an HF-ordering
$$\begin{align*}a_1 < a_2 < \cdots < a_n \, .\end{align*}$$
Let
$A_i:= \{a_1, \ldots , a_i \}$
for
$1 \leq i \leq n$
. Then, if
$|\mathrm {b}(A_i)|$
is the number of blocks in
$A_i$
,
$$ \begin{align*}\delta(A_i)= \begin{cases} |A_{i-1}|- |\mathrm{b}(A_{i-1})| +1 -1 = \delta(A_{i-1}) & \text{ if } a_i \text{ belongs to one block in } A_i \\ |A_{i-1}|- |\mathrm{b}(A_{i-1})| +1 & \text{ if } a_i \text{ belongs to no blocks in } A_i \, .\end{cases}\end{align*} $$
Therefore
$\delta (A_i) \geq \delta (A_{i-1})$
for all i.
Remark 4.4. The function
$\delta $
is a predimension in the following sense:
-
1.
$\delta (\emptyset )=0$
; -
2.
$\delta (\{a\})\leq 1$
(in fact, in our case
$= 1$
); -
3.
$\delta (A\cup B)+\delta (A\cap B)\leq \delta (A)+\delta (B)$
if
$A,B$
are subsystems of a common PSTS P (Submodularity of
$\delta $
).
This predimension function can be used to define a notion of well-embedded substructure in the class of PSTS.
Definition 4.5. If A is a finite PSTS and
$B\supseteq A$
is a PSTS (possibly infinite), we define
$$ \begin{align*}A\leq^* B \Leftrightarrow \delta(A)\leq \delta(B_0) \text{ for every finite } B_0 \text{ such that } A\subseteq B_0\subseteq B.\end{align*} $$
If
$A\leq ^* B$
, we say that A is well embedded in B.
We compare the behaviour of the predimension
$\delta $
in the class of finite unconfined PSTS and the class of oriented PSTS defined in [Reference Evans12] in the more general case of finite oriented colored k-hypergraphs that have a
$\mathcal {G}$
-orientation. The class defined below is the case
$k=3, t=2$
and a single colour in Definition 1.3 in [Reference Evans12].
Definition 4.6. An orientation of a PSTS P is a one-to-one mapping
$c:\operatorname {\mathrm {b}}(P)\rightarrow P$
such that
$c(e)\in e$
for every block e, where
$\operatorname {\mathrm {b}}(P)$
is the set of blocks of P as in Definition 4.1.
We say that
$c(e)$
is an apex of e. Given an orientation c of P, we say that
$A\subseteq P$
is c-closed in P or closed with respect to c if for every block e of P with apex in A,
$e\subseteq A$
.
Let
$\mathcal {C}$
be the class of all finite PSTSs. Then
-
•
$\mathcal {C}_{\mathrm {or}} =\{A\in \mathcal {C}\mid A \text { can be oriented and for every } X\subseteq A \text { with } |X|\leq 2,\; X\leq ^\ast A\}; \, $
-
•
$ \mathcal {C}_{\mathrm {un}}=\{A\in \mathcal {C}\mid A \text { is unconfined }\}. $
We show that the finite unconfined PSTSs are a proper subclass of
$\mathcal {C}_{\mathrm {or}}$
.
Proposition 4.7.
$\mathcal {C}_{\mathrm {un}}\subseteq \mathcal {C}_{\mathrm {or}} \, .$
Proof. We check by induction on
$|A|$
that if A is unconfined, then it has an orientation. We may assume
$A\neq \emptyset $
. Let
$a\in A$
belong to at most one block of A. By induction hypothesis,
$A\smallsetminus \{a\}$
has an orientation c. If a belongs to the block e, we make a the apex of e. This gives an orientation of A extending c.
Now we prove by induction on A that if A is unconfined and
$X\subseteq A$
, and
$|X|\leq 2$
, then
$X\leq ^* A$
. It is enough to check that if
$X\subseteq A$
, then
$\delta (X)\geq \min \{ |X|,2\}$
. We may assume
$A\neq \emptyset $
. Choose
$a\in A$
belonging to at most one block of A and let
$A^\prime = A\smallsetminus \{a\}$
. We can apply the induction hypothesis to
$A^\prime $
. If
$a\not \in X$
, then
$X\subseteq A^\prime $
and the induction hypothesis gives the result. If
$a\in X$
, let
$X^\prime =X\smallsetminus \{a\}$
. Then
$\delta (X^\prime )\geq \min \{|X^\prime |,2\}$
and, moreover,
$\delta (X^\prime )=\delta (X)$
or
$\delta (X^\prime )=\delta (X)+1$
. If
$|X|\leq 2$
, then
$\delta (X)=|X|$
and clearly
$\delta (X)\geq \min \{|X|,2\}$
. If
$|X|>2$
, then
$\min \{|X|,2\}= 2$
and
$\delta (X)\geq \delta (X^\prime )+1\geq 2$
.
The next example shows that
$\mathcal {C}_{\mathrm {un}}\neq \mathcal {C}_{\mathrm {or}}$
.
Example 4.8. Let A be the PSTS consisting of the vertices
$\{a_1,\ldots ,a_9\}$
with horizontal blocks
$$\begin{align*}\{a_1,a_2,a_3\},\{a_4,a_5,a_6\},\{a_7,a_8,a_9\} \end{align*}$$
and vertical blocks
$$\begin{align*}\{a_1,a_4,a_7\},\{a_2,a_5,a_8\},\{a_3,a_6,a_9\}. \end{align*}$$
Then A is not unconfined, but it can be oriented and it satisfies the additional condition on subsets X with
$|X|\leq 2$
. Hence,
$A\in \mathcal {C}_{\mathrm {or}}\smallsetminus \mathcal {C}_{\mathrm {un}}$
.
By Corollary 1.1 in [Reference Evans12], the class (
$\mathcal {C}_{\mathrm {or}}, \leq ^*)$
has the amalgamation property. However, the following example shows that
$\leq ^*$
does not behave equally well in
$\mathcal {C}_{\mathrm {un}}$
, which renders the results in [Reference Evans12] not applicable in our case.
Example 4.9. Consider two isomorphic PSTSs:
-
•
$B_1$
on the set
$\{a,b,e,f, a \cdot b, a \cdot e, e \cdot f, f \cdot (a \cdot e), b \cdot (a \cdot e), f \cdot (b \cdot (a \cdot e) )\},$
-
•
$B_2$
on the set
$\{a^\prime , b^\prime , c,d, a^\prime \cdot b^\prime, a^\prime \cdot c, c \cdot d, c \cdot (a^\prime \cdot b^\prime), d \cdot (a^\prime \cdot c), d \cdot (c \cdot (a^\prime \cdot b^\prime)) \},$
with blocks as in the figure below.
Let
$A_1 =\{a,b \} \subseteq B_1$
and
$A_2 =\{a^\prime ,b^\prime \} \subseteq B_2$
. Then the map
$ \alpha = \{ \langle a, a^\prime \rangle , \langle b, b^\prime \rangle \}$
is an isomorphism between
$A_1$
and
$A_2$
.
By inspection, we see that
$A_i \leq ^* B_i$
for
$i=1,2$
.
Amalgamating
$B_1$
and
$B_2$
over
$A_2=\alpha (A_1)$
forces the identification
$a \cdot b \mapsto a^\prime \cdot b^\prime $
. The amalgam that results from this identification and no others is in
$\mathcal {C}_{\mathrm {or}}$
but not in
$\mathcal {C}_{\mathrm {un}}$
, because all its vertices are in at least two blocks. It follows that
$(\mathcal {C}_{\mathrm {un}}, \leq ^*)$
does not have the amalgamation property.
Moreover, in any other amalgam, for each vertex the valency (i.e., the number of blocks to which the vertex belongs) cannot be lower than the valency in the original PSTSs. It follows that any amalgam of
$B_1$
and
$B_2$
over
$A_1 \cong A_2$
is not unconfined. Therefore this example shows, more generally, that the amalgamation property does not hold for the class
$(\mathcal {C}_{\mathrm {un}}, \subseteq )$
, where
$\subseteq $
is the substructure relation.
5 Amalgamation
Since, by Example 4.9, the class
$(\mathcal {C}_{\mathrm {un}}, \subseteq )$
does not have the amalgamation property, we introduce a notion of strong substructure based on HF-orderings which makes
$\mathcal {C}_{\mathrm {un}}$
a generalised amalgamation class. This leads to the construction of a generic object for
$\mathcal {C}_{\mathrm {un}}$
(with respect to the notion of strong substructure) which turns out to be the free STS on
$\omega $
generators.
Definition 5.1. For
$A, B \in \mathcal {C}_{\mathrm {un}}$
,
$$ \begin{align*}A \leq B \ \Leftrightarrow \ A\subseteq B \text{ and there is an HF-ordering of } B, \text{ where } A \text{ is an initial segment}.\end{align*} $$
When
$A \leq B$
, we say that A is strong in B.
Since A and B are finite, the condition
$A \leq B$
is first-order.
To see this, we define certain formulas in the relational language of STSs (so blocks interpret a ternary relation R that is symmetric and irreflexive). In what follows, we implicitly assume that the elements
$a_i$
are pairwise distinct. There is a formula
$\delta _1(x_1, \ldots , x_n)$
, in the relational language of PSTSs, that says that
$x_1<x_2<\cdots <x_n$
is an HF-ordering, namely,
$$ \begin{align*}\delta_1(x_1, \ldots, x_n) \equiv \bigwedge_{i=1}^n \bigg[ \bigwedge_{1\leq j <k<i} \bigg( R(x_i, x_j, x_k) \rightarrow \bigwedge_{\tiny \begin{array}{l} 1\leq j' <k'<i \\ \{j,k\} \neq \{j',k'\} \end{array}} \neg R(x_i,x_{j'},x_{k'}) \bigg) \bigg] \, .\end{align*} $$
Now let
$S_n$
denote the symmetric group on n elements, and let
$$ \begin{align*}\delta_2 (x_1, \ldots, x_n) \equiv \bigvee_{\pi \in S_n} \delta_1(x_{\pi(1)}, \ldots, x_{\pi(n)}).\end{align*} $$
Then
$\delta _2(a_1, \ldots , a_n)$
holds if and only if there is an HF-ordering of
$a_1, \ldots , a_n$
.
Consider the following modification of
$\delta _2$
:
Then for
$A=\{a_1, \ldots , a_n\} \subseteq \{a_1, \ldots , a_n, a_{n+1}, \ldots , a_{n+m}\}=B$
we have
$$\begin{align*}B \models \delta_3 (a_1, \ldots, a_n, a_{n+1}, \ldots , a_{n+m}) \text{ if and only if } A\leq B. \end{align*}$$
So for each
$m,n$
,
$A \subseteq B$
with
$|A|=m$
and
$|B|=n+m$
, there is a formula that asserts that
$A \leq B$
.
Remark 5.2.
$\mathcal {C}_{\mathrm {un}}$
is closed under isomorphism and
$\leq $
is a partial order on
$\mathcal {C}_{\mathrm {un}}$
refining
$\subseteq $
and satisfying the following conditions:
-
1. If
$A\leq B$
and
$f:B\cong B^{\prime }$
is an isomorphism such that
$f(A)=A^{\prime }$
, then
$A^{\prime }\leq B^{\prime }$
. -
2. If
$A\subseteq B\subseteq C$
,
$B\in \mathcal {C}_{\mathrm {un}}$
and
$A\leq C$
, then
$A\leq B$
.
This means that
$(\mathcal {C}_{\mathrm {un}},\leq )$
is a smooth class as defined in [Reference Kueker and Laskowski23].
The following are conditions C3 and C4 in [Reference Wagner, Kaye and Macpherson29].
Lemma 5.3. Let
$A,A_1,A_2 \in \mathcal {C}_{\mathrm {un}}$
. Then
-
1.
$\emptyset \leq A$
; -
2. if
$B\in \mathcal {C}_{\mathrm {un}}$
is such that
$A_1\subseteq B$
and
$A_2\leq B$
, then
$A_1\cap A_2\leq A_1$
.
Proof. 1. By Proposition 3.7, since every
$A\in \mathcal {C}_{\mathrm {un}}$
has an HF-ordering.
2. Given an HF-ordering of B with initial segment
$A_2$
, the elements of
$A_1$
inherit an HF-ordering with initial segment
$A_1\cap A_2$
.
If B is a partial unconfined STS, possibly infinite, and
$A \subseteq B$
is finite, we define
$$\begin{align*}A \leq B \ \Leftrightarrow \ A \leq A^\prime \text{ for every } A^\prime \in \mathcal{C}_{\mathrm{un}} \text{ such that } A \subseteq A^\prime \subseteq B \,. \end{align*}$$
The condition
$A \leq B$
is first-order in this case, too: for
$m \in \omega $
, let
$\delta _{4,m}(x_1, \ldots , x_n) $
be the formula that says
$$ \begin{align*}\{x_1, \ldots, x_n\} \text{ is strong in any }m\text{-element extension }\{x_1, \ldots, x_n, y_1, \ldots, y_m\}\, ,\end{align*} $$
that is,
$$ \begin{align*}\forall y_1 \ldots y_m \, \bigg[ \bigg( \bigwedge_{\tiny \begin{array}{l} 1 \leq i \leq n \\ 1 \leq j \leq m \end{array}} \neg x_i=y_j \ \ \wedge \bigwedge_{1\leq i <j \leq m} \neg y_i=y_j \bigg) \rightarrow \delta_3(x_1, \ldots, x_n, y_1, \ldots, y_m) \bigg].\end{align*} $$
Now let
$$ \begin{align*}\mathrm{strong}_m(x_1, \ldots, x_n) \equiv \bigwedge_{k\leq m} \, \delta_{4,k}(x_1, \ldots, x_n) \, ,\end{align*} $$
and suppose
$A=\{a_1, \ldots , a_n \} \subseteq B$
, where the
$a_i$
are pairwise distinct. Then
$$ \begin{align*}B \models \left\{\mathrm{strong}_m(a_1, \ldots, a_n) : m\in \omega \right\} \text{ if and only if } A \leq B \, .\end{align*} $$
We shall see that
$(\mathcal {C}_{\mathrm {un}}, \leq )$
has the amalgamation property AP. Now that we have shown that
$(\mathcal {C}_{\mathrm {un}},\leq )$
is smooth, by [Reference Kueker and Laskowski23] this will imply that there is a countable unconfined STS F, the generic model, such that:
-
•
$F = \bigcup _{n < \omega } C_n$
, where
$C_i \in \mathcal {C}_{\mathrm {un}}$
and
$C_i \leq C_j$
if
$i\leq j$
; -
• if
$A \in \mathcal {C}_{\mathrm {un}}$
, then there is an embedding
$f:A \rightarrow F$
such that
$f(A)\leq F$
; -
• for all
$A \leq B$
such that
$A \leq F$
, there is an embedding
$f: B \to F$
such that
$f(B) \leq F$
and
$f|_A = \mathrm {id}_A$
.
Moreover, up to isomorphism there is a unique countable model satisfying these three properties.
The class
$\mathcal {C}_{\mathrm {un}}$
turns out to be an interesting example of a variant of
$\leq $
-amalgamation appearing in [Reference Wagner, Kaye and Macpherson29] which we define next in our context and which allows us to establish that our generic is not saturated. We prove that this variant, called n-amalgamation, holds in
$\mathcal {C}_{\mathrm {un}}$
. We subsequently use it to prove the amalgamation property.
Definition 5.4. Let
$A,B\in \mathcal {C}_{\mathrm {un}}$
and
$n<\omega $
. We write
$A\leq ^n B$
if
$A \subseteq B$
and for every
$X\subseteq B\smallsetminus A$
such that
$|X|\leq n$
, we have
$A\leq A\cup X$
.
Given a partial unconfined STS B, possibly infinite, and
$A\in \mathcal {C}_{\mathrm {un}}$
such that
$A\subseteq B$
, we write
$A\leq ^n B$
if
$A\leq ^n B_0$
for every finite
$B_0\subseteq B$
.
In either case we say that A is n-strong in B.
Note that
$A\leq B$
if and only if
$A\leq ^n B$
for every n.
Remark 5.5. The condition of being an n-strong substructure of a partial unconfined STS B is first-order: for
$A=\{a_1, \ldots , a_k\} \subseteq B$
, where the
$a_i$
are pairwise distinct,
$$ \begin{align*}B\models \mathrm{strong}_n(a_1,\ldots,a_k) \text{ if and only if } \{a_1,\ldots,a_k\}\leq^n B.\end{align*} $$
Lemma 5.6. If
$A\leq ^n B$
and
$B\leq ^n C$
, then
$A\leq ^n C$
.
Proof. Assume
$X\subseteq C \smallsetminus A$
and
$|X|\leq n$
. We check that
$A\leq A\cup X$
. Since
$B\leq ^n C$
, we have
$B\leq B\cup X$
. By Lemma 5.3,
$A\cup (X\cap B)\leq A\cup X$
. Since
$A\leq ^n B$
, we know that
$A\leq A\cup (X\cap B)$
. Hence
$A\leq A\cup X$
.
Lemma 5.7.
-
1. Assume
$A\leq B$
,
$ b\in B\smallsetminus A$
and there is a block
$\{a_1,a_2,b\}$
with
$a_1,a_2\in A$
. Then
$Ab\leq B$
. -
2. Assume
$A\leq ^n B$
,
$b\in B\smallsetminus A$
and there is a block
$\{a_1,a_2,b\}$
with
$a_1,a_2\in A$
. Then
$Ab\leq ^{n-1} B$
.
Proof. 1. Start with an HF-ordering of B with initial segment A. Then
$\{a_1,a_2,b\}$
is the only block containing b and elements smaller than b in the order. We can make b the least element in
$B\smallsetminus A$
and obtain, again, an HF-ordering of B, now with
$Ab$
as initial segment.
2. Similar proof.
Definition 5.8. We say that
$(\mathcal {C}_{\mathrm {un}}, \leq )$
has the n-amalgamation property if for every
$A\leq B$
in
$\mathcal {C}_{\mathrm {un}}$
there is some
$m<\omega $
such that whenever
$C\in \mathcal {C}_{\mathrm {un}}$
and
$A\leq ^m C$
, there are
$D\in \mathcal {C}_{\mathrm {un}}$
and embeddings
$f:B\rightarrow D$
and
$g:C\rightarrow D$
such that
$$ \begin{align*}f\restriction A= g\restriction A, \quad f(B)\leq^n D \, \text{ and } \, g(C)\leq D \, .\end{align*} $$
In [Reference Wagner, Kaye and Macpherson29] Wagner uses the term
$\leq ^\ast $
-amalgamation to mean that n-amalgamation holds for every n. The notion also appears in [Reference Baldwin and Shi5] with the name uniform amalgamation. In [Reference Herwig19], Herwig proves that saturation of the generic is equivalent to
$\leq ^\ast $
-amalgamation, but under the additional assumption that there is no infinite ascending chain of minimal pairs (condition C2 in [Reference Wagner, Kaye and Macpherson29]). By Lemma 2.18 in [Reference Baldwin and Shi5], this means the generic does not have finite closures according to Definition 2.10 in [Reference Baldwin and Shi5]. When the generic does not contain infinite ascending chains of minimal pairs, the saturation of the generic is in fact equivalent to the conjunction of
$\leq ^\ast $
-amalgamation and C2. We show that C2 does not hold in our class
$(\mathcal {C}_{\mathrm {un}},\leq )$
, and so the generic is not saturated in our case.
Definition 5.9. A minimal pair is a pair
$(A,B)$
of elements of
$\mathcal {C}_{\mathrm {un}}$
such that
$A\subsetneq B$
,
$A\not \leq B$
, and
$A\leq A^\prime $
for every
$A^\prime $
such that
$A\subseteq A^\prime \subsetneq B$
.
Proposition 5.10.
$\mathcal {C}_{\mathrm {un}}$
contains an infinite ascending chain of minimal pairs, that is, there is a sequence
$((A_i,A_{i+1})\mid i<\omega )$
in
$\mathcal {C}_{\mathrm {un}}$
such that each
$(A_i,A_{i+1})$
is a minimal pair. Hence condition C2 of [Reference Wagner, Kaye and Macpherson29] does not hold.
Proof. Let
$F_3$
be the free STS with three generators
$a_1,a_2,a_3$
, and let
$b=(a_1\cdot a_2)\cdot (a_1\cdot a_3)$
. As shown in [Reference Barbina and Casanovas7], the homomorphism
$f:F_3\rightarrow F_3$
induced by
$f(a_1)=b$
,
$f(a_2)=a_2$
, and
$f(a_3)=a_3$
is an embedding and it is not surjective. It is easy to see that if
$A=\{b,a_2,a_3\}$
and
$B=\{b,a_1,a_2,a_3, a_1\cdot a_2, a_1\cdot a_3\}$
, then
$(A,B)$
is a minimal pair. This construction can be iterated as follows. Start with
$N_0$
freely generated by
$A_0=\{a_1,a_2,a_3\}$
and let
$b_0= a_1$
. Assume
$N_n$
is freely generated by
$\{b_n,a_2,a_3\}$
and find a proper extension
$N_{n+1}$
freely generated by
$\{b_{n+1},a_2,a_3\}$
, where
$b_n= (b_{n+1}\cdot a_2)\cdot (b_{n+1} \cdot a_3)$
. Let
$A_{n+1}= A_n\cup \{b_{n+1},a_2\cdot b_{n+1}, a_3\cdot b_{n+1}\}$
. Then
$(A_n,A_{n+1})$
is a minimal pair.
Proposition 5.11.
$(\mathcal {C}_{\mathrm {un}},\leq )$
has the n-amalgamation property for every n. In fact, if
$A\leq B$
and
$n<\omega $
are given, we can always take
$m= n+|B\smallsetminus A|$
.
Proof. Assume
$A\leq B$
and
$A\leq ^m C$
, where
$m= n+|B\smallsetminus A|$
. We want to find
$B^\ast \cong _A B$
and
$D\in \mathcal {C}_{\mathrm {un}}$
such that
$C\leq D$
and
$B^\ast \leq ^n D$
. We may assume
$C\cap B=A$
. Note that the blocks containing only elements of A are the same in B and in C. Assume there are
$b\in B\smallsetminus A$
,
$c\in C\smallsetminus A$
and
$a_1,a_2\in A$
such that
$\{a_1,a_2,b\}$
is a block of B and
$\{a_1,a_2,c\}$
is a block of C. Redefine
$A^\prime = A\cup \{c\}$
,
$B^\prime = (B\smallsetminus \{b\})\cup \{c\}$
and modify the blocks of B by exchanging b with c to obtain the blocks of
$B^\prime $
. Then
$B^\prime \cong _A B$
and
$B^\prime \cap C=A^\prime $
. By Lemma 5.7, we have
$A^\prime \leq B^\prime $
and
$A^\prime \leq ^{m-1} C$
. Iterating this process gives
$B^\ast \cong _A B$
such that if
$A^\ast =B^\ast \cap C$
, then
$A^\ast \leq B^\ast $
,
$A^\ast \leq ^{n +i}C$
for some
$i \geq 0$
and there are no
$b\in B^\ast \smallsetminus A^\ast $
,
$c\in C\smallsetminus A^\ast $
and
$a_1,a_2\in A^\ast $
such that
$\{a_1,a_2,b\}$
is a block of
$B^\ast $
and
$\{a_1,a_2,c\}$
is a block of C. Now consider
$D=B^\ast \cup C$
as a free amalgam of
$B^\ast $
and C over
$A^\ast $
, that is, with the blocks in
$B^\ast $
and in C and no others. Then D is a PSTS. We claim that
$D\in \mathcal {C}_{\mathrm {un}}$
,
$C\leq D,$
and
$B^\ast \leq ^n D$
.
First we show that D has an HF-ordering where C is an initial segment. This proves that
$D\in \mathcal {C}_{\mathrm {un}}$
and
$C\leq D$
. Take an HF-ordering
$<_C$
of C and an HF-ordering
$<_{B^\ast }$
of
$B^\ast =A^\ast \cup (B^\ast \smallsetminus C)$
, where
$A^\ast $
is an initial segment. Then the sum
$$ \begin{align*}(C,<_C)+(B^\ast\smallsetminus C,<_{B^\ast}\restriction (B^\ast\smallsetminus C))\end{align*} $$
is an HF-ordering of D. If not, there is an element of
$B^\ast \smallsetminus C$
that belongs to different blocks containing smaller elements, but these elements then are in
$A^\ast \cup (B^\ast \smallsetminus C)$
, contradicting the choice of the ordering
$<_{B^\ast }$
of
$B^\ast $
as an HF-ordering over
$A^\ast $
.
Finally, we check that
$B^\ast \leq ^n D$
. Let
$X\subseteq D\smallsetminus B^\ast = C\smallsetminus A^\ast $
with
$|X|\leq n$
; we show that
$B^\ast \leq B^\ast \cup X$
. Since
$A^\ast \leq B^\ast $
, we have an HF-ordering
$<_{B^\ast }$
of
$B^\ast $
with initial segment
$A^\ast $
. Since
$A^\ast \leq ^n C$
, we know that
$A^\ast \leq A^\ast \cup X$
, and hence there is an HF-ordering
$<_{A^\ast \cup X}$
of
$A^\ast \cup X$
with initial segment
$A^\ast $
. We combine these orderings by taking the sum
$(B^\ast ,<_{B^\ast })+(X,<_{A^\ast \cup X}\restriction X)$
. Since an element of X cannot have a block containing elements of
$B^\ast $
unless the elements belong to
$A^\ast $
, we obtain an HF-ordering of
$B^\ast \cup X$
with initial segment
$B^\ast $
.
Proposition 5.12.
$(\mathcal {C}_{\mathrm {un}},\leq )$
has the amalgamation property: if
$A,B,C\in \mathcal {C}_{\mathrm {un}}$
,
$A\leq B$
and
$A\leq C$
, there are
$D\in \mathcal {C}_{\mathrm {un}}$
and embeddings
$f:B\rightarrow D$
,
$g:B\rightarrow D$
such that
$$ \begin{align*}f\restriction A= g\restriction A, \quad f(B)\leq D \, \text{ and } \, g(C)\leq D \, .\end{align*} $$
Proof. The proof of Proposition 5.11 can be used with the same construction of the PSTS
$B^\ast \cong _AB$
and the PSTS D.
Proposition 5.13. The generic is isomorphic to the free STS with
$\omega $
generators.
Proof. First note that the generic F is an STS, that is, the product of two distinct elements
$a_1,a_2$
is defined: let b be a new vertex and let
$A=\{a_1,a_2,b\}$
be an STS (so
$ \{a_1, a_2, b \}$
is a block). Then
$A\in \mathcal {C}_{\mathrm {un}}$
and
$\{a_1,a_2\}\leq A$
, and, therefore, there is an embedding
$f:A\rightarrow F$
over
$\{a_1,a_2\}$
. Moreover, F must be a free STS, since it has a well-founded HF-ordering. On the other hand, the generic can be constructed by including at each stage an element which does not form a block with any previous elements. Then the corresponding HF-ordering has infinitely many elements which do not form a block with any preceding elements. By Proposition 3.5, these elements belong to a free base of F.
We extend the notion of strong subset so that it applies to infinite PSTSs.
Definition 5.14. Let
$A,B$
be arbitrary PSTSs. We write
$A\leq B$
if there is an HF-ordering
$<$
of B over A, or, equivalently, if there is an HF-ordering of B that has A as an initial segment.
Remark 5.15. When A is finite and B is unconfined, this definition of
$A\leq B$
is equivalent to the definition given after Lemma 5.3, that is,
$A\leq B$
if and only if
$A\subseteq B$
and
$A\leq C$
for every finite C such that
$A\subseteq C\subseteq B$
. More generally, if
$A,B$
are arbitrary PSTSs and B is unconfined, then
$$ \begin{align*}A\leq B \text{ if and only if } A\subseteq B \text{ and } A\cap C \leq C \text{ for every finite } C\subseteq B.\end{align*} $$
Proof. Assume
$A \subseteq B$
and
$A\cap C\leq C$
for every finite
$C\subseteq B$
. We show that there is an HF-ordering of B over A. The argument is an application of the compactness theorem for propositional logic. For every pair
$(a,b)\in B^2$
we introduce a propositional variable
$p_{(a,b)}$
meaning
$a<b$
. The set of sentences
$$ \begin{align*}\{\neg p_{(a,a)}\mid a\in B\}&\cup\{p_{(a,b)}\wedge p_{(b,c)}\rightarrow p_{(a,c)}\mid a,b,c\in B\}\\ &\cup\{p_{(a,b)}\vee p_{(b,a)}\mid a,b\in B,\; a\neq b\}\end{align*} $$
defines a linear ordering in B and the set
$$ \begin{align*}\{\neg( p_{(b,a)}\wedge p_{(c,a)}\wedge p_{(b^\prime,a)}\wedge p_{(c^\prime,a)})\mid \{a,b,c\}\neq \{a,b^\prime,c^\prime\} \text{ blocks of } B\}\end{align*} $$
expresses that the order is an HF-ordering of B. Finally,
$$ \begin{align*}\{ p_{(a,b)}\mid a\in A,\; b\in B\smallsetminus A\}\end{align*} $$
expresses that A is an initial segment. By assumption, every finite subset of this set of sentences is satisfiable. By compactness, the whole set is satisfiable.
Proposition 5.16. If M is an unconfined STS and
$A=\operatorname {\mathrm {acl}}(A)\subseteq M$
, then
$A\leq M$
.
Proof. We can expand the monster model
$\mathbb {M}$
by adding an HF-ordering
$<$
of
$\mathbb {M}$
, but we work in
$\mathbb {M}$
. By P. M. Neumann’s Lemma (2.3 in [Reference Neumann25]—also [Reference Hodges20, Corollary 4.2.2]), given
$a_1,\ldots ,a_n\not \in \operatorname {\mathrm {acl}}(A)$
, for any set B in
$\mathbb {M}$
there are
$b_1\ldots b_n$
with
$b_1,\ldots ,b_n\equiv _A a_1\ldots a_n$
such that
$b_1,\ldots ,b_n\not \in B$
. Hence if
$M\smallsetminus A=\{a_i\mid i<\kappa \}$
and
$p(x_i\mid i<\kappa )=\operatorname {\mathrm {tp}}((a_i\mid i<\kappa )/A)$
, then, for any set B, the type p has a realization
$(b_i\mid i<\kappa ) $
such that
$\{b_i\mid i<\kappa \}\cap B=\emptyset $
. Using this, for any
$\lambda $
we can construct a sequence of models
$(M_i\mid i<\lambda )$
containing A such that
$M=M_0$
,
$M_i\cong _A M_j$
and
$M_i\cap M_j=A$
for every
$i\neq j$
. Let
$B=\operatorname {\mathrm {cl}}_<(A)\subseteq \mathbb {M}$
and let
$\mu = |B|= |A|+\omega $
. We may assume
$\mu <\lambda $
, which implies
$M_i\cap B = A$
for some i (if
$A\subsetneq M_i\cap B$
for every
$i<\lambda $
, we can choose
$a_i\in (M_i\cap B)\smallsetminus A$
and the
$a_i$
are all distinct, which contradicts
$|B|<\lambda $
). By Lemma 3.11,
$<$
is an HF-ordering over B. Therefore
$<_i=<\restriction M_i$
is an HF-ordering of
$M_i$
over
$A= B\cap M_i$
. Since
$M_i\cong _A M$
, there is an HF-ordering of M over A.
Corollary 5.17. If
$M_1\preccurlyeq M_2$
are unconfined STSs, then
$M_1\leq M_2$
.
Proof. By Proposition 5.16 since
$\operatorname {\mathrm {acl}}(M_1)=M_1$
.
6 Binary trees
This section introduces certain tree constructions in unconfined STSs. These trees are an essential tool for our proof of the completeness of the theory of infinite unconfined STSs in Section 7.
Let M be an unconfined STS. A binary tree of height
$\alpha \leq \omega $
is a subset
$\{a_s\mid s\in 2^{<\alpha }\}$
of M such that:
-
1. if
$s\neq t$
, then
$a_s\neq a_t$
; -
2.
$a_s= a_{s0}\cdot a_{s1}$
; -
3. these are all the blocks of the tree: the only block containing
$a_\emptyset $
is
$\{a_\emptyset , a_0, a_1\}$
and if
$s=ti$
, the only blocks containing
$a_s$
are
$\{a_t,a_{t0},a_{t1}\}$
and
$\{a_s,a_{s0},a_{s1}\}$
.
A leaf is an element
$a_s$
of the tree such that there are no
$a_{s0}, a_{s1}$
in the tree with
$a_s=a_{s0}\cdot a_{s1}$
.
Remark 6.1.
-
1. A binary tree of height
$n+1$
can be seen as a construction of
$a_\emptyset $
from
$\{a_s\mid s\in 2^n\}$
in the form of a binary tree, with the root
$a_\emptyset $
at the top. Every free STS embeds many copies of this tree: it suffices to choose a level with at least
$2^n$
elements and take the products of these elements that belong to higher levels, thus obtaining the root
$a_\emptyset $
after n steps. If
$\{a_s\mid s\in 2^n\}$
are the chosen elements in the given level, the tree can be described as
$\{a_s\mid s\in 2^{\leq n}\}$
, where
$a_s= a_{s0}\cdot a_{s1}$
if
$s\in 2^{<n}$
. A binary tree of height
$\omega $
can also be seen as a (non well-founded) construction of
$a_\emptyset $
over
$\emptyset $
. -
2. The tree
$\{a_s\mid s\in 2^{<\alpha }\}$
admits a natural HF-ordering that in the well-founded case reflects the order of construction of the root described in part 1: we order every level arbitrarily and we make the elements of level i precede the elements of level
$i+1$
. In particular,
$a_s> a_t$
if
$s\subsetneq t$
.
An alternative HF-ordering can be defined on a binary tree, which will be used in the proof of Proposition 6.6 below.
Lemma 6.2. The binary tree of height
$\alpha $
has an HF-ordering where the root
$a_\emptyset $
is the smallest element instead of being the largest.
Proof. If
$<$
is a natural HF-ordering of the binary tree, with
$a_\emptyset $
at the top, then the reverse order
$>$
is also an HF-ordering and now
$a_\emptyset $
is the smallest element.
Given an element a of an infinite unconfined STS, we can build a binary tree of arbitrary finite length having a as its root. If the STS is
$\omega $
-saturated, we can find such a tree of height
$\omega $
.
Lemma 6.3.
-
1. An HF-ordering of an infinite STS does not have a maximum.
-
2. If
$<$
is an HF-ordering of an infinite STS M, then for every
$a\in M$
, for every
$b \geq a$
, there are
$b_1,b_2>b$
such that
$a=b_1\cdot b_2$
.
Proof. 1. Assume
$a\in M$
is a maximum. Since
$|M|>3$
, the element a belongs to two different blocks,
$\{a,a_1,a\cdot a_1\}$
and
$\{a,a_2,a\cdot a_2\}$
. By maximality,
$a> a_1,a_1\cdot a, a_2, a_2\cdot a$
, in contradiction with
$<$
being an HF-ordering.
2. Assume not, and take
$b \geq a$
such that if
$a=a_1\cdot a_2$
, then
$a_1\leq b$
or
$a_2\leq b$
. Since M is infinite, by part 1 we can choose
$b_1>b_2>b$
such that
$b_1\cdot b_2<b_1$
. Note that
$\{b_1,a,a\cdot b_1\}\neq \{b_1,b_2, b_1\cdot b_2 \}$
, since otherwise
$a=b_1\cdot b_2$
and
$b_1,b_2>b$
. If
$b_ 1> a\cdot b_1$
, then the previous blocks contradict that
$<$
is an HF-ordering. Hence,
$b_1<a\cdot b_1$
. In this case,
$a= b_1\cdot (a\cdot b_1)$
with
$b_1,a\cdot b_1>b$
, a contradiction with the choice of b.
Proposition 6.4. Let
$<$
be an HF-ordering of the infinite STS M and let
$n<\omega $
. For every
$a\in M$
there is a binary tree
$T=\{a_s\mid s\in 2^{<n}\}$
in M such that:
-
1.
$a_s>a$
for every s; -
2.
$a_s>a_t$
if
$s\subsetneq t$
.
Proof. By induction on n. The initial cases
$n=0,1$
are trivial. Consider the case
$n=2$
. Let
$b>a$
. We use Lemma 6.3 to get some
$b_1>b_2 >b$
in M such that
$b=b_1\cdot b_2$
. We put
$a_\emptyset = b_1$
,
$a_0=b_2$
, and
$a_1 = b$
.
Now we assume inductively the result holds for
$n\geq 2$
. Given
$a\in M$
, the inductive hypothesis gives some tree
$T_0=\{a_s\mid s\in 2^{<n}\}$
as required for a. Again by the inductive hypothesis we can find in M a tree
$T_1=\{a^\prime _s\mid s\in 2^{<n}\}$
with
$a^\prime _s>a_\emptyset $
and condition 2 holds. Now we combine
$T_0$
and
$T_1$
to get a binary tree
$T=\{b_s \mid s\in 2^{<n+1}\}$
. We set
$b_{0s}= a_s$
,
$b_{1s}= a^\prime _s$
, and
$b_\emptyset = a_\emptyset \cdot a^\prime _\emptyset $
. It is enough to check that
$a_\emptyset \cdot a^\prime _\emptyset> a^\prime _\emptyset $
. Since
$n\geq 2$
this is clear, since otherwise the blocks
$\{a^\prime _\emptyset ,a^\prime _0,a^\prime _1\}$
and
$\{a^\prime _\emptyset , a_\emptyset , a_\emptyset \cdot a^\prime _\emptyset \}$
are different and contradict that
$<$
is an HF-ordering.
Corollary 6.5. Let
$<$
be an HF-ordering of the infinite STS M and assume M is
$\omega $
-saturated as an
$(R, <)$
-structure. For every
$a\in M$
there is a binary tree
$T=\{a_s\mid s\in 2^{<\omega }\}$
in M such that:
-
1.
$a_s>a$
for every s; -
2.
$a_s>a_t$
if
$s\subsetneq t$
.
Proof. The tree is a realization of a type over a in M in the extended language with the order relation. The consistency of the type is granted by Proposition 6.4.
Binary trees allow us to give conditions under which a certain element in an infinite unconfined STS M can be placed between a subsytem A of M and the complement
$M \smallsetminus A$
. In the presence of a suitable amount of saturation, for a
$<$
-closed set A we can always find an HF-ordering and a least element in
$M \setminus A$
that is above A. This result in essential in the back-and-forth argument that proves the completeness of the theory of infinite unconfined STSs in Section 7.
In the proposition below, the symbol
$<$
denotes an HF-ordering, while
$\leq $
is used for the relation of being a strong substructure.
Proposition 6.6. Assume M is an infinite unconfined STS,
$A=\langle A\rangle \subseteq M$
and
$a\in M\smallsetminus A$
. The following are equivalent:
-
1.
$\operatorname {\mathrm {cl}}_<(a)=\{a\}$
for some HF-ordering of M with initial segment A; -
2.
$A\leq Aa\leq M$
; -
3. there are
$M^\prime \succeq M$
, an HF-ordering
$<^\prime $
of
$M^\prime $
and a binary tree
$T=\{a_s\mid s\in 2^{<\omega }\}$
in
$M^\prime $
such that
$\operatorname {\mathrm {cl}}_{<^\prime }(A)=A$
,
$a=a_\emptyset $
,
$T>^\prime A,$
and
$a_s>^\prime a_{s0},a_{s1}$
for every
$s\in 2^{\omega }$
.
Moreover, these conditions imply
$a\leq M$
.
Proof. 1
$\Rightarrow $
(2 and
$a\leq M$
). Fix an HF-ordering
$<$
of M with initial segment A and such that
$\operatorname {\mathrm {cl}}_<(a)=\{a\}$
. Then we can move a to the bottom (showing
$a\leq M$
) and we can move a to the top of A, making it the first element of
$M\smallsetminus A$
(showing
$Aa\leq M$
).
2
$\Rightarrow $
1. Since
$Aa\leq M$
and
$A\leq Aa$
, there is an HF-ordering of M having an initial segment
$Aa$
, where a is the last element of the segment. Since
$a\not \in A$
,
$\operatorname {\mathrm {cl}}_<(a)=\{a\}$
.
1
$\Rightarrow $
3. Let
$<$
be an HF-ordering of M with initial segment A such that
$\operatorname {\mathrm {cl}}_<(a)=\{a\}$
. Let
$(M^\prime ,<^\prime )\succeq (M,<)$
be
$\omega $
-saturated. Then
$<^\prime $
is an HF-ordering of
$M^\prime $
,
$\operatorname {\mathrm {cl}}_{<^\prime }(A)=A$
,
$a>^\prime A$
, and
$\operatorname {\mathrm {cl}}_{<^\prime }(a)=\{a\}$
. By Corollary 6.5, choose a tree
$T_0=\{a_s\mid s\in 2^{<\omega }\}$
in
$M^\prime $
such that
$a_s>^\prime a$
for every s and such that
$a_s>^\prime a_t$
if
$s\subsetneq t$
. Then
$a\cdot a_\emptyset>^\prime a_\emptyset $
, since otherwise the blocks
$\{a_\emptyset ,a_0,a_1\}\neq \{a_\emptyset , a, a\cdot a_\emptyset \}$
contradict that
$<^\prime $
is an HF-ordering. Let
$b_0=a\cdot a_\emptyset $
and
$B_0= \{b_0\}\cup T_0$
. Note that
$\operatorname {\mathrm {cl}}_{<^\prime }(B_0)=B_0\cup \{a\}$
. Now we modify the order
$<^\prime $
, thus obtaining a new HF-ordering
$<_0$
such that
$<_0\restriction B_0= <^\prime \restriction B_0$
and
$ <_0\restriction (M\smallsetminus B_0)= <^\prime \restriction (M\smallsetminus B_0)$
. This ordering
$<_0$
is obtained by moving
$B_0$
below a but above A, in particular by declaring that
$a>_0 b_0$
and
$B_0>_0 A$
and, hence,
$a>_0a_s$
for every s. This can be done by Lemma 3.12. We have obtained an incomplete tree with root a followed by
$b_0$
on the left and the complete tree
$T_0$
on the right. Now
$b_0$
is a leaf and we should complete the tree below
$b_0$
. The construction must be iterated
$\omega $
times in order to obtain a full binary tree.
3
$\Rightarrow $
1. Let
$M^\prime $
,
$<^\prime $
, and T be as in the assumption. Notice that
$\operatorname {\mathrm {cl}}_{<^\prime }(T)=T$
. By Lemma 6.2 T has an HF-ordering
$<^{\prime \prime }$
, where
$a_\emptyset $
is the smallest element. By Lemma 3.12 we can assume that
$<^{\prime \prime } = <^\prime \restriction T$
and A is an initial segment. Let
$<=<^\prime \restriction M$
. Then
$<$
is an HF-ordering of M, A is an initial segment, and
$\operatorname {\mathrm {cl}}_<(a)=\{a\}$
.
Corollary 6.7. Let M be an infinite unconfined STS and
$A\subseteq M$
. If
$<$
is an HF-ordering of M such that
$(M,<)$
is
$\kappa $
-saturated for some
$\kappa>|A|$
and
$\operatorname {\mathrm {cl}}_<(A)=A$
, then there is some
$a\in M\smallsetminus A$
such that
$Aa\leq M$
.
7 Completeness and stability
In this section we show that the theory of infinite unconfined STSs is complete and stable. Since all free STSs are models of the theory, it follows that any two free STSs are elementarily equivalent. Moreover, there is a countable model of the theory which is not free.
Lemma 7.1. Let M be an unconfined STS. If
$A\leq M$
(as in Definition 5.1), then
$\langle A\rangle \leq M$
and there is an HF-ordering of
$\langle A\rangle $
over A whose final segment
$\langle A\rangle \smallsetminus A$
is well-ordered. If N is an unconfined STS and
$B\leq N$
and
$f:A\cong B$
is an isomorphism of PSTSs, then f can be extended to an isomorphism
$f^\prime :\langle A\rangle \cong \langle B \rangle $
.
Proof. We could use Lemma 3.13 to verify the first assertion, but the following proof also gives the isomorphism. Decompose
$\langle A\rangle \smallsetminus A$
into a disjoint union
$\bigcup _{n<\omega }A_n$
, where
$A_0$
is the set of elements of
$\langle A\rangle \smallsetminus A$
which are a product of two elements of A, and
$A_{n+1}$
is the set of elements of
$\langle A\rangle \smallsetminus (A\cup A_0\cup \cdots \cup A_n)$
which are a product of two elements of
$A\cup A_0\cup \cdots \cup A_n$
. Fix an HF-ordering of M with initial segment A. There are no blocks between elements of
$A_0$
, and the only blocks of elements of
$A_0$
with smaller elements are blocks with elements of A that justify their inclusion in
$A_0$
. Hence we can move
$A_0$
down, just above A, and we can give
$A_0$
a well-founded HF-ordering over A. This shows that
$A\cup A_0\leq M$
. By a similar argument we can move down each
$A_{n+1}$
above
$A\cup A_0\cup \cdots \cup A_n$
and give it a well-founded HF-ordering over this set. The sequence of these well-founded orders is a well-founded HF-order of
$\langle A\rangle \smallsetminus A$
which makes
$\langle A\rangle $
an initial segment of the order of M. If we perform a similar decomposition
$\bigcup _{n<\omega }B_n$
of
$\langle B\rangle \smallsetminus B$
, then we can extend f inductively to an isomorphism of partial STSs
$f_n : A\cup A_0 \cup \cdots \cup A_n\cong B\cup B_0\cup \cdots \cup B_n$
. The union of this ascending chain of isomorphisms is the required isomorphism
$f^\prime $
.
The following is a stronger form of Corollary 6.7.
Lemma 7.2. Let M be an infinite unconfined STS and
$A\subseteq M$
. If
$<$
is an HF-ordering of M,
$\operatorname {\mathrm {cl}}_<(A)=A,$
and M is
$\kappa $
-saturated as an
$\{R,<\}$
-structure for some
$\kappa>|A|$
, then
$Aa\leq M$
for some
$a\in M\smallsetminus \langle A\rangle $
.
Proof. Since
$\operatorname {\mathrm {cl}}_<(A)=A$
, we have
$A\leq M$
by Lemma 3.11. Then
$\langle A\rangle \leq M$
by Lemma 7.1. By Corollary 6.7 we know that there is
$a\in M\smallsetminus \langle A\rangle $
such that
$\langle A\rangle a\leq M$
. It is easy to see that
$Aa\leq \langle A\rangle a$
and hence
$Aa\leq M$
.
Remark 7.3. If M is a saturated model of cardinality
$\kappa $
in the language L, then for every extension
$L^\prime \supseteq L$
with
$|L^\prime |\leq \kappa $
, for every set of sentences
$\Sigma $
in
$L^\prime $
consistent with
$\operatorname {\mathrm {Th}}(M)$
, there is an expansion
$M^\prime $
of M such that
$M^\prime \models \Sigma $
. If
$A\subseteq M$
has cardinality
$<\kappa $
we may allow
$\Sigma $
to have parameters in A, since the expansion
$M_A=(M,a)_{a\in A}$
is still saturated. Moreover, we can let
$\Sigma $
contain free variables, since we can replace them by constants. The same happens if M is a special model. For details see [Reference Casanovas8].
For simplicity, the next two results are formulated in terms of saturated models, but we could alternatively use special models (
$\kappa $
-saturated in the lemma and
$\omega _1$
-saturated in the theorem), whose existence can always be assumed without extra set-theoretical hypotheses.
Lemma 7.4. Let M be a saturated unconfined STS, let
$A\leq M$
and assume
$|A|<\kappa =|M|$
. Then there is an HF-ordering
$<$
of M such that M is saturated as an
$\{R,<\}$
-structure and
$\operatorname {\mathrm {cl}}_<(A)=A$
.
Proof. Let
$<$
be an HF-ordering of M having A as an initial segment. Notice that the expansion
$M_A= (M,a)_{a\in A}$
is saturated. Let
$(M^\prime _A,<^\prime )$
be a saturated model that is elementarily equivalent to
$(M_A,<)$
and has cardinality
$\kappa $
. For each
$a\in A$
that is not a product in M of two elements
$a_1,a_2<a$
, the sentence
$\forall xy \, (x,y<a\rightarrow x\cdot y \neq a)$
holds in
$(M_A,<)$
. Hence,
$\operatorname {\mathrm {cl}}_{<^\prime }(A)=A$
. Since
$M_A\cong M^\prime _A$
, there is some ordering
$<^{\prime \prime }$
of M such that
$(M_A,<^{\prime \prime })\cong (M^\prime _A,<^\prime )$
. Then
$<^{\prime \prime }$
satisfies the requirements.
Theorem 7.5. Let
$M,N$
be uncountable saturated unconfined STSs. The set of isomorphisms between countable substructures
$A\subseteq M$
and
$B\subseteq N$
(in particular, A and B are STSs) such that
$A\leq M$
and
$B\leq N$
is a back-and-forth system between M and N.
Proof. The case
$A=B=\emptyset $
is allowed and shows that there is at least one such isomorphism. Now assume
$f:A\cong B$
, where
$A\leq M$
and
$B\leq N$
are countable substructures, and let
$a\in M\smallsetminus A$
. We want to find countable substructures
$A^\prime \leq M$
and
$B^\prime \leq N$
extending A and B with
$a \in A^\prime $
and
$f^\prime : A^\prime \cong B^\prime $
for some
$f^\prime \supseteq f$
. The back step (i.e., extending f by adding some
$b\in N\smallsetminus B$
) is similar. We fix an arbitrary HF-ordering
$<_M$
of M, where A is an initial segment and we use Lemma 7.4 to choose an HF-ordering
$<_N$
of N such that
$(N,<_N)$
is saturated and
$\operatorname {\mathrm {cl}}_{<_N}(B)=B$
.
Case 1.
$\operatorname {\mathrm {cl}}_{<_M}(a)=\{a\}$
, or, equivalently,
$Aa\leq M$
. Corollary 6.7 gives
$b\in N\smallsetminus B$
such that
$Bb\leq N$
, in which case, by Proposition 6.6 and by changing the ordering
$<_N$
if necessary, we may assume that
$\operatorname {\mathrm {cl}}_{<_N}(b)=\{b\}$
and
$b>_N B$
. Then f extends to an isomorphism of PSTSs
$f^\prime :Aa\cong Bb$
. By Lemma 7.1, we have
$\langle Aa\rangle \leq M$
,
$\langle Bb\rangle \leq N,$
and
$f^\prime $
extends to an isomorphism
$f^{\prime \prime }:\langle Aa\rangle \cong \langle Bb\rangle $
.
Case 2.
$\operatorname {\mathrm {cl}}_{<_M}(a)\smallsetminus A=\{a_0,\ldots ,a_n\}$
with
$a=a_0>_M a_1 >_M \dots >_M a_n$
. Note that
$\operatorname {\mathrm {cl}}_{<_M}(a_n)=\{a_n\}$
and
$a_n\not \in A$
. As in Case 1, we can find
$b_n\in N\smallsetminus B$
such that
${Bb_n\leq N}$
, and f extends to an isomorphism
$f_n:\langle Aa_n\rangle \cong \langle Bb_n\rangle $
such that
${f_n(a_n)=b_n}$
. Assume inductively that we have found
$b_{i+1},\ldots ,b_n\in N$
and an isomorphism
$$ \begin{align*}f_{i+1}:\langle Aa_{i+1}\dots a_n\rangle \cong \langle B b_{i+1}\dots b_n\rangle\end{align*} $$
with
$f_{i+1}\supseteq f$
and such that
$f_{i+1}(a_j)= b_j$
for every j. If
$a_i\in \langle Aa_{i+1}\dots a_n\rangle $
, we let
$f_i=f_{i+1}$
and
$b_i= f_i(a_i)$
. If
$a_i\not \in \langle Aa_{i+1}\ldots a_n\rangle $
, we see that
$\operatorname {\mathrm {cl}}_{<_M}(a_i)= \{a_i\}$
and, as for
$a_n$
, we get
$b_i\in N\smallsetminus \langle Bb_{i+1}\ldots b_n\rangle $
such that
$ \langle Bb_{i+1}\ldots b_n\rangle b_i\leq N$
and
$f_{i+1}$
extends to an isomorphism
$f_i:\langle Aa_i\ldots a_n\rangle \cong \langle B b_i\ldots b_n\rangle $
with
$f_i(a_i)=b_i$
. Finally we obtain
$b_0,\ldots ,b_n$
and an isomorphism
$f_0:\langle Aa_0\ldots a_n\rangle \cong \langle Bb_0\ldots b_n\rangle $
extending f with
$f_0(a_i)=b_i$
for every i. Moreover,
$\langle Aa_0\ldots a_n\rangle \leq M$
and
$\langle Bb_0\ldots b_n\rangle \leq N$
. Since
$ \langle B b_0\ldots b_n\rangle \leq N$
, if necessary we can change the order on
$\langle Bb_0\ldots b_n\rangle $
by that induced by
$f_0$
so that
$b_0>_Nb_1>\cdots >_N b_n$
.
Case 3.
$\operatorname {\mathrm {cl}}_{<_M}(a)\smallsetminus A= \{a_i\mid i<\omega \}$
with
$a=a_0$
and
$a_i>_M a_{i+1}$
. We claim that for every
$n<\omega $
there are
$b_0,b_1,\ldots , b_n\in N$
such that:
-
1.
$B\leq Bb_n\leq Bb_{n-1}b_n\leq \cdots \leq Bb_0\ldots b_n \leq N$
. -
2.
$ Aa_0\ldots a_n\cong Bb_0\ldots b_n$
as PSTSs by some isomorphism
$f_0$
extending f such that
$f_0(a_i)=b_i$
for every
$i\leq n$
. We cannot ensure that
$\langle Aa_0\ldots a_n\rangle \cong \langle Bb_0\ldots b_n\rangle $
, since
$Aa_0\ldots a_n\leq M$
may not hold.
The
$b_i$
are obtained inductively, starting with
$b_n$
. We choose
$b_n\in N\smallsetminus B$
so that
$Bb_n\leq N$
. It is easy to see that
$Aa_n\cong Bb_n$
by an isomorphism extending f. Assume inductively
$f_{i+1}:Aa_{i+1}\ldots a_n\cong Bb_{i+1}\ldots b_n$
with
$f\subseteq f_{i+1}$
and
$f_{i+1}(a_j)=b_j$
, and assume
$$ \begin{align*}B\leq Bb_n\leq \cdots \leq Bb_{i+1}\ldots b_n\leq N.\end{align*} $$
There are several cases for
$a_i$
. If
$a_i= a_j\cdot a_k$
with
$i<j$
and
$k\leq n$
, we take
$b_i =b_j\cdot b_k$
. If
$a_i = a_j\cdot c$
with
$i<j\leq n$
and
$c\in A$
, we put
$b_i=b_j\cdot f_{i+1}(c)$
. In other cases, we use Lemma 7.2 to get
$b_i\in N\smallsetminus Bb_{i+1}\ldots b_n$
such that
$Bb_ib_{i+1}\ldots b_n\leq N$
and which is not a product of elements of
$Bb_{i+1}\ldots b_n$
. In all cases,
$Bb_{i+1}\ldots b_n\leq Bb_ib_{i+1}\ldots b_n\leq N$
and
$f_{i+1}$
extends to some
$f_i: Aa_i\ldots a_n\cong Bb_i\ldots b_n$
with
$f_i(a_i)=b_i$
.
Now we define a set
$\Sigma $
of formulas over B in the language extended by the symbol
$<$
, with free variables
$\{x_i\mid i<\omega \}$
and expressing the following conditions:
-
1.
$(x_i\mid i<\omega )$
realizes the diagram of
$(a_i\mid i<\omega )$
over A (as a PSTS) conjugated by the isomorphism f; -
2.
$<$
is an HF-ordering and coincides with
$<_N$
on B; -
3.
$x_i>x_{i+1}$
; -
4. if
$b\in B$
is not a product of smaller elements of B in the order
$<_N$
, then
$\forall xy \, (x,y<b\rightarrow x\cdot y\neq b)$
; -
5. if
$a_i$
is not the product of smaller elements
$a_j, a_k$
nor the product of a smaller
$a_j$
with an element of A, then
$\forall xy\, (x,y<x_i\rightarrow x\cdot y \neq x_i)$
.
Every finite subset of
$\Sigma $
is satisfiable in N. More precisely, for every
$n<\omega $
the order
$<_N$
satisfies all five conditions if we restrict
$\Sigma $
to the variables
$x_0,\ldots ,x_n$
and we assign to these variables the sequence
$b_0,\ldots ,b_n$
described above. Note that we can interpret the order as an HF-ordering of N that coincides with
$<_N$
on B and has B as an initial segment, followed by
$b_n,\ldots ,b_0$
in ascending order. Now we use Remark 7.3 to obtain an interpretation of
$\Sigma $
in N over B, namely, an HF-ordering
$<^\prime $
of N and a sequence
$(b_i\mid i <\omega )$
of elements of N that satisfy all conditions on
$\Sigma $
over B. Then
$f\cup \{(a_i,b_i)\mid i<\omega \}$
is an isomorphism of PSTSs between
$A(a_i\mid i<\omega )$
and
$B(b_i\mid i<\omega )$
. Note that
$\operatorname {\mathrm {cl}}_{<^\prime }(B\cup \{b_i\mid i<\omega \}) =B\cup \{b_i\mid i<\omega \}$
and, therefore,
$B(b_i\mid i<\omega )\leq N$
. Hence
$\langle A(a_i\mid i<\omega )\rangle \leq M$
and
$\langle B(b_i\mid i<\omega )\rangle \leq N$
, and so, by Lemma 7.1, we can extend f to an isomorphism
$f^\prime :\langle A(a_i\mid i<\omega )\rangle \cong \langle B(b_i\mid i<\omega )\rangle $
.
Corollary 7.6. Let
$M,N$
be infinite unconfined STS. If
$A\leq M$
,
$B\leq N$
, and
$f:A\rightarrow B$
is an isomorphism of PSTS, then f is a partial elementary map from M to N.
Proof. First consider the case where A and B are countable. By Lemma 7.1,
$\langle A\rangle \leq M$
,
$\langle B\rangle \leq N$
, and f extends to some isomorphism
$f^\prime :\langle A\rangle \cong \langle B\rangle $
. We can find uncountable saturated (or special
$\omega _1$
-saturated) elementary extensions
$M^\prime \succeq M$
and
$N^\prime \succeq N$
. Notice that
$A\leq M^\prime $
and
$B\leq N^\prime $
. By Proposition 7.5,
$f^\prime $
belongs to a back-and-forth system between
$M^\prime $
and
$N^\prime $
and so it is a partial elementary map from
$M^\prime $
to
$N^\prime $
and also from M to N.
Consider now the general case. Fix an HF-ordering of M having A as an initial segment. Consider a finite set
$A_0\subseteq A$
and let
$A_0^\prime =\operatorname {\mathrm {cl}}_<(A_0)$
. Since A is an initial segment,
$A_0^\prime \subseteq A$
. By Lemma 3.11, we may assume that
$A_0^\prime $
is an initial segment of A. Then
$A_0^\prime \leq A$
and
$A_0^\prime \leq M$
. Now order B in such a way that f is an order isomorphism. This gives an HF-ordering of B. Moreover, if
$B_0=f(A_0)$
and
$B_0^\prime = f(A_0^\prime )$
, then
$B_0\subseteq B_0^\prime $
and
$B_0^\prime $
is an initial segment of B. Hence
$B_0^\prime \leq B$
and
$B_0^\prime \leq N$
. Since
$A_0^\prime $
and
$B_0^\prime $
are countable, by the initial case we know that
$f\restriction A_0^\prime $
is elementary. Hence, f is elementary.
The completeness of the theory of infinite unconfined STS is implicit in the proof of Corollary 7.6.
Corollary 7.7. The theory of all infinite unconfined STS is complete; it is the complete theory of every free STS with
$\geq 3$
generators.
Proof. Corollary 7.6 implies that the empty mapping between unconfined STS is elementary. The claim follows directly.
Remark 7.8. Assume M is an infinite unconfined STS and
$A=\langle A\rangle \leq M$
. By Corollary 7.6, for any
$a\not \in A$
the condition
$Aa\leq M$
from Proposition 6.6 defines a complete type
$\operatorname {\mathrm {tp}}(a/A)$
: if
$b\not \in A$
and
$Ab\leq M$
, the mapping which is the identity on A and sends a to b is elementary.
Lemma 7.9. Let M be an infinite unconfined STS and let
$\bar {a},\bar {b}$
be tuples from M. If for some HF-orderings
$<$
and
$<^\prime $
of M,
$\operatorname {\mathrm {cl}}_<(\bar {a})$
and
$\operatorname {\mathrm {cl}}_{<^\prime }(b)$
have the same diagram as PSTS, then
$\operatorname {\mathrm {tp}}_M(\bar {a})=\operatorname {\mathrm {tp}}_M(\bar {b})$
.
Proof. By Corollary 7.6, since
$\operatorname {\mathrm {cl}}_<(\bar {a})\leq M$
and
$\operatorname {\mathrm {cl}}_{<^\prime }(\bar {b})\leq M$
.
Proposition 7.10. The theory of free STSs is stable.
Proof. We count
$1$
-types over a model M and show that their number is
$\leq |M|^\omega $
. We assume that M is an elementary substructure of the monster model
$\mathbb {M}$
. Then
$M\leq \mathbb {M}$
by Lemma 5.17, and we can fix an HF-ordering
$<$
of
$\mathbb {M}$
, where M is an initial segment. If
$a,b \in \mathbb {M}$
and
$\operatorname {\mathrm {cl}}_<(a)$
,
$\operatorname {\mathrm {cl}}_<(b)$
have the same diagram over M as PSTS, then, by Lemma 7.9, they have same type over M. Hence, the number of
$1$
-types over M is bounded by the number of PSTS isomorphism types of countable tuples over M, which is clearly
$\leq |M|^\omega $
.
Proposition 7.11. Let
$M,N$
be models of the theory of free STSs. If
$M\leq N$
, then
$M\preccurlyeq N$
.
Proof. By Corollary 5.17 we may assume that N is
$\omega _1$
-saturated. Let
$\bar {a}\in M$
be a finite tuple. We want to show that
$\operatorname {\mathrm {tp}}_N(\bar {a})=\operatorname {\mathrm {tp}}_M(\bar {a})$
. Fix an HF-ordering
$<$
of N with initial segment M and let
$\bar {a}^\prime $
be a countable tuple enumerating
$\operatorname {\mathrm {cl}}_<(\bar {a})$
. It follows from Definition 3.10 that elements in
$\bar {a}^\prime \smallsetminus \bar {a}$
precede elements in
$\bar {a}$
in the ordering. It suffices to show that
$\operatorname {\mathrm {tp}}_N(\bar {a}^\prime )=\operatorname {\mathrm {tp}}_M(\bar {a}^\prime )$
. Let
$p(\bar {x})=\operatorname {\mathrm {tp}}_M(\bar {a}^\prime )$
. By
$\omega _1$
-saturation, there is some tuple
$\bar {b}\in N$
realizing
$p(\bar {x})$
. This implies that
$\bar {b}\leq N$
(the formulas expressing this belong to
$p(\bar {x})$
), and moreover
$\bar {a}^\prime $
and
$\bar {b}$
have the same quantifier-free type as PSTSs. They have the same diagram as STSs. Moreover
$\bar {a}^\prime \leq N$
. By Corollary 7.6,
$\bar {a}^\prime \equiv \bar {b}$
in N. Hence
$\operatorname {\mathrm {tp}}_N(\bar {a}^\prime )=\operatorname {\mathrm {tp}}_N(\bar {b})=\operatorname {\mathrm {tp}}_M(\bar {a}^\prime )$
.
Proposition 7.12. Let M be an infinite unconfined STS and let
$A =\langle A\rangle \subseteq M$
be infinite. Then
$A\equiv M$
. Moreover,
-
1.
$\operatorname {\mathrm {acl}}(A)\preceq M$
; -
2.
$A \leq M$
if and only if
$ \operatorname {\mathrm {acl}}(A)=A$
.
Proof. Since A is an infinite unconfined STS, by completeness of the theory
$A\equiv M$
. Claim 1 follows from Proposition 7.11, since, by Proposition 5.16,
$\operatorname {\mathrm {acl}}(A)\leq M$
. Claim 2 follows from 1 and Proposition 7.11.
Remark 7.13. Let M be an infinite unconfined STS. If
$A\subseteq M$
, then
$\operatorname {\mathrm {acl}}(A)$
is the intersection of all substructures
$B\supseteq A$
of M such that
$B\leq M$
.
Proof. The trivial case where A is contained in a block is easy. Otherwise,
$\langle A\rangle $
is infinite and, by Proposition 7.12,
$\operatorname {\mathrm {acl}}(A)$
contains the intersection of all substructures B of M such that
$A\subseteq B\leq M$
. On the other hand, if B is one of these structures, again by Proposition 7.12,
$\operatorname {\mathrm {acl}}(A)\subseteq \operatorname {\mathrm {acl}}(B) =B$
.
Remark 7.14. Let
$F_n$
be the free STS with
$n\geq 3$
generators. Every surjective homomorphism
$f:F_n\rightarrow F_n$
is an automorphism of
$F_n$
.
Proof. See [Reference Barbina and Casanovas7, Corollary 2.11].
As remarked by the anonymous referee, a group where every surjective endomorphism is an automorphism is called Hopfian. Proofs of this property for groups often use ad-hoc techniques, whereas our argument applies to any free algebras arising from a class that satisfies the hypotheses of Theorems 1 and 2 in [Reference Jónsson and Tarski22]—that is, the class contains a finite algebra with more than one element, and is such that any algebra that is free for the finite elements in the class is free for the whole class (for the second condition in the case of STSs see [Reference Barbina and Casanovas7, Lemma 2.6]).
Proposition 7.15. Let
$F_n$
be the free STS with
$n\geq 3$
generators. Every elementary embedding
$f:F_n\rightarrow F_n$
is surjective and, therefore, is an automorphism of
$F_n$
.
Proof. Let
$F_n=\langle \bar {a}\rangle $
, where
$\bar {a}=a_1,\ldots ,a_n$
is a free base, and let
$a_i^\prime =f(a_i) = t_i(\bar {a})$
for every
$i=1,\ldots ,n$
, where
$t_i$
is a corresponding term. Then
$F_n$
satisfies
$$ \begin{align*}\exists x_1\ldots x_n \bigwedge_{i=1}^n a_i^\prime = t_i(x_1,\ldots,x_n).\end{align*} $$
Since
$f(F_n)\preceq F_n$
, the same sentence holds in
$f(F_n)$
and, by isomorphism,
$F_n$
satisfies
$$ \begin{align*}\exists x_1\ldots x_n \bigwedge_{i=1}^n a_i= t_i(x_1,\ldots,x_n).\end{align*} $$
Choose
$\bar {b}= b_1,\ldots ,b_n\in F_n$
such that
$a_i= t_i(\bar {b})$
for every
$i=1,\ldots ,n$
. Then
$F_n=\langle b_1,\ldots ,b_n\rangle $
and
$b_1,\ldots ,b_n$
are independent by Remark 7.14. Now consider the automorphism
$g:F_n\rightarrow F_n$
defined by
$g(b_i)=a_i$
for
$i=1,\ldots ,n$
. Observe that for every i
$$ \begin{align*}g(a_i)= g(t_i(\bar{b}))= t_i(g(\bar{b}))=t_i(\bar{a})= a_i^\prime.\end{align*} $$
This implies that
$f=g$
and, therefore, that f is an automorphism.
Proposition 7.16. If
$3\leq n<m$
, there is no elementary embedding of
$F_m$
, the free STS with m generators, into
$F_n$
, the free STS of n generators, despite the elementary equivalence of
$F_m$
and
$F_n$
.
Proof. Assume
$n<m$
and
$f:F_m\rightarrow F_n$
is an elementary embedding with
$f(F_m)=F_m^\prime $
. There is a copy
$F_m^{\prime \prime }$
of
$F_m$
such that
$F_n \leq F_m^{\prime \prime }$
, so
$F_n\preccurlyeq F_m^{\prime \prime }$
by Proposition 7.11. Without loss of generality,
$F_m=F_m^{\prime \prime }$
. Let g be the inclusion map
$F_n \mapsto F_m$
restricted to
$F_m^\prime $
. Then
$ g \circ f\, : F_m \to F_m$
is an elementary injection with
$g \circ f(F_m)\neq F_m$
, contradicting Proposition 7.15.
Proposition 7.17. There is a (countable) unconfined STS which is not free.
Proof. Let
$N=F_3$
be the free STS generated by three elements
$a_1,a_2,a_3$
, and let
$b = (a_1 \cdot a_2) \cdot (a_1 \cdot a_3)$
. As shown in [Reference Barbina and Casanovas7, Example 6.9], the homomorphism
$f:N\rightarrow N$
determined by
$f(a_1)=b$
,
$f(a_2)=a_2$
, and
$f(a_3)=a_3$
is an embedding but it is not surjective. Hence, there is some proper substructure of N isomorphic to N. So we can define an ascending chain
$(N_n\mid n<\omega )$
of STSs such that
$N_n\cong N$
and
$N_n\neq N_{n+1}$
. Let
$N_\omega =\bigcup _{n<\omega }N_n$
. Since
$N_\omega $
is a union of a countable chain of unconfined STSs and unconfinedness fails on a finite subset, we have that
$N_\omega $
is unconfined. Moreover, it is not finitely generated. Since it is countable, if it is free then it has a free base B of
$\omega $
elements and it is (isomorphic to) the generic. There is an embedding
$f:F_4\rightarrow N_\omega $
such that
$f(F_4)\leq N_\omega $
. Choose n such that the image in f of the base of
$F_4$
is contained in
$N_n$
. Then
$f(F_4)\leq N_n$
and by Proposition 7.11,
$f:F_4\rightarrow N_n$
is elementary. Since
$N_n\cong F_3$
, this contradicts Proposition 7.16. Hence,
$N_\omega $
is not free.
Acknowledgments
We are grateful to the anonymous referee for a prompt review and valuable suggestions and comments that have much improved the manuscript. The first author acknowledges membership of Gruppo Nazionale per le Strutture Algebriche, Geometriche e loro Applicazioni (GNSAGA-INdAM).
Funding
Research partially supported by grants PID2020-116773GB-I00 and PID2023-147428NB-I00 from the Spanish Government. The first author has also been supported by PRIN2022 Models, sets and classifications, prot. 2022TECZJA.
