1 Introduction
We say that a first-order structure M is a Fraïssé structure if it is countably infinite and ultrahomogeneous (see [Reference Hodges5, Reference Macpherson10] for background ). Let M be a Fraïssé structure, and let
$\operatorname {\mathrm {Age}}_\omega (M)$
be the class of structures A which are embeddable in M, including infinite structures. For finite
$A \in \operatorname {\mathrm {Age}}_\omega (M)$
, immediately by the definition of ultrahomogeneity we have that for each embedding
$f : A \to M$
, each automorphism g of
$f(A)$
extends to an automorphism
$\theta (g)$
of M, giving a map
$\theta : \operatorname {\mathrm {Aut}}(f(A)) \to \operatorname {\mathrm {Aut}}(M)$
. Two questions immediately arise:
-
• If A is infinite, does there exist an embedding $f : A \to M$
with such an extension map
$\theta $
? -
• Can we additionally require that $\theta $
is a group embedding (i.e., preserves composition), or that
$\theta $
is unique?
Let
$A \in \operatorname {\mathrm {Age}}_\omega (M)$
, and let
$f : A \to M$
be an embedding. We say that f is group-extensive if there exists a group embedding
$\theta : \operatorname {\mathrm {Aut}}(f(A)) \to \operatorname {\mathrm {Aut}}(M)$
such that
$\theta (g)$
extends g for all
$g \in \operatorname {\mathrm {Aut}}(f(A))$
. We call f uniquely extensive if each automorphism of
$f(A)$
extends uniquely to an automorphism of M. Any uniquely extensive embedding is group-extensive (by uniqueness, the extension map must preserve composition), and it is straightforward to see that an embedding
$f : A \to M$
is uniquely extensive if and only if it is group-extensive and the pointwise-stabiliser of
$f(A)$
in
$\operatorname {\mathrm {Aut}}(M)$
is trivial. If M has strong amalgamation, then it is easy to see that no finite A admits a uniquely extensive embedding, so for uniquely extensive embeddings we restrict attention to infinite A.
We will say that
$\operatorname {\mathrm {Age}}_\omega (M)$
is group-extensible if each
$A \in \operatorname {\mathrm {Age}}_\omega (M)$
admits a group-extensive embedding into M. We write
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
for the set of infinite elements of
$\operatorname {\mathrm {Age}}_\omega (M)$
, and say that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible if each of its elements admits a uniquely extensive embedding into M.
Bilge and Melleray showed that
$\operatorname {\mathrm {Age}}_\omega (M)$
is group-extensible for structures M with free amalgamation ([Reference Bilge and Melleray3, Theorem 3.9]—an adaptation of an argument of Uspenskij in [Reference Uspenskij15]), and this was generalised to structures M with a stationary independence relation (SIR) by Müller [Reference Müller13]. (SIRs were originally defined in [Reference Tent and Ziegler14]: they encode the notion of a symmetric canonical amalgam, one particular case of which is the free amalgam.) The construction in each case is similar, and is sometimes referred to as a Katětov tower construction (Katětov used this to produce the Urysohn space in [Reference Katětov and Frolík7]). A general abstract categorical formulation of this construction is given in [Reference Kubiś and Mašulović8], and investigated further in [Reference Kwiatkowska, Sullivan and Winkel9].
Henson [Reference Henson4] showed that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible for M equal to the random graph (also shown independently by Macpherson and Woodrow in [Reference Macpherson and Woodrow11]), and Bilge [Reference Bilge1] extended this result in his Ph.D. thesis to any transitive free amalgamation structure M in a finite relational language (and satisfying the non-triviality condition that there are two distinct points related by some relation, i.e., M is not an indiscernible set). For the particular case of the generic
$K_n$
-free graph, see [Reference Bilge and Jaligot2]. In [Reference Kwiatkowska, Sullivan and Winkel9, Proposition 6.1], the authors of the present paper showed that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible for M equal to the generic ordered graph, again using a Katětov tower construction; we believe that a straightforward generalisation of this, analogous to [Reference Bilge1, Theorem 8.30], should give unique extensibility for the generic order expansion of a non-trivial transitive free amalgamation structure in a finite relational language.
Given Müller’s result that
$\operatorname {\mathrm {Age}}_\omega (M)$
is group-extensible for M with an SIR, it is therefore natural to wonder if the presence of an SIR on M implies that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible. The graph M consisting of the disjoint union of
$\omega $
-many countably infinite cliques shows that this is not the case, but one may argue that this example is somehow too trivial. Jaligot [Reference Jaligot6] showed that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible for M equal to the random tournament (which admits an independence relation satisfying all the axioms of an SIR except symmetry), and Melleray [Reference Melleray12] showed that, for any separable metric space A, there exists an isometric embedding f of A into the (complete) Urysohn space
$\mathbb {U}$
such that every isometry of
$f(A)$
extends uniquely to an isometry of
$\mathbb {U}$
. (Note that the rational Urysohn space admits a (local) SIR; see [Reference Tent and Ziegler14, Example 2.2.1(a)].)
In this article, we consider the case of the generic poset M: the Fraïssé limit of the class of all finite posets. Observe that M admits an SIR: for
$A, B, C \subseteq _{\text {fin\!}} M$
, define
if the poset
$A \cup B \cup C$
is the transitive closure of the free amalgam of
$B \cup A$
,
$C \cup A$
over A. More explicitly, we define
if for
$b \in B \setminus A$
,
$c \in C \setminus A$
we have:
-
• $b \neq c$
; -
• $b < c \iff $
there exists
$a \in A$
with
$b < a < c$
; -
• $b> c \iff $
there exists
$a \in A$
with
$b> a > c$
.
The main (and indeed only) theorem of this article states that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible.
Theorem 5.1. Let M denote the generic poset, and let A be a countably infinite poset. Then there exists an embedding
$f : A \to M$
with coinfinite image such that each automorphism of
$f(A)$
extends uniquely to an automorphism of M.
We also note that the induced group embedding
$\operatorname {\mathrm {Aut}}(f(A)) \to \operatorname {\mathrm {Aut}}(M)$
given by the above theorem will in addition be an embedding of topological groups with closed image (this is immediate by Lemma 5.9(i)). Also, the fact that the embedding f given by Theorem 5.1 has coinfinite image ensures that we exclude the trivial case of surjective f when
$A \cong M$
.
1.1 Comparison with previous results
Our construction of the embedding f differs significantly from the previous examples mentioned above and is very particular to the generic poset; essentially, the fundamental difficulty that prevents a straightforward generalisation of the previous results of Bilge for free amalgamation classes or Jaligot for tournaments is that the poset relation
$<$
is transitive.
We now briefly outline the proof ideas of previous results.
In the case of linear orders (which one might initially expect to be analogous to partial orders), we have that
$\operatorname {\mathrm {Age}}_{\text {inf}}(\mathbb {Q}, <)$
is not uniquely extensible: we show that any
$A \in \operatorname {\mathrm {Age}}_{\text {inf}}(\mathbb {Q}, <)$
with
$A \not \cong \mathbb {Q}$
does not admit a uniquely extensive embedding into
$\mathbb {Q}$
as follows. Let
$f : A \to \mathbb {Q}$
be an embedding. As
$f(A) \not \cong \mathbb {Q}$
we have that
$f(A)$
is either not dense as a linear order or has an endpoint, and so there are
$u, v \in \mathbb {Q}$
with
$(u, v) \cap f(A) = \varnothing $
. Let g be a non-trivial automorphism of
$(u, v)$
. Then
$\operatorname {\mathrm {id}}_{\mathbb {Q}}$
and
$g \cup \operatorname {\mathrm {id}}_{\mathbb {Q} \setminus (u, v)}$
are distinct automorphisms of
$\mathbb {Q}$
extending
$\operatorname {\mathrm {id}}_{f(A)}$
, so f is not uniquely extensive. (In fact, a stronger statement is true: if a countably infinite linear order A admits a uniquely extensive embedding
$f : A \to \mathbb {Q}$
, then
$A \cong \mathbb {Q}$
and f is surjective. See [Reference Bilge1, Proposition 8.33].)
A sketch proof of unique extensibility for the random graph [Reference Henson4] is as follows: given a countably infinite graph A, inductively construct a chain
$A = M_0 \subseteq M_1 \subseteq \cdots $
where, to build
$M_k$
from
$M_{k - 1}$
, for each
$F \subseteq _{\text {fin\!}} M_{k - 1}$
with
$|F \cap M_0| = k$
we add a new vertex
$v_F$
adjacent to exactly F. Note that, for
$k \geq 1$
, each
$g \in \operatorname {\mathrm {Aut}}(M_{k-1})$
fixing
$M_0$
setwise extends uniquely to an element of
$\operatorname {\mathrm {Aut}}(M_k)$
via
$v_F \mapsto v_{g(F)}$
. Let
$M_\omega = \bigcup _{k < \omega } M_k$
; then each
$g \in \operatorname {\mathrm {Aut}}(A)$
extends to an element of
$\operatorname {\mathrm {Aut}}(M_\omega )$
. For
$v \in M_\omega $
let
$\operatorname {\mathrm {N}}(v)$
denote the neighbourhood of v in
$M_\omega $
. It is clear that any
${h \in \operatorname {\mathrm {Aut}}(M_\omega )}$
extending
$g \in \operatorname {\mathrm {Aut}}(A)$
satisfies
$|\operatorname {\mathrm {N}}(h(v)) \cap M_0| = |\operatorname {\mathrm {N}}(v) \cap M_0|$
for each
$v \in M_\omega \setminus M_0$
, and therefore stabilises each “layer”
$M_k$
setwise, giving uniqueness of automorphism extension. To show that
$M_\omega $
is isomorphic to the random graph, one checks that for each pair of finite disjoint sets
$U, V \subseteq M_\omega $
, there is a “witness”
$m \in M_\omega \setminus (U \cup V)$
with m adjacent to all of U and none of V: for this, as we have
$U, V \subseteq M_{k-1}$
for some
$k \geq |U|$
, we may pad out U with vertices from
$M_0 \setminus V$
to produce
$F \subseteq M_{k-1}$
with
$|F \cap M_0| = k$
, and the new vertex of
$M_k$
whose
$M_{k-1}$
-neighbourhood is F then gives the required witness m.
An analogous construction [Reference Bilge and Jaligot2] by Bilge and Jaligot for the generic triangle-free graph again uses the invariant
$|\operatorname {\mathrm {N}}(v) \cap M_0|$
to define layers
$M_k$
which are setwise-stabilised by any extension of an automorphism of
$M_0$
, but there is an additional complication: one cannot begin with
$M_0 = A$
, as then it is not always possible to pad out U with vertices from
$M_0$
as in the argument above. (For example, consider the case where A is an infinite star graph with central vertex a. Let
$U = \{a, u\}$
be an anticlique with
$u \in M_1 \setminus M_0$
. Any padding-out F of U with an additional vertex from A in an attempt to find a witness for U in
$M_2$
will not work, as there cannot be a new vertex of
$M_2$
adjacent to F: this would create a triangle.) Bilge and Jaligot fix this issue by taking
$M_0 = A \sqcup \mathbb {N}$
, where the edges of
$\mathbb {N}$
are given by
$\{n, n + 1\}$
for
$n \in \mathbb {N}$
(so the graph on
$\mathbb {N}$
is rigid, that is, has trivial automorphism group), and where there are no edges between A and
$\mathbb {N}$
. They then perform the same construction as above, always requiring with each new vertex added that it is adjacent to at least one element of A. This ensures that any
$h \in \operatorname {\mathrm {Aut}}(M_\omega )$
extending an element of
$\operatorname {\mathrm {Aut}}(A)$
must fix
$\mathbb {N}$
, and therefore h setwise-stabilises each
$M_k$
. Padding out with the new
$M_0$
now works: one uses elements of
$\mathbb {N}$
.
In the case of the generic poset that we are concerned with in this article, we also use the idea of attaching a poset to A to define
$M_0$
and then inductively constructing a chain
$M_0 \subseteq M_1 \subseteq \cdots $
. However, our approach requires several new ideas (also in the construction of
$M_0$
): it is difficult to see how the construction of Bilge and Jaligot could work, as it seems that the transitivity of
$<$
breaks natural invariants that one might try.
1.2 Structure of the article and general proof outline
Let M denote the generic poset, and let A be a countably infinite poset. Let
$G = \operatorname {\mathrm {Aut}}(A)$
. The rough overview of the construction of a uniquely extensive embedding
$A \to M$
is as follows. First, we attach a new poset
$R \cup S \cup T$
to A to produce a poset
$M_0$
(see Definition 5.4). Each point of R and S will have its type over A being a G-invariant limit point in the type space consisting of types of one-point extensions over A (see Definition 2.2), which we discuss in Sections 2 and 3, and this will enable us to easily extend the action
$G \curvearrowright A$
to
$G \curvearrowright A \cup R \cup S$
. The set T will also be defined relative to
$A \cup R \cup S$
in such a way that we may easily extend the action
$G \curvearrowright A \cup R \cup S$
to
$G \curvearrowright M_0$
.
In Section 5.2 we then inductively construct a chain
$M_0 \subseteq M_1 \subseteq \cdots $
of G-posets (posets with a G-action by automorphisms), and we do this in such a way that the union P is isomorphic to the generic poset (by guaranteeing witnesses for each possible one-point extension of a finite substructure—see Lemma 5.12). As we construct P as a G-poset, we immediately have that each automorphism of A extends to an automorphism of P. To guarantee uniqueness of automorphism extension—the most difficult and technically intricate part of the construction—we also ensure that P has the property that any
$h \in \operatorname {\mathrm {Aut}}(P)$
with
$h|_A = \operatorname {\mathrm {id}}_A$
must also be the identity on
$M_0$
(see Lemma 5.11 and the proof of the main Theorem 5.1), and furthermore is the identity on the upward-closure
$S^+$
of S (see Sections 4 and 5.4). This is then sufficient to show that in fact
$h = \operatorname {\mathrm {id}}_P$
(see Lemma 5.5), giving uniqueness.
1.3 Future directions
Given the technical nature of the construction of uniquely extensive embeddings for the generic poset in this article, we imagine that more general results for a broader class of structures may require different techniques. We would also be keen to know if the main theorem of this article leads to other interesting results regarding the automorphism group of the generic poset: certainly, this group is not as well-understood as the automorphism groups of other well-known Fraïssé structures.
2 Valid triples and exterior types
We first define some terminology and notation that we will use throughout the rest of this article.
Definition 2.1. Let P be a poset, and let
$Q \subseteq P$
. We write
We call
$Q^-$
and
$Q^+$
the downward- and upward-closure of Q, respectively.
For
$v \in P$
, we write
$v^- = \{v\}^-$
,
$v^+ = \{v\}^+$
. For
$Q \subseteq P$
and
$v \in P$
, we write
$v \mathbin {\bot } Q$
if
$v \mathbin {\bot } w$
for all
$w \in Q$
.
Definition 2.2. Let A be a poset. We say that a poset E is a one-point extension of A if
$A \subseteq E$
and
$|E \setminus A| = 1$
, and we refer to the unique element e of
$E \setminus A$
as the extension point of E. We write
$\operatorname {\mathrm {tp}}(e / A)$
for the quantifier-free type of e over A. All types considered in this article will be quantifier-free.
We define
$\eta (A)$
to be the set of types
$\operatorname {\mathrm {tp}}(e/A)$
where e is the extension point of a one-point extension of A, and call
$\eta (A)$
the set of exterior types over A. We will usually write
$p \in \eta (A)$
rather than
$p(x) \in \eta (A)$
, with the free variable x being clear from context. For
$A' \subseteq A$
we write
$p|_{A'}$
for the restriction of p to
$A'$
(i.e., the set of formulae in p only involving elements of
$A'$
).
Remark 2.3. We call the elements of
$\eta (A)$
exterior types rather than external types, to avoid a terminological clash with other notions of external type in model theory.
Definition 2.4. Let A be a poset. For
$p \in \eta (A)$
, if
$\phi (x, \bar {a}) \in p$
, we will usually conflate x and p for the sake of brevity and just write
$\phi (p, \bar {a})$
. For example, rather than writing that the formula
$x < a$
is contained in p, we simply write
$p < a$
. (Informally, we think of p as a one-point extension taken up to isomorphism over A.)
For
$p \in \eta (A)$
, we let
Let
$(U, V, W)$
be a partition of A. We say that
$(U, V, W)$
is a valid triple for A if there exists
$p \in \eta (A)$
with
$(U_p, V_p, W_p) = (U, V, W)$
. It is immediate that there is a one-to-one correspondence between elements of
$\eta (A)$
and valid triples given by
$p \mapsto (U_p, V_p, W_p)$
. In the sequel we will mildly abuse notation and identify exterior types with valid triples when convenient: we thus often write
$p = (U_p, V_p, W_p)$
. (One could instead define the set of exterior types entirely in terms of valid triples if desired.)
If A is finite and
$(U, V, W)$
is a valid triple for A, then we say that
$(U, V, W)$
is a finite valid triple.
Let P be a poset. We refer to a valid triple for a substructure of P as a valid triple in P.
The proof of the following lemma is straightforward.
Lemma 2.5. Let A be a poset, and let
$(U, V, W)$
be a partition of A. Then
$(U, V, W)$
is a valid triple if and only if the following hold:
-
• $u < w$
for
$u \in U$
,
$w \in W$
; -
• $\neg (u> v)$
for
$u \in U$
,
$v \in V$
; -
• $\neg (w < v)$
for
$w \in W$
,
$v \in V$
.
Definition 2.6. Let
$A, B$
be posets with
$A \subseteq B$
. Let
$(U, V, W)$
be a valid triple for A. We call
$b \in B \setminus A$
a witness for
$(U, V, W)$
if
$\operatorname {\mathrm {tp}}(b/A) = (U, V, W)$
.
Recall that in the introduction we defined the generic poset M to be the Fraïssé limit of the class of finite posets. See [Reference Hodges5, Chapter 7], [Reference Macpherson10, Section 2.2] for more background: to amalgamate finite posets
$B, C$
over A, one takes the free amalgam and then the transitive closure. We assume that the reader is familiar with the basic theory of Fraïssé limits. In particular, we shall often use the following:
-
(i) the generic poset M contains a witness for each finite valid triple in M (this follows by the extension property of M);
-
(ii) if P is a countable poset containing a witness for each finite valid triple in P, then P is isomorphic to the generic poset M (this is by Fraïssé’s theorem).
We now fix a countably infinite poset A for the remainder of this article.
Definition 2.7. We equip
$\eta (A)$
with the following topology: for
$A_0 \subseteq _{\text {fin\!}} A$
and for
$p_0$
the type over
$A_0$
of a one-point extension of
$A_0$
, we specify that
$\langle p_0 \rangle = \{p \in \eta (A) \mid p \supseteq p_0\}$
is a basic open set of
$\eta (A)$
.
Let
$(U_0, V_0, W_0) = p_0$
. We will also often mildly abuse notation and write
$\langle U_0, V_0, W_0 \rangle $
for the basic open set
$\langle p_0 \rangle $
.
Lemma 2.8.
$\eta (A)$
is a Polish space.
Proof. The topology given in Definition 2.7 is second countable, as A is countable and the language
$\{<\}$
of posets is finite. To define a metric on
$\eta (A)$
, we enumerate A as
$a_0, a_1, \ldots $
. For
$k \in \mathbb {N}$
, let
$A_k = \{a_i \mid i < k\}$
. Given distinct
$p, q \in \eta (A)$
, let
$m \in \mathbb {N}$
be the least index such that
$p|_{A_m} \neq q|_{A_m}$
. We define
$d(p, q) = \frac {1}{m+1}$
. It is straightforward to see that d is a metric compatible with the topology on
$\eta (A)$
, and that
$\eta (A)$
is (sequentially) compact and hence complete with respect to d.
Remark 2.9. As the theory of the generic poset is
$\omega $
-categorical and has quantifier elimination, we have that
$\eta (A)$
is a subspace of
$S_1(A)$
, the Stone space of
$1$
-types in the usual model-theoretic sense (where we consider A as a subset of the generic poset M). It is straightforward to see that
$\eta (A)$
is a closed subspace of
$S_1(A)$
: if a type is not exterior, this is witnessed by a formula
$x = a$
.
Definition 2.10. Let
$p, q \in \eta (A)$
. We say that
$(p, q)$
is
$<$
-valid if there exists a poset
$E = A \cup \{b, c\}$
extending A with
$\operatorname {\mathrm {tp}}(b/A) = p$
,
$\operatorname {\mathrm {tp}}(c/A) = q$
and
$b < c$
. We define
$\mathbin {\bot }$
-valid and
$>$
-valid similarly.
The proof of the following lemma is again straightforward.
Lemma 2.11. Let
$p, q \in \eta (A)$
. Then:
-
• $(p, q)$
is
$<$
-valid
$\iff $
($U_p \subseteq U_q$
and
$V_p \subseteq U_q \cup V_q$
); -
• $(p, q)$
is
$\mathbin {\bot }$
-valid
$\iff $
($U_p \cap W_q = \varnothing $
and
$U_q \cap W_p = \varnothing $
).
(Note that
$(p, p)$
is
$<$
-valid and
$\mathbin {\bot }$
-valid for all
$p \in \eta (A)$
.)
Definition 2.12. We define a binary relation
$\ll $
on
$\eta (A)$
by:
$p \ll q$
if
$p \neq q$
and
$(p, q)$
is
$<$
-valid. Lemma 2.11 implies that
$\ll $
is a strict partial order (i.e., transitive and irreflexive).
Lemma 2.13. Let
$p, q \in \eta (A)$
. Then p and q have a meet
$p \wedge q$
and a join
$p \vee q$
in the strict partial order
$\ll $
. Also, for each basic open set
$\langle p_0 \rangle $
and
$p, q \in \langle p_0 \rangle $
, we have that
$p \wedge q, p \vee q \in \langle p_0 \rangle $
.
Proof. It is straightforward to check that
$(U_p \cap U_q, (V_p \cap V_q) \cup (V_p \cap U_q) \cup (V_q \cap U_p), W_p \cup W_q)$
is in
$\eta (A)$
and equal to the meet
$p \wedge q$
, and that
$(U_p \cup U_q, (V_p \cap V_q) \cup (V_p \cap W_q) \cup (V_q \cap W_p), W_p \cap W_q)$
is in
$\eta (A)$
and equal to the join
$p \vee q$
. Let
$\langle U_0, V_0, W_0 \rangle $
be a basic open set containing p and q. Then
$U_0 \subseteq U_p \cap U_q$
,
$V_0 \subseteq V_p \cap V_q$
, and
$W_0 \subseteq W_p \cap W_q$
. So
$\langle U_0, V_0, W_0 \rangle $
also contains
$p \wedge q$
and
$p \vee q$
.
3 Upper and lower limits
Definition 3.1. Let
$\theta \subseteq \eta (A)$
and
$p \in \eta (A)$
. We say that p is an upper limit of
$\theta $
if for every open set
$O \subseteq \eta (A)$
with
$p \in O$
, there exists
$r \in \theta \cap O$
with
$r \ll p$
: equivalently, the type p is a limit point of
$\{r \in \theta \mid r \ll p\}$
. We define lower limits similarly, replacing
$\ll $
with
$\gg $
.
Lemma 3.2. Let
$\theta \subseteq \eta (A)$
be topologically closed and also closed under (finite) meets. Then an element of
$\eta (A)$
is a limit point of
$\theta $
if and only if it is an upper or lower limit of
$\theta $
.
Proof.
$\Leftarrow $
: immediate.
$\Rightarrow $
: Suppose
$p \in \eta (A)$
is a limit point of
$\theta $
but is not an upper or lower limit of
$\theta $
. Then there are open sets
$O_0$
,
$O_1$
containing p such that, in the partial order
$\ll $
, the set
$O_0 \cap \theta $
does not contain any types smaller than p and
$O_1 \cap \theta $
does not contain any types larger than p. Let
$O = O_0 \cap O_1$
. So
$O \cap \theta $
only contains p and types incomparable to p. Let
$O' \subseteq O$
be a basic open set containing p. Then
$O'$
is closed under joins and meets (see Lemma 2.13). As p is a limit point, there is some
$q \in O' \cap \theta $
,
$q \neq p$
. Then
$p \wedge q \in O' \cap \theta $
, so
$p \wedge q = p$
. This implies
$p \ll q$
, contradiction.
Definition 3.3. Let
Observe that
$\lambda (A)$
and
$\mu (A)$
are closed subsets of
$\eta (A)$
(it is easy to see that their complements are open) and are closed under meets and joins, as can be seen from the explicit valid triples for the meet and the join given in the proof of Lemma 2.13.
Also note that for each partition
$(U, V, W)$
of A, we have
We use these equivalences in the proof of Lemma 3.4.
Lemma 3.4. Let
$p \in \lambda (A)$
.
-
(i) There is $V_0 \subseteq _{\text {fin\!}} A$
with
$V_0^-=V_p$
if and only if p is not an upper limit of
$\lambda (A)$
. -
(ii) There is $W_0 \subseteq _{\text {fin\!}} A$
with
$W_0^+=W_p$
if and only if p is not a lower limit of
$\lambda (A)$
.
Proof.
-
(i) $\Rightarrow $
: As
$p \in \lambda (A)$
, we have
$p = (\varnothing , V_p, W_p)$
. Let
$O = \langle \varnothing , V_0, \varnothing \rangle $
. We have
$p \in O$
as
$V_0 \subseteq V_p$
. Suppose there exists
$q \in O \cap \lambda (A)$
with
$q \ll p$
. As
$q \ll p$
, by Lemma 2.11 we have
$U_q=\varnothing $
and
$V_q \subseteq V_p$
. As
$q \in \lambda (A)$
we have
$V_q^- = V_q^{}$
, so as
$q\in O$
we have
$V_q \supseteq V_0^- = V_p$
, thus
$V_p = V_q$
and so
$p = q$
, contradiction. So p is not an upper limit of
$\lambda (A)$
.$\Leftarrow $
: Let
$O = \langle \varnothing , V_0, W_0 \rangle $
be an open set containing p such that there is no
$q \in O \cap \lambda (A)$
with
$q \ll p$
. Let
$q = (\varnothing , V_0^-, A\setminus V_0^-)$
. Then
$q\in O\cap \lambda (A)$
and
$(q,p)$
is
$<$
-valid. So
$q=p$
and thus
$V_0^-=V_p$
. -
(ii) $\Rightarrow $
: Let
$O = \langle \varnothing , \varnothing , W_0\rangle $
. We have
$p \in O$
as
$W_0 \subseteq W_p$
. Suppose there exists
$q \in O \cap \lambda (A)$
with
$q \gg p$
. As
$q \gg p$
we have
$W_q \subseteq W_p$
, and
$W_q \supseteq W_0^+ = W_p$
, so
$W_q=W_p$
. But
$U_q=\varnothing $
so
$p=q$
, contradiction. Thus p is not a lower limit in
$\lambda (A)$
.$\Leftarrow $
: Let
$O=\langle \varnothing , V_0, W_0 \rangle $
be an open set containing p such that there is no
$q\in O\cap \lambda (A)$
with
$q\gg p$
. Let
$q = (\varnothing , A\setminus W_0^+, W_0^+)$
. Then
$q\in O\cap \lambda (A)$
and
$(q,p)$
is
$>$
-valid. So we have
$q=p$
and
$W_0^+=W_p$
.
Definition 3.5. Let G be a group, and let
$G \curvearrowright A$
be an action via automorphisms. We induce an action
$G \curvearrowright \eta (A)$
by translation of parameters: for
$p = (U_p, V_p, W_p) \in \eta (A)$
, we define
$g \cdot p = (g \cdot U_p,\, g \cdot V_p,\, g \cdot W_p)$
. It is immediate that
$(g \cdot U_p,\, g \cdot V_p,\, g \cdot W_p)$
is a valid triple. (It is also straightforward to see that the action
$G \curvearrowright \eta (A)$
is continuous, though we shall not use this.)
Definition 3.6. Let
$\sigma ^+ \colon \lambda (A) \to \mu (A)$
denote the shift map
$\sigma ^+(\varnothing , V, W) = (V, W, \varnothing )$
, and let
$\sigma ^-$
be the inverse of
$\sigma ^+$
.
It is easy to see that
$\sigma ^+$
and
$\sigma ^-$
are
$\operatorname {\mathrm {Aut}}(A)$
-equivariant homeomorphisms which preserve the partial order
$\ll $
. It is also straightforward to see using Lemma 2.11 that for
$p \in \lambda (A)$
, we have that
$(p, \sigma ^+(p))$
is
$<$
-valid and
$\mathbin {\bot }$
-valid.
Proposition 3.7. There is
$p \in \lambda (A)$
such that the following hold:
-
• p is an upper limit or a lower limit of $\lambda (A)$
; -
• p is a fixed point of the action $\operatorname {\mathrm {Aut}}(A) \curvearrowright \eta (A)$
.
Proof. For
$a \in A$
, we write
$c_a \in \mathbb N \cup \{\infty \}$
for the supremum of the lengths of the descending chains in A starting at a. We split the proof into two cases:
$\sup _{a \in A} c_a = \infty $
or
$\sup _{a \in A} c_a < \infty $
. (Note that in the first case A contains arbitrarily long finite chains, but it is possible for A not to contain an infinite chain.)
Suppose
$\sup _{a \in A} c_a = \infty $
. Let
$V = \{a \in A \mid c_a < \infty \}$
and
$W = \{a \in A \mid c_a = \infty \}$
. Then for
$v \in V$
there is no
$w \in W$
with
$w < v$
, as otherwise v would begin arbitrarily long finite descending chains. So
$(\varnothing , V, W)$
is a valid triple: denote the corresponding type by p. We have
$p \in \lambda (A)$
, and it is clear that p is
$\operatorname {\mathrm {Aut}}(A)$
-fixed. Suppose for a contradiction that p is neither an upper nor a lower limit of
$\lambda (A)$
. Then by Lemma 3.4 there are
$V_0 \subseteq _{\text {fin\!}} V$
,
$W_0 \subseteq _{\text {fin\!}} W$
with
$V_0^- = V$
,
$W_0^+ = W$
. Letting
$n = \max(\{0\} \cup \{c_{v_0} \mid v_0 \in V_0\})$
, we have
$c_v \leq n$
for all
$v\in V$
. By assumption
$\sup _{a \in A} c_a = \infty $
, so
$W\neq \varnothing $
. Let
$w_0 \in W_0$
be a minimal element of
$W_0$
and consider a descending chain of length
$n+2$
starting at
$w_0$
. Let
$a \in A$
be the second element of this chain. Since
$w_0> a$
and
$w_0$
was minimal in
$W_0$
, we have
$a \in V$
, but
$c_a \geq n+1$
, contradiction.
We now consider the case
$\sup _{a \in A} c_a<\infty $
. There is
$n \in \mathbb {N}$
with
$\{a \in A \mid c_a = n\}$
infinite. (Note that there may be multiple such n—we choose one.) Let
$V = \{a \in A \mid c_a \leq n\}$
and
$W = A \setminus V$
. Then
$(\varnothing , V, W)$
is a valid triple; denote its corresponding type by p. It is clear that
$p \in \lambda (A)$
and that p is
$\operatorname {\mathrm {Aut}}(A)$
-fixed. Then
$\{a \in A \mid c_a = n\} \subseteq V$
is an infinite set of pairwise incomparable elements, and so V does not contain a finite cofinal set. So there is no
$V_0 \subseteq _{\text {fin\!}} A$
with
$V_0^- = V$
, and thus by Lemma 3.4(i) we have that p is an upper limit of
$\lambda (A)$
.
3.1 Opposite posets
Definition 3.8. Let P be a poset. We define the poset
$P^{\,\text {op}}$
to have the same domain as P, and define
$<^{P^{\, \text {op}}}$
by:
$u <^{P^{\, \text {op}}} v \Leftrightarrow u>^P v$
.
Let
$p \in \eta (A)$
. Then we define
$p^{\,\text {op}} \in \eta (A^{\,\text {op}})$
by
$p^{\,\text {op}} = (W_p, V_p, U_p)$
. (It is easy to check that this is a valid triple for
$A^{\,\text {op}}$
.) It is also straightforward to see that
$p \mapsto p^{\,\text {op}}$
is a homeomorphism
$\eta (A) \to \eta (A^{\,\text {op}})$
, equivariant under the action of
$\operatorname {\mathrm {Aut}}(A) = \operatorname {\mathrm {Aut}}(A^{\,\text {op}})$
.
It is likewise straightforward to check that, for
$p, q \in \eta (A)$
, we have that
$(p, q)$
is
$<$
-valid over A if and only if
$(p^{\,\text {op}}, q^{\,\text {op}})$
is
$>$
-valid over
$A^{\,\text {op}}$
. So, defining the poset relation
$\ll $
on
$\eta (A^{\,\text {op}})$
exactly as for
$\eta (A)$
(see Definition 2.12), we have that
$p^{\,\text {op}} \ll q^{\,\text {op}}$
in
$\eta (A^{\,\text {op}})$
if and only if
$p \gg q$
in
$\eta (A)$
.
We will use the below lemma in our main construction in Section 5 to ensure that we need only consider upper limits.
Lemma 3.9. Let p be an
$\operatorname {\mathrm {Aut}}(A)$
-fixed lower limit of
$\lambda (A)$
. Then
$p^{\,\text {op}}$
is an
$\operatorname {\mathrm {Aut}}(A^{\,\text {op}})$
-fixed upper limit of
$\mu (A^{\,\text {op}})$
.
The proof of the above lemma is immediate.
4 Sets of moieties
In the proof of our main theorem, Theorem 5.1, we will attach a poset
$R \cup S \cup T$
to our original countable poset A, where S is an infinite antichain. Our construction will use particular collections
$\Sigma $
,
$\Sigma '$
of subsets of S satisfying certain useful properties. In this section we show the existence of these collections of subsets, before beginning the main proof.
Definition 4.1. Let S be a countably infinite set, and let
$S' \subseteq S$
. We say that
$S'$
is a moiety
Footnote
1
of S if
$S'$
and
$S \setminus S'$
are infinite.
Now we prove the main lemma of this section, which is key to the main construction in the next section.
Lemma 4.2. Let S be a countably infinite set. There are infinite collections
$\Sigma , \Sigma ' \subseteq \mathcal {P}(S)$
of moieties of S satisfying the following:
-
(i) for $\mathcal {U}, \mathcal {W} \subseteq _{\text {fin\!}} \Sigma $
,
$\mathcal {V} \subseteq _{\text {fin\!}} \Sigma '$
, and
$C, D \subseteq _{\text {fin\!}} S$
such that $$\begin{align*}\textstyle C \cup \bigcup \mathcal{U} \subseteq \bigcap \mathcal{W} \text{ and } (C \cup \bigcup \mathcal{U}) \cap (D \cup \bigcup \mathcal{V}) = \varnothing, \end{align*}$$
there is $Z \in \Sigma $
satisfying $$\begin{align*}\textstyle C \cup \bigcup \mathcal{U} \subseteq Z \subseteq \bigcap \mathcal{W} \text{ and } Z \cap (D \cup \bigcup \mathcal{V}) = \varnothing. \end{align*}$$
If $\mathcal {U} \cap \mathcal {W} = \varnothing $
, there are infinitely many such Z. -
(ii) For $\mathcal {U}, \mathcal {W} \subseteq _{\text {fin\!}} \Sigma '$
,
$\mathcal {V} \subseteq _{\text {fin\!}} \Sigma $
, and
$C, D \subseteq _{\text {fin\!}} S$
such that $$\begin{align*}\textstyle C \cup \bigcup \mathcal{W} \subseteq \bigcap \mathcal{U} \text{ and } (C \cup \bigcup \mathcal{W}) \cap (D \cup \bigcup \mathcal{V}) = \varnothing, \end{align*}$$
there is $Z \in \Sigma '$
satisfying $$\begin{align*}\textstyle C \cup \bigcup \mathcal{W} \subseteq Z \subseteq \bigcap \mathcal{U} \text{ and } Z \cap (D \cup \bigcup \mathcal{V}) = \varnothing. \end{align*}$$
If $\mathcal {U} \cap \mathcal {W} = \varnothing $
, there are infinitely many such Z.
(Here, we follow the usual empty intersection convention: for
$\mathcal {T} \subseteq \mathcal {P}(S)$
, we define
$\bigcap \mathcal {T} = S$
if
$\mathcal {T} = \varnothing $
.)
Remark 4.3. For the convenience of the reader, we note that statement (ii) is just statement (i) with
$\Sigma $
,
$\Sigma '$
, and
$\mathcal {U}$
,
$\mathcal {W}$
swapped.
To see an example of how the empty intersection convention applies: taking
$\mathcal {U} = \mathcal {V} = \mathcal {W} = \varnothing $
, statement (i) gives that for all disjoint
$C, D \subseteq _{\text {fin\!}} S$
, there are infinitely many
$Z \in \Sigma $
with
$C \subseteq Z$
and
$Z \cap D = \varnothing $
, and statement (ii) gives the same but for
$\Sigma '$
.
Proof. Let
$\mathcal {L}_{\mathcal {PO}} = \{<\}$
be the language of posets, and let
$\mathcal {L} = \mathcal {L}_{\mathcal {PO}} \cup \{\chi _0, \chi _1, \chi _2\}$
with
$\chi _i$
a unary relation symbol for
$i < 3$
. For an
$\mathcal {L}$
-structure N, we write
$N^{}_i = \chi _i^{N}$
, and we say that N satisfies condition
$(\ast )$
if the following hold:
-
• $<^N$
is a partial order and
$\{N_0, N_1, N_2\}$
is a partition of N; -
• for $n_0 \in N_0$
,
$n_1 \in N_1$
,
$n_2 \in N_2$
, the following three conditions hold: $$ \begin{align*} n_0 &< n_1 \,\vee\, n_0 \mathbin{\bot} n_1,\\ n_0 &< n_2 \,\vee\, n_0 \mathbin{\bot} n_2,\\ n_1 &< n_2 \,\vee\, n_1 \mathbin{\bot} n_2; \end{align*} $$
-
• for distinct $n^{}_1, n^{\prime }_1 \in N_1$
, we have
$n^{}_1 \mathbin {\bot } n^{\prime }_1$
.
Let
$\mathcal {K}$
be the class of finite
$\mathcal {L}$
-structures satisfying conditions
$(\ast )$
. It is straightforward to check that
$\mathcal {K}$
is an amalgamation class (take the usual poset amalgam given by the transitive closure of the free amalgam); we denote its Fraïssé limit by N. The structure N satisfies condition
$(\ast )$
. In particular, we have that
$N_1$
is an infinite antichain. We may thus identify
$N_1$
with S, and then it is an easy check that
$N_0 = S^- \setminus S$
and
$N_2 = S^+ \setminus S$
. (Recall Definition 2.1.)
It is straightforward to check (using the extension property of N) that N satisfies the following for all distinct
$u, v \in N$
:
-
• if $u, v \in N_0$
, then
$u^+ \cap S \neq v^+ \cap S$
and we have
$(v^+ \cap S \subseteq u^+ \cap S) \Rightarrow u < v$
; -
• if $u, v \in N_2$
, then
$u^- \cap S \neq v^- \cap S$
and we have
$(u^- \cap S \subseteq v^- \cap S) \Rightarrow u < v$
; -
• if $u \in N_0$
,
$v \in N_2$
and
$u < v$
, then
$u^+ \cap v^- \cap S \neq \varnothing $
.
Let
$\Sigma = \{v^- \cap S \mid v \in N_2\}$
and
$\Sigma ' = \{v^+ \cap S \mid v \in N_0\}$
. It is easy to see that
$\Sigma $
and
$\Sigma '$
are infinite sets of moieties of S.
We now prove part (i). If
$\mathcal {U} \cap \mathcal {W} \neq \varnothing $
, then
$C \cup \bigcup \mathcal {U} = \bigcap \mathcal {W}$
, so take
$Z = C \cup \bigcup \mathcal {U}$
.
Now suppose
$\mathcal {U} \cap \mathcal {W} = \varnothing $
. By the definition of
$\Sigma $
and
$\Sigma '$
, there are
$U, W \subseteq _{\text {fin\!}} N_2$
and
$V \subseteq _{\text {fin\!}} N_0$
such that
$\mathcal {U} = \{ u^- \cap S \mid u \in U\}$
,
$\mathcal {V} = \{ v^+ \cap S \mid v \in V\}$
, and
$\mathcal {W} = \{ w^- \cap S \mid w \in W\}$
. We have
$U \cap W = \varnothing $
.
We now show that
$(U, V, W)$
is a valid triple. As
$\bigcup \mathcal {U} \subseteq \bigcap \mathcal {W}$
, for
$u \in U$
,
$w\in W$
we have
$u^- \cap S \subseteq w^- \cap S$
, so
$u < w$
. As
$\bigcup \mathcal {U} \cap \bigcup \mathcal {V} = \varnothing $
, for
$u \in U$
,
$v \in V$
we have
$u^- \cap v^+ \cap S = \varnothing $
and so
$\neg (u> v)$
. For
$v \in V$
,
$w \in W$
, as
$v \in S^- \setminus S$
,
$w \in S^+ \setminus S$
, and S is an antichain, we also have
$\neg (v> w)$
. So
$(U, V, W)$
is a valid triple of a finite subset of N.
Moreover, since
$(C\cup \bigcup \mathcal {U}) \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
and
$C \subseteq \cap \mathcal {W}$
, we also have that
$(C\cup U, D\cup V, W)$
is a finite valid triple. There are infinitely many witnesses
$z \in N_2$
for this finite valid triple (note that any witness in
$N_2$
will satisfy
$(\ast )$
as
$W \subseteq N_2$
), giving infinitely many
$Z = z^- \cap S$
satisfying
$C \cup \bigcup \mathcal {U} \subseteq Z \subseteq \bigcap \mathcal {W}$
and
$Z \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
as required.
The proof of (ii) is analogous to that of (i): just swap
$\mathcal {U}$
and
$\mathcal {W}$
and flip the signs.
5 The main construction
In this section, we will prove the main result of this article.
Theorem 5.1. Let M denote the generic poset, and let A be a countably infinite poset. Then there exists an embedding
$f : A \to M$
with coinfinite image such that each automorphism of
$f(A)$
extends uniquely to an automorphism of M.
In the terminology of the introduction, the above theorem states that
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible for M equal to the generic poset. We first show in the below lemma that to prove the main theorem it suffices to restrict attention to a smaller class of posets.
Lemma 5.2. Let
$\mathcal {U}$
be the class of countably infinite posets A such that
$\lambda (A)$
contains an
$\operatorname {\mathrm {Aut}}(A)$
-fixed upper limit of
$\lambda (A)$
. If every element of
$\mathcal {U}$
admits a uniquely extensive embedding into M, then
$\operatorname {\mathrm {Age}}_{\text {inf}}(M)$
is uniquely extensible.
Proof. Let
$A \in \operatorname {\mathrm {Age}}_{\text {inf}}(M) \setminus \mathcal {U}$
. Then by Proposition 3.7 there exists an
$\operatorname {\mathrm {Aut}}(A)$
-fixed lower limit p of the set of types
$\lambda (A)$
. By Lemma 3.9 we have that
$p^{\,\text {op}}$
is an upper limit of
$\mu (A^{\,\text {op}})$
, so
$\sigma ^-(p^{\,\text {op}})$
is an upper limit of
$\lambda (A^{\,\text {op}})$
. So by assumption there is a uniquely extensive embedding
$f : A^{\,\text {op}} \to M$
. But
$M \cong M^{\,\text {op}}$
, so A also admits a uniquely extensive embedding.
Remark 5.3. Not all countably infinite posets belong to
$\mathcal {U}$
, as we now show. Let
$A = (\mathbb {N}, <)$
. For each
$p \in \mu (A)$
, if
$p \mathbin {\bot } n$
for some
$n \in \mathbb {N}$
, then
$p \mathbin {\bot } m$
for all
$m \geq n$
, so p is an isolated point of
$\mu (A)$
. Thus the only non-isolated point of
$\mu (A)$
is
$p = (A, \varnothing , \varnothing )$
, which is
$\ll $
-maximal in
$\mu (A)$
. So
$\mu (A)$
does not contain any lower limit of itself, and hence
$\lambda (A^{\,\text {op}})$
does not contain any upper limit of itself: thus
$(\mathbb {N}, <)^{\,\text {op}} \notin \mathcal {U}$
.
We will therefore assume from now on that for our fixed countable poset A, there is an
$\operatorname {\mathrm {Aut}}(A)$
-fixed upper limit in
$\lambda (A)$
. We fix one such upper limit and denote it by p. We let
$q = \sigma ^+(p)$
. Then q is an
$\operatorname {\mathrm {Aut}}(A)$
-fixed upper limit of
$\mu (A)$
, and
$(p, q)$
is
$<$
-valid and
$\mathbin {\bot }$
-valid (see Definition 3.6.).
Our construction will begin by attaching a countable poset
$R \cup S \cup T$
to A. We write
$G = \operatorname {\mathrm {Aut}}(A)$
for the remainder of this section. A G-poset is a poset together with a G-action via automorphisms, and a G-poset embedding of G-posets is a poset embedding which is G-equivariant.
Definition 5.4. Let
$R = \{r_i \mid i < \omega \}$
,
$S = \{s_j \mid j < \omega \}$
, and
$T = \{t_a \mid a \in V_p\}$
be antichains, with R and S countably infinite and the domains of
$A, R, S, T$
disjoint.
We define a countable poset
$M_0 = A \cup R \cup S \cup T$
by specifying the partial order relation between each of the posets
$A, R, S, T$
:
-
• each element of R has type p over A;
-
• each element of S has type q over A;
-
• $r_i < s_j$
if
$i \geq j$
and
$r_i \mathbin {\bot } s_j$
if
$i < j$
; -
• $t_a> v$
for
$v \in V_p$
with
$a \geq v$
, and
$t_a$
is incomparable to all other points of
$M_0$
.
We briefly check that
$M_0$
as specified above is indeed a poset: we need to check that
$<$
as defined is transitive and irreflexive. By the definition of the relation
$<$
involving points of T, we have that T is an antichain consisting of points greater than elements of
$M_0 \setminus T$
, so cannot create any
$<$
-cycles or violate transitivity. We therefore just need to check that
$A \cup R \cup S$
as defined above is a poset. The relation defined on
$R \cup S$
is easily seen to be a poset. For each
$r \in R$
,
$s \in S$
, and
$a \in A$
, recalling that
$\operatorname {\mathrm {tp}}(r/A) = p$
,
$\operatorname {\mathrm {tp}}(s/A) = q$
: as
$p = (\varnothing , V_p, W_p)$
and
$q = (V_p, W_p, \varnothing )$
, we cannot have
$r> a$
or
$s < a$
, and we have
$(r < a) \Rightarrow (\forall \, r' \in R, s' \in S)(r' < a \wedge s' \mathbin {\bot } a)$
and
$(s> a) \Rightarrow (\forall \, s' \in S, r' \in R)(s' > a \wedge r' \mathbin {\bot } a)$
. So
$<$
is transitive and irreflexive for
$M_0$
as required.
Note that
$R \cup S $
is a rigid poset (i.e., it has trivial automorphism group). Each element of R is less than some element of S (but is only less than finitely many elements of S), and each element of T is not related to any element of S.
We define a G-action on
$M_0$
extending
$G \curvearrowright A$
as follows: for each
$g \in G$
, g fixes
$R \cup S$
pointwise, and
$g \cdot t_a = t_{ga}$
for
$t_a \in T$
. (Note that as p and q are G-fixed, this does indeed give a G-action.) From now on, we consider
$M_0$
as a G-poset with this action. Note that as
$G \curvearrowright A$
is faithful, any G-poset embedding of this action will also be faithful.
In the remainder of the article, we will construct a G-poset P extending
$G \curvearrowright M_0$
such that P is isomorphic to the generic poset. As P will be a G-poset, we will immediately have that each automorphism of A extends to an automorphism of P—but the key difficulty lies in guaranteeing uniqueness of automorphism extension, or equivalently that
$\operatorname {\mathrm {id}}_P$
is the only automorphism of P extending
$\operatorname {\mathrm {id}}_A$
. The following lemma will be crucial; it shows that, in the generic poset, the only automorphism fixing an upwards-closed set pointwise is the identity.
Lemma 5.5. Let M be the generic poset, and let
$v \in M$
. Let
$f \in \operatorname {\mathrm {Aut}}(M)$
fix
$v^+$
pointwise. Then
$f = \operatorname {\mathrm {id}}_M$
.
Proof. We first claim that for
$m \in M$
such that
$m \mathbin {\bot } v$
, we have
$f(m) = m$
. Let
$m \in M$
with
$m \mathbin {\bot } v$
. As
$f(v) = v$
we have
$f(m) \mathbin {\bot } v$
. Suppose for a contradiction that
$f(m) \neq m$
. If
$f(m)> m$
or
$f(m) \mathbin {\bot } m$
, then
$(\{v, m\}, \{f(m)\}, \varnothing )$
is a valid triple, and as M is the generic poset this valid triple has a witness
$n \in M$
. As
$n \in v^+$
we have
$f(n) = n$
. But
$m < n$
and
$f(m) \mathbin {\bot } n$
, contradiction. If
$f(m) < m$
, then
$(\{v, f(m)\}, \{m\}, \varnothing )$
is a valid triple and we obtain a contradiction similarly, completing the proof of our claim.
Now let
$m \in M$
with
$m < v$
. We have
$f(m) < v$
. Suppose for a contradiction that
$f(m) \neq m$
. If
$f(m)> m$
or
$f(m) \mathbin {\bot } m$
, then
$(\{m\},\{f(m), v\}, \varnothing )$
is a valid triple with a witness in M, fixed by f by the previous claim—contradiction. If
$f(m) < m$
, we similarly use the valid triple
$(\{f(m)\}, \{m, v\}, \varnothing )$
.
As for each
$m \in M$
we have
$m \geq v$
,
$m \mathbin {\bot } v$
, or
$m < v$
, we have therefore shown that f fixes each point of M.
5.1 Outline of the remainder of the construction
To construct the G-poset P extending
$G \curvearrowright M_0$
, we will inductively construct a chain of G-posets
$M_0 \subseteq M_1 \subseteq \cdots $
, and then take
$P = \bigcup _{k < \omega } M_k$
. We will do this in such a way that P is isomorphic to the generic poset (equivalently, P contains a witness for each finite valid triple in each
$M_k$
), but so that any automorphism
$f \in \operatorname {\mathrm {Aut}}(P)$
extending
$\operatorname {\mathrm {id}}_A$
fixes
$S^+$
pointwise: these two requirements are somewhat in tension, and this leads to the complexity of our construction.
To build
$M_k$
from
$M_{k - 1}$
, we take any sufficiently “nice” (we say acceptable) type over
$M_{k - 1}$
whose support outside S is finite and whose downward intersection with S is in a particular sense well-behaved (Definition 5.6), and then we add a witness to
$M_k$
for each element of the G-orbit of this type (Definition 5.8), extending the G-action to these new witness vertices via the G-action on types so that the new vertices added at stage k form a G-orbit. We call the result an acceptable chain.
Let P be the union of an acceptable chain. By Lemma 5.9(vi), for
$m, n \in P$
added at different stages and both lying in
$S^+$
, we will have
$m^- \cap S \neq n^- \cap S$
. So any
$h \in \operatorname {\mathrm {Aut}}(P)$
which fixes S pointwise cannot send m to n, and thus h will setwise-stabilise each layer
$M_k \setminus M_{k-1}$
of new points which lie in
$S^+$
. This is a halfway step to the goal of ensuring that we fix
$S^+$
pointwise, but we still have several problems to solve.
-
• We need to guarantee that any $h \in \operatorname {\mathrm {Aut}}(P)$
fixing A pointwise does in fact fix S pointwise (see Lemma 5.11 for an initial half-step here towards at least setwise-fixing S). In the proof of Theorem 5.1 we then take an acceptable chain satisfying an additional condition (condition (c)) which will indeed finally ensure that S is stabilised setwise. We will also ensure that
$R \cup T$
is stabilised setwise, and the rigidity of
$R \cup S$
will then imply that S is stabilised pointwise (this is why we introduce R in the definition of
$M_0$
: we use it to add rigidity and thereby fix each point of S). -
• We also need to take a particular acceptable chain so that its union P is isomorphic to the generic poset. We show that this is possible in Lemma 5.12, Lemma 5.14, and the proof of the main Theorem 5.1 (see condition (a) in the proof). The need to satisfy the one-point extension property of the generic poset while still having Lemma 5.9(vi) is the reason for introducing the collections $\Sigma $
and
$\Sigma '$
of moieties in Section 4 (see also properties (AC3) and (AC4) in Definition 5.6, the definition of an acceptable pair). -
• The final issue is that we need to ensure that each layer $M_k \setminus M_{k-1}$
of new points lying in
$S^+$
is actually fixed pointwise by h, not just setwise. This is the reason for the introduction of T in the definition of
$M_0$
. See Lemma 5.14 and condition (b) in the proof of the main Theorem 5.1.
Of course, there are several other technical points of the construction which we cannot cover in this overview—but we hope that the above description at least gives the reader an idea of the macro-structure of the proof. The reader may also find it helpful to read Section 5 non-linearly: once a particular concept has been introduced, it may be helpful to skip forward to the proof of Theorem 5.1 to see how it is used in the final construction.
5.2 Acceptable chains
From now on, we take
$\Sigma $
and
$\Sigma '$
to be fixed infinite sets of moieties of S satisfying conditions (i) and (ii) of Lemma 4.2 (the lemma guarantees that such exist).
Recall the definition of the G-poset
$M_0$
from Definition 5.4: in particular, recall that each element of G fixes S pointwise.
Definition 5.6. Let
$M_0 \subseteq B$
, where B is a countable G-poset extending
$M_0$
. We say that a pair
$(U,W)$
of subsets of B is acceptable if it satisfies the following conditions:
-
(AC1) $U < W$
(i.e.,
$u < w$
for all
$u \in U$
,
$w \in W$
); -
(AC2) $U \setminus S$
,
$W \setminus S$
are finite; -
(AC3) if $U^- \cap S \neq \varnothing $
, then we have
$U^- \cap S \in \Sigma $
and also
$U^- \cap S \neq m^- \cap S$
for any
$m \in B$
; -
(AC4) if $U^- \cap (R \cup T)=\varnothing $
, then
$W^+ \cap S \in \Sigma ' \cup \{S\}$
.
For an acceptable pair
$(U,W)$
, we define
$\tau _B(U,W)$
(or simply
$\tau (U,W)$
if clear from context) to be the type over B given by the valid triple
$(U^-, B \setminus (U^-\cup W^+), W^+)$
.
(We think of
$\tau _B(U, W)$
as being “generated” via
$U < \tau _B(U, W) < W$
from the “support”
$(U, W)$
, making
$\tau _B(U, W)$
incomparable to all elements of B for which this is possible.)
Note that if
$(U, W)$
is an acceptable pair, then so is
$(gU, gW)$
for
$g \in G$
, and
$g \cdot \tau_B(U, W) = \tau_B(gU, gW)$
. Also note that the G-orbit of
$\tau _B(U, W)$
is countable, by (AC2) and the fact that each element of G fixes S pointwise.
We will use the following notation for stabilisers throughout the rest of Section 5.
Notation 5.7. Let P be a G-poset. Considering the action
$G \curvearrowright P$
, for Q a subset of P, we write
$\operatorname {\mathrm {St}}(Q)$
for the pointwise-stabiliser of Q in G. Considering the action on the type space
$G \curvearrowright \eta (P)$
(see Definition 3.5), for
$r \in \eta (P)$
we write
$\operatorname {\mathrm {St}}(r)$
for the stabiliser in G of the type r. (The actions in Section 5 are all group actions of G, and so we may write
$\operatorname {\mathrm {St}}$
instead of
$\operatorname {\mathrm {St}}_G$
without any confusion.)
Definition 5.8. Let B be a countable G-poset extending
$M_0$
, and let
$(U,W)$
be an acceptable pair of subsets of B. Let
$\Omega $
be the G-orbit of
$\tau (U, W)$
in
$\eta (B)$
(this orbit is countable, as noted in Definition 5.6). Let
$B \ast (U, W)$
denote the G-poset constructed by extending B as follows:
-
• add a point $e_r$
for each type
$r \in \Omega $
; -
• to define the partial order on $B \ast (U,W)$
, give each
$e_r$
type r over B, and take the transitive closure of the free amalgam over B of the posets
$B \cup \{e_r\}$
for
$r \in \Omega $
(i.e.,
$e_r < e_{r'}$
if and only if there exists
$m\in B$
with
$e_r < m < e_{r'}$
); -
• the G-action is defined by $g \cdot e_r = e_{g \cdot r}$
for
$g\in G$
.
Note that the new points
$\{e_r \mid r \in \Omega \}$
form a G-orbit, and for each new point
$e_r$
we have
$\operatorname {\mathrm {St}}(e_r) = \operatorname {\mathrm {St}}(r)$
.
We say that a G-poset
$B'$
extending B is an acceptable extension if there is an acceptable pair
$(U,W)$
of subsets of B with
$B' = B \ast (U, W)$
. We call an acceptable chain any sequence of G-posets
$(M_k)_{k < l}$
,
$l \in \mathbb {N} \cup \{\omega \}$
, such that
$M_k$
is an acceptable extension of
$M_{k-1}$
for each
$k \geq 1$
.
We now show some properties satisfied by any acceptable chain.
Lemma 5.9 (Properties of acceptable chains).
Let
$(M_k)_{k < l}$
be an acceptable chain. Let
$k < l$
and let
$m \in M_k$
. The following properties hold:
-
(i) there is $A_0\subseteq _{\text {fin\!}} A$
with
$\operatorname {\mathrm {St}}(A_0) \subseteq \operatorname {\mathrm {St}}(m)$
; -
(ii) if $m \in S^- \setminus S$
, there is
$C \subseteq _{\text {fin\!}} V_p$
with
$m^- \cap V_p = C^- \cap V_p$
; -
(iii) if $m \notin (R \cup T)^+$
then
$m^+ \cap S \in \Sigma ' \cup \{S\}$
; -
(iv) if $m \notin S$
then
$m^- \cap S \in \Sigma \cup \{\varnothing \}$
; -
(v) if $m \in S^+$
, then for distinct
$n \in G \cdot m$
we have
$m \mathbin {\bot } n$
; -
(vi) if $m \in S^+$
, then for
$n \in M_k \setminus (G \cdot m)$
we have
$m^- \cap S \neq n^- \cap S$
.
We also have that:
-
(*) for each $k < l$
, the set
$\{m^- \cap S \mid m \in M_k \setminus S\}$
is finite.
Proof. We prove each claim separately via induction on k. For the first five claims, when proving the induction step from
$k-1$
to k, we may assume that
$m \in M_k \setminus M_{k-1}$
and that there is some acceptable pair
$(U, W)$
of subsets of
$M_{k-1}$
with
$m = e_{\tau (U, W)}$
.
(i): In the base case, if
$m \in A$
take
$A_0 = \{m\}$
, if
$m = t_a \in T$
take
$A_0 = \{a\}$
and if
$m \in R \cup S$
take
$A_0 = \varnothing $
. Now we do the induction step. For each
$n \in (U \cup W) \setminus S$
, by the induction hypothesis there is
$A_n \subseteq _{\text {fin\!}} A$
satisfying
$\operatorname {\mathrm {St}}(A_n) \subseteq \operatorname {\mathrm {St}}(n)$
. Let
$A_0 = \bigcup _{n \in (U \cup W) \setminus S} A_n$
. By (AC2) we have
$A_0 \subseteq _{\text {fin\!}} A$
. Then for each
$g \in \operatorname {\mathrm {St}}(A_0)$
and
$n \in U \cup W$
, we have
$gn=n$
(recall that G fixes S pointwise), so
$g \cdot \tau (U,W)=\tau (U,W)$
and hence
$gm = m$
.
(ii): In the base case we have
$m \in V_p$
or
$m \in R$
: take
$C = \{m\}$
or
$C = \varnothing $
, respectively. For the induction step, as
$m = e_{\tau (U, W)} \in S^- \setminus S$
and S is an antichain, we have
$U \subseteq S^- \setminus S$
, so U is finite by (AC2). By the induction hypothesis, for each
$u \in U$
there is
$C_u \subseteq _{\text {fin\!}} V_p$
with
$u^- \cap V_p = C_u^- \cap V_p$
. Let
$C = \bigcup _{u\in U} C_u$
. Then
$C \subseteq _{\text {fin\!}} V_p$
and
$m^- \cap V_p = U^- \cap V_p = C^- \cap V_p$
.
(iii): In the base case
$m \in V_p$
and
$m^+ \cap S = S$
. For the induction step, we have
$m^+ \cap S = W^+ \cap S$
, and
$W^+ \cap S \in \Sigma ' \cup \{S\}$
by (AC4).
(iv): In the base case
$m^- \cap S = \varnothing $
. For the induction step
$m^- \cap S = U^- \cap S$
, and
$U^- \cap S \in \Sigma \cup \{\varnothing \}$
by (AC3).
(v): In the base case, we have
$m\in S$
, so
$G \cdot m = \{m\}$
. We now do the induction step. Recall that
$M_k \setminus M_{k-1} = G \cdot m$
. As
$m \in S^+$
and G fixes S pointwise, we have
$G \cdot m \subseteq S^+$
. Suppose for a contradiction there is
$n \in G \cdot m$
with
$n \neq m$
such that
$m, n$
are comparable. We have
$n = gm$
for some
$g \in G$
. If
$m < n$
, then
$g^{-1}m < m$
, so it suffices to consider the case
$n < m$
. By the definition of
$M_k$
, there is
$n' \in M_{k-1}$
with
$n < n' < m$
. As
$n \in S^+$
, we have
$n' \in S^+$
. We have
$gn' < gm = n$
, so
$gn' < n'$
, contradicting the induction hypothesis for
$n' \in M_{k-1}$
.
(vi): In the base case, we have
$m \in S$
, so
$m^- \cap S = \{m\}$
and
$G \cdot m = \{m\}$
. For
$n \in S \setminus \{m\}$
we have
$n^- \cap S = \{n\}$
and for
$n \in M_0 \setminus S$
we have
$n^- \cap S = \varnothing $
. Now we do the induction step. If
$n \notin S^+$
then
$n^- \cap S = \varnothing $
, and so as
$m \in S^+$
we immediately have
$m^- \cap S \neq n^- \cap S$
. So we may assume
$m, n \in S^+$
. If both
$m, n \in M_{k-1}$
, we are done by the induction assumption, so without loss of generality we may assume
$m \in M_k \setminus M_{k-1}$
and
$n \in M_{k-1}$
(as m and n are in different G-orbits). As before we write
$m = e_{\tau (U, W)}$
. By (AC3) we have
$m^- \cap S = U^- \cap S \neq n^- \cap S$
.
$(\ast )$
: In the base case,
$m^- \cap S = \varnothing $
for
$m \in M_0 \setminus S$
. For the induction step, observe that as G fixes S pointwise, each element of
$M_k \setminus M_{k-1}$
has the same type over S.
Remark 5.10. Let P be the union of an acceptable chain. By Lemma 5.9(i), the induced group embedding
$G \to \operatorname {\mathrm {Aut}}(P)$
is also an embedding of topological groups (where, as usual, the topology is that of pointwise convergence).
Lemma 5.11. Let
$(M_k)_{k < l}$
be an acceptable chain, and let
$P = \bigcup _{k<l} M_k$
. Then:
-
(i) each $s\in S$
is a minimal element of the set of elements of P with type q over A; -
(ii) $R \cup T$
is exactly the set of minimal points of the set
$\{m \in P \mid (m^+ \cup m^-) \cap S \text { is finite}\}$
.
Proof. (i): Let
$m \in P$
, and suppose
$m < s$
for some
$s \in S$
. By Lemma 5.9(ii) there is
$C \subseteq _{\text {fin\!}} V_p$
with
$m^- \cap V_p = C^- \cap V_p$
. As p is an upper limit of
$\lambda (A)$
, by Lemma 3.4 we cannot have
$V_p \subseteq C^-$
. So
$m^- \cap V_p \neq V_p$
, and so m does not have type q over A.
(ii): It is straightforward to check from the definition of
$M_0$
that
$R \cup T \subseteq \{m \in P \mid (m^+ \cup m^-) \cap S \text { is finite}\}$
. As
$R \cup T$
is an antichain, it suffices to show that
$\{m \in P \mid (m^+ \cup m^-) \cap S \text { is finite}\} \subseteq (R \cup T)^+$
. Let
$m \in P$
with
$(m^+ \cup m^-) \cap S$
finite. By Lemma 5.9(iii), if
$m \notin (R \cup T)^+$
then
$m^+ \cap S \in \Sigma ' \cup \{S\}$
, so as
$\Sigma '$
is a collection of moieties of S and S is infinite, we have that
$m^+ \cap S$
is infinite, contradiction.
5.3 Guaranteeing witnesses for one-point extension
To construct an acceptable chain whose union is the generic poset, we will show that it is possible to satisfy the one-point extension property: that is, we will show that in the construction we may ensure there is a witness for each finite valid triple.
Lemma 5.12. Let
$(M_k)_{k < l}$
be an acceptable chain. Let
$k < l$
and let
$(U_0,V_0,W_0)$
be a finite valid triple in
$M_k$
.
-
(i) If $U_0^- \cap S \neq \varnothing $
, then there exists
$Z \in \Sigma $
such that
$(U_0 \cup Z, W_0)$
is an acceptable pair in
$M_k$
with
$\tau (U_0 \cup Z, W_0)$
in the open set
$\langle U_0, V_0, W_0 \rangle $
. -
(ii) If $U_0^- \cap S = \varnothing $
, then there exists
$Z \in \Sigma ' \cup \{\varnothing \}$
such that
$(U_0, W_0 \cup Z)$
is an acceptable pair in
$M_k$
with
$\tau (U_0, W_0 \cup Z)$
in the open set
$\langle U_0, V_0, W_0 \rangle $
.
Proof. (i): As
$U_0^- \cap S \neq \varnothing $
, we have
$W_0 \subseteq S^+ \setminus S$
and
$U_0^- \cap (R \cup T) \neq \varnothing $
. Let
Note that by definition we have
$C \cup \bigcup \mathcal {U} = U_0^- \cap S$
and
$D \cup \bigcup \mathcal {V} = V_0^+ \cap S$
.
Then:
-
• by Lemma 5.9(iv) we have $\mathcal {U} \subseteq \Sigma $
and
$\mathcal {W} \subseteq \Sigma $
; -
• by Lemma 5.9(iii) we have $\mathcal {V} \subseteq \Sigma '$
(note that as
$(U_0, V_0, W_0)$
is a valid triple and
$U_0^- \cap S \neq \varnothing $
, there is no
$v \in V_0$
with
$v^+ \cap S = S$
); -
• by the definition of $M_0$
(specifically, that all pairs of elements of S and T are incomparable and also that each element of R is less than only finitely many elements of S), we have that D is finite; -
• as $(U_0, V_0, W_0)$
is a valid triple we have
$C \cup \bigcup \mathcal {U} \subseteq \bigcap \mathcal {W}$
and
$(C \cup \bigcup \mathcal {U}) \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
; -
• as $W_0 \subseteq S^+$
and
$U_0 < W_0$
, by Lemma 5.9(v) and (vi) we have
$\mathcal {U} \cap \mathcal {W} = \varnothing $
.
So by Lemma 4.2(i) there are infinitely many
$Z \in \Sigma $
with
$C \cup \bigcup \mathcal {U} \subseteq Z \subseteq \bigcap \mathcal {W}$
and
$Z \cap V_0^+ = Z \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
. We take one such Z with the additional property that Z does not lie in the set
$\{m^- \cap S \mid m \in M_k \setminus S\}$
(this set is finite by Lemma 5.9
($\ast $
)). We then have
$U_0^- \cap S \subseteq Z$
and
$Z < W_0$
, and as
$Z \cap V_0^+ = \varnothing $
we also have
$V_0 \cap Z^- = \varnothing $
. So
$(U_0 \cup Z, W_0)$
is an acceptable pair with
$\tau (U_0 \cup Z, W_0) \in \langle U_0, V_0, W_0 \rangle $
.
(ii): If
$U_0^- \cap (R \cup T) \neq \varnothing $
, then trivially
$(U_0, W_0)$
is an acceptable pair and
$\tau (U_0, W_0) \in \langle U_0, V_0, W_0 \rangle $
. So assume
$U_0 ^- \cap (R \cup T) = \varnothing $
. If
$W_0^+ \cap S = S$
then we immediately have that
$(U_0, W_0)$
is an acceptable pair, so we may assume
$W_0^+ \cap S \neq S$
. Let
Note that by definition we have
$C \cup \bigcup \mathcal {W} = W_0^+ \cap S$
and
$D \cup \bigcup \mathcal {V} = V_0^- \cap S$
.
Then:
-
• by Lemma 5.9(iii) we have $\mathcal {U} \subseteq \Sigma '$
and
$\mathcal {W} \subseteq \Sigma '$
; -
• by Lemma 5.9(iv) we have $\mathcal {V} \subseteq \Sigma $
; -
• C is finite by an analogous argument to that for D in case (i);
-
• as $(U_0, V_0, W_0)$
is a valid triple we have
$C \cup \bigcup \mathcal {W} \subseteq \bigcap \mathcal {U}$
and
$(C \cup \bigcup \mathcal {W}) \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
.
So by Lemma 4.2(ii) there is
$Z \in \Sigma '$
with
$W_0^+ \cap S = C \cup \bigcup \mathcal {W} \subseteq Z \subseteq \bigcap \mathcal {U}$
and
$Z \cap V_0^- = Z \cap (D \cup \bigcup \mathcal {V}) = \varnothing $
. Recalling that
$U_0 \cap S = \varnothing $
, we thus have
$U_0 < W_0 \cup Z$
. So
$(U_0, W_0 \cup Z)$
is an acceptable pair and
$\tau (U_0, W_0 \cup Z) \in \langle U_0, V_0, W_0 \rangle $
.
5.4 The stabiliser lemma
The previous section, together with a standard bookkeeping argument to schedule the tasks of adding witnesses for each finite valid triple (as in the usual proof of Fraïssé’s theorem—see [Reference Hodges5, Section 7.1]), shows that there exists an acceptable chain
$(M_k)_{k < \omega }$
whose union is the generic poset. To guarantee unique extension of automorphisms of A, we further refine the construction by controlling better the action of G on
$S^+$
.
Notation 5.13. Let
$(M_k)_{k < l}$
be an acceptable chain, and let
$P = \bigcup _{k < l} M_k$
. When we write
$S^+$
, this means the upward-closure of S in P. For
$k < l$
, we define
$S^+_k = S^+ \cap M_k$
.
Lemma 5.14. Let
$(M_k)_{k < l}$
be an acceptable chain with
$l> 0$
finite. Let
$(U_0, V_0, W_0)$
be a finite valid triple in
$M_{l-1}$
. Assume
$U_0^- \cap S \neq \varnothing $
.
Then we can extend
$(M_k)_{k < l}$
to an acceptable chain
$(M_k)_{k < l'}$
such that
$M_{l'-1}$
contains a point with a type lying in the open set
$\langle U_0, V_0, W_0 \rangle $
, and the following holds:
Proof. First observe that, given an acceptable chain up to stage
$M_k$
, to prove
($\star $
) for k it suffices to show the equality for a single point of
$M_k \setminus M_{k - 1}$
, as
$M_k \setminus M_{k - 1}$
forms a G-orbit and the G-action on this orbit is determined by the action on types over
$M_{k-1}$
(see Definition 5.6). Also observe that given G-posets
$Q' \subseteq Q \subseteq P$
, for
$m \in P$
we have
$\operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(m/Q)}) \subseteq \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(m/Q')})$
. We will use these observations repeatedly throughout this proof.
Recall that
$A = V_p \cup W_p$
. For
$a\in V_p$
we define
$t^{\prime }_a = t^{}_a$
, and for
$a \in W_p$
we define
$t^{\prime }_a = a$
. Note that
$t^{\prime }_a \notin S^-$
for all
$a \in A$
, and also note that as p is G-fixed, for all
$g \in G$
we have
$gV_p = V_p$
and
$gW_p = W_p$
. Let
$s_0 \in S$
, and for
$a \in A$
let
$T^{\prime }_a = \{t^{\prime }_a, s^{}_0\}$
. Also, by Lemma 5.9(i) there is
$A_0 \subseteq _{\text {fin\!}} A$
with
$\operatorname {\mathrm {St}}({A_0}) \subseteq \operatorname {\mathrm {St}}({U_0 \cup W_0})$
(apply Lemma 5.9(i) to each element of
$U_0 \cup W_0$
and then take the union of the finite sets obtained). Enumerate
$A_0=\{a_i \mid i < d\}$
.
We define
$M_{l + i}$
for
$i < d$
inductively, together with associated distinguished points
$e_i \in M_{l + i}$
. Let
$i < d$
, and assume we have defined
$M_{l + j}$
and
$e_j \in M_{l + j}$
for
$j < i$
. By Lemma 5.12(i), there is
$Z_i \in \Sigma $
such that
$(T^{\prime }_{a_i} \cup Z_i, \varnothing )$
is an acceptable pair in
$M_{l + i - 1}$
. Let
$M_{l + i} = M_{l + i - 1} \ast (T^{\prime }_{a_i} \cup Z_i, \varnothing )$
, and let
$\tau _i = \tau _{M_{l+i-1}}(T^{\prime }_{a_i} \cup Z_i, \varnothing )$
and
$e_i = e_{\tau _i} \in M_{l + i}$
. So we have
$\tau _i = ((T^{\prime }_{a_i} \cup Z_i)^-, M_{l+i-1} \setminus (T^{\prime }_{a_i} \cup Z_i)^-, \varnothing )$
, where the downward-closure is taken in
$M_{l+i-1}$
. This completes the inductive definition. Note that for each
$i < d$
and for each
$g \in G$
we have that
$ge_i \in S^+$
and that
$ge_i$
is maximal in
$M_{l + i}$
. We therefore also have that
$\{ge_i \mid i < d, g \in G\}$
is an antichain: by Lemma 5.9(v) each G-orbit is an antichain, and given distinct
$ge_i$
,
$g'e_{i'}$
with
$i < i'$
, we see that by maximality of
$g'e_{i'}$
we have
$ge_i \mathbin {\bot } g'e_{i'}$
or
$ge_i < g'e_{i'}$
, and the latter cannot occur by the definition of
$\tau _{i'}$
.
Claim.
$\operatorname {\mathrm {St}}({\tau _i}) = \operatorname {\mathrm {St}}({a_i})$
for all
$i < d$
, and
$(\star $
) holds for all
$l \leq k < l + d$
.
Proof of claim.
First note that it suffices to show
($\star $
) for
$m = e_i$
,
$i < d$
(by the observations at the start of the proof), and also note that
$\operatorname {\mathrm {St}}({e_i}) = \operatorname {\mathrm {St}}({\tau _i})$
. It is immediate by the definition of
$\tau _i$
and the fact that G pointwise-fixes S that
$\operatorname {\mathrm {St}}({a_i}) \subseteq \operatorname {\mathrm {St}}({\tau _i})$
. As
it suffices to show
$\operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_i / M_0)}) \subseteq \operatorname {\mathrm {St}}({a_i})$
. For
$g \in \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_i / M_0)})$
we have
$t^{\prime }_{ga_i} = gt^{\prime }_{a_i} \in (T^{\prime }_{a_i} \cup Z_i)^-$
. As
$t^{\prime }_{ga_i} \notin S^-$
, this implies
$t^{\prime }_{ga_i} \leq t^{\prime }_{a_i}$
. Similarly
$t^{\prime }_{a_i} \leq t^{\prime }_{ga_i}$
, so
$t^{\prime }_{a_i} = t^{\prime }_{ga_i}$
and thus
$ga_i = a_i$
.
Recall that we assumed
$U_0^- \cap S \neq \varnothing $
. By Lemma 5.12(i) there is
$Z_d \in \Sigma $
such that
$(U_0\cup \{e_i \mid i < d\} \cup Z_d, \varnothing )$
is an acceptable pair in
$M_{l + d - 1}$
. Let
$M_{l + d} = M_{l + d - 1} \ast (U_0\cup \{e_i \mid i < d\} \cup Z_d, \varnothing )$
, and let
$\tau _d = \tau _{M_{l + d - 1}}(U_0\cup \{e_i \mid i < d\} \cup Z_d, \varnothing )$
and
$e_d = e_{\tau _d} \in M_{l + d}$
. Note that
$e_d \in S^+$
and
$e_d$
is maximal in
$M_{l + d}$
.
Claim.
$\operatorname {\mathrm {St}}({\tau _d}) = \operatorname {\mathrm {St}}({A_0})$
and
($\star $
) holds for
$k = l + d$
.
Proof of claim.
Let
$g \in \operatorname {\mathrm {St}}({A_0})$
. Then we have that g fixes every element of
$U_0 \cup \{e_i \mid i < d\}\cup Z_d$
pointwise, by the following: we took
$A_0$
with
$\operatorname {\mathrm {St}}({A_0}) \subseteq \operatorname {\mathrm {St}}({U_0 \cup W_0})$
, we have the previous claim and also we have
$Z_d \subseteq S$
. So
$g\tau _d = \tau _d$
.
Let
$g \in \operatorname {\mathrm {St}}({\tau _d}) \subseteq \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_d / M_0 \cup S^+_{l+d-1})}) \subseteq \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_d / (M_{l+d-1} \setminus M_{l-1}))})$
. (Here, note that
$M_{l+d-1} \setminus M_{l-1} = G \cdot \{e_j \mid j < d\} \subseteq S^+_{l+d-1}$
.) Then for each
$i < d$
we have
$ge_i \in (U_0 \cup \{e_j \mid j < d\} \cup Z_d)^-$
, and as
$ge_i \notin (U_0 \cup Z_d)^-$
by maximality and
$G \cdot \{e_j \mid j < d\}$
is an antichain, we must have
$ge_i = e_i$
. So
$g \in \bigcap _{i < d} \operatorname {\mathrm {St}}({e_i}) = \operatorname {\mathrm {St}}({A_0})$
.
As
$e_d$
is maximal in
$M_{l + d}$
and
$e_d> U_0$
, we have that
$(U_0, V_0, \{e_d\} \cup W_0)$
is a valid triple in
$M_{l + d}$
. By Lemma 5.12(i) there is
$Z_{d + 1} \in \Sigma $
such that
$(U_0 \cup Z_{d + 1}, \{e_d\} \cup W_0)$
is an acceptable pair in
$M_{l + d}$
and
$\tau _{d + 1} := \tau _{M_{l + d}}(U_0 \cup Z_{d + 1}, \{e_d\} \cup W_0) \in \langle U_0, V_0, W_0 \rangle $
. Let
$M_{l + d + 1} = M_{l + d} \ast (U_0 \cup Z_{d + 1}, \{e_d\} \cup W_0)$
and
$e_{d + 1} = e_{\tau _{d + 1}}$
. Note that
$e_{d + 1} \in S^+$
.
Claim.
$\operatorname {\mathrm {St}}({\tau _{d + 1}}) = \operatorname {\mathrm {St}}({A_0})$
and
($\star $
) holds for
$k = l + d + 1$
.
Proof of claim.
Let
$g \in \operatorname {\mathrm {St}}({A_0})$
. Then g fixes every element of
$U_0 \cup Z_{d + 1} \cup \{e_d\} \cup W_0$
pointwise, so
$g\tau _{d + 1} = \tau _{d + 1}$
.
Let
$g \in \operatorname {\mathrm {St}}({\tau _{d + 1}}) \subseteq \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_{d + 1} / M_0 \cup S^+_{l + d})}) \subseteq \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(e_{d + 1} / (M_{l + d} \setminus M_{l + d - 1}))})$
. Then
$ge_d \in (\{e_d\} \cup W_0)^+$
. Suppose for a contradiction that
$ge_d^{} \in W_0^+$
. Then
$ge_d> w$
for some
$w \in W_0$
, so
$e_d> g^{-1}w$
and thus
$g^{-1}w \in (U_0\cup \{e_i \mid i < d\} \cup Z_d)^-$
. Recalling that
$U_0^- \cap S \neq \varnothing $
and
$U_0 < W_0$
and S is an antichain, we have
$w \in S^+ \setminus S$
, so
$g^{-1}w \in S^+ \setminus S$
. As
$Z_d \subseteq S$
, we have
$g^{-1}w \notin Z_d^-$
. As
$U_0 < W_0$
, if
$g^{-1}w \in U_0^-$
then
$g^{-1}w < w$
, contradicting Lemma 5.9(v). If
$g^{-1}w \in \{e_i \mid i < d\}^-$
, then
$g^{-1}w < e_i$
for some
$i < d$
, and so
$g^{-1}w \in (T^{\prime }_{a_i} \cup Z_i)^-$
. But
$g^{-1}w \in S^+ \setminus S$
, contradiction.
So
$ge_d^{} \in e_d^+$
. As
$e_d$
is maximal in
$M_{l + d}$
we have
$ge_d = e_d$
. By the previous claim we have
$\operatorname {\mathrm {St}}({e_d}) = \operatorname {\mathrm {St}}({A_0})$
, so
$g \in \operatorname {\mathrm {St}}({A_0})$
.
We therefore see that
$(M_k)_{k < l + d + 2}$
has the required properties: we have
$\operatorname {\mathrm {tp}}(e_{d + 1} / M_{l + d}) = \tau _{d + 1} \in \langle U_0, V_0, W_0 \rangle $
, and
$(\star )$
holds for
$l \leq k < l + d + 2$
.
5.5 The main theorem
We now conclude the proof of our main theorem.
Proof of Theorem 5.1.
By Lemmas 5.12 and 5.14, there is an acceptable chain
$(M_k)_{k < \omega }$
satisfying the following properties:
-
(a) for each $k < \omega $
and for every finite valid triple
$(U_0, V_0, W_0)$
in
$M_k$
, there is
$l> k$
and a point
$m \in M_l$
with
$\operatorname {\mathrm {tp}}(m / M_{l-1}) \in \langle U_0, V_0, W_0 \rangle $
; -
(b) for each $1\hspace{-0.5pt} \leq\hspace{-0.5pt} k\hspace{-0.5pt} <\hspace{-0.5pt} \omega $
and
$m\hspace{-0.5pt} \in\hspace{-0.5pt} S^+_{k}\hspace{-0.5pt} \setminus\hspace{-0.5pt} S^+_{k - 1}$
, we have
$\operatorname {\mathrm {St}}({m})\hspace{-0.5pt} =\hspace{-0.5pt} \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(m / M_0 \cup S^+_{k - 1})})$
; -
(c) for each $k < \omega $
and acceptable pair
$(U_0, W_0)$
of finite subsets of
$M_k$
with
$U_0^- \cap S = \varnothing $
, there is
$l> k$
and
$m \in M_l$
with
$\operatorname {\mathrm {tp}}(m/M_k) = \tau _{M_k}(U_0, W_0)$
.
(Here, there are two types of task to be completed: finding witnesses for each finite valid triple so that conditions (a) and (b) hold, and finding witnesses for each finite acceptable pair to satisfy condition (c). It is immediate how to complete the latter task and satisfy condition (c), using the definition of an acceptable extension. To satisfy conditions (a) and (b): given a finite valid triple
$(U_0, V_0, W_0)$
, if
$U_0^- \cap S = \varnothing $
then we use Lemma 5.12(ii), and if
$U_0^- \cap S \neq \varnothing $
then we use Lemma 5.14. We use a standard bookkeeping argument for the tasks: that is, we schedule the countably many tasks to be completed with a scheduling function similar to that used in the usual proof of Fraïssé’s theorem, found in [Reference Hodges5, Section 7.1]—we omit the details.)
Let
$P = \bigcup _{k < \omega } M_k$
. Condition (a) implies that P is (isomorphic to) the generic poset. By construction, P is a G-poset extending
$G \curvearrowright A$
, so every automorphism of A extends to an automorphism of P. It remains to show uniqueness of extension.
Let
$h \in \operatorname {\mathrm {Aut}}(P)$
with
$h|_A = \operatorname {\mathrm {id}}_A$
. We will show that
$h = \operatorname {\mathrm {id}}_P$
. We do this via the following steps:
-
(i) h fixes S setwise;
-
(ii) h fixes R setwise and fixes T setwise;
-
(iii) h fixes $R \cup T \cup S$
pointwise; -
(iv) h fixes $S^+$
pointwise.
The final claim gives that
$h = \operatorname {\mathrm {id}}_P$
, via Lemma 5.5. We now prove these claims in order.
(i): By Lemma 5.11(i), each point in S is minimal in the set of points in P with type q over A. We now show that every point that is minimal in the set of points in P with type q over A is an element of S. Let
$m \in P$
be such a point and suppose for a contradiction that
$m \notin S$
. Then
$m \notin S^- \cup S^+$
by minimality of each point of S and by the minimality of m. So
$m \mathbin {\bot } S$
. Let k be such that
$m \in M_k \setminus M_{k-1}$
and let
$(U,W)$
be an acceptable pair in
$M_{k-1}$
with
$\operatorname {\mathrm {tp}}(m / M_{k - 1}) = \tau (U,W)$
. As
$m \mathbin {\bot } S$
we have
$U \cap S = W \cap S = \varnothing $
, so U and W are finite. Also
$m \mathbin {\bot } S$
implies
$U^- \cap S = \varnothing $
, and in addition
$m^+ \cap S = W^+ \cap S$
, so
$(U, W \cup \{m\})$
is an acceptable pair in
$M_k$
. Thus by condition (c) of our acceptable chain there is
$n \in P \setminus M_k$
satisfying
$\operatorname {\mathrm {tp}}(n / M_k) = \tau _{M_k}(U, W \cup \{m\})$
. Then
$n^- \cap A = U^- \cap A = m^- \cap A$
and
$n^+ \cap A = (W^+ \cap A) \cup (m^+ \cap A) = m^+ \cap A$
. So
$\operatorname {\mathrm {tp}}(n/A) = q$
, but
$n<m$
, so m is not minimal, contradiction.
So S is exactly the set of minimal points of the set of points in P with type q over A. As the set of points in P with type q over A is fixed setwise by h, we have that S is fixed setwise by h.
(ii): We have that h fixes
$R \cup T$
setwise immediately by the previous claim and Lemma 5.11(ii). As each element of R is related to some element of S and each element of T is not related to any element of S, we have that h fixes R setwise and fixes T setwise.
(iii): Each point in T has a different type over A, so
$h|_T = \operatorname {\mathrm {id}}_T$
. As h fixes
$R \cup S$
as a set and the partial order on
$R \cup S$
is rigid, we have
$h|_{R \cup S} = \operatorname {\mathrm {id}}_{R \cup S}$
.
(iv): We show by induction that h fixes
$S^+_{k}$
pointwise for
$k < \omega $
. As
$S^+_{0} = S$
, the case
$k = 0$
is given by the previous claim. Suppose that h fixes
$S^+_{k - 1}$
pointwise. Let
$m \in S^+_{k} \setminus S^+_{k - 1}$
. As
$\operatorname {\mathrm {tp}}(m/S) = \operatorname {\mathrm {tp}}(h(m)/S)$
, in particular we have
$m^- \cap S = h(m)^- \cap S$
, and so by Lemma 5.9(vi) we have that
$h(m) = gm$
for some
$g \in G$
. By the induction assumption and the previous claim we have
$h|_{M_0 \,\cup \, S^+_{k - 1}} = \operatorname {\mathrm {id}}_{M_0 \,\cup \, S^+_{k - 1}}$
, so
$gm$
and m have the same type over
$M_0 \cup S^+_{k - 1}$
. So
$g \in \operatorname {\mathrm {St}}({\operatorname {\mathrm {tp}}(m / M_0 \,\cup \, S^+_{k - 1})})$
, and by condition (b) in our construction of P, we have
$g \in \operatorname {\mathrm {St}}(m)$
. So
$h(m) = gm = m$
.
Acknowledgments
We would like to thank Alessandro Codenotti and Aristotelis Panagiotopoulos for discussions in the joint project with the second and third authors on generic embeddings into Fraïssé structures, which were a useful tool in early attempts to prove the main result (though they do not appear in this article). We would also like to thank Adam Bartoš, David Bradley-Williams, and Wiesław Kubiś for initial discussions, and we would like to thank Itay Kaplan for his talk in Münster in September 2023 on the automorphism group of the Rado meet-tree, which indirectly sparked our interest in universality of automorphism groups. Finally, we would like to thank the anonymous referee, whose thorough review of the article improved the presentation.
Funding
A.K. and R.S. were funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy EXC 2044–390685587, Mathematics Münster: Dynamics–Geometry–Structure and CRC 1442 Geometry: Deformations and Rigidity. R.S. was additionally funded by Project 24-12591M of the Czech Science Foundation (GAČR).
