1 Introduction
A countable structure M has a generic automorphism if its automorphism group has a comeagre conjugacy class. This is an important property which has certain implications on the automorphism group G (for example, every element is a commutator, G cannot be written as a proper free product with amalgamation and more; see [Reference Macpherson13, Proposition 4.2.12]).
A much stronger property is having ample generics, which means that for all
$n\in \mathbf N$
,
$ G $
has a generic tuple of length
$ n $
or, in other words,
$ G^{n} $
contains a comeagre orbit under the action of
$ G $
by diagonal conjugation. Having ample generics implies in particular the small index property [Reference Macpherson13, Theorem 5.2.5]—which is desirable because, for instance, it implies that if M is
$\aleph _0$
-categorical, then the automorphism group
$ G $
(as a pure group) determines
$ M $
up to bi-interpretability (among all countable
$\aleph _0$
-categorical structures; see, e.g., [Reference Macpherson13, Proposition 5.2.2]).
This article started as an attempt to find a counterexample to a question of Dugald Macpherson (also appearing in the third author’s thesis [Reference Siniora16, Chapter 7, Question 10]) which asks whether there is an ultrahomogeneous
$ \aleph _0 $
-categorical structure admitting ample generics with the strict order property (i.e., defining a partial order with infinite chains). Note that the answer to this question in general is negative (since [Reference Kwiatkowska11] shows that the countable atomless Boolean algebra has ample generics), so it seems that the question should be investigated under the NIP assumption. The obvious candidate,
$ ({\mathbf Q},<) $
, fails: by the works of Hodkinson (unpublished), Truss [Reference Truss18], and the third author (who gave a new proof of this result) [Reference Siniora16, Lemma 6.1.1], we know that
$ \operatorname {\mathrm {Aut}}({\mathbf Q},<) $
has no generic pair of automorphisms (although
$ \operatorname {\mathrm {Aut}}({\mathbf Q},<) $
does have a generic automorphism by [Reference Kuske and Truss10, Reference Truss17]).
Meet-trees are partial orders in which for every element
$ a $
, the set of elements below it is linearly ordered, equipped with a meet function (see Definition 2.11). They are often used as a basis for interesting examples in the realm of NIP unstable theories (in the sense of Shelah’s classification theory). For example, in [Reference Kaplan and Shelah6, Reference Kaplan and Shelah7], trees were the basis for a counterexample to an old conjecture of Shelah regarding the existence of indiscernibles in NIP. See also [Reference Simon14, Section 2.3.1]. Finite meet-trees form a Fraïssé class and thus there is a countable universal ultrahomogeneous and
$ \aleph _0 $
-categorical meet-tree
$ \mathbf T $
which we call the universal countable dense meet-tree. We therefore thought that it would be interesting to understand the automorphism group of
$ \mathbf T $
with respect to generic automorphisms.
Our main result is:
Main Theorem. Let
$ \mathbf T $
be the universal countable dense meet-tree. Then its automorphism group
$ G= \operatorname {\mathrm {Aut}}(\mathbf T) $
has a generic automorphism, but not a generic pair of automorphisms.
Note that the Main Theorem implies that in particular,
$ \operatorname {\mathrm {Aut}}(\mathbf T)$
does not have ample generics—which, as was mentioned, would imply having the small index property. However, it follows from [Reference Droste, Holland and Macpherson2, Theorem 4.1] that
$ \operatorname {\mathrm {Aut}}(\mathbf T)$
(as well as the analogues for meet-trees of bounded arity, for which we also show the non-existence of a generic pair) does have the small index property.
We use a criterion for having a generic automorphism that was established by Truss [Reference Truss17, Theorem 2.1] and then improved to a characterisation independently by Ivanov [Reference Ivanov5, Theorem 1.2] and Kechris and Rosendal [Reference Kechris and Rosendal9, Theorem 6.2]. Namely, to show that an ultrahomogeneous structure
$ M $
with age
$ \mathcal K $
has a generic
$ n $
-tuple of automorphisms, one needs to prove that the class
$ \mathcal K^{n} $
of pairs
$ (A,\bar {p}) $
such that
$ A\in \mathcal K $
and
$ \bar {p} $
is an n-tuple of partial automorphisms of
$ A $
, has the joint embedding property (JEP) and a version of the amalgamation property which we call the existential amalgamation property (EAP)Footnote
1
(see Fact 2.9).
To show EAP in the case of finite meet-trees, we find a cofinal subclass of
$ \mathcal K^1 $
consisting of amalgamation bases (which is the aforementioned criterion from [Reference Truss17]). Starting with some member
$ (A,p_A) $
, we extend
$ p_A $
to a partial automorphism
$ p_B $
on a bigger domain
$ B $
in such a way that
$(B,p_B)$
is an amalgamation base in
$ \mathcal K^1 $
. The idea in finding
$ p_B $
is model-theoretic: instead of giving a precise description of
$ p_B $
, we define it as being “pseudo existentially closed” in the sense that, roughly, any behaviour that happens in some extension of
$ p_B $
is already witnessed in
$ p_B $
itself (see Definition 6.3). This method eliminates the need for a careful analysis of the interactions between multiple orbits of
$p_B$
that we might otherwise need.
Finally let us remark that while we did not check all the details, our methods seem to recover a proof of existence of generics for
$(\mathbf Q,<)$
(see Remark 6.13), and also provide a similar result for lexicographically ordered meet-trees (see Remark 6.14). They could also be helpful in finding generics in the case of meet-trees of bounded arity (see Remark 6.12; see also Corollary 3.8 for the non-existence of generic pairs in this case).
The paper is organized as follows. In Section 2 we recall Fraïssé classes and formally define EAP. We then discuss trees and give their basic properties. In Section 3 we prove that the automorphism group of the countable dense tree does not have a generic pair of automorphisms (in fact we give a more general statement, also about trees with bounded arity). In Section 4 we follow [Reference Kuske and Truss10] and discuss determined finite partial automorphisms in an abstract context, giving a sufficient condition under which they form a class of amalgamation bases. In Section 5 we discuss the possible orbits of partial automorphisms in meet-trees. Finally, in Section 6 we prove that the class of determined partial automorphisms of meet-trees is indeed cofinal, thus proving EAP for the class of finite meet-trees.
We end the introduction with some open questions.
Our main results are similar to the ones in [Reference Kuske and Truss10, Reference Truss18] regarding
$ ({\mathbf Q},<) $
and the universal partial order (although it is not known if the universal partial order has a generic pair); more recently, a new preprint [Reference Kwiatkowska and Malicki12] appeared giving similar results on two different structures (the universal ordered boron tree—roughly speaking, a graph theoretic binary tree with a lexicographical order—and the universal ordered poset). The latter’s motivation came from a different yet related question of finding an ultrahomogeneous ordered structure whose automorphism group has ample generics and is extremely amenable (in other words, by [Reference Kechris, Pestov and Todorcevic8], its age has the Ramsey property).
Even more recently, a preprint [Reference Duchesne3] appeared, which analyses the homeomorphism groups of the so-called Ważewski dendrites, in particular showing the analogue of the Main Theorem for the group of homeomorphisms of the Ważewski dendrite
$D_{\{\infty \}}$
(into which
$ \operatorname {\mathrm {Aut}}(\mathbf T)$
naturally embeds as a meagre subgroup, namely as the stabiliser of an end point). We were not aware of this work. By private communication with Duchesne, it appears that though it is not written explicitly there, our result follows from the main theorem there and vice versa. Both papers use the aforementioned criterion for establishing the existence of a generic automorphism, but the methods of finding amalgamation bases are different. (Interestingly, from the point of view of [Reference Duchesne3], meet-trees with bounded arity are analogues to dendrites with bounded branching. The latter do not have a dense conjugacy class according to [Reference Duchesne3, Proposition 1.1], while the former do, see also Remark 6.12.)
Question 1.1. What is the correct generalization of all these results?
Model theoretically, it seems appealing to consider the situation in general NIP
$ \aleph _0 $
-categorical structures with perhaps some further restrictions, as was done in [Reference Simon15]. This situation does not quite generalize ours since trees are not “rank 1” in the sense defined there, and the universal partial order is not NIP.
Another natural question that comes to mind is the following. In all the examples known to us, if EAP occurs for
$ \mathcal K^{1} $
then in fact there is a cofinal class of amalgamation bases (a property we denote by CAP, see Definition 2.6).
Question 1.2. Is it always the case that EAP is equivalent to CAP for the class
$ \mathcal K^{1} $
(where
$ \mathcal K $
is any Fraïssé class)?
We are not sure what the situation is with trees of bounded arity; it may be a candidate for a counterexample—see Remark 6.12.
Since we know that the generic automorphism exists, it seems natural to ask how complicated it is.
Question 1.3. What can be said, model theoretically—in terms of classification theory—about the structure
$ (\mathbf T,\sigma ) $
, where
$ \sigma $
is a generic automorphism?
2 Preliminaries
2.1 Fraïssé classes and limits
We briefly recall the basic notions related to Fraïssé classes. See [Reference Hodges4, Chapter 6] for more exposition. In contrast to [Reference Hodges4], it will be convenient for us to consider classes of structures with partial functions. Formally, they can be thought of as relations (via their graphs), so this is only a superficial change.
Definition 2.1. Let
$\mathcal K$
be a class of first order structures (possibly with some partial functions), closed under isomorphisms.
-
• We say that
$\mathcal K$
has the hereditary property (HP), if given any
$A\in \mathcal K$
and substructure
$B\subseteq A$
, we have
$B\in \mathcal K$
. -
• We say that
$\mathcal K$
has the joint embedding property (JEP) if given any
$A_1,A_2\in \mathcal K$
, there is some
$B\in \mathcal K$
such that both
$A_1$
and
$A_2$
can be embedded in B. -
• We say that
$A\in \mathcal K$
is an amalgamation base (in
$\mathcal K$
) if given any
$B_1,B_2\in \mathcal K$
and embeddings
$i_j\colon A\to B_j$
for
$j=1,2$
, there is some
$C\in \mathcal K$
and embeddings
$i^{\prime }_j\colon B_j\to C$
for
$j=1,2$
such that
$i^{\prime }_1\circ i_1=i^{\prime }_2\circ i_2$
. -
• We say that
$\mathcal K$
has the amalgamation property (AP) if every
$A\in \mathcal K$
is an amalgamation base in
$\mathcal K$
. -
• We say that
$\mathcal K$
is uniformly locally finite if given any
$n\in \mathbf N$
, there is an upper bound on the size of an n-generated element of
$\mathcal K$
. -
• A Fraïssé class is a class of finitely generated structures which is closed under isomorphisms, and has HP, JEP, and AP.
-
• The age
$ \operatorname {\mathrm {Age}}(M)$
of a first-order structure M is the class of all (isomorphism types of) finitely-generated substructures of M.
${\lozenge }$
We recall the notion of a partial automorphism (which is fundamental for this paper).
Definition 2.2. Given a first order structure M, a partial function
$M\to M$
is called a partial automorphism if it preserves the quantifier-free types over the empty set.
${\lozenge }$
Fact 2.3. If
$\mathcal K$
is a Fraïssé class, then there is a unique
$($
up to isomorphism
$)$
, countable structure
$\mathbf K$
whose age is exactly
$\mathcal K$
and which is ultrahomogeneous
$($
i.e., every finite partial automorphism of
$\mathbf {K}$
extends to an automorphism
$)$
.
Furthermore, if
$\mathcal K$
is uniformly locally finite, then the theory of
$\mathbf K$
has quantifier elimination and
$($
if
$\mathbf K$
is infinite
$)$
is
$\aleph _0$
-categorical.
Proof This is classical; see for instance [Reference Hodges4, Theorem 6.1.2] and [Reference Hodges4, Theorem 6.4.1].⊣
Definition 2.4 The structure
$\mathbf K$
as in Fact 2.3 is called the (Fraïssé) limit of
$\mathcal K$
.
${\lozenge }$
2.2 Partial automorphisms, generic automorphisms
If M is a countable first-order structure, then
$ \operatorname {\mathrm {Aut}}(M)$
has a natural Polish group structure (with the pointwise convergence topology), and we can use descriptive set theory to study it. The notion of a generic is due to [Reference Truss17] and [Reference Kechris and Rosendal9] (for tuples).
Definition 2.5.
-
• An element
$\sigma \in \operatorname {\mathrm {Aut}}(M)$
is called generic if its conjugacy class is comeagre in
$ \operatorname {\mathrm {Aut}}(M)$
(i.e., it contains a dense
$G_\delta $
set). -
• More generally, a tuple
$(\sigma _1,\ldots ,\sigma _n)\in \operatorname {\mathrm {Aut}}(M)$
is generic if its diagonal conjugacy class (i.e., the orbit under the action
$ \operatorname {\mathrm {Aut}}(M)$
on
$ \operatorname {\mathrm {Aut}}(M)^n$
by coordinatewise conjugation) is comeagre. -
• We say that
$ \operatorname {\mathrm {Aut}}(M)$
has ample generics if it has generic tuples of elements of arbitrary length.
${\lozenge }$
The definition of EAP below is due to [Reference Ivanov5] (where it is called almost amalgamation property). It is also used in [Reference Kechris and Rosendal9] (where it is called weak amalgamation property).
Definition 2.6. Fix a class
$\mathcal K$
of first order structures, closed under isomorphisms.
-
• We say that
$\mathcal K$
has EAP (existential amalgamation property) if for every
$A\in \mathcal K$
, there is some
$B\in \mathcal K$
and an embedding
$i_{AB}\colon A\to B$
such that for any embeddings
$i_{BC}\colon B\to C$
,
$i_{BD}\colon B\to D$
(with
$C,D\in \mathcal K$
), there are embeddings
$i_{CE}\colon C\to E$
and
$i_{DE}\colon D\to E$
(where
$E\in \mathcal K$
) such that
$i_{CE}\circ i_{BC}\circ i_{AB}=i_{DE}\circ i_{BD}\circ i_{AB}$
. -
• We say that
$\mathcal K$
has CAP (cofinal amalgamation property) if we can choose the B such that
$i_{CE}\circ i_{BC}=i_{DE}\circ i_{BD}$
(i.e., if
$\mathcal K$
has a cofinal subclass of amalgamation bases).
${\lozenge }$
Remark 2.7. If
$\mathcal K$
has CAP, it has EAP.
${\lozenge }$
Definition 2.8. Suppose that
$\mathcal K$
is a Fraïssé class. Let
$\mathcal K^n$
be the class of pairs
$(A,\bar {p})$
where
$A\in \mathcal K$
and
$\bar {p}=(p_i)_{i<n}$
is an n-tuple of partial automorphisms of A.Footnote
2
Fact 2.9. Fix any
$n\in \mathbf N$
and
$\mathcal K$
is a Fraïssé class with limit
$\mathbf K$
, then the following are equivalent
$:$
-
•
$ \operatorname {\mathrm {Aut}}(\mathbf K)$
has a generic n-tuple, -
•
$\mathcal K^n$
has JEP and EAP.
Proof This is [Reference Kechris and Rosendal9, Theorem 6.2]. Under the additional assumption that
$\mathbf K$
is
$\aleph _0$
-categorical (which includes our applications), this is a special case of [Reference Ivanov5, Theorem 1.2].⊣
Corollary 2.10. If
$\mathcal K$
is a Fraïssé class with limit
$\mathbf K$
and
$\mathcal K^n$
has JEP and CAP, then
$\mathbf K$
has a generic n-tuple of automorphisms.
Proof Immediate by Remark 2.7 and Fact 2.9. (For
$n=1$
this is essentially [Reference Truss17, Theorem 2.1].)⊣
2.3 Trees
Definition 2.11.
-
• A tree is a partially ordered set
$(A, \leq )$
which is semilinear (that is, for every
$a_0\in A$
, the set
$A_{\leq a_0}=\{a\in A\mid a\leq a_0 \}$
is linearly ordered) and such that every pair of elements has a common lower bound. -
• A meet-tree (or
$\mathbin {\wedge }$
-tree)
$(A, \leq , \mathbin {\wedge })$
is a tree which is also a lower semilattice, i.e., a tree
$(A,\leq )$
together with a binary (meet or infimum) function
${\mathbin {\wedge }}:A^2\to A$
such that for every
$a,b \in A$
,
$a\mathbin {\wedge } b$
is the largest element of
$A_{\leq a}\cap A_{\leq b}$
.
${\lozenge }$
Remark 2.12. If
$(A,\leq )$
is a tree with the property that every pair has an infimum, then there is a unique way to expand it to a meet-tree. In particular, every finite tree has a unique meet-tree structure. However, not every embedding of finite trees yields an embedding of the resulting meet-trees.
${\lozenge }$
Remark 2.13. The
$\mathbin {\wedge }$
operation is associative, commutative, and idempotent.
${\lozenge }$
Definition 2.14. Given a tree T, the arity of T is the maximal size of a set
$A\subseteq T$
of pairwise incomparable elements such that if
$a_1,a_2,a_3\in A$
are distinct and
$b\in T$
is such that
$b<a_1$
and
$b<a_2$
, then
$b<a_3$
(or
$\infty $
if there is no finite bound).
Remark 2.15. If T is a meet-tree, arity can be equivalently defined in the following way: we say that T is k-ary if k is the maximal size of a subset
$A\subseteq T$
such that all pairs have the same meet, which is not equal to any of them. Note that this definition shows that being at most k-ary is an universal property in the language of meet-trees (it is not hard to see that it is not an universal property in the pure order language).
${\lozenge }$
Fact 2.16. The class of all finite meet-trees is a Fraïssé class
$($
in the language of meet-trees
$)$
. Given any positive integer k, the class of all finite k-ary meet-trees is a Fraïssé class
$($
in the language of meet-trees
$)$
.
Consequently, there is a countable generic meet-tree,
$\mathbf T$
, and for every k there is a countable generic k-ary meet-tree,
$\mathbf T_k$
.
$\mathbf T$
and each
$\mathbf T_k$
are
$\aleph _0$
-categorical, ultrahomogeneous and have elimination of quantifiers.
Proof The first part is straightforward. The second part follows from Fact 2.3.⊣
(Notice that in particular, a
$1$
-ary meet-tree is simply linear, and
$\mathbf T_1$
is (interdefinable with) the universal linear ordering, isomorphic to
$(\mathbf Q,\leq )$
.)
We will use the notation
$\mathbf T$
and
$\mathbf T_k$
throughout the paper.
Remark 2.17. The class of all finite trees (in the pure order language) is not a Fraïssé class—it does not have the amalgamation property; it does, however, have a model companion: there is a unique countable existentially closed tree (in the pure order language). It is an
$\aleph _0$
-categorical binary tree, but in contrast to
$\mathbf T_2$
, which is a meet-tree, no two incomparable elements have a meet. (See [Reference Bodirsky, Bradley-Williams, Pinsker and Pongrácz1] for more details.) It might be interesting to ask whether it has a generic automorphism, but the methods based on Fact 2.9 used in this paper do not seem to apply directly.
${\lozenge }$
Remark 2.18. Another approach to trees is by graph theory: we can identify every finite tree with an acyclic directed graph, but the Fraïssé limits of classes of finite trees in this language will be quite different (for instance, the “order” on each branch will not be dense). In [Reference Kwiatkowska and Malicki12], the authors study the existence of generic automorphisms in this context.
${\lozenge }$
The following simple observation, reminiscent of the ultrametric triangle inequality, will be immensely useful in the rest of this paper.
Fact 2.19. Let
$a,b,c$
be elements of a meet-tree T. Then
$:$
-
•
$a\mathbin {\wedge } b\mathbin {\wedge } c=a\mathbin {\wedge } b$
or
$a\mathbin {\wedge } b\mathbin {\wedge } c=a\mathbin {\wedge } c$
, -
• if
$a\mathbin {\wedge } b>a\mathbin {\wedge } c$
, then
$a\mathbin {\wedge } c=b\mathbin {\wedge } c$
, -
• if
$a\mathbin {\wedge } b\geq a\mathbin {\wedge } c$
, then
$a\mathbin {\wedge } c\leq b\mathbin {\wedge } c$
.
Proof The proof is straightforward (using semilinearity).⊣
Note that the first bullet in Fact 2.19 says in particular that if T is a meet-tree and
$A\subseteq T$
, then the substructure of T generated by A is exactly the set of meets of pairs of elements of A.
Definition 2.20. Given a partial order
$(P,\leq )$
, and an
$A\subseteq P$
,
-
• a (lower) cut in A is a downwards closed, (upwards) directed subset of A (i.e., a
$C\subseteq A$
such that for any
$c\in C$
and
$a\in A$
, if
$a\leq c$
, then
$a\in C$
, and for any
$c_1,c_2\in C$
, there is some
$c\in C$
such that
$c\geq c_1,c_2$
). -
• an order type over A is simply a complete quantifier-free type over A in P, in the pure order language (with equality).
${\lozenge }$
Remark 2.21. Fix a partial order
$(P,\leq )$
(possibly with some additional structure) and a subset
$A\subseteq P$
.
Given an order type p over A, we have two corresponding cuts in A, namely
$p_{\geq }:=\{a\in A\mid p\vdash x\geq a \}$
and
$p_{>}:=\{a\in A\mid p\vdash x>a \}$
. The two are equal if and only if p is not realised in A. If P is linear, then the two cuts uniquely determine p, but in general, it is not true.
Conversely, given a nonempty cut
$C\subseteq A$
, there is an order type p over A such that
$p_{\geq }=C$
.
${\lozenge }$
Definition 2.22. Given any
$b\in P$
, by the order type of b over A,
$ \operatorname {\mathrm {otp}}(b/A)$
, we mean simply the quantifier-free type of b over A in the order language, and by the cut of b in A we mean simply the cut
$\{a\in A\mid b\geq a \}$
(which is the same as
$ \operatorname {\mathrm {otp}}(b/A)_{\geq }$
in the notation of Remark 2.21).
${\lozenge }$
Remark 2.23. In a tree, a directed set is linear, so a cut is simply a downwards closed chain.
${\lozenge }$
Remark 2.24. Note that for any poset
$(P,\leq )$
, the cuts in P are ordered simply by inclusion. If we denote by
$\hat P$
the set of all cuts in P, partially ordered by inclusion, it is easy to see that:
-
• P naturally embeds into
$\hat P$
(where each element is identified with its cut in P); -
•
$\hat P$
is complete in the sense that every directed subset of
$\hat P$
has a supremum (namely, the union); -
• if P is a tree, then so is
$\hat P$
, and moreover,
$\hat P$
has a canonical meet-tree structure, with the meet given by intersection; -
• if
$(P,\leq ,\mathbin {\wedge })$
is a meet-tree, then
$(P,\leq ,\mathbin {\wedge })$
is a substructure of
$(\hat P,\subseteq ,\cap )$
.
${\lozenge }$
The following fact appears to be folklore.
Fact 2.25. Let B be a meet-tree,
$b\in B$
, and
$A\subseteq B$
a finite substructure
$($
in the language of meet-trees
$)$
. Put
$b' = \max \{x \mathbin {\wedge } b : x\in A\}$
, and let
$a\in A$
be such that
$a\geq b'$
. Then the quantifier-free type
$ \operatorname {\mathrm {qftp}}(b/A)$
is determined by knowing whether
$b=b'$
or
$b'<b$
, the element a, and the order type of
$b'$
over
$A_{\leq a}$
.
$($
In particular, if B has quantifier elimination
$($
for instance, if
$B=\mathbf T$
or
$B=\mathbf T_k$
for some
$k>0$
, in the sense of Fact 2.16
$)$
, this also determines
$ \operatorname {\mathrm {tp}}(b/A)$
.
$)$
Proof The proof is left as an exercise to the reader.⊣
Corollary 2.26. Fix a meet-tree T, and arbitrary
$a_1,a_2\in T$
, as well as a finite
$B\subseteq T$
. Then if
$a_1\mathbin {\wedge } a_2>\max _{b\in B}b\mathbin {\wedge } a_1$
, then
$ \operatorname {\mathrm {qftp}}(a_1/B)= \operatorname {\mathrm {qftp}}(a_2/B)$
(in particular, if
$T=\mathbf T$
, then
$ \operatorname {\mathrm {tp}}(a_1/B)= \operatorname {\mathrm {tp}}(a_2/B)$
).
Proof Note that the assumption immediately implies that
$a_1,a_2\neq \max _{b\in B}b\mathbin {\wedge } a_1$
, so by Fact 2.25 it is enough to show that
$\max _{b\in B}b\mathbin {\wedge } a_2=\max _{b\in B}b\mathbin {\wedge } a_1$
. But the assumption tells us immediately that for every
$b\in B$
we have
$b\mathbin {\wedge } a_1<a_1\mathbin {\wedge } a_2$
, so by Fact 2.19,
$b\mathbin {\wedge } a_1=b\mathbin {\wedge } a_2$
, which completes the proof.⊣
3 There is no generic pair
In this section, we will use Fact 2.9 to show that the countable generic meet-trees
$\mathbf T$
and
$\mathbf T_k$
do not admit generic pairs of automorphisms.
Definition 3.1.
-
• Given a pair
$(g_1,g_2)$
of partial functions, we say that
$(g_1^{\prime },g_2^{\prime })$
is an extension of
$(g_1,g_2)$
if
$g_1^{\prime },g_2^{\prime }$
are partial functions such that
$g_1\subseteq g_1^{\prime }$
and
$g_2\subseteq g_2^{\prime }$
. -
• Given two pairs
$(g_1^{\prime },g_2^{\prime })$
,
$(g_1^{\prime \prime },g_2^{\prime \prime })$
of partial automorphisms of a partially ordered set P and a point
$a\in P$
, we say that they are irreconcilable over a if there is no partial ordering Q and partial automorphisms
$f_1,f_2$
of Q such that
$(P,g_1^{\prime },g_2^{\prime },a),(P,g_1^{\prime \prime },g_2^{\prime \prime },a)\hookrightarrow (Q,f_1,f_2,b)$
for some
$b\in Q$
.
${\lozenge }$
Remark 3.2. If
$(g_1^{\prime },g_2^{\prime }), (g_1^{\prime \prime },g_2^{\prime \prime }),(g_1^{\prime \prime \prime },g_2^{\prime \prime \prime })$
are pairs of partial automorphisms of a poset P such that
$(g_1^{\prime },g_2^{\prime })$
and
$(g_1^{\prime \prime },g_2^{\prime \prime })$
are irreconcilable over
$a\in P$
, while
$(g_1^{\prime \prime \prime },g_2^{\prime \prime \prime })$
extends
$(g_1^{\prime },g_2^{\prime })$
, then it is easy to see that:
-
•
$(g_1^{\prime \prime \prime },g_2^{\prime \prime \prime })$
and
$(g_1^{\prime \prime },g_2^{\prime \prime })$
are irreconcilable over a, -
• there is no
$f\in \operatorname {\mathrm {Aut}}(P)$
fixing a, such that
$g_1^{\prime }\cup fg_1^{\prime \prime }f^{-1}$
and
$g_2^{\prime }\cup fg_2^{\prime \prime }f^{-1}$
are partial automorphisms.
${\lozenge }$
Proposition 3.3. Suppose L is a dense linear order, unbounded from below. Suppose g is a finite partial automorphism of L, and
$a,b\in L$
are such that
$b\leq g(a)\leq a$
. Then there are
$d_1,d_2\in L$
such that
$g\cup \{(d_1,b),(b,d_2)\}$
is a partial automorphism.
Proof We may assume without loss of generality that L is countable (by replacing it with a countable dense subset containing b, the range and the domain of g). In this case, there is some
$K\supseteq L$
, countable, totally ordered without endpoints; since L is dense without lower bound, we may assume that for every
$k\in K\setminus L$
, we have
$k>a$
.
Countable dense orderings without endpoints are ultrahomogeneous, so g can be extended to some
$f\in \operatorname {\mathrm {Aut}}(K)$
. Put
$d_1:=f^{-1}(b),d_2:=f(b)$
. Now, we have
$b\leq a$
, so
$d_2=f(b)\leq f(a)=g(a)\leq a$
, so
$d_2\in L$
. On the other hand,
$b\leq g(a)=f(a)$
, so
$d_1=f^{-1}(b)\leq f^{-1}(f(a))=a$
, so
$d_1\in L$
. Since f is a partial automorphism, so is
$g\cup \{(d_1,b),(b,d_2)\}\subseteq f$
, so we are done.⊣
The following fact is essentially [Reference Siniora16, Lemma 6.1.1], but we slightly strengthen the conclusion using Proposition 3.3, and we give a more detailed proof.
Proposition 3.4. Let
$(L,<)$
be a dense linear order, unbounded from below, and take some
$a\in L$
. Let
$q_1,q_2$
be finite partial automorphisms of L such that
${q_1(a),q_2(a)<a}$
. Then
$(q_1,q_2)$
admits two irreconcilable extensions
$(q_1^{\prime },q_2^{\prime })$
and
$(q_1^{\prime \prime },q_2^{\prime \prime })$
to pairs of finite partial automorphisms of L.
Proof Given a finite partial automorphism g of L and an element
$b_0\in L$
, put
$C(b_0,g):=\#\{b\in \operatorname {\mathrm {dom}}(g)\mid b\leq b_0 \}+ \#\{b\in \operatorname {\mathrm {range}}(g)\mid b\leq b_0 \}$
. Note that
$C(b_0,g)$
is always a non-negative integer; note also that C is monotone in
$b_0$
: if
$b_0^{\prime }\leq b_0$
, then
$C(b_0^{\prime },g)\leq C(b_0,g)$
. Given a pair
$(g_1,g_2)$
of finite partial automorphisms, denote by
$m(g_1,g_2)$
the minimal element of the
$\langle g_1,g_2\rangle $
-orbit of a (i.e., the smallest element that can be obtained from a by successive applications of
$g_1,g_2,g_1^{-1},g_2^{-1}$
). Write
$C_m(g_1,g_2)$
for
$C(m(g_1,g_2),g_1)+C(m(g_1,g_2),g_2)$
.
Call a pair
$(g_1,g_2)$
minimal if
$C_m(g_1,g_2)$
is minimal among its extensions. We may assume without loss of generality that
$(q_1,q_2)$
is minimal (otherwise, we can simply extend it).
Write c for
$m(q_1,q_2)$
and B for the union of domains and ranges of
$q_1$
and
$q_2$
. Clearly,
$c\in B$
. Furthermore,
$c\leq q_1(a),q_2(a)$
, so it satisfies the assumptions of Proposition 3.3 for both
$q_1$
and
$q_2$
.
We claim that c is in only one of
$ \operatorname {\mathrm {dom}}(q_1), \operatorname {\mathrm {dom}}(q_2), \operatorname {\mathrm {range}}(q_1), \operatorname {\mathrm {range}}(q_2)$
. We will show that
$c\notin \operatorname {\mathrm {range}}(q_1)\cap \operatorname {\mathrm {range}}(q_2)$
(the other cases are either analogous or easy to see). Suppose this is not the case. Since c is minimal in its orbit, either
$q_1^{-1}(c)>c$
or
$q_2^{-1}(c)>c$
(otherwise, if
$q_1(c)=q_2(c)=c$
, the orbit of c would have only one point, but we know that
$a>c$
is in the same orbit). Suppose without loss of generality that the former holds. Let
$d\in L$
be such that
$g_1:=q_1\cup \{(c,d)\}$
is a partial automorphism (which we have by Proposition 3.3). Then, since
$c<q_1^{-1}(c)$
, we have
$d<c$
. It is easy to see that
$C(d,q_2)\leq C(c,q_2)-1$
(we do not count c on the left-hand side) and
$$\begin{align*}C(d,g_1)\leq C(d,q_1)+1\leq C(c,q_1)-1+1=C(c,q_1).\end{align*}$$
(The first inequality is because the only extra element we count in
$C(d,g_1)$
is d, and the second one is because c is counted in
$C(c,q_1)$
, but not in
$C(d,q_1)$
.) Since
$m(g_1,q_2)\leq d$
, we conclude that
$C_m(g_1,q_2)<C(c,q_1)+C(c,q_2)$
, contradicting minimality of
$(q_1,q_2)$
.
From now, we consider the case when
$c\in \operatorname {\mathrm {range}}(q_1)$
(the other cases are analogous), whence
$c\notin \operatorname {\mathrm {dom}}(q_2)\cup \operatorname {\mathrm {range}}(q_2)$
.
Let
$c^+>c$
be such that
$(c,c^+]\cap B=\emptyset $
, and let
$c^-<c$
be such that
$[c^-,c)\cap B=\emptyset $
. Note that
$c^+$
exists by density and the fact that
$a>c$
, while
$c^-$
exists by density and the assumption that L has no lower bound. We claim that
$q_2^{\prime }:=q_2\cup \{(c,c^+)\}$
and
$q_2^{\prime \prime }:=q_2\cup \{(c,c^-)\}$
are both partial automorphisms of L. Then if we put
$q_1^{\prime }=q_1^{\prime \prime }=q_1$
, then clearly
$(q_1^{\prime },q_2^{\prime })$
and
$(q_1^{\prime \prime },q_2^{\prime \prime })$
will be irreconcilable over a. Note that since
$c\notin \operatorname {\mathrm {dom}}(q_2)$
, we already know that
$q_2^{\prime }$
and
$q_2^{\prime \prime }$
are well-defined partial functions, and by choice of
$c^-$
and
$c^+$
, they are both injective, so it is enough to show that they preserve the (non-strict) order.
Take any
$b\geq c$
,
$b\in \operatorname {\mathrm {dom}}(q_2)$
; note that this implies that
$b>c$
, since
$c\notin \operatorname {\mathrm {dom}}(q_2)$
. We need to show that
$q_2(b)\geq c^+,c^-$
. We know that
$q_2(b)\neq c$
(because
$c\notin \operatorname {\mathrm {range}}(q_2)$
) and of course
$q_2(b)\in B$
, so we have
$q_2(b)\notin [c^-,c^+]$
. It follows that it is enough to show that
$q_2(b)\geq c^-$
. Suppose towards contradiction that
$q_2(b)<c^-$
. Let
$d\in L$
be such that
$g_2:=q_2\cup \{(c,d)\}$
is a partial automorphism of L (which we have by Proposition 3.3). Since we have
$c < b$
, we have
$d < q_2(b)<c^-<c$
, so
$d<c$
. As before, we have
$C(d,q_1)\leq C(c,q_1)-1$
and
$C(d,g_2)\leq C(d,q_2)+1\leq C(c,q_2)-1+1$
(for the last inequality, note that
$q_2(b)$
is counted in
$C(c,q_2)$
, but not in
$C(d,q_2)$
). Clearly,
$m(q_1,g_2)\leq d$
, so we have
$C_m(q_1,g_2)\leq C(d,q_1)+C(d,g_2)<C(c,q_1)+C(c,q_2)$
, a contradiction.
Now, given some
$b\leq c$
with
$b\in \operatorname {\mathrm {dom}}(q_2)$
, we need to show that
$q_2(b)\leq c^+,c^-$
. As before, it is enough to show that
$q_2(b)\leq c^+$
. Arguing by contradiction, suppose
$q_2(b)>c^+$
. Using Proposition 3.3, we can find d such that
$g_2:=q_2\cup \{(d,c)\}$
is a partial automorphism. But then, since
$q_2(b)>c^+>c$
, we have that
$c>b=g_2^{-1}(q_2(b))>g_2^{-1}(c)=d$
. Arguing as in the preceding paragraph, we contradict the minimality of
$(q_1,q_2)$
.⊣
Lemma 3.5. Let T be a meet-tree. Suppose
$f,g$
are partial automorphisms of T such that
$ \operatorname {\mathrm {dom}}(f)$
and
$ \operatorname {\mathrm {dom}}(g)$
are closed under
$\mathbin {\wedge }$
, and satisfy the condition that for every
$\eta \in \operatorname {\mathrm {dom}}(f)$
, there is some
$a_{\eta }\in \operatorname {\mathrm {dom}}(g)$
such that
$a_{\eta }\geq \eta $
and
$g{\upharpoonright }_{T_{\leq a_{\eta }}}\subseteq f$
.
Then
$f\cup g$
is a partial automorphism of T (whose domain is closed under
$\mathbin {\wedge }$
).
Proof Put
$h:=f\cup g$
. Note that if
$\eta \in \operatorname {\mathrm {dom}}(f)\cap \operatorname {\mathrm {dom}}(g)$
, then
$g{\upharpoonright }_{T_{\leq a_{\eta }}}\subseteq f$
, so in particular,
$f(\eta )=g(\eta )$
, so h is a well-defined partial function. Note also that given
$\eta \in \operatorname {\mathrm {dom}}(f)$
, we have
$h{\upharpoonright }_{T_{\leq a_{\eta }}}\subseteq f$
.
Claim. The domain
$ \operatorname {\mathrm {dom}}(h)$
is closed under
$\mathbin {\wedge }$
.
Proof Since
$ \operatorname {\mathrm {dom}}(f)$
and
$ \operatorname {\mathrm {dom}}(g)$
are closed under
$\mathbin {\wedge }$
, it is enough to show that if
$\eta \in \operatorname {\mathrm {dom}}(f)$
and
$\nu \in \operatorname {\mathrm {dom}}(g)$
, then
$\eta \mathbin {\wedge } \nu \in \operatorname {\mathrm {dom}}(h)$
.
If
$\eta \mathbin {\wedge }\nu =\eta $
, then there is nothing to prove. Otherwise,
$\eta \leq a_{\eta }\in \operatorname {\mathrm {dom}}(g)$
, so
$a_{\eta }\mathbin {\wedge }\eta =\eta>\eta \mathbin {\wedge } \nu $
. By Fact 2.19, we infer that
$\eta \mathbin {\wedge } \nu =a_{\eta }\mathbin {\wedge } \nu $
; since
$a_{\eta }\in \operatorname {\mathrm {dom}}(g)$
, the conclusion follows. Claim
We will show that h is an isomorphism between substructures of T. To that end, we need to show that h is injective and that for any
$\eta ,\nu \in \operatorname {\mathrm {dom}}(h)$
, we have
$\eta \leq \nu $
if and only if
$h(\eta )\leq h(\nu )$
, and that
$h(\eta \mathbin {\wedge }\nu )=h(\eta )\mathbin {\wedge } h(\nu )$
.
Notice that
$f^{-1}$
and
$g^{-1}$
satisfy the assumptions of the proposition we are proving: indeed, given
$\eta ^{\prime }=f(\eta )\in \operatorname {\mathrm {dom}}(f^{-1})$
, we have some
$a_{\eta }\in \operatorname {\mathrm {dom}}(g)$
with
$a_{\eta }\geq \eta $
and
$g{\upharpoonright }_{T_{\leq a_{\eta }}}\subseteq f$
. But this clearly implies that
$f(a_{\eta })=g(a_{\eta })\geq \eta ^{\prime }$
and
$g^{-1} {\upharpoonright }_{T_{\leq f(a_{\eta })}}\subseteq f^{-1}$
. Thus by the first paragraph of this proof,
$h^{-1}=f^{-1}\cup g^{-1}$
is a well-defined partial function, so h is injective. By the same token, it is enough to show that h preserves meets and that
$\eta \leq \nu $
implies
$h(\eta )\leq h(\nu )$
(i.e., the converse will follow).
Now, let us fix arbitrary
$\eta ,\nu \in \operatorname {\mathrm {dom}}(h)$
such that
$\eta \leq \nu $
. We need to show that
$h(\eta )\leq h(\nu )$
. If
$\nu \in \operatorname {\mathrm {dom}}(f)$
, then it easily follows that
$\eta \in \operatorname {\mathrm {dom}}(f)$
, so it is enough to consider the case when
$\eta \in \operatorname {\mathrm {dom}}(f)$
and
$\nu \in \operatorname {\mathrm {dom}}(g)$
. It follows that
$a_{\eta }\mathbin {\wedge }\nu \in \operatorname {\mathrm {dom}}(g)$
, so in fact
$a_{\eta }\mathbin {\wedge }\nu \in \operatorname {\mathrm {dom}}(f)\cap \operatorname {\mathrm {dom}}(g)$
(because
$a_{\eta }\mathbin {\wedge } \nu \leq a_{\eta }$
); since trivially
$a_{\eta }\mathbin {\wedge }\nu \geq \eta $
, we have:
$$\begin{align*}h(\nu)=g(\nu)\geq g(a_{\eta}\mathbin{\wedge} \nu)=h(a_{\eta}\mathbin{\wedge} \nu)=f(a_{\eta}\mathbin{\wedge} \nu)\geq f(\eta)=h(\eta). \end{align*}$$
Now, we need to show that
$h(\eta \mathbin {\wedge } \nu )=h(\eta )\mathbin {\wedge } h(\nu )$
. We may assume that
$\eta \in \operatorname {\mathrm {dom}}(f)$
,
$\nu \in \operatorname {\mathrm {dom}}(g)$
, and also that
$\eta>\eta \mathbin {\wedge }\nu $
(if we have equality, then
$\eta \leq \nu $
, and the conclusion follows from the preceding paragraph). Then
$\eta =a_{\eta }\mathbin {\wedge }\eta>\eta \mathbin {\wedge }\nu $
, so (by Fact 2.19)
$\eta \mathbin {\wedge }\nu =a_{\eta }\mathbin {\wedge }\nu $
. As in the preceding paragraph, we have that
$a_{\eta }\mathbin {\wedge }\nu \in \operatorname {\mathrm {dom}}(f)\cap \operatorname {\mathrm {dom}}(g)$
. Thus, we have
$f(a_{\eta })\mathbin {\wedge } f(\eta )=f(\eta )>f(\eta \mathbin {\wedge }\nu )$
. On the other hand
$g(\eta \mathbin {\wedge }\nu )=g(a_{\eta }\mathbin {\wedge }\nu )=g(a_{\eta })\mathbin {\wedge } g(\nu )$
. In conclusion, we have
$h(a_{\eta })\mathbin {\wedge } h(\eta )>h(\eta \mathbin {\wedge }\nu )=h(a_{\eta })\mathbin {\wedge } h(\nu )$
. It follows by Fact 2.19 that
$h(\eta \mathbin {\wedge }\nu )=h(a_{\eta })\mathbin {\wedge } h(\nu )=h(\eta )\mathbin {\wedge } h(\nu )$
, so we are done.⊣
Corollary 3.6. Suppose
$p_1,p_2$
are finite partial automorphisms of a dense, unrooted meet-tree M, such that for some
$a\in M$
, we have
$p_1(a)=p_2(a)<a$
. Then
$(p_1,p_2)$
admits extensions
$(p_1^{\prime },p_2^{\prime })$
and
$(p_1^{\prime \prime },p_2^{\prime \prime })$
which are irreconcilable over a.
Proof Note that since M is dense and unrooted,
$M_{\leq a}$
is a dense linear ordering, without lower bound.
For
$i=1,2$
, write
$q_i:=p_i{\upharpoonright }_{M_{\leq a}}$
, and let
$q_i^{\prime },q_i^{\prime \prime }$
be the extensions given by Proposition 3.4 (to partial automorphisms of
$M_{\leq a}$
), and put
$p_i^{\prime }:=p_i\cup q_i^{\prime }$
,
$p_i^{\prime \prime }:=p_i\cup q_i^{\prime \prime }$
. Then by Lemma 3.5 (with
$f=q_i^{\prime }$
or
$f=q_i^{\prime \prime }$
,
$g=p_i$
, and
$a_{\eta }:=a$
for all
$\eta $
),
$p_i^{\prime }$
and
$p_i^{\prime \prime }$
are partial automorphisms, and clearly,
$(p_1^{\prime },p_2^{\prime })$
and
$(p_1^{\prime \prime },p_2^{\prime \prime })$
are irreconcilable over a.⊣
Corollary 3.7. If M is a dense and unrooted meet-tree and
$\mathcal K:= \operatorname {\mathrm {Age}}(M)$
, then
$\mathcal K^2$
(the class of
$\mathcal K$
-structures with pairs of partial automorphisms) does not have the EAP
$($
see Definition 2.6
$)$
.
Proof Since M is unrooted, in particular, it contains two elements
$a>b$
and
$p_1^0=p_2^0=\{(a,b) \}$
is a partial automorphism. Then any extension
$(p_1,p_2)$
of
$(p_1^0,p_2^0)$
satisfies the hypothesis of Corollary 3.6, so it admits two extensions irreconcilable over a. This clearly implies the failure of EAP.⊣
The following corollary is the second half of the Main Theorem (the first half we will prove later in Theorem 6.11).
Corollary 3.8. If
$\mathbf K$
is one of
$\mathbf T$
or
$\mathbf T_k$
for
$k>0$
(in particular, if it is the dense linear ordering), then
$\mathbf K$
does not admit a generic pair of automorphisms.
4 Determined partial automorphisms
We aim to show that the universal countable meet-tree admits a generic automorphism (even though, by Corollary 3.8, we already know it does not admit a generic pair of automorphisms). Very broadly, the proof follows [Reference Kuske and Truss10]. More precisely, we will find a sufficient condition for a partial automorphism to be an amalgamation base in the class
$\mathcal K^1$
(where
$\mathcal K$
is the class of finite meet-trees), and in the next section, we will find a cofinal class of automorphisms satisfying this condition, thus showing CAP for
$\mathcal K^1$
. This, in conjunction with Corollary 2.10, will give us the existence of generics.
4.1 Determined partial automorphisms in an abstract context
The notion of a strict extension and a determined automorphism is due to [Reference Kuske and Truss10]. We have slightly modified it: the authors of [Reference Kuske and Truss10] do not ask that the domain of a strict extension is a substructure, which is a trivial requirement in the case of relational structures. We also introduce the notion of a strictly positive extension.
Definition 4.1. Let M be a first order structure, and let p be a finite partial automorphism of M.
-
• We say that an extension
$f\supseteq p$
of partial automorphisms of M is strict if it is an automorphism of a substructure (i.e.,
$ \operatorname {\mathrm {dom}}(f)= \operatorname {\mathrm {range}}(f)$
is a substructure of M) and
$ \operatorname {\mathrm {dom}}(f)$
is generated by the f-orbits of elements of
$ \operatorname {\mathrm {dom}}(p)$
. -
• We say that an extension
$f\supseteq p$
of partial automorphisms of M is positively strict if f is an endomorphism of a substructure (i.e.,
$ \operatorname {\mathrm {dom}}(f)\supseteq \operatorname {\mathrm {range}}(f)$
and
$ \operatorname {\mathrm {dom}}(f)$
is a substructure of M) and
$ \operatorname {\mathrm {dom}}(f)$
is generated by the positive f-orbits of elements of
$ \operatorname {\mathrm {dom}}(p)$
(i.e., the images of
$ \operatorname {\mathrm {dom}}(p)$
by the positive powers of f). -
• Given two extensions
$f_1,f_2$
of p, we say that
$f_1$
and
$f_2$
are isomorphic over p if there is an isomorphism
$\theta \colon \operatorname {\mathrm {dom}}(f_1)\to \operatorname {\mathrm {dom}}(f_2)$
fixing
$ \operatorname {\mathrm {dom}}(p)$
pointwise, such that
$\theta \circ f_1=f_2\circ \theta $
(note that we do not require that
$\theta $
extends to an automorphism of M). -
• We say that p is [positively] determined if, up to isomorphism over p, it admits a unique [positively] strict extension.
${\lozenge }$
Recall that we want to find a cofinal class of amalgamation bases in
$\mathcal K^1$
. Proposition 4.2 and Lemma 4.3 show that under reasonable assumptions (which, as we will see in Lemma 4.16, are satisfied by the class of meet-trees), the notions of a determined automorphism and an amalgamation base in the class
$\mathcal K^1$
are essentially equivalent.
Proposition 4.2. Suppose
$\mathcal K$
is a Fraïssé class with Fraïssé limit
$\mathbf K$
, and suppose p is a partial automorphism of
$\mathbf K$
such that for the structure
$B\leq \mathbf K$
generated by
$ \operatorname {\mathrm {dom}}(p)\cup \operatorname {\mathrm {range}}(p)$
, we have that
$(B,p)$
is an amalgamation base in
$\mathcal K^1$
. Then p is determined.
Proof This is not important for our applications, so we only sketch the proof. We can do it by contraposition. If
$f_1,f_2\supseteq p$
are strict, not isomorphic over p, then there are some finite
$f_i^{\prime }\subseteq f_i$
(
$i=1,2$
) such that for no automorphism
$\theta $
of
$\mathbf K$
fixing
$ \operatorname {\mathrm {dom}}(p)$
we have that
$f_1^{\prime }\cup \theta f_2^{\prime }\theta ^{-1}$
is a partial automorphism of
$\mathbf K$
. This easily implies that for the appropriate
$C_1,C_2$
, we cannot amalgamate
$(C_1,f_1^{\prime })$
and
$(C_2,f_2^{\prime })$
over
$(B,p)$
.⊣
Lemma 4.3. Suppose
$\mathcal K$
is a Fraïssé class with Fraïssé limit
$\mathbf K$
. Consider the class
$\overline {\mathcal K}$
of structures
$($
possibly not finitely generated
$)$
whose age is contained in
$\mathcal K$
, and let
$\overline {\mathcal K}^1_{\mathrm {t}}$
be the class of
$\overline {\mathcal K}$
-structures equipped with a
$($
total
$)$
automorphism.
If
$\overline {\mathcal K}^1_{\mathrm {t}}$
has the AP, then for every determined partial automorphism p of
$\mathbf K$
, we have that if
$B\subseteq \mathbf K$
is generated by
$ \operatorname {\mathrm {dom}}(p)\cup \operatorname {\mathrm {range}}(p)$
, then
$(B,p)$
is an amalgamation base in
$\mathcal K^1$
.
Proof Consider two embeddings (in
$\mathcal K^1$
)
$(B,p)\to (C_1,h_1),(C_2,h_2)$
. We may assume without loss of generality that the embeddings are simply inclusions and
$C_1,C_2\subseteq \mathbf K$
. Let
$f_1,f_2$
be strict extensions of
$h_1,h_2$
(respectively) to partial automorphisms of
$\mathbf K$
. Then for
$i=1,2$
, let
$f_i^{\prime }\supseteq p$
be the restriction of
$f_i$
to substructure of
$\mathbf K$
generated by the
$f_i$
-orbit of
$ \operatorname {\mathrm {dom}}(p)$
, and put
$B_i:= \operatorname {\mathrm {dom}}(f_i^{\prime })$
and
$\overline C_i:= \operatorname {\mathrm {dom}}(f_i)$
for
$i=1,2$
. Note that
$f_i^{\prime }\supseteq p$
is a strict extension for
$i=1,2$
, and since p is determined, we have an isomorphism
$\theta _2\colon (B_1,f_1^{\prime })\to (B_2,f_2^{\prime })$
fixing
$ \operatorname {\mathrm {dom}}(p)$
(and hence B) pointwise. Write
$(\overline B,f):=(B_1,f_1^{\prime })$
and write
$\theta _1$
for the inclusion mapping
$\overline B\to \overline C_1$
.
Note that clearly,
$\overline B,\overline C_1,\overline C_2\in \overline {\mathcal K}$
, and
$\theta _i$
yields an embedding
$(\overline {B},f)\to (\overline C_i,f_i)$
so, since
$(\overline {B},f)$
is an amalgamation base in
$\overline {\mathcal K}^1_{\mathrm {t}}$
, we have some
$(D,h)\in \overline {\mathcal K}^1_{\mathrm {t}}$
and embeddings
$j_i\colon (\overline C_i,f_i)\to (D,h)$
(for
$i=1,2$
) such that
$j_1\circ \theta _1=j_2\circ \theta _2$
. Now, put
$D_0^{\prime }:=j_1[C_1]\cup j_2[C_2]$
and let
$D^{\prime }$
be the substructure of D generated by
$D_0^{\prime }\cup h[D_0^{\prime }]$
. Put
$h^{\prime }:=h{\upharpoonright }_{D_0^{\prime }}$
,
$j_i^{\prime }:=j_i{\upharpoonright }_{C_i}$
. The following diagrams summarise the maps constructed, with the maps on right hand side being restrictions of the maps on the left hand side.
Since
$D\in \overline {\mathcal K}$
, we have
$D^{\prime }\in \mathcal K$
, so clearly
$(D^{\prime },h^{\prime })\in \mathcal K^1$
. Clearly,
$j_i^{\prime }$
is an embedding of
$(C_i,h_i)$
into
$(D^{\prime },h^{\prime })$
, and since
$j_1\circ \theta _1=j_2\circ \theta _2$
and each
$\theta _i$
fixes B pointwise, we also have
$$\begin{align*}j_1^{\prime} {\upharpoonright}_B=j_1 {\upharpoonright}_B=(j_1\circ \theta_1) {\upharpoonright}_B=(j_2\circ \theta_2) {\upharpoonright}_B=j_2 {\upharpoonright}_B=j_2^{\prime} {\upharpoonright}_B. \end{align*}$$
Analogously, since
$j_i\circ \theta _i\circ f\subseteq h\circ j_i\circ \theta _i$
(because
$j_i\circ \theta _i$
is an embedding of
$(\overline B,f)$
into
$(D,h)$
), we have
$j_i^{\prime } {\upharpoonright }_B\circ p\subseteq h^{\prime }\circ j_i^{\prime } {\upharpoonright }_{B}$
, so
$(D^{\prime },h^{\prime })$
is an amalgam of
$(C_1,h_1)$
and
$(C_2,h_2)$
over
$(B,p)$
, which completes the proof.⊣
Remark 4.4. The proof of Lemma 4.2 shows something slightly more general. Namely, if p is a determined partial automorphism such that for the unique strict extension
$\hat p\supseteq p$
, the structure
$( \operatorname {\mathrm {dom}}(\hat p),\hat {p})$
is an amalgamation base in
$\overline {\mathcal K}^1_{\mathrm {t}}$
, then
$(B,p)$
(defined as there) is an amalgamation base in
$\mathcal K^1$
.
${\lozenge }$
Remark 4.5. The assumption that we have AP in
$\overline {\mathcal K}^1_{\mathrm {t}}$
(or at least that
$( \operatorname {\mathrm {dom}}(\hat {p}),\hat p)$
is an amalgamation base there) is necessary in Lemma 4.3. See Remark 4.20.
${\lozenge }$
Remark 4.6. If
$f\supseteq p$
is a strict extension, then
$f_+$
, its restriction to the substructure generated by the positive f-orbits of elements of
$ \operatorname {\mathrm {dom}}(p)$
, is a strictly positive extension. It is also easy to see that
$ \operatorname {\mathrm {dom}}(f)=\bigcup f^{-n} \operatorname {\mathrm {dom}}(f_+)$
(because it is a substructure of
$ \operatorname {\mathrm {dom}}(f)$
and it contains the f-orbits of elements of
$ \operatorname {\mathrm {dom}}(p)$
).
${\lozenge }$
We will be looking for determined partial automorphisms in order to apply Lemma 4.3. The following proposition shows that it is, in fact, enough to show positive determination.
Proposition 4.7. If p is a positively determined finite partial automorphism, then it is determined.
Proof Fix two strict extensions
$f,g\supseteq p$
. Let
$f_+,g_+$
be the respective positive parts. Fix an isomorphism
$\theta _+\colon \operatorname {\mathrm {dom}}(f_+)\to \operatorname {\mathrm {dom}}(g_+)$
such that
$g_+=\theta _+\circ f_+\circ \theta _+^{-1}$
(which exists by the assumption). Put
$\theta _n:=g^{-n}\circ \theta _+\circ f^{n}$
.
Take any
$a_+\in \operatorname {\mathrm {dom}}(f_+)$
. Then for any
$k\geq 0$
we have:
$$\begin{align*}f^{k}(a_+)=f_+^{k}(a_+)=\theta_+^{-1}\circ g_+^{k}\circ \theta_+(a_+)=\theta_+^{-1}\circ g^{k}\circ \theta_+(a_+), \end{align*}$$
and hence
$g^{-k}\circ \theta _+\circ f^{k}(a_+)=\theta _+(a_+)$
. It follows that if
$n\leq m$
, then
$\theta _n\subseteq \theta _m$
. Indeed, if
$a\in \operatorname {\mathrm {dom}}(\theta _n)$
, then
$f^n(a)\in \operatorname {\mathrm {dom}}(f_+)$
, so
$g^{n-m}\circ \theta _+\circ f^{m-n}(f^n(a))=\theta _+\circ f^n(a)$
, and thus
$$\begin{align*}\theta_m(a)=g^{-n}\circ g^{n-m}\circ\theta_+\circ f^{m-n}(f^n(a))=g^{-n}\circ \theta_+\circ f^n(a)=\theta_n(a). \end{align*}$$
It follows that
$\theta :=\bigcup _n \theta _n$
is a well-defined function. It is not hard to see that
$ \operatorname {\mathrm {dom}}(\theta )=\bigcup _n \operatorname {\mathrm {dom}}(\theta _n)= \operatorname {\mathrm {dom}}(f)$
and
$ \operatorname {\mathrm {range}}(\theta )=\bigcup _n( \operatorname {\mathrm {range}}(\theta _n))= \operatorname {\mathrm {dom}}(g)$
. Finally, since
$\theta _+$
is an isomorphism (between its domain and range), so is each
$\theta _n$
, and hence also
$\theta $
.⊣
The goal of this section is to find a useful criterion for a partial automorphism to be positively determined. To that end, we want to understand positively strict extensions of a partial automorphism by building it in a sequence of “minimal” steps. The following definition means to capture this notion of a single step.
Definition 4.8. Let
$p\subsetneq f$
be partial automorphisms of a structure M. We say that f is an immediate extension of p if
$ \operatorname {\mathrm {dom}}(f)\setminus \operatorname {\mathrm {dom}}(p)$
has only one element a, and moreover,
$a\in \operatorname {\mathrm {range}}(p)$
and the p-orbit of a is the shortest non-cyclic orbit (i.e., no other non-cyclic orbit is shorter).
${\lozenge }$
Note the extra condition at the end of the above definition might seem a bit technical. The point is that the infinite positively strict extensions are exactly the unions of infinite immediate chains, see Remark 4.10.
Remark 4.9. If p is a partial automorphism of a structure M, then p has a unique extension
$\overline {p}$
to a partial automorphism of M such that
$ \operatorname {\mathrm {dom}}(\overline {p})$
is the substructure of M generated by
$ \operatorname {\mathrm {dom}}(p)$
. Furthermore, if
$q\supseteq p$
is a partial automorphism extending p, then
$\overline {q}\supseteq \overline {p}$
.
${\lozenge }$
Remark 4.10. If
$f\supseteq p$
is a positively strict extension, then by straightforward induction, there is a sequence
$(f_n)_{n}$
(with n ranging over
$\omega $
or a finite ordinal if f is finite) such that
$f_0=p$
, for each
$n>0$
, the extension
$f_{n-1}\subseteq f_{n}$
is immediate, and
$f=\bigcup _n \overline {f_n}$
.
Conversely, if
$(f_n)_{n\in \omega }$
is such that
$f_0=p$
and for each
$n>0$
, the extension
$f_{n-1}\subseteq f_{n}$
is immediate, then
$\bigcup _n \overline {f_n}$
is a positively strict extension of p.
${\lozenge }$
The following Lemma will be useful in showing that the determination of a partial automorphism.
Lemma 4.11. Let M be a first order structure. Suppose p is a finite partial automorphism of M such that for every sequence
$p=f_0\subsetneq f_1\subsetneq f_2\subsetneq \cdots \subsetneq f_n\subsetneq f_{n+1}$
such that for all
$i\leq n$
, the extension
$f_i\subsetneq f_{i+1}$
is immediate, the following holds
$:$
-
• If
$g_n\supseteq f_n$
is positively strict, then there is an automorphism
$\tau _n\in \operatorname {\mathrm {Aut}}(M)$
fixing
$ \operatorname {\mathrm {dom}}(f_n)$
pointwise, such that
$\tau _n\circ f_{n+1}\circ \tau _n^{-1}\subseteq g_n$
.
Then p is positively determined
$($
and hence determined
$)$
.
Proof Fix any two positively strict extensions
$f,g\supseteq p$
. For simplicity, suppose that f is infinite (the case when f is finite is analogous).
Let
$(f_n)_{n}$
be a sequence as in Remark 4.10, so that
$f_0=p$
and
$\bigcup _n \overline {f_n}=f$
. We will recursively define a sequence
${\theta _n}$
of automorphisms of M such that:
-
• for all n, the domain of p is fixed pointwise by
$\theta _n$
, -
• if
$n\leq m$
, then
$\theta _n {\upharpoonright }_{ \operatorname {\mathrm {dom}}(\overline {f_n})}=\theta _m {\upharpoonright }_{ \operatorname {\mathrm {dom}}(\overline {f_n})}$
, -
• for all n we have
$\theta _n \circ \overline {f_n}\circ \theta _n^{-1}\subseteq g$
.
Then
$\theta :=\bigcup _n \theta _n{\upharpoonright }_{ \operatorname {\mathrm {dom}}(\overline {f_n})}$
will clearly be a well-defined embedding
$ \operatorname {\mathrm {dom}}(f)\to \operatorname {\mathrm {dom}}(g)$
, fixing
$ \operatorname {\mathrm {dom}}(p)$
, such that
$\theta \circ f\circ \theta ^{-1}\subseteq g$
. It is easy to see that
$\theta $
must be onto
$ \operatorname {\mathrm {dom}}(g)$
(because its image is a substructure which contains the positive g-orbits of elements of
$ \operatorname {\mathrm {dom}}(p)$
), and hence
$\theta \circ f\circ \theta ^{-1}=g$
. Since
$f,g$
are arbitrary, it will follow that p is positively determined, and hence (by Proposition 4.7) also determined.
It is clear that
$\theta _0=\operatorname {id}_M$
satisfies all the conditions listed above. Suppose we have
$\theta _0,\ldots ,\theta _n$
. Put
$g_n:=\theta _n^{-1}\circ g\circ \theta _{n}$
. Then
$g_n\supseteq p$
is positively strict (because
$g\supseteq p$
is positively strict and
$\theta _n$
fixes
$ \operatorname {\mathrm {dom}}(p)$
pointwise) and
$g_n\supseteq f_n\supseteq p$
, so
$g_n$
is a positively strict extension of
$f_n$
. This allows us to take
$\tau _n\in \operatorname {\mathrm {Aut}}(M)$
as in the hypothesis. Put
$\theta _{n+1}:=\theta _n\circ {\tau _n}$
. Since
$\tau _n$
fixes
$ \operatorname {\mathrm {dom}}(f_n)$
, it follows that
$\theta _{n+1} {\upharpoonright }_{ \operatorname {\mathrm {dom}}(f_n)}=\theta _n {\upharpoonright }_{ \operatorname {\mathrm {dom}}(f_n)}$
, and hence also
$\theta _{n+1} {\upharpoonright }_{ \operatorname {\mathrm {dom}}(\overline {f_n})}=\theta _n {\upharpoonright }_{ \operatorname {\mathrm {dom}}(\overline {f_n})}$
.
Finally, since
$\tau _n\circ f_{n+1}\circ \tau _{n}^{-1}\subseteq g_n=\theta _n^{-1}\circ g\circ \theta _{n}$
, it easily follows that
$\theta _{n+1}\circ \overline {f_{n+1}}\circ \theta _{n+1}^{-1}\subseteq g$
.⊣
4.2 Determined partial automorphisms of trees
Now, we will proceed to show that determined partial automorphisms of finite trees are amalgamation bases (in the class of finite trees with partial automorphisms). To that end, we will show that the hypothesis of Lemma 4.3 is satisfied, i.e., that the class of meet-trees with an automorphism has the amalgamation property; we divide the proof into several steps.
Definition 4.12.
(Note that for the particular case of linear orders, the definition of completeness given above is slightly more stringent than the usual one: it implies that there is a maximal element.)
Remark 4.13. If
$(B,g),(C_1,f_1),(C_2,f_2)$
are trees with automorphisms, B is downwards closed in
$C_1$
and
$C_2$
,
$B=C_1\cap C_2$
and
$f_1\cap f_2=g$
, then
$\hat B=\hat C_1\cap \hat C_2$
and
$\hat g=\hat f_1\cap \hat f_2$
, and
$\hat g,\hat f_1,\hat f_2$
are automorphisms of
$\hat B,\hat C_1,\hat C_2$
, respectively (where
$\hat g(\hat b)=g[\hat b]$
etc.).
${\lozenge }$
Remark 4.14. If
$B_1,B_2$
are sets,
$f_1$
is a bijection on
$B_1$
,
$f_2$
is a bijection on
$B_2$
, and
$f_1$
and
$f_2$
agree on
$B=B_1\cap B_2$
, then
$f_1\cup f_2$
is a bijection on
$B_1\cup B_2$
: because they agree on B,
$f_1\cup f_2$
is a well-defined function, and it is easy to check that
$f_1^{-1}\cup f_2^{-1}$
is its inverse.
${\lozenge }$
Lemma 4.15. Suppose
$(B,g),(C_1,f_1),(C_2,f_2)$
are meet-trees with automorphisms such that
$B=C_1\cap C_2$
and
$g=f_1\cap f_2$
. Then there are
$B^{\prime },C_1^{\prime },C_2^{\prime },g^{\prime },f_1^{\prime },f_2^{\prime }$
such that
$:$
-
•
$B^{\prime }= C_1^{\prime }\cap C_2^{\prime }$
and is downwards closed in each of
$C_1^{\prime },C_2^{\prime }$
, -
•
$g^{\prime }$
is automorphism of
$B^{\prime }$
and
$f_i^{\prime }$
is an automorphism of
$C_i^{\prime }$
for
$i=1,2$
, -
•
$g^{\prime }=f_1^{\prime }\cap f_2^{\prime }$
, -
•
$(B,g)\subseteq (B^{\prime },g^{\prime })$
and
$(C_i,f_i)\subseteq (C_i^{\prime },f_i^{\prime })$
for
$i=1,2$
.
Proof Let
$B_i^{\prime }$
be the downwards closure of B in
$C_i$
for
$i=1,2$
. Put
$B^{\prime }:=B_1^{\prime }\cup B_2^{\prime }$
,
$g^{\prime }:=f_1 {\upharpoonright }_{B_1^{\prime }}\cup f_2 {\upharpoonright }_{B_2^{\prime }}$
,
$C_i^{\prime }:=C_i\cup B^{\prime }$
, and
$f_i^{\prime }:=f_i\cup g^{\prime }$
for
$i=1,2$
.
We put on each
$B_i^{\prime }$
the meet-tree structure inherited from
$C_i$
. We proceed to define the meet-tree structure on
$B^{\prime }$
. Recall from Remark 2.24 that we have a canonical ordering on the cuts in B. Now, take some
$c_1,c_2$
from
$B_1^{\prime }\setminus B$
and
$B_2^{\prime }\setminus B$
, respectively, and denote by
$q_1,q_2$
their cuts in B, and take any
$b_1,b_2\in B$
such that
$b_i>c_i$
. Then:
-
• if
$q_1\leq q_2$
, we declare
$c_1<c_2$
and
$c_1\mathbin {\wedge } c_2=c_1$
, -
• if
$q_1>q_2$
, we declare
$c_1>c_2$
and
$c_1\mathbin {\wedge } c_2=c_2$
, -
• if
$q_1$
and
$q_2$
are incomparable, we declare that
$c_1$
and
$c_2$
are incomparable and
$c_1\mathbin {\wedge } c_2=b_1\mathbin {\wedge } b_2$
.
The fact that this definition of
$<$
defines a semilinear partial order is left as an exercise. Let us only show that the
$\mathbin {\wedge }$
is correct and well-defined in the last case. We need to show that given
$c\in B^{\prime }$
, we have that
$c\leq c_1,c_2$
if and only if
$c\leq b_1\mathbin {\wedge } b_2$
(this immediately implies that
$c_1\mathbin {\wedge } c_2$
does not depend on the choice of
$b_1$
and
$b_2$
). The fact that the left-hand side implies the right-hand side is trivial, since
$b_i\geq c_i$
. For the converse, suppose
$c\leq b_1\mathbin {\wedge } b_2$
. Note that
$c_1$
and c are comparable, so it is enough to show that
$c\not> c_1$
. But
$c\leq b_2$
, and we cannot have
$c_1\leq b_2$
(because
$c_1$
and
$c_2\leq b_2$
are incomparable). The definition of the meet-tree structure on each
$C_i^{\prime }$
is straightforward.
Now, we need to check that
$g^{\prime }$
is an automorphism of
$B^{\prime }$
. It is clear that
$f_i {\upharpoonright }_{B_i^{\prime }}$
is an automorphism of
$B_i^{\prime }$
for each i, and by Remark 4.14,
$g^{\prime }$
is a bijection, so we only need to check that it preserves the ordering and the meets. But this is easy to see as a consequence of the observation that
$g^{\prime }$
preserves
$B,B_1^{\prime }\setminus B, B_2^{\prime }\setminus B$
, and the cuts over B of all elements of
$B^{\prime }$
.
Finally, again by Remark 4.14, each
$f_i^{\prime }$
is a bijection on
$C_i^{\prime }$
, and the fact that it is an automorphism follows from Lemma 3.5 (with
$f=g^{\prime }$
and
$g=f_i$
).⊣
Lemma 4.16. The class of meet-trees with automorphisms has the amalgamation property.
Proof Suppose
$(B,g),(C_1,f_1),(C_2,f_2)$
are meet-trees with automorphisms, with fixed embeddings of
$(B,g)$
into each
$(C_i,f_i)$
. We need to find a tree with automorphism
$(D,h)$
such that
$(C_i,f_i)$
embed in
$(D,h)$
for
$i=1,2$
in such a way that the two resulting embeddings of
$(B,g)$
into
$(D,h)$
coincide.
We may assume for simplicity that
$(B,g)\subseteq (C_i,f_i)$
for
$i=1,2$
, while
$C_1\cap C_2=B$
and
$f_1\cap f_2=g$
. We will find a
$(D,h)$
such that
$(C_i,f_i)\subseteq (D,h)$
(which will immediately imply that the two embeddings of
$(B,g)$
coincide).
By Lemma 4.15, we may assume without loss of generality that B is downwards closed in
$C_1,C_2$
. Then by Remark 4.13, we may also assume that
$B,C_1,C_2$
are complete. We put
$D:=C_1\cup C_2$
and
$h:=f_1\cup f_2$
. We need to describe the meet-tree structure on D and to show that h is an automorphism of this structure. Now, for each
$c\in C_1\cup C_2$
, put
$b_c:=\sup \{b\in B\mid b\leq c \}$
(this is well-defined by completeness of B).
On D, we define the structure in the following way:
-
• on each
$C_i$
, the structure is simply the original structure, -
• given
$c_1\in C_1\setminus B$
and
$c_2\in C_2\setminus B$
, we declare
$c_1$
and
$c_2$
to be incomparable and put
$c_1\mathbin {\wedge } c_2:=b_{c_1}\mathbin {\wedge } b_{c_2}$
(where the meet on the right-hand side is in the sense of B).
Note that this gives a meet-tree structure: indeed, transitivity of the order follows easily from the fact that B is downwards closed in
$C_1$
and
$C_2$
, and given any
$d_0\in D$
, the interval
$(-\infty ,d_0]$
in D is contained in
$C_1$
or
$C_2$
(depending on whether
$d_0\in C_1$
or
$d_0\in C_2$
), so semilinearity follows from semilinearity of
$C_1$
and
$C_2$
. By the same token, given
$c_1\in C_1$
and
$c_2\in C_2$
, the intersection
$(-\infty ,c_1]\cap (-\infty ,c_2]$
is contained in B, so it is contained in
$(-\infty ,b_{c_1}]\cap (-\infty ,b_{c_2}]=(-\infty ,b_{c_1}\mathbin {\wedge } b_{c_2}]$
.
Furthermore, h is an automorphism of D: by Remark 4.14, it is a bijection, and it clearly preserves meets and inequalities within each
$C_i$
. Now, given
$c_1\in C_1\setminus C_2$
and
$c_2\in C_2\setminus C_1$
, the two are incomparable, and since
$h(c_1)=f_1(c_1)\in C_1\setminus C_2$
and
$h(c_2)=f_2(c_2)\in C_2\setminus C_1$
(because
$C_1,C_2$
are clearly h-invariant),
$h(c_1)$
and
$h(c_2)$
are incomparable. It is also not hard to see that
$b_{f_i(c_i)}=f_i(b_{c_i})$
, which implies that h preserves meets.
Finally, clearly
$D\supseteq C_1,C_2$
and
$h\supseteq f_1,f_2$
, so
$(D,h)$
is as desired.⊣
One could ask whether the analogue of Lemma 4.16 for trees of bounded arity is true. Unfortunately, this is not the case, which the following proposition shows.
Proposition 4.17. For every integer
$k>1$
, the class of meet-trees of arity at most k with an automorphism does not have the amalgamation property.
Proof Fix k and let
$B=\{b\}$
,
$C_1=B\cup \{c_1^1,c_1^2,\ldots ,c_1^k\}$
,
$C_2=B\cup \{c_2\}$
be meet-trees such that
$c_2>b$
and for all
$i\neq j$
we have
$c_1^i,c_1^j>c_1^i\mathbin {\wedge } c_1^j=b$
. Define f on B as
$f(b)=b$
,
$f_1\supseteq f$
on
$C_1$
as
$f_1(c_1^i)=c_1 ^{i+1}$
, for
$i<k$
,
$f_1(c_1^k)=c_1^1$
, and finally define
$f_2\supseteq f$
on
$C_2$
as the identity map.
We claim that
$(C_1,f_1)$
and
$(C_2,f_2)$
do not amalgamate over
$(B,f)$
. Indeed, suppose we do have an amalgam
$(D,g)$
, with D being a tree of arity at most k. It follows that for some i we have
$c_1^i\mathbin {\wedge } c_2>b$
. We may assume without loss of generality that
$i=1$
. But then by Fact 2.19, since
$b=c_1^1\mathbin {\wedge } c_1^2$
, it follows that
$c_1^2\mathbin {\wedge } c_2=b$
. On the other hand, since g is an automorphism of D, we have
$b=g(b)<g(c_1^1\mathbin {\wedge } c_2)=g(c_1^1)\mathbin {\wedge } g(c_2)=c_1^2\mathbin {\wedge } c_2$
, a contradiction.⊣
In the opposite direction to Proposition 4.17, the following Remark describes a possible class of amalgamation classes for the case of bounded arity.
Remark 4.18. We suspect that the following is true (but, as we do not use it, we will did not check it very carefully): if
$k>1$
and
$(B,g)$
is a meet-tree of arity at most k with an automorphism, such that every g-periodic
$b\in B$
has maximal rank (i.e., there are
$b_1,\ldots , b_k$
which are pairwise incomparable, such that
$b_i\mathbin {\wedge } b_j=b$
for all
$i\neq j$
), then
$(B,g)$
is an amalgamation base (in the class of all meet-trees of arity at most k with an automorphism).
${\lozenge }$
The following corollary summarises the results of this section. In the rest of the paper, we will show (using Lemma 4.11) that determined finite partial automorphisms of
$\mathbf T$
are cofinal, which will imply that
$\mathbf T$
has a generic automorphism.
Corollary 4.19. If p is a finite partial automorphism of
$\mathbf T$
and
$B\subseteq \mathbf T$
is generated by
$ \operatorname {\mathrm {dom}}(p)\cup \operatorname {\mathrm {range}}(p)$
, then
$(B,p)$
is an amalgamation base in the class of finite trees with partial automorphisms if and only if p is determined.
Proof Note that if the age of a structure consists of finite meet-trees, then it is a meet-tree itself, and conversely, the age of any meet-tree consists of finite meet-trees. The corollary follows immediately by Lemmas 4.3 and 4.16 and Proposition 4.2.⊣
Remark 4.20. Note that the construction from Proposition 4.17 actually shows that the analogue of Corollary 4.19 for
$\mathbf T_k$
fails (when
$k>1$
): an automorphism of
$\mathbf T_k$
which is just a single fixed point is trivially determined, and the example shows that it does not yield an amalgamation base.
${\lozenge }$
Remark 4.21. One can show that the class of linear orders with an automorphism does have AP (essentially, arguing as in the proof of Lemma 4.15), so the analogue of Corollary 4.19 for
$\mathbf T_1$
holds. This can be used (along with a variant of Theorem 6.8) to recover the fact that
$({\mathbf Q},<)$
has a generic automorphism, see Remark 6.13.
${\lozenge }$
5 Orbits in meet-trees
Having Corollary 4.19, to show CAP for the class of finite automorphisms of meet-trees, it is enough to show that determined partial automorphisms are cofinal. Before we can do that, we need to understand the orbits of partial automorphisms in trees and their extensions.
Definition 5.1. A (finite) partial orbit (in a meet-tree) is a finite sequence
$\eta =(\eta _0,\eta _1,\ldots ,\eta _n)$
of elements of the tree such that the map
$\eta _i\mapsto \eta _{i+1}$
for
$i=0,\ldots , n-1$
is a partial automorphism.
Given a finite partial automorphism p, an orbit of p is a partial orbit
$\eta =(\eta _0,\ldots , \eta _n)$
such that
$p(\eta _i)=\eta _{i+1}$
for all
$i<n$
and either
$\eta _0=\eta _k$
for some
$k\leq n$
, or
$\eta _0\notin \operatorname {\mathrm {range}}(p)$
and
$\eta _n\notin \operatorname {\mathrm {dom}}(p)$
.
Infinite partial orbits and orbits of infinite partial automorphisms are defined analogously.
${\lozenge }$
Until the end of the paper, we will use the convention that lower-case Greek letters represent (usually finite) partial orbits in meet-trees, and each such orbit
$\eta $
is enumerated as
$\eta _0,\ldots ,\eta _n$
, as in Definition 5.1.
Remark 5.2. Since every finite tree can be embedded in
$\mathbf T$
(which is ultrahomogeneous), every finite partial meet-tree automorphism can be extended to a total meet-tree automorphism (possibly after enlarging the tree). In particular, every finite partial orbit is contained in the orbit of some total automorphism.
(Likewise, every finite automorphism and finite partial orbit in a meet-tree of arity at most k can be extended to an automorphism or a full orbit of a meet-tree of arity at most k.)
${\lozenge }$
Definition 5.3. Let
$\eta =(\eta _0,\eta _1,\ldots ,\eta _n)$
be a partial orbit, while k is a positive integer.
Then:
-
• We say that
$\eta $
is a k-cycle (or k-cyclic) if k is minimal such that for some
$\eta _k=\eta _0$
. -
• We say that
$\eta $
is an ascending k-spiral if k is minimal such that
$\eta _k>\eta _0$
. Likewise, we say that it is a descending k-spiral if k is minimal such that
$\eta _k<\eta _0$
. -
• We say that
$\eta $
is an ascending k-comb if it is not a spiral and k is minimal such that
$\eta _{2k}\mathbin {\wedge } \eta _k>\eta _k\mathbin {\wedge } \eta _0$
. Likewise, we say that it is a descending k-comb if it is not a spiral and k is minimal such that
$\eta _{2k}\mathbin {\wedge } \eta _k<\eta _k\mathbin {\wedge } \eta _0$
. -
• Otherwise, if
$\eta $
is not a cycle, spiral, nor a comb, we say that
$\eta $
is a quasi-cycle (or quasi-cyclic).
If
$\eta $
is a k-cycle, we say that k is the period of
$\eta $
; if
$\eta $
is a k-spiral or a k-comb, we say that k is its spiral length.
We define the length of
$\eta $
as the size of
$\{\eta _0,\ldots ,\eta _n\}$
.
(See Figures 1 and 2 for some examples of orbits of various types.)
${\lozenge }$
The
$\zeta $
-orbit is a
$2$
-cycle and the
$\eta $
-orbit is an ascending
$4$
-spiral, while the
$\mu $
-orbit is an ascending
$4$
-comb. The root is a fixed point.
The
$\eta $
-orbit is a quasi-cycle of pseudo-period
$3$
(see Definition 5.10 below) and the
$\mu $
-orbit is a
$3$
-cycle, while the root is a fixed point.
Remark 5.4. Note that if
$\eta =(\eta _0,\ldots ,\eta _n)$
is a cycle or a quasi-cycle, then for all
$k\leq n/2$
, we have
$\eta _0\mathbin {\wedge } \eta _k=\eta _k\mathbin {\wedge } \eta _{2k}$
.
${\lozenge }$
Remark 5.5. If
$\eta \subseteq \bar \eta $
are finite partial orbits, then if
$\eta $
is a k-cycle, an ascending/descending k-spiral or k-comb, then so is
$\bar \eta $
(respectively). It follows that a suborbit of a quasi-cycle is a quasi-cycle. On the other hand, if
$\eta $
is a quasi-cycle, then it does not say much about the kind of orbit
$\bar \eta $
can be (see Remark 5.18).
${\lozenge }$
Remark 5.6. If
$\eta =(\eta _0,\ldots ,\eta _n)$
is a partial orbit, then so is
$\eta ^{-1}=(\eta _n,\eta _{n-1},\ldots ,\eta _0)$
. If we think of
$\eta $
as a sequence of steps in a process, then
$\eta ^{-1}$
can be thought of as “time-reversal” of this process.
${\lozenge }$
The following proposition describes the spiral behaviour of orbits.
Proposition 5.7. Suppose that
$\eta =(\eta _0,\ldots ,\eta _n)$
is k-spiral. Then for
$i,j,l\in [0,n]:$
-
(1)
$\eta _i$
is comparable to
$\eta _j$
if and only if
$i\equiv j\pmod k$
, -
(2) if
$i\equiv j\not \equiv l\pmod k$
, then
$\eta _i\mathbin {\wedge } \eta _l=\eta _j\mathbin {\wedge } \eta _l$
, -
(3) if
$2l\leq n$
and
$\eta _0\mathbin {\wedge } \eta _l\neq \eta _l\mathbin {\wedge } \eta _{2l}$
, then k divides l (so
$\eta _0<\eta _l<\eta _{2l}$
or
$\eta _0>\eta _l>\eta _{2l}$
).
Proof The case of
$k=1$
is straightforward, so we may assume that
$k>1$
. We may assume without loss of generality that
$\eta $
is ascending (replacing it with
$\eta ^{-1}$
if necessary), and we may also assume that
$n\geq jk$
(extending
$\eta $
if necessary).
(1): It is clear (by straightforward induction) that if
$i\equiv j\pmod k$
, then
$\eta _i$
and
$\eta _j$
are comparable. For the converse, we may assume without loss of generality that
$i<j$
, and in fact that
$i=0$
. Since
$\eta $
is an ascending k-spiral,
$\eta _0<\eta _{jk}$
. This clearly implies that
$\eta _j\not \leq \eta _0$
(otherwise, we would have
$\eta _{jk}\leq \eta _0$
), so by comparability,
$\eta _j>\eta _0$
. Let m be maximal such that
$km\leq j$
. Since
$j>0$
and k is minimal such that
$\eta _k>\eta _0$
, we have
$m>0$
. Now, it is easy to see that we have
$\eta _{km},\eta _j<\eta _{jk}$
, so
$\eta _{km},\eta _j$
are comparable. It follows that
$\eta _0,\eta _{j-km}$
are comparable. But
$0\leq j-km<k$
, so by the choice of k, it follows that
$j-km=0$
, so k divides j.
(2): By (1),
$\eta _i$
and
$\eta _j$
are comparable, so without loss of generality we can assume
$\eta _i\leq \eta _j$
. It follows that
$\eta _i\mathbin {\wedge } \eta _j=\eta _i$
. Also by (1),
$\eta _i,\eta _l$
are not comparable, so
$\eta _i\mathbin {\wedge }\eta _l<\eta _i$
. Together, we have that
$\eta _i\mathbin {\wedge } \eta _j>\eta _i\mathbin {\wedge } \eta _l$
, so by Fact 2.19,
$\eta _i\mathbin {\wedge } \eta _l=\eta _j\mathbin {\wedge } \eta _l$
.
(3): Write N for the least common multiple of l and k; we may assume without loss of generality that
$N\leq n$
(extending
$\eta $
if necessary).
Consider for simplicity the case when
$\eta _0\mathbin {\wedge } \eta _l>\eta _l\mathbin {\wedge } \eta _{2l}$
(the other case is similar). If
$l=N$
, we are done. Otherwise, by straightforward induction,
$\eta _0\mathbin {\wedge } \eta _l>\eta _l\mathbin {\wedge } \eta _{N}$
, so in particular
$\eta _0\mathbin {\wedge } \eta _l\neq \eta _N\mathbin {\wedge } \eta _l$
. But k divides both
$0$
and N, so by (2) we conclude that k divides l. (This also contradicts the hypothesis that
$l\neq N$
.)⊣
Proposition 5.8. Let
$\eta =(\eta _0,\ldots ,\eta _n)$
be a partial orbit. Take any positive
$k\leq n/2$
and integers
$i_1\equiv i_2\equiv j_1\equiv j_2\pmod k$
such that
$i_1<i_2$
and
$j_1<j_2$
.
If
$\eta _0\mathbin {\wedge } \eta _k<\eta _k\mathbin {\wedge } \eta _{2k}$
(in particular, if
$\eta $
is an ascending k-spiral or k-comb), then
$:$
-
1.
-
(a)
$\eta _{i_1}\mathbin {\wedge } \eta _{i_2}=\eta _{i_1}\mathbin {\wedge } \eta _{i_1+k};$
-
(b)
$ \operatorname {\mathrm {otp}}(\eta _{i_1}\mathbin {\wedge } \eta _{i_2},\eta _{j_1}\mathbin {\wedge } \eta _{j_2})= \operatorname {\mathrm {otp}}(i_1,j_1)$
.
-
Likewise, if
$\eta _0\mathbin {\wedge } \eta _k>\eta _k\mathbin {\wedge } \eta _{2k}$
(in particular, if
$\eta $
is a descending k-spiral or k-comb), then
$:$
-
2.
-
(a)
$\eta _{i_1}\mathbin {\wedge } \eta _{i_2}=\eta _{i_2-k}\mathbin {\wedge } \eta _{i_2};$
-
(b)
$ \operatorname {\mathrm {otp}}(\eta _{i_1}\mathbin {\wedge } \eta _{i_2},\eta _{j_1}\mathbin {\wedge } \eta _{j_2})= \operatorname {\mathrm {otp}}(j_2,i_2)$
.
-
Proof We will consider the ascending case (the descending case is completely analogous, and in fact it follows by considering the “time reversal”). (1a) follows by induction with respect to
$i_2-i_1$
; if
$i_2-i_1=k$
, then the conclusion is trivial. Otherwise, if
$i_2>i_1+k$
, by the induction hypothesis, we have that
$\eta _{i_1+k}\mathbin {\wedge } \eta _{i_2}=\eta _{i_1+k}\mathbin {\wedge } \eta _{i_1+2k}$
. Since
$\eta _0\mathbin {\wedge } \eta _k<\eta _k\mathbin {\wedge } \eta _{2k}$
, also
$\eta _{i_1}\mathbin {\wedge } \eta _{i_1+k}<\eta _{i_1+k}\mathbin {\wedge } \eta _{i_1+2k}$
, whence
$\eta _{i_1}\mathbin {\wedge } \eta _{i_1+k}<\eta _{i_1+k}\mathbin {\wedge } \eta _{i_2}$
, and the conclusion follows by Fact 2.19.
For (1b), by (1a), we may assume without loss of generality that
$i_2=i_1+k$
and
$j_2=j_1+k$
. We may also assume without loss of generality that
$i_1<j_1$
. Straightforward induction shows that
$\eta _{i_1}\mathbin {\wedge } \eta _{i_1+k}<\eta _{j_1}\mathbin {\wedge } \eta _{j_1+k}$
, which finishes the proof.⊣
Remark 5.9. If p is a partial automorphism of a first-order structure C and
$a,b\in C$
, then
$p\cup \{(a,b)\}$
is a partial automorphism of C if and only if
$ \operatorname {\mathrm {qftp}}(b/ \operatorname {\mathrm {range}}(p))=p( \operatorname {\mathrm {qftp}}(a/ \operatorname {\mathrm {dom}}(p))$
.
${\lozenge }$
Definition 5.10. Given a finite partial orbit
$\eta =(\eta _0,\ldots ,\eta _n)$
(
$n>0$
), its pseudo-period is the smallest
$u>0$
such that
$\eta _0\mathbin {\wedge } \eta _u=\max _{0<i\leq n} \eta _0\mathbin {\wedge } \eta _i$
.
${\lozenge }$
Remark 5.11. Note that if
$\eta $
is a cycle, then its period is also its pseudo- period.
${\lozenge }$
Proposition 5.12. The pseudo-period is invariant under time reversal.
More precisely, if
$\eta =(\eta _0,\ldots ,\eta _n)$
is a partial orbit of pseudo-period u, then u is also the pseudo-period of
$\eta ^{-1}=(\eta _n,\eta _{n-1},\ldots ,\eta _1,\eta _0)$
, i.e., it is the smallest
$m_0>0$
such that
$\eta _{n-m_0}\mathbin {\wedge } \eta _n=\max _{0<m\leq n} \eta _n\mathbin {\wedge } \eta _{n-m}$
.
Proof Let
$u^{\prime }$
be the pseudo-period of
$\eta ^{-1}$
. By symmetry, it is enough to show that
$u^{\prime }\geq u$
. This is equivalent to saying that for all positive
$m<u$
, we have
$\eta _n\mathbin {\wedge } \eta _{n-m}<\eta _n\mathbin {\wedge } \eta _{n-u}$
. Note that for such m we have
$0<u-m<u$
, so
$\eta _0\mathbin {\wedge } \eta _{u-m}<\eta _0\mathbin {\wedge } \eta _u$
. Now, let f be an automorphism of a meet-tree such that for
$f(\eta _i)=\eta _{i+1}$
for
$i=0,\ldots , n-1$
. By applying
$f^{n-u}$
, we obtain that
$\eta _{n-u}\mathbin {\wedge } \eta _{n-m}<\eta _{n-u}\mathbin {\wedge } \eta _n$
. By Fact 2.19, it follows that
$\eta _{n-u}\mathbin {\wedge } \eta _{n-m}=\eta _n\mathbin {\wedge } \eta _{n-m}$
and so we are done.⊣
Proposition 5.13. Suppose
$\eta =(\eta _0,\ldots ,\eta _n)$
is a quasi-cycle of pseudo-period u. Then either
$n\geq 2u$
or
$\eta $
can be extended to
$\bar \eta =(\eta _0,\ldots ,\eta _n,\eta _{n+1},\ldots ,\eta _{2u})$
, a partial orbit such that
$\eta _{2u}=\eta _0$
(so
$\bar \eta $
is a
$2u$
-cycle).
As a consequence,
$\eta $
is an orbit of a finite partial automorphism p such that
$\eta _0\mathbin {\wedge } \eta _u$
is a fixed point of
$p^u$
(in particular,
$p^u(\eta _0\mathbin {\wedge } \eta _u)$
is defined).
Proof Note first that the “as a consequence” part follows easily from the statement by Remark 5.4.
Let f be a meet-tree automorphism, one of whose orbits includes
$\eta $
. For each
$i>n$
, put
$\eta _i:=f^i(\eta _0)$
. We may assume without loss of generality that
$n+1\leq 2u$
(otherwise, the conclusion is trivial).
Claim.
$(\eta _0,\ldots ,\eta _{2u-1})$
is a quasi-cycle of pseudo-period u.
Proof First, to show that the pseudo-period is the same, notice that for
$u<i<2u$
we have (by Proposition 5.12 applied to the partial orbit
$(\eta _{i-u},\ldots , \eta _i)$
)
$\eta _{i-u}\mathbin {\wedge } \eta _i>\eta _u\mathbin {\wedge } \eta _i$
, so (by Fact 2.19 and another application of Proposition 5.12)
$\eta _u\mathbin {\wedge } \eta _i=\eta _u\mathbin {\wedge } \eta _{i-u}<\eta _0\mathbin {\wedge } \eta _u$
, and hence
$\eta _0\mathbin {\wedge } \eta _i=\eta _u\mathbin {\wedge } \eta _i<\eta _0\mathbin {\wedge } \eta _u$
.
We will prove by induction that
$(\eta _0,\ldots ,\eta _m)$
is a quasi-cycle, where
$m<2u$
. If
$m\leq n$
, then there is nothing to prove. Suppose now that
$n\leq m<2u-1$
and we know that
$(\eta _0,\ldots ,\eta _m)$
is a quasi-cycle, and we show that so is
$(\eta _0,\ldots ,\eta _{m+1})$
.
First, we show that
$\eta _{m+1}\not \geq \eta _0$
—the argument for
$\eta _{m+1}\not \leq \eta _{0}$
is symmetric, in light of Proposition 5.12, and the two together show that we have neither a cycle nor a spiral. Note that since
$m+1<2u$
, we have
$m+1-u<u$
. It follows immediately that
$\eta _0\mathbin {\wedge } \eta _u>\eta _0\mathbin {\wedge } \eta _{m+1-u}$
, and by Proposition 5.12, it also follows that
$\eta _{m+1}\mathbin {\wedge } \eta _{m+1-u}>\eta _{m+1}\mathbin {\wedge } \eta _u$
. This clearly implies that either
$\eta _0\mathbin {\wedge } \eta _{m+1-u}< \eta _{m+1}\mathbin {\wedge } \eta _{m+1-u}$
or
$\eta _{m+1}\mathbin {\wedge } \eta _u< \eta _0\mathbin {\wedge } \eta _u$
(having in mind that the two sides of each inequality are comparable by semilinearity).
Suppose first that
$\eta _0\mathbin {\wedge } \eta _{m+1-u}< \eta _{m+1}\mathbin {\wedge } \eta _{m+1-u}$
. By Fact 2.19,
$\eta _0\mathbin {\wedge } \eta _{m+1-u}=\eta _0\mathbin {\wedge } \eta _{m+1}$
. But note that since
$\eta $
is a quasi-cycle (and
$m+1-u\leq n$
),
$\eta _0\mathbin {\wedge } \eta _{m+1-u}<\eta _0$
, so it follows that
$\eta _0\not \leq \eta _{m+1}$
. Otherwise, if
$\eta _{m+1}\mathbin {\wedge } \eta _u< \eta _0\mathbin {\wedge } \eta _u$
, then analogously
$\eta _{m+1}\mathbin {\wedge } \eta _u=\eta _0\mathbin {\wedge } \eta _{m+1}=\eta _0\mathbin {\wedge } \eta _u\mathbin {\wedge } \eta _{m+1}$
, and since
$\eta _0>\eta _0\mathbin {\wedge } \eta _u$
(because
$\eta $
is a quasi-cycle), we have
$\eta _0>\eta _0\mathbin {\wedge } \eta _u\mathbin {\wedge } \eta _{m+1}=\eta _0\mathbin {\wedge } \eta _{m+1}$
, so
$\eta _{m+1}\not \geq \eta _0$
.
Now, if, in addition, we have that m is odd, i.e.,
$m+1=2c$
for some
$c<u$
, then we need to show that
$(*)\eta _0\mathbin {\wedge } \eta _c=\eta _c\mathbin {\wedge } \eta _{2c}$
. Since
$c<u\leq m=2c-1$
, we have
$2c>u$
, so
$c>u-c$
, whence
$m=2c-1\geq 2(u-c)$
. Thus, by the induction hypothesis,
$\eta _0\mathbin {\wedge }\eta _{u-c}=\eta _{u-c}\mathbin {\wedge } \eta _{2u-2c}$
. On the other hand,
$0<u-c<u$
, so
$\eta _0\mathbin {\wedge } \eta _{u-c}<\eta _0\mathbin {\wedge } \eta _u$
, whence
$\eta _0\mathbin {\wedge } \eta _{u-c}=\eta _u\mathbin {\wedge } \eta _{u-c}$
, so
$\eta _u\mathbin {\wedge } \eta _{u-c}=\eta _{u-c}\mathbin {\wedge } \eta _{2u-2c}$
. By applying
$f^{2c-u}$
, we obtain
$(**)\eta _{2c}\mathbin {\wedge } \eta _c=\eta _c\mathbin {\wedge } \eta _u$
. But since
$c<u$
, we have also
$\eta _0\mathbin {\wedge } \eta _c<\eta _0\mathbin {\wedge } \eta _u$
, so by another application of Fact 2.19,
$(***)\eta _0\mathbin {\wedge } \eta _c=\eta _u\mathbin {\wedge } \eta _c$
.
$(**)$
and
$(***)$
together imply
$(*)$
, which shows that
$(\eta _0,\ldots ,\eta _{2u-1})$
is a quasi-cycle, completing the proof of the claim. Claim
We will show that
$\bar \eta =(\eta _0,\ldots ,\eta _{2u-1},\eta _0)$
is a partial orbit (which is clearly sufficient).
In light of the claim, we may assume that
$n=2u-1$
. By Remark 5.9, to complete the proof, it is enough to show that
$ \operatorname {\mathrm {qftp}}(\eta _0/\eta _1,\ldots ,\eta _{2u-1})= \operatorname {\mathrm {qftp}}(\eta _{2u}/\eta _1,\ldots ,\eta _{2u-1})$
. Since
$(\eta _0,\ldots ,\eta _n)$
is a quasi-cycle, it follows that
$\eta _0,\eta _u>\eta _0\mathbin {\wedge }\eta _u$
, and hence also
$\eta _u,\eta _{2u}>\eta _{u}\mathbin {\wedge }\eta _{2u}$
. We will show that for every
$1\leq i,j\leq n$
, we have that
$b:=\eta _i\mathbin {\wedge } \eta _j<\eta _0\mathbin {\wedge } \eta _u$
if and only if
$b<\eta _u$
, if and only if
$b<\eta _u\mathbin {\wedge } \eta _{2u}$
. Since
$\eta $
is a quasi-cycle, it easily follows that we cannot have
$b>\eta _u$
, so by Fact 2.25 (with
$a=\eta _u$
and
$b^{\prime }$
equal to
$\eta _0\mathbin {\wedge } \eta _u$
or
$\eta _u\mathbin {\wedge } \eta _{2u}$
, using Proposition 5.12), it will follow that the types are equal as required.
It is clear that if
$b<\eta _0\mathbin {\wedge } \eta _u$
or
$b<\eta _u\mathbin {\wedge } \eta _{2u}$
, then
$b<\eta _u$
, so suppose that
$b<\eta _u$
, and let us show that
$b<\eta _u\mathbin {\wedge } \eta _{2u}$
and
$b<\eta _0\mathbin {\wedge } \eta _{u}$
. Note that if
$b=\eta _i\mathbin {\wedge } \eta _j$
, then by Fact 2.19, it follows that either
$b=\eta _u\mathbin {\wedge } \eta _i$
or
$b=\eta _u\mathbin {\wedge } \eta _j$
. Without loss of generality we may assume the former.
Now, since
$b\neq \eta _u$
, we have
$i\neq u$
. Let us consider the case when
$i>u$
(the other case is analogous). Write k for
$i-u$
, so that
$i=u+k$
. Clearly,
$\eta _0\mathbin {\wedge } \eta _u>\eta _0\mathbin {\wedge } \eta _k$
, so
$\eta _u\mathbin {\wedge } \eta _{2u}>\eta _{u+k}\mathbin {\wedge } \eta _u=\eta _i\mathbin {\wedge } \eta _u$
. Furthermore,
$0<k<u$
, so
$\eta _0\mathbin {\wedge } \eta _u>\eta _0\mathbin {\wedge } \eta _{u-k}$
, so
$\eta _0\mathbin {\wedge } \eta _{u-k}=\eta _u\mathbin {\wedge } \eta _{u-k}$
. whence
$\eta _k\mathbin {\wedge } \eta _u=\eta _{u+k}\mathbin {\wedge } \eta _u$
. But
$\eta _0\mathbin {\wedge } \eta _u>\eta _0\mathbin {\wedge } \eta _k$
, so
$\eta _0\mathbin {\wedge } \eta _k=\eta _u\mathbin {\wedge } \eta _k=\eta _{u+k}\mathbin {\wedge } \eta _u=\eta _i\mathbin {\wedge } \eta _u$
(since
$u+k=i$
) and we are done.⊣
Proposition 5.14. Let
$\eta =(\eta _0,\ldots ,\eta _n)$
be a quasi-cycle with pseudo-period u.
Then if
$i,j,k\in \{0,\ldots ,n\}$
satisfy
$i\equiv j\pmod u$
and
$k\neq i,j$
, then
$\eta _i\mathbin {\wedge } \eta _k=\eta _j\mathbin {\wedge } \eta _k$
.
Proof By Proposition 5.12, we may assume that
$j<k$
. Indeed, otherwise, if
$j>k$
, then we can simply consider
$\eta ^{-1}$
—this preserves u, but reverses the order of
$\eta _j$
and
$\eta _k$
in the orbit. Further, we may also assume without loss of generality that
$j<i$
(otherwise, if
$i<j<k$
, we can just swap i and j; the case of
$i=j$
is trivial). Moreover, it is enough to consider the case when
$j=0$
(truncating
$\eta $
if necessary). This leaves us with some
$i,k>0$
such that
$i\neq k$
and u divides i, and we need to show that
$\eta _0\mathbin {\wedge } \eta _k=\eta _i\mathbin {\wedge } \eta _k$
.
By Proposition 5.13, we have a finite partial automorphism p such that
$\eta $
is an orbit of p and
$p^u(\eta _0\mathbin {\wedge } \eta _u)=\eta _0\mathbin {\wedge } \eta _u$
. Let
$f\supseteq p$
be a total meet-tree automorphism.
Claim. If
$0<m\leq n$
, then
$\eta _0\mathbin {\wedge } \eta _m=\eta _0\mathbin {\wedge } \eta _u$
if and only if u divides m.
Proof Suppose first that u divides m, so
$m=lu$
. The proof is by induction with respect to l. Since
$\eta $
is a quasi-cycle, we have that
$\eta _{lu-u}\mathbin {\wedge } \eta _{lu}=\eta _{lu-2u}\mathbin {\wedge } \eta _{lu-u}=\cdots =\eta _0\mathbin {\wedge } \eta _u$
, so in particular,
$\eta _0\mathbin {\wedge } \eta _u=\eta _{lu-u}\mathbin {\wedge } \eta _{lu}$
. By the induction hypothesis,
$\eta _0\mathbin {\wedge }\eta _u=\eta _0\mathbin {\wedge } \eta _{lu-u}$
, so
$\eta _0\mathbin {\wedge }\eta _{lu-u}=\eta _{lu-u}\mathbin {\wedge } \eta _{lu}$
. By Fact 2.19, it follows that
$\eta _0\mathbin {\wedge } \eta _{lu}\geq \eta _0\mathbin {\wedge } \eta _{lu-u}=\eta _0\mathbin {\wedge } \eta _u$
. Since by the definition of u,
$\eta _0\mathbin {\wedge } \eta _u\geq \eta _0\mathbin {\wedge } \eta _{lu}$
, this completes the proof.
Now, suppose
$\eta _0\mathbin {\wedge } \eta _m=\eta _0\mathbin {\wedge } \eta _u$
. Let l be maximal such that
$lu\leq m$
. Then, by the preceding paragraph,
$\eta _0\mathbin {\wedge } \eta _{lu}=\eta _0\mathbin {\wedge } \eta _{u}$
, so by Fact 2.19,
$\eta _{lu}\mathbin {\wedge } \eta _m\geq \eta _0\mathbin {\wedge } \eta _u$
. Now,
$\eta _0\mathbin {\wedge } \eta _u$
is a fixed point of
$f^u$
, and hence also of
$p^{-lu}$
. By applying
$f^{-lu}$
to the last inequality, we obtain
$f^{-lu}(\eta _{lu}\mathbin {\wedge } \eta _m)=\eta _0\mathbin {\wedge } \eta _{m-lu}\geq \eta _0\mathbin {\wedge } \eta _u$
. But
$m-lu<u$
, so by minimality of u, we have that
$m-lu=0$
, so
$m=lu$
. Claim
Now, by Claim, we have
$\eta _0\mathbin {\wedge } \eta _i=\eta _0\mathbin {\wedge } \eta _u\geq \eta _0\mathbin {\wedge } \eta _k$
. If the inequality is strict, by Fact 2.19,
$\eta _0\mathbin {\wedge } \eta _k=\eta _i\mathbin {\wedge } \eta _k$
and we are done. Otherwise, by Claim, u divides k and
$\eta _0\mathbin {\wedge } \eta _k=\eta _0\mathbin {\wedge } \eta _u$
, so we need to show that
$\eta _i\mathbin {\wedge } \eta _k=\eta _0\mathbin {\wedge } \eta _u$
.
We have that u divides
$k-i$
so by Claim, we have
$\eta _0\mathbin {\wedge } \eta _{\lvert k-i\rvert }=\eta _0\mathbin {\wedge } \eta _u$
. Since
$\eta _0\mathbin {\wedge } \eta _u$
is a fixed point of
$p^u$
and u divides
$i,k$
(and hence also
$\min (i,k)$
),
$\eta _0\mathbin {\wedge } \eta _u$
is also a fixed point of
$p^{\min (i,k)}$
, so we have that
$$\begin{align*}\eta_i\mathbin{\wedge} \eta_k\kern1pt{=}\kern1pt\eta_{\min(i,k)}\mathbin{\wedge} \eta_{\min(i,k)+\lvert k-i\rvert}=p^{\min(i,k)}(\eta_0\mathbin{\wedge} \eta_{\lvert k-i\rvert})\kern1pt{=}\kern1pt p^{\min(i,k)}(\eta_0\mathbin{\wedge} \eta_u)\kern1pt{=}\kern1pt\eta_0\mathbin{\wedge} \eta_u, \end{align*}$$
so we are done.⊣
The next two corollaries are related to Question 5.17, and they are not necessary to prove the main result of the paper, Theorem 6.8.
Corollary 5.15. If
$\eta =(\eta _0,\ldots ,\eta _n)$
is a quasi-cycle with pseudo-period u, and
$N>n$
is minimal such that u divides N, then every extension
$\bar \eta =(\eta _0,\ldots ,\eta _{N-1})$
is also a quasi-cycle with pseudo-period u.
Proof The case of
$N=2u$
is the claim in the proof of Proposition 5.13, so we may assume that
$n\geq 2u$
.
First, we will show that the pseudo-period is indeed u. Take any
$m\in (n,N)$
. Then u does not divide m and
$2u\leq n<m< n+u$
, so
$(\eta _u,\ldots ,\eta _m)$
is a quasi-cycle with pseudo-period u; take
$m^{\prime }\equiv m \pmod u$
such that
$u<m^{\prime }<2u$
, so that Proposition 5.14 implies that
$\eta _u\mathbin {\wedge } \eta _m=\eta _u\mathbin {\wedge } \eta _{m^{\prime }}$
, so
$\eta _u\mathbin {\wedge } \eta _m=\eta _u\mathbin {\wedge } \eta _{m^{\prime }}<\eta _u\mathbin {\wedge } \eta _{2u}$
. Then
$\eta _u\mathbin {\wedge } \eta _{2u}=\eta _0\mathbin {\wedge }\eta _u$
, so
$\eta _u\mathbin {\wedge }\eta _m<\eta _0\mathbin {\wedge }\eta _u$
, and so, by Fact 2.19,
$\eta _0\mathbin {\wedge } \eta _m=\eta _u\mathbin {\wedge }\eta _m<\eta _0\mathbin {\wedge }\eta _u$
.
Now, we will show that
$(\eta _0,\ldots ,\eta _m)$
is a quasi-cycle by induction with respect to
$m\geq n$
. The case of
$m= n$
is clear. Suppose now that
$n<m<N-1$
and
$(\eta _0,\ldots ,\eta _m)$
is a quasi-cycle (with pseudo-period u). We need to show that so is
$(\eta _0,\ldots ,\eta _{m+1})$
.
It easily follows from the assumption that u does not divide
$m+1$
, so we have some positive
$k\in (u,2u)$
such that
$k\equiv m+1\pmod u$
. By Proposition 5.14, it follows that
$\eta _u\mathbin {\wedge } \eta _{m+1}=\eta _u\mathbin {\wedge } \eta _k<\eta _u\mathbin {\wedge } \eta _{2u}=\eta _0\mathbin {\wedge } \eta _u<\eta _0$
. It follows that
$\eta _{m+1}\not \geq \eta _0$
. The not-inequality
$\eta _{m+1}\not \leq \eta _0$
can be proven similarly, or follows immediately from the above argument by considering the partial orbit
$(\eta _{m+1},\eta _m,\ldots ,\eta _0)$
(and applying Proposition 5.12). In conclusion,
$(\eta _0,\ldots ,\eta _{m+1})$
is not a cycle, and not a spiral. We need to prove that it is not a comb.
Suppose now that m is odd, so
$m+1=2c$
. We need to show that
$\eta _0\mathbin {\wedge } \eta _c=\eta _c\mathbin {\wedge } \eta _{2c}$
. Let
$k<u$
be such that
$k\equiv c\pmod u$
(since u does not divide
$2c$
, we have
$k>0$
, and u divides none of
$k,2k,c,2c$
). Then clearly
$c,k\neq 0$
,
$c\neq 2c$
, and
$k\neq 2k$
, so (since
$\eta _1,\ldots ,\eta _{m+1})$
is a quasi-cycle with pseudo-period u), by Proposition 5.14,
$\eta _c\mathbin {\wedge } \eta _{2c}=\eta _k\mathbin {\wedge } \eta _{2c}=\eta _k\mathbin {\wedge } \eta _{2k}$
. Again by Proposition 5.14,
$\eta _0\mathbin {\wedge } \eta _c=\eta _0\mathbin {\wedge } \eta _k$
. Since
$k<u$
,
$2k<2u\leq n$
, we have
$\eta _0\mathbin {\wedge } \eta _k=\eta _k\mathbin {\wedge } \eta _{2k}$
, whence
$\eta _0\mathbin {\wedge } \eta _c=\eta _c\mathbin {\wedge } \eta _{2c}$
.⊣
Corollary 5.16. If
$\eta =(\eta _0,\ldots ,\eta _n)$
is a quasi-cycle, then it can be extended to a cycle.
Proof Let u be the pseudo-period of
$\eta $
. The case of
$n<2u$
is Proposition 5.13, so we may assume that
$n\geq 2u$
. Let N be as in Corollary 5.15, and let
$(\eta _0,\ldots ,\eta _N)$
be an arbitrary extension of
$\eta $
. We will show that
$(\eta _0,\ldots ,\eta _{N-1},\eta _0)$
is a partial orbit. Write B for the subtree generated by
$\{\eta _1,\ldots ,\eta _{N-1}\}$
. By Remark 5.9, it is enough to show that
$ \operatorname {\mathrm {qftp}}(\eta _0/B)= \operatorname {\mathrm {qftp}}(\eta _N/B)$
. By Corollary 5.15, we may assume without loss of generality that
$N=n+1$
. It follows easily from Proposition 5.14 that for every
$i\in (0,N)$
,
$i\neq u$
we have
$\eta _0\neq \eta _0\mathbin {\wedge } \eta _i=\eta _u\mathbin {\wedge } \eta _i=\eta _N\mathbin {\wedge } \eta _i\neq \eta _N$
. Likewise,
$\eta _0\neq \eta _0\mathbin {\wedge } \eta _u=\eta _u\mathbin {\wedge } \eta _{2u}=\eta _u\mathbin {\wedge } \eta _N\neq \eta _N$
. Using this, the conclusion follows easily from Fact 2.25.⊣
The preceding corollary suggests the following question.
Question 5.17. If p is a finite partial automorphism of a tree, and
$\eta $
is a quasi-cyclic orbit of p, does p admit an extension
$\bar p$
(to a finite partial automorphism, possibly of a larger tree) such that the orbit
$\bar \eta $
of
$\bar p$
containing
$\eta $
is no longer quasi-cyclic?
Corollary 5.16 gives a positive answer under the additional assumption that p has no other orbits besides
$\eta $
. In general, this seems plausible, but we do not know the answer.
Remark 5.18. We believe that Corollary 5.16 can be extended to say the following (with a similar proof). If
$\eta =(\eta _0,\ldots ,\eta _n)$
is a quasi-cycle with pseudo-period u, then
$\eta $
can be extended to exactly the following kinds of finite partial orbits:
-
• a k-cycle,
-
• a quasi-cycle with pseudo-period u (of arbitrary length),
-
• a quasi-cycle with pseudo-period k (of arbitrary length),
-
• both an ascending and a descending spiral of spiral length k (of arbitrary length),
-
• both an ascending and a descending spiral comb of spiral length k (of arbitrary length),
-
• if
$n<2u$
, both an ascending and a descending spiral comb of spiral length u (of arbitrary length).
(Here
$k>n$
is a multiple of u.)
${\lozenge }$
6 Finding determined automorphisms
Recall that
$\mathbf T$
is the universal countable meet-tree.
Definition 6.1. Given a finite partial automorphism p, we call a point
$a\in \operatorname {\mathrm {dom}}(p)$
an initial point of p if
$a\notin \operatorname {\mathrm {range}}(p)$
or a is in a cyclic orbit of p.
${\lozenge }$
Definition 6.2. Given sets
$P,Q$
, a partial function
$p\colon P\to Q$
, an element
${a\in P}$
, and an integer k, we write
$p^k(a){\downarrow }$
if
$a\in \operatorname {\mathrm {dom}}(p^k)$
, i.e., if
$p^k(a)$
is well-defined. Otherwise, we write
$p^k(a){\uparrow }$
(if
$p^k(a)$
is undefined).
When p is fixed in the context, and we have an orbit
$\eta =(\eta _0,\ldots ,\eta _n)$
of p, then we also write
$\eta _m{\downarrow }$
for
$p^m(\eta _0){\downarrow }$
and
$\eta _m{\uparrow }$
for
$p^m(\eta _0){\uparrow }$
.
${\lozenge }$
We want to find a cofinal class of determined finite partial automorphisms. In order to do that, we introduce the following notion of a pseudo existentially closed partial automorphism of
$\mathbf T$
. The idea is that “any behavior” of orbits of p in extensions is already “witnessed” in p, and if possible, we want this to be witnessed at least twice (for technical reasons). This idea is made a bit more precise in Proposition 6.5.
Definition 6.3. Let p be a finite partial automorphism of
$\mathbf T$
. We say that p is pseudo existentially closed (PEC) (in
$\mathbf T$
) if it satisfies the following condition.
For every extension
$q\supseteq p$
to a partial automorphism of
$\mathbf T$
, every triple
$\eta _0,\mu _0,\zeta _0$
of initial points of p (cf. Definition 6.1) in orbits
$\eta ,\mu ,\zeta $
(respectively) of p, and every
$m_1,m_2>0$
such that
$q^{m_1}(\mu _0){\downarrow },q^{m_2}(\zeta _0){\downarrow }$
, there exist (strictly) positive integers
$m_1^{\prime },m_2^{\prime },m_1^{\prime \prime },m_2^{\prime \prime }$
such that:
-
• if
$\mu _{m_1}{\uparrow }$
Footnote
3
, then
$m_1^{\prime }\neq m_1^{\prime \prime }$
, -
• the triples
$(\eta _0,q^{m_1}(\mu _0),q^{m_2}(\zeta _0))$
,
$(\eta _0,\mu _{m_1^{\prime }},\zeta _{m_2^{\prime }})$
, and
$(\eta _0,\mu _{m_1^{\prime \prime }},\zeta _{m_2^{\prime \prime }})$
are well-defined, and all have the same quantifier-free type (in
$\mathbf T$
; in particular, they have the same order type), -
• if there is some k such that
$\mu _0\mathbin {\wedge } q^k(\mu _0)\neq q^k(\mu _0)\mathbin {\wedge } q^{2k}(\mu _0)$
(in particular,
$q^{2k}(\mu _0){\downarrow }$
), then for minimal such k, we have
$m_1\equiv m_1^{\prime }\equiv m_1^{\prime \prime }\pmod k$
. (Notice that in Proposition 6.5
(1) we show that in this case,
$\mu $
must be a spiral and k is its spiral length.)
${\lozenge }$
Now we show that all finite partial automorphisms admit “PEC closure” (note that it is not canonical, in particular it is not a closure operator, hence the scare quotes).
Proposition 6.4. Every finite partial automorphism of
$\mathbf T$
can be extended to a finite pseudo existentially closed
$($
PEC
$)$
partial automorphism.
Proof Take any partial automorphism p. We extend it in three steps:
-
1. Given an orbit
$\eta $
of p, if in some extension
$f\supseteq p$
,
$\eta $
is extended to an orbit which is not a quasi-cycle, then we extend
$\eta $
so that it is witnessed already in the corresponding extension of p; we repeat that for each orbit of p. -
2. For each triple
$\eta _0,\mu _0,\zeta _0$
of initial points of p, each residue mod the spiral length k of
$\mu $
(if it exists, i.e.,
$\mu $
is a spiral or a comb) and each quantifier-free type
$r(x,y,z)$
, we check whether for some
$f\supseteq p$
there are
$m_1,m_2$
(with
$m_1$
having the appropriate residue mod k, if
$\mu $
is a spiral or a comb) such that
$\models r(\eta _0,f^{m_1}(\mu _0),f^{m_2}(\zeta _0))$
. If the answer is yes, we extend
$\mu $
and
$\zeta $
to already contain witnesses
$\mu _{m_1^{\prime }},\zeta _{m_2^{\prime }}$
for that. -
3. We repeat the previous step, only this time, checking whether it is possible to have two witnesses
$(\mu _{m_1^{\prime }},\zeta _{m_2^{\prime }})$
and
$(\mu _{m_1^{\prime \prime }},\zeta _{m_2^{\prime \prime }})$
with
$m_1^{\prime }\neq m_1^{\prime \prime }$
.
This procedure terminates: we never add any new orbits in any of the steps, so step 1 finishes. After step 1, the set of initial points is fixed (because there are no new orbits, and step 1 ensures that there can be no new cycles), as are the spiral lengths of all the relevant orbits, so in each of steps 2 and 3 there is only a finite number of conditions to check.
It is fairly easy to check that after the three steps, we obtain a PEC partial automorphism. Step 1 guarantees that the minimal k checked in the last bullet of Definition 6.3 is simply the spiral length of
$\mu $
. Step 2 provides the witness
$(m_1^{\prime },m_2^{\prime })$
required in the second bullet. Finally, at this point, the hypothesis of the first bullet of Definition 6.3 implies that
$m_1\neq m_1^{\prime }$
, so by the third step, we also have
$(m_1^{\prime \prime },m_2^{\prime \prime })$
with
$m_1^{\prime }\neq m_1^{\prime \prime }$
(otherwise, we can just take
$m_1^{\prime \prime }=m_1^{\prime }$
and
$m_2^{\prime \prime }=m_2^{\prime }$
).⊣
Proposition 6.5. If p is PEC and
$\eta ,\mu $
are orbits of p, while
$f\supseteq p$
is contained in some
$\bar f\in \operatorname {\mathrm {Aut}}(\mathbf T)$
(in particular, if f is a finite partial automorphism of
$\mathbf T$
), then
$:$
-
(1) if the f-orbit containing
$\eta $
is neither a quasi-cycle nor a cycle, then there is some k such that
$\eta _{2k}{\downarrow }$
and
$\eta _0\mathbin {\wedge } \eta _k\neq \eta _k\mathbin {\wedge } \eta _{2k}$
(note that even if
$\eta $
is not a comb, by Proposition 5.7
$(3)$
, it follows that the minimal such k is the spiral length of
$\eta $
), -
(2) if the f-orbit containing
$\eta $
is a k-cycle, k-spiral
$($
ascending or descending
$)$
, k-comb
$($
ascending or descending
$)$
, or a quasi-cycle
$($
respectively
$)$
, then so is
$\eta $
(respectively), -
(3) if
$\eta ,\mu $
are distinct, then so are the f-orbits extending them.
Proof We may assume without loss of generality that
$f=\bar f\in \operatorname {\mathrm {Aut}}(\mathbf T)$
. Write
$\bar \eta $
for the f-orbit extending
$\eta $
, enumerated as
$(\bar \eta _i)_{i\in \mathbf Z}$
so that
$\eta _0=\bar \eta _0$
and
$f(\bar \eta _i)=\bar \eta _{i+1}$
. Likewise, let
$\bar \mu \supseteq \mu $
be the f-orbit containing
$\mu $
.
For (1), since
$\bar \eta $
is not a quasi-cycle, there is some k such that
$\eta _0\mathbin {\wedge } \bar \eta _k\neq \bar \eta _k\mathbin {\wedge } \bar \eta _{2k}$
. We may assume without loss of generality that this k is minimal. We claim that
$\eta _{2k}{\downarrow }$
, whence
$\bar \eta _k=\eta _k$
and
$\bar \eta _{2k}=\eta _{2k}$
and we are done. Otherwise, suppose towards contradiction that
$\eta _{2k}{\uparrow }$
, and apply PEC with
$m_1=2k$
,
$m_2=k$
(and
$\eta =\mu =\zeta = \eta $
) and conclude that there positive
$m_1^{\prime },m_2^{\prime },m_1^{\prime \prime },m_2^{\prime \prime }$
with
$m_1^{\prime }\equiv m_1^{\prime \prime }\equiv 2k\pmod k$
such that
$\eta _{m_1^{\prime }}{\downarrow },\eta _{m_1^{\prime \prime }}{\downarrow }$
. But since
$m_1^{\prime },m_1^{\prime \prime }$
are distinct and positive, it follows that
$\max (m_1^{\prime },m_1^{\prime \prime })\geq 2k$
, so
$\eta _{2k}{\downarrow }$
, a contradiction.
For (2), suppose first that
$\bar \eta $
is a k-spiral or a k-cycle, so
$\eta _0$
is comparable to
$\bar \eta _k$
. We claim that
$\eta _k{\downarrow }$
, whence
$\bar \eta _k=\eta _k$
and we are done. Indeed, by PEC (with
$m_1=m_2=k$
), there is some
$m_1^{\prime }>0$
such that
$\eta _{m_1^{\prime }}{\downarrow }$
and
$ \operatorname {\mathrm {otp}}(\eta _0,\eta _{m_1^{\prime }})= \operatorname {\mathrm {otp}}(\eta _0,\bar \eta _k)$
. But then
$\eta _{m_1^{\prime }}=\bar \eta _{m_1^{\prime }}$
is comparable to
$\eta _0=\bar \eta _0$
, so by definition of a k-cycle or k-spiral,
$m_1^{\prime }\geq k$
, so
$\eta _{k}{\downarrow }$
.
Otherwise, if
$\bar \eta $
is a k-comb, then it is not a quasi-cycle, so
$\eta $
is not a quasi-cycle by (1). Since
$\bar \eta $
is not a cycle, nor a spiral, neither is
$\eta $
, so it is an l-comb, whence
$\bar \eta $
is an l-comb, so
$l=k$
.
Finally, if
$\bar \eta $
is a quasi-cycle, then by Remark 5.5, so is
$\eta $
, completing the proof of (2).
Finally, (3) is immediate by PEC: if
$\bar \eta _{m_1}=\bar \mu _{m_2}$
, then we have some
$m_1^{\prime },m_2^{\prime }$
such that
$\eta _{m_1^{\prime }}=\mu _{m_2^{\prime }}$
.⊣
Remark 6.6. It is easy to see that an immediate extension (in the sense of Definition 4.8) of a PEC automorphism of
$\mathbf T$
is itself PEC (because the initial points are the same, since there can be no new cycles, no new orbits, and we only extend existing orbits positively).
${\lozenge }$
Remark 6.7. Note that if the answer to Question 5.17 is positive, then it follows by Proposition 6.5
(2) that a PEC partial automorphism has no quasi-cyclic orbits. This would make the proof of Theorem 6.8 below a bit simpler—namely, we could drop the final three paragraphs of the proof, and we would no longer need Proposition 5.14.
${\lozenge }$
The following theorem is one of the main building blocks of the proof that the universal countable meet-tree has a generic automorphism.
Theorem 6.8. Let p be a PEC finite partial automorphism of
$\mathbf T$
, and A the meet-tree generated by the union of all orbits of p.
Let
$\xi =(\xi _0,\xi _1,\ldots ,\xi _n)$
be an orbit of p such that no non-cyclic orbit of p has smaller length.
Then if
$p\cup \{(\xi _n, v)\}$
and
$p\cup \{(\xi _n,w)\}$
are both extensions of p to a partial automorphism of
$\mathbf T$
, then
$ \operatorname {\mathrm {tp}}(v/A)= \operatorname {\mathrm {tp}}(w/A)$
.
Note that in the context of the theorem, both
$p\cup \{(\xi _n, v)\}$
and
$p\cup \{(\xi _n,w)\}$
are immediate extensions of p in the sense of Definition 4.8, which will allow us to apply Lemma 4.11.
Proof Put
$B:=\langle \operatorname {\mathrm {range}}(p)\rangle $
,
$p_v:=p\cup \{(\xi _n,v)\}$
, and
$p_w:=p\cup \{(\xi _n,w)\}$
. Note that the conclusion is trivially true if
$\xi $
is a cycle, so in the rest of the proof, we assume that
$\xi $
is not a cycle, and so
$\xi _{n+1}{\uparrow }$
. Furthermore,
$ \operatorname {\mathrm {tp}}(v/ \operatorname {\mathrm {range}}(p))=p( \operatorname {\mathrm {tp}}(\xi _n/ \operatorname {\mathrm {dom}}(p)))= \operatorname {\mathrm {tp}}(w/ \operatorname {\mathrm {range}}(p))$
, and hence
$ \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(w/B)$
.
Claim 1. For every
$\eta _i\in \operatorname {\mathrm {dom}}(p)$
, we have
$ \operatorname {\mathrm {tp}}(\eta _i/B) \neq \operatorname {\mathrm {tp}}(v/B)$
.
Proof Suppose towards contradiction that
$ \operatorname {\mathrm {tp}}(\eta _i/B) = \operatorname {\mathrm {tp}}(v/B)$
. First, we show that in this case
$p\cup \{(\xi _n,\eta _i)\}$
is a partial automorphism. Let
$\bar c$
enumerate
$ \operatorname {\mathrm {dom}}(p)$
. Let
$\varphi (x,\bar c)$
be a quantifier-free formula. We need to show that if
$\varphi (\xi _n,\bar c)$
holds, then so does
$\varphi (\eta _i,p(\bar c))$
. But since
$p_v$
is a partial automorphism,
$\varphi (\xi _n,\bar c)$
holds if and only if
$\varphi (v,p(\bar c))$
holds. But this is true if and only if
$\varphi (x,p(\bar c))\in \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(\eta _i/B)$
, i.e.,
$\varphi (\eta _i,p(\bar c))$
holds.
Now, if
$\eta =\xi $
and
$p\cup \{(\xi _n,\eta _i)\}$
is a partial automorphism, it means that
$\xi $
can be turned into a cycle in an extension of p. Since we have assumed
$\xi $
is not already a cycle, this contradicts Proposition 6.5
(2). Otherwise, if
$\eta \neq \xi $
and
$p\cup \{(\xi _n,\eta _i)\}$
is a partial automorphism, we contradict Proposition 6.5
(3). Claim
Let
$v^{\prime }:= \max _{b\in B} b\mathbin {\wedge } v$
and likewise,
$w^{\prime }:=\max _{b\in B} b\mathbin {\wedge } w$
.
Claim 2.
$ \operatorname {\mathrm {tp}}(v/A)= \operatorname {\mathrm {tp}}(w/A)$
if and only if
$v^{\prime }$
and
$w^{\prime }$
have the same order type over
$A_{\leq b}$
for some
$b\geq v^{\prime },w^{\prime }$
.
Proof We have that
$v'=\max _{a\in A} a\mathbin {\wedge } v$
. Indeed, otherwise, we would have
$a\mathbin {\wedge } v>v'$
for some
$a\in A\setminus B$
, and hence also for some
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus \operatorname {\mathrm {range}}(p)$
(namely, any such that
$\eta _0\geq a$
), we would have would have
$\eta _0\mathbin {\wedge } v>v^{\prime }$
, and so, by Corollary 2.26,
$ \operatorname {\mathrm {tp}}(\eta _0/B)= \operatorname {\mathrm {tp}}(v/B)$
, Claim 1. Analogously,
$w'=\max _{a\in A} a\mathbin {\wedge } w$
.
Furthermore,
$v=v'$
holds if and only if
$w=w'$
: these hold if and only if for some
$b\in B$
, the type
$ \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(w/B)$
implies
$b\geq x$
. Thus, the conclusion follows by Fact 2.25. Claim
If
$v^{\prime }\in B$
, then
$ \operatorname {\mathrm {tp}}(v/B)$
contains a formula
$\varphi (x,B)$
which says “
$x\geq v^{\prime }$
and
$v^{\prime }=\max _{b\in B} x\mathbin {\wedge } b$
”. Since
$ \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(w/B)$
, we conclude w also satisfies this formula, so
$v'=w'$
, and in particular, they have the same order type over A, so by Claim 2,
$ \operatorname {\mathrm {tp}}(v/A)= \operatorname {\mathrm {tp}}(w/A)$
, completing the proof.
By the preceding paragraph, for the rest of the proof, we may assume that
$v'\notin B$
. Note that as we have seen in the proof of Claim 2, we have that
$v=v'$
if and only
$w=w'$
, and analogously, since
$v'\notin B$
, we have
$w'\notin B$
. We will treat separately the cases when
$v=v'\notin B$
and
$v\neq v'\notin B$
, but first, we make some observations that apply to both of them.
Put
$\alpha :=\max \{b\in B\mid b\leq v' \}$
(
$-\infty $
if the set is empty), and choose
$\beta \in B$
to be minimal above
$v'$
, so
$\beta \geq v'$
and
$(v',\beta )\cap B=\emptyset $
. Then
$v'\in (\alpha ,\beta )$
and
$(\alpha ,\beta )\cap B=\emptyset $
. Note that
$\beta \mathbin {\wedge } v=v'$
. Indeed,
$\beta \mathbin {\wedge } v\leq v'$
by definition of
$v'$
, and since
$\beta \geq v'$
and
$v\geq v'$
, also
$\beta \mathbin {\wedge } v\geq v'$
. Since
$ \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(w/B)$
, it follows that
$w'\in (\alpha ,\beta )$
and
$w'=w\mathbin {\wedge } \beta $
. Notice that analogously, for every
$b\in B$
such that
$b\geq \beta $
, we have also
$b\wedge v=v'$
and
$b\wedge w=w'$
.
In the analysis of the two cases, we will use the
$\alpha $
and
$\beta $
heavily.
Claim 3. Every element of
$A\cap (\alpha ,\beta )$
is of the form
$\eta _0\mathbin {\wedge } \beta $
for some
${\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B}$
.
Proof Let
$a\in A\cap (\alpha ,\beta )$
. Then for some
$\eta ,\mu ,i,j$
we have
$a=\eta _i\mathbin {\wedge }\mu _j$
. Since
$a<\beta $
, we have
$\eta _i\mathbin {\wedge } \beta \geq a$
and
$\mu _j\mathbin {\wedge } \beta \geq a$
. By Fact 2.19, only one of these inequalities can be strict. Suppose without loss of generality that
$\eta _i\mathbin {\wedge } \beta = a$
. Since
$a\in (\alpha ,\beta )$
, it follows that
$a\notin B$
, so (because
$\beta \in B$
)
$\eta _i\notin B$
, so also
$\eta _i\notin \operatorname {\mathrm {range}}(p)$
, whence
$\eta _i\in \operatorname {\mathrm {dom}}(p)$
, which completes the proof. Claim
Since
$v',w'\in (\alpha ,\beta )$
, by Claims 2 and 3, it is enough to show that for every
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B$
, at least two of the following hold:
-
(i)
$\eta _0\mathbin {\wedge } \beta \leq v'$
if and only if
$\eta _0\mathbin {\wedge } \beta \leq w'$
, -
(ii)
$\eta _0\mathbin {\wedge } \beta \geq v'$
if and only if
$\eta _0\mathbin {\wedge } \beta \geq w'$
, -
(iii)
$\eta _0\mathbin {\wedge } \beta = v'$
if and only if
$\eta _0\mathbin {\wedge } \beta =w'$
,
because any two of these conditions imply that
$v',w'$
have the same order type over
$(\alpha ,\beta )\cap A$
, and hence also over
$A_{\leq \beta }$
.
Now, if
$\eta _0\wedge \beta \notin (\alpha ,\beta )$
, then it is clear that these equivalences hold (because
$v',w'\in (\alpha ,\beta )$
). Hence, for the rest of the proof, let us fix an arbitrary
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B$
such that
$\eta _0\wedge \beta \in (\alpha ,\beta )$
. The goal is to show that for this
$\eta _0$
, two of the above three equivalences hold.
Case 1.
$v' = v \notin B$
.
If
$\eta _0\mathbin {\wedge } \beta \geq v'$
, then trivially
$\eta _0 \geq v$
. Since
$p_v$
extends p (as a partial automorphism of
$\mathbf T$
),
$v=p_v^{n+1}(\xi _0)$
and
$\xi _{n+1}{\uparrow }$
, by Definition 6.3 (applied to
$m_1=m_2=n+1$
,
$q=p_v$
), there are
$i<j\leq n$
such that
$\xi _i,\xi _j\leq \eta _0$
, and hence they are comparable. Since
$\xi $
is not a cycle, it follows that it must be a spiral (see Definition 5.3 to recall the orbit types). Thus, if
$\xi $
is not a spiral, then for all
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B$
we have
$\eta _0\mathbin {\wedge } \beta <v'$
and analogously,
$\eta _0\mathbin {\wedge } \beta <w'$
.
By the preceding paragraph, we may assume that
$\xi $
is spiral, of spiral length k for some k. We will show (*) that
$\eta _0\mathbin {\wedge } \beta \geq v$
(equivalently,
$\eta _0\geq v$
) if and only if
$\eta _0\geq \xi _{n+1-k}$
(and so, by symmetry,
$\eta _0\mathbin {\wedge }\beta \geq w$
if and only if
$\eta _0\geq \xi _{n+1-k}$
).
Suppose first that
$\xi $
is descending. Then
$v< \xi _{n+1-k}$
, so if
$\eta _0\geq \xi _{n+1-k}$
, then trivially
$\eta _0\geq v$
. Conversely, if
$\eta _0\geq v$
, then by Definition 6.3 (and the equality
$v=p_v^{n+1}(\xi _0)$
), for some
$i\equiv n+1\pmod k$
, we have
$\eta _0\geq \xi _i$
. Since
$i\equiv n+1\equiv n+1-k\pmod k$
and
$\xi $
is descending,
$\xi _i\geq \xi _{n+1-k}$
and so
$\xi _{n+1-k}\leq \eta _0$
.
Otherwise, suppose
$\xi $
is ascending. Then
$v>\xi _{n+1-k}$
, so if
$\eta _0\geq v$
, then trivially
$\eta _0\geq \xi _{n+1-k}$
. Conversely, if
$ \eta _0\not \geq v$
, then again by Definition 6.3, there is some
$i\equiv n+1\pmod k$
,
$i\leq n$
, such that
$\xi _i\not \leq \eta _0$
, and as before, we have
$\xi _i\leq \xi _{n+1-k}$
, so
$\xi _{n+1-k}\not \leq \eta _0$
, completing the proof of (*), which shows (ii).
To complete the proof in this case, it is enough to show (iii), i.e., that given
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B$
, we have
$\eta _0\mathbin {\wedge } \beta =v$
if and only if
$\eta _0\mathbin {\wedge } \beta =w$
. We will show that these equalities are impossible (given that
$\xi $
is spiral and
$v=v'\notin B$
, and hence
$w=w'\notin B$
). Notice that for some
$\mu _i\in \operatorname {\mathrm {range}}(p)$
(so without loss of generality,
$i>0$
) we have that
$\mu _i\geq \beta $
. Since
$\beta =\mu _i\mathbin {\wedge }\beta>\beta \mathbin {\wedge }\eta _0$
, by Fact 2.19, it follows that
$\beta \mathbin {\wedge }\eta _0=\mu _i\mathbin {\wedge }\eta _0$
.
Suppose
$\xi $
is a descending k-spiral and
$\eta _0\mathbin {\wedge } \beta =v$
. By Definition 6.3 (with
$q=p_v$
,
$m_1=n+1$
,
$m_2=i$
), there is some
$j\equiv n+1\pmod k$
and
$i'>0$
such that
$\eta _0\mathbin {\wedge } \mu _{i'}=\xi _j$
. Since
$\xi $
is descending,
$\xi _j>v$
, so
$\eta _0\mathbin {\wedge }\mu _{i'}>\eta _0\mathbin {\wedge } \mu _i=v$
, and by Fact 2.19, we have that
$v=\eta _0\mathbin {\wedge } \mu _i=\mu _i\mathbin {\wedge } \mu _{i'}$
. Since
$i,i'>0$
, it follows that
$v\in B$
, a contradiction.
Now, suppose
$\xi $
is an ascending k-spiral and
$\eta _0\mathbin {\wedge } \beta =v$
. Arguing as in the preceding paragraph, we conclude that for some
$j\equiv n+1\pmod k$
and a positive
$i'$
we have
$\eta _0\mathbin {\wedge } \mu _{i'}=\xi _j$
. We may assume without loss of generality that
$i'$
is maximal (i.e., for all
$i^{\prime \prime }>i'$
there is no
$j'\equiv n+1\pmod k$
such that
$\eta _0\mathbin {\wedge } \mu _{i^{\prime \prime }}=\xi _{j'}$
).
We claim that
$i'\leq i-k$
. Indeed, put
$l:=i'-i$
and let
$f\in \operatorname {\mathrm {Aut}}(\mathbf T)$
be an arbitrary extension of
$p_v$
; note that the f-orbit of
$\xi _j$
is still an ascending k-spiral, and also that
$f^k(\xi _j)\leq f^{n+1-j}(\xi _j)=v\leq \eta _0$
, so in particular,
$f^k(\xi _j)\not \leq \mu _{i'}$
—otherwise,
$f^k(\xi _j)\leq \mu _{i'}\mathbin {\wedge } \eta _0=\xi _j$
, which would contradict the assumption that the f-orbit of
$\xi _j$
is an ascending k-spiral. Since
$\eta _0\mathbin {\wedge } \mu _i=v>\xi _j=\eta _0\mathbin {\wedge } \mu _{i'}$
, we have
$\mu _i\mathbin {\wedge } \mu _{i'}=\xi _j$
, so
$\mu _{i'}\mathbin {\wedge } f^l(\mu _{i'})=f^l(\xi _j)$
. Now,
$\mu _{i'}\geq \xi _j,f^l(\xi _j)$
, so the latter two are comparable, whence k divides l (by Proposition 5.7); this implies that
$f^l(\xi _j)$
and
$f^k(\xi _j)$
are comparable. On the other hand, since
$f^k(\xi _j)\not \leq \mu _{i'}$
and
$f^l(\xi _j)\leq \mu _{i'}$
, we have
$f^l(\xi _j)<f^k(\xi _j)$
, so
$l<k$
. Since k divides l and l cannot be
$0$
, it follows that
$l\leq -k$
.
It follows that in fact
$j=n+1-k$
. Otherwise, if
$j< n+1-k$
, then
$ \xi _{n+1-k}>\xi _j=\mu _i\mathbin {\wedge }\mu _{i'}$
. On the other hand,
$\mu _{i-k}\geq \xi _{n+1-k}$
, so
$\mu _{i-k}\mathbin {\wedge } \mu _i\geq \xi _{n+1-k}$
, and hence
$\mu _{i-k}\mathbin {\wedge } \mu _{i'}=\xi _j$
. It would follow that
$\mu _i\mathbin {\wedge } \mu _{i'+k}=\xi _{j+k}$
. Now,
$\mu _i\mathbin {\wedge } \eta _0=v>\xi _{j+k}$
, so
$\mu _{i'+k}\mathbin {\wedge }\eta _0=\xi _{j+k}$
, contradicting the maximality of
$i'$
.
Thus, we have that
$i'\leq i-k$
and
$\mu _{i'}\mathbin {\wedge } \eta _0=\xi _{n+1-k}$
. It follows that
$\mu _{i'+k}\mathbin {\wedge } \eta _k=v$
(
$\mu _{i'+k}$
is well-defined because
$i'\leq i-k$
and
$\mu _i$
is well-defined, while
$\eta _k$
is well-defined because
$\xi $
is the shortest non-cyclic orbit). But
$\mu _{i'+k}\mathbin {\wedge } \eta _k\in B$
, contradicting
$v\notin B$
, so we conclude that
$\eta _0\mathbin {\wedge } \beta \neq v,w$
, showing (iii) in Case 1.
Thus, we have completed the proof in Case 1 (i.e., under the assumption that
$v=v'\notin B$
). The following is the last remaining case.
Case 2.
$v' < v$
and
$v ' \notin B$
. Recall that we have fixed some
$\eta _0\in \operatorname {\mathrm {dom}}(p)\setminus B$
such that
$\eta _0\mathbin {\wedge } \beta \in (\alpha ,\beta )$
, and we need to show that it compares to
$v'$
in the same way as it compares to
$w'$
.
Claim 4. In the case we are considering,
$\eta _0\in (\alpha ,\beta )$
.
Proof We have that
$\eta _0\mathbin {\wedge } \beta \in (\alpha ,\beta )$
. It trivially follows that
$\eta _0\mathbin {\wedge } \beta $
and
$v'$
have the same order type over
$B_{\leq \beta }$
. Let
$\bar b\in B$
be such that
$\eta _0\mathbin {\wedge } \bar b=\max _{b\in B} \eta _0\mathbin {\wedge } b$
. Then
$\eta _0\mathbin {\wedge } \beta \leq \eta _0\mathbin {\wedge } \bar b$
. If the inequality is strict, then by Fact 2.19, we have
$\eta _0\mathbin {\wedge } \beta = \bar b\mathbin {\wedge } \beta \in B\cap (\alpha ,\beta )$
, which contradicts the fact that
$B\cap (\alpha ,\beta )=\emptyset $
. Otherwise,
$\eta _0\mathbin {\wedge } \beta =\eta _0\mathbin {\wedge } \bar b\in (\alpha ,\beta )$
, so
$\max _{b\in B} \eta _0\mathbin {\wedge } b$
has the same order type over
$B_{\leq \beta }$
as
$v'$
. Since, by Claim 1,
$ \operatorname {\mathrm {tp}}(v/B)\neq \operatorname {\mathrm {tp}}(\eta _0/B)$
, by Fact 2.25 and the inequality
$v\neq v'$
, we conclude that
$\eta _0= \max _{b\in B} \eta _0\mathbin {\wedge } b=\eta _0\mathbin {\wedge } \beta $
, and therefore
$\eta _0=\eta _0\mathbin {\wedge } \beta \in (\alpha ,\beta )$
. Claim
Claim 5. For all orbits
$\mu $
of p and
$k>0$
, we have that
$\eta _0=v \mathbin {\wedge } \mu _k$
if and only if there are
$l,r>0$
such that
$\xi _n \mathbin {\wedge } \mu _{k-1} = \xi _{l-1} \mathbin {\wedge } \mu _{r-1}$
and
$\eta _0 = \xi _l \mathbin {\wedge } \mu _r$
.
In particular,
$\eta _0=v'$
if and only if
$\eta _0=w'$
.
Proof Suppose
$\eta _0=v\mathbin {\wedge } \mu _k$
. By Definition 6.3 (applied to
$q=p_v$
,
$m_1=n+1$
,
$m_2=k$
), we have some
$l,r$
such that
$\eta _0=\xi _l\mathbin {\wedge } \mu _r$
, and they clearly satisfy the right-hand side. The converse is immediate (just apply
$p_v$
to both sides of the first equality).
For the “in particular”, just note that
$v'=v\mathbin {\wedge } \mu _k$
for some
$\mu ,k$
(namely, any such that
$\mu _k\in B$
and
$\mu _k\geq \beta $
) and
$w'=w\mathbin {\wedge } \mu _k$
for the same
$\mu ,k$
(because
$ \operatorname {\mathrm {tp}}(v/B)= \operatorname {\mathrm {tp}}(w/B)$
) and apply the first part. Claim
By Claims 4 and 5, it is enough to show that we have
$\eta _0\leq v'$
if and only if
$\eta _0\leq w'$
. Note that since
$v'\in (\alpha ,\beta )$
, this implies that
$v'$
and
$\eta _0$
are comparable. Note also that since
$v'<v$
and
$\eta _0<\beta $
, it is easy to see that
$\eta _0\leq v'$
if and only if
$\eta _0<v$
.
Suppose
$\xi $
is not a quasi-cycle, then by Proposition 6.5
(1), for some (minimal) k, we have that
$\xi _0\mathbin {\wedge } \xi _k\neq \xi _k\mathbin {\wedge } \xi _{2k}$
(so by semilinearity, there is a strict inequality). We claim that under this assumption,
$\eta _0\leq v'$
(since
$\eta _0<\beta $
, equivalently,
$\eta _0< v$
) if and only if
$\eta _0\leq \xi _{n+1-k}\mathbin {\wedge } \xi _{n+1-2k}$
.
If
$\xi _0\mathbin {\wedge } \xi _k<\xi _{k}\mathbin {\wedge } \xi _{2k}$
, then by applying
$p_v^{n+1-2k}$
to both sides,
$\xi _{n+1-k}\mathbin {\wedge } \xi _{n+1-2k}<\xi _{n+1-k}\mathbin {\wedge } v$
, which makes one implication trivial. In the other direction, if
$v> \eta _0$
, then since
$\xi _{n+1}{\uparrow }$
, by Definition 6.3 (applied to
$q=p_v$
,
$m_1=m_2=n+1$
), there are distinct
$i_1,i_2\equiv n+1\pmod k$
such that
$\xi _{i_1},\xi _{i_2}\geq \eta _0$
, whence
$\xi _{i_1}\mathbin {\wedge } \xi _{i_2}\geq \eta _0$
. We may assume without loss of generality that
$i_1<i_2$
, whence
$i_1\leq n+1-2k$
(because
$i_1\equiv i_2\equiv n+1\pmod k$
and
$i_2\leq n$
). By Proposition 5.8(1b), it follows that
$\xi _{i_1}\mathbin {\wedge } \xi _{i_2}\leq \xi _{n+1-2k}\mathbin {\wedge } \xi _{n+1-k}$
, and hence
$\eta _0\leq \xi _{n+1-2k}\mathbin {\wedge } \xi _{n+1-k}$
.
Otherwise, suppose
$\xi _0\mathbin {\wedge } \xi _k>\xi _k\mathbin {\wedge } \xi _{2k}$
. If
$\eta _0< v$
, then by Definition 6.3 (with
$q=p_v$
,
$m_1=m_2=n+1$
), there is some
$i\equiv n+1\pmod k$
such that
$\xi _i> \eta _0$
, whence
$\xi _i\mathbin {\wedge } v\geq \eta _0$
. Then by Proposition 5.8(2),
$\xi _i\mathbin {\wedge } v=\xi _{n+1-k}\mathbin {\wedge } v<\xi _{n+1-2k}\mathbin {\wedge } \xi _{n+1-k}$
. Conversely, suppose
$\eta _0\not < v$
. Then, again by Definition 6.3 (having in mind that
$\xi _{n+1}{\uparrow }$
), there are distinct
$i_1,i_2\equiv n+1\pmod k$
such that
$\eta _0\not \leq \xi _{i_1},\xi _{i_2}$
, so in particular,
$\eta _0 \not \leq \xi _{i_1}\mathbin {\wedge } \xi _{i_2}$
; since
$i_1,i_2\leq n$
and
$i_1,i_2\equiv n+1\pmod k$
, we have
$\max (i_1,i_2)\leq n+1-k$
, and thus by Proposition 5.8(2b),
$\xi _{i_1}\mathbin {\wedge } \xi _{i_2}\geq \xi _{n+1-k}\mathbin {\wedge } \xi _{n+1-2k}$
, whence
$\xi _{n+1-k}\mathbin {\wedge } \xi _{n+1-2k}\not \geq \eta _0$
.
We are left with the case when
$\xi $
is a quasi-cycle. Note that by Proposition 6.5
(2), it follows that
$(\xi _0,\ldots ,\xi _n,v)$
is also a quasi-cycle. Let u be the pseudo-period of
$\xi $
(cf. Definition 5.10). We will show that
$v>\eta _0$
if and only if there is some positive
$k\neq n+1-u$
such that
$\xi _k\mathbin {\wedge } \xi _{n+1-u}\geq \eta _0$
.
Suppose
$v>\eta _0$
. Considering
$\xi _{n+1}{\uparrow }$
, by Definition 6.3, there are distinct positive
$k, k'\leq n$
such that
$\xi _k,\xi _{k'}>\eta _0$
. Note that this implies that
$v\mathbin {\wedge } \xi _k\geq \eta _0$
, so also
$v\mathbin {\wedge } \xi _{n+1-u}\geq \eta _0$
(by Proposition 5.12), and in particular,
$\xi _{n+1-u}\geq \eta _0$
. Since
$k\neq k'$
, we may assume without loss of generality that
$k\neq n+1-u$
, and then clearly
$\xi _k\mathbin {\wedge } \xi _{n+1-u}\geq \eta _0$
.
Now, suppose
$0<k\neq n+1-u$
and
$\xi _k\mathbin {\wedge } \xi _{n+1-u}\geq \eta _0$
. Then by Proposition 5.14,
$\xi _n\mathbin {\wedge } \xi _{k-1}=\xi _{n-u}\mathbin {\wedge } \xi _{k-1}$
, so also
$v\mathbin {\wedge } \xi _k=\xi _{n+1-u}\mathbin {\wedge } \xi _k\geq \eta _0$
, and hence
$v> \eta _0$
.
This finishes the proof in Case 2, completing the proof of Theorem 6.8.⊣
Corollary 6.9. A PEC partial automorphism of
$\mathbf T$
is determined (in the sense of Definition 4.1).
Proof It is enough to check that every PEC partial automorphism p satisfies the hypothesis of Lemma 4.11. Take
$p=f_0\subsetneq f_1\subsetneq \ldots \subsetneq f_n\subsetneq f_{n+1}$
such that
$f_i\subsetneq f_{i+1}$
is immediate for
$i\leq n$
and a positively strict extension
$g\supseteq f_n$
. Let
$a=\nu _m$
be the sole element of
$ \operatorname {\mathrm {dom}}(f_{n+1})\setminus \operatorname {\mathrm {dom}}(f_n)$
. Put
$v:=f_{n+1}(a), w:=g(a)$
. Then by Remark 6.6,
$f_n$
is PEC, so by Theorem 6.8,
$ \operatorname {\mathrm {tp}}(v/A)= \operatorname {\mathrm {tp}}(w/A)$
(where A is the substructure of
$\mathbf T$
generated by the orbits of
$f_n$
), so, by ultrahomogeneity of
$\mathbf T$
, there is some
$\sigma \in \operatorname {\mathrm {Aut}}(\mathbf T/A)$
such that
$\sigma (v)=w$
. It follows that
$\sigma \circ f_{n+1}\circ \sigma ^{-1}\subseteq g$
, and so
$\tau _n:=\sigma $
witnesses that the hypothesis of Lemma 4.11 is satisfied, which completes the proof.⊣
Corollary 6.10. The class
$\mathcal K^1$
of finite meet-trees with a single partial automorphism has CAP and JEP.
Proof Given any
$(B',p')\in \mathcal K^1$
, we may assume that
$B'\subseteq \mathbf T$
, and then extend
$p'$
to a finite partial automorphism
$p^{\prime \prime }$
of
$\mathbf T$
such that
$B'\subseteq \operatorname {\mathrm {dom}}(p^{\prime \prime })$
. By Proposition 6.4, we can extend
$p^{\prime \prime }$
to a PEC partial automorphism p of
$\mathbf T$
. If we take B to be the tree generated by
$ \operatorname {\mathrm {dom}}(p)\cup \operatorname {\mathrm {range}}(p)$
, then by Corollaries 4.19 and 6.9, if p is a PEC automorphism of
$\mathbf T$
, then
$(B,p)$
is an amalgamation base in
$\mathcal K^1$
, and clearly
$(B',p')\subseteq (B,p)$
, which shows CAP.
To see JEP, take any
$(A,p_A),(B,p_B)\in \mathcal K^1$
. We may assume without loss of generality that
$A\cap B=\emptyset $
. Let v be a new element. Then let
$A\vee _v B:=A\cup B\cup \{v\}$
, ordered in such a way
$a\mathbin {\wedge } b=v$
for all
$a\in A$
and
$b\in B$
. Clearly,
$p_A\cup p_B$
is a partial automorphism of
$A\vee _v B$
and
$(A,p_A)$
and
$(B,p_B)$
embed into
$(A\vee _v B,p_A\cup p_B)$
.⊣
The following theorem, along with Corollary 3.8, completes the Main Theorem.
Theorem 6.11. The universal meet-tree
$\mathbf T$
has a generic automorphism.
Remark 6.12. It seems like it might be possible to use largely the same methods to show that for each
$k>0$
,
$\mathbf T_k$
has a generic automorphism. More specifically, we believe that the analogue of Theorem 6.8 is true with essentially the same proof (after we replace the notion of PEC by the appropriate variant for
$\mathbf T_k$
), which will yield a cofinal class of determined automorphisms of
$\mathbf T_k$
. On the other hand, Proposition 4.17 shows that the analogue of Lemma 4.16 fails if
$k>1$
, so we cannot simply use Lemma 4.3 to conclude that the class of determined automorphisms witnesses CAP, as we did in the proof of Corollary 6.10.
Instead, one could try to show that every finite partial automorphism of
$\mathbf T_k$
can be extended to one which is PEC (in
$\mathbf T_k$
) and has the property that its unique strict extension satisfies the hypothesis of Remark 4.18, which (together with Lemma 4.3 and a proof of Remark 4.18) would yield CAP. For
$k=2$
, this seems straightforward, but the general case appears to be more difficult—it is plausible that for
$k>2$
we might have EAP but not CAP, leading to a negative answer to Question 1.2.
Note that in any case we easily get JEP for the class of finite k-ary meet-trees for all
$ k $
: for
$ k>1 $
it is exactly as in the proof of Corollary 6.10, and for
$ k=1 $
(i.e., linear orders) it is also quite easy. Thus, for all
$ k $
, the automorphism group of
$ \mathbf T_k $
has a dense conjugacy class.
${\lozenge }$
Remark 6.13. The caveats mentioned in Remark 6.12 do not seem to apply in the case of
$k=1$
(see Remark 4.21), so we can slightly adjust the proof of Theorem 6.11 to recover the fact that
$(\mathbf Q,<)$
has a generic automorphism.
${\lozenge }$
Remark 6.14. Consider the class of finite meet-trees expanded with a lexicographic ordering (i.e., a total order
$\unlhd $
, extending the tree order, such that if
$b\unlhd a$
and
$a\mathbin {\wedge } a'>a\mathbin {\wedge } b$
, then
$b\unlhd a'$
). It is easy to see that it is a Fraïssé class, and one can ask whether the limit of this class has a generic automorphism.
The proof of Lemma 4.16 seems to adapt to this context in a straightforward manner, so the main difficulty seems to lie with the analogue of Theorem 6.8.
Note that the orbit analysis for trees with a lexicographic ordering is much simpler: there are no nontrivial cycles (there can be fixed points), which implies that the spiral length can only be equal to
$1$
(so the only spirals are just monotone sequences, the only spiral combs are
$1$
-combs), and the pseudo-period of a quasi-cycle is always one (so all quasi-cycles are “fans”).
${\lozenge }$
Acknowledgements
We would like to thank Bruno Duchesne for letting us know of his work mentioned above and for his other comments. We would also like to thank the anonymous referee for their helpful remarks. The first author would like to thank the Israel Science Foundation for partial support of this research (grants no. 1533/14 and 1254/18). The second author is supported by the Narodowe Centrum Nauki grant no. 2016/22/E/ST1/00450 and the Lady Davis fellowship.
