1 Introduction
The field of symmetric and permutation models of choiceless set theory is commonly perceived as chaotic. One needs to only look at the encyclopedic form of [Reference Howard and Rubin1], complete with a floppy disc, to understand where that impression comes from. The purpose of this article is to provide several natural properties of group actions which translate into fragments of the axiom of choice in the associated permutation models (or Fraenkel–Mostowski models, as they are frequently called). Very many results quoted in [Reference Howard and Rubin1] follow essentially immediately, and every now and then a novel conclusion about a known model appears. The main point is that the properties of group actions considered have intrinsic interest, perhaps justifying the study of permutation models in the eyes of a non-specialist. Evaluation of these properties in very natural cases is often challenging, and it leads to natural questions in model theory, combinatorics, geometric topology, and other fields.
The sections are ordered in decreasing strength of the fragments of the axiom of choice they deal with. In Section 2, I fix the terminology and gather some well-known or easy results concerning the construction of the permutation models. In Section 3, I consider the axiom of well-ordered choice and provide a dynamical equivalent to it, cofinal orbits – Definition 3.2 and Theorem 3.3. The ideal of nowhere dense subsets of a manifold of any finite dimension has cofinal orbits [Reference Young8]. For any interesting topological space, the status of cofinal orbits of the ideal of nowhere dense sets seems to be a challenging and often open problem. In Section 4, I consider the axiom of dependent choices. A dynamical equivalent to it is isolated in Definition 4.2 and Theorem 4.3; its version for symmetric models was considered previously by Karagila and Schilhan [Reference Karagila and Schilhan5]. In Section 5, I consider the axiom of countable choice and its dynamical equivalent,
$\sigma $
-closure. I show that many dynamical ideals have this property, such as the ideal of countable closed subsets of the real line, or the well-ordered subsets of rationals. In Section 6, I consider the statement that unions of well-orderable collections of well-orderable sets are well-orderable. There is a neat dynamical criterion similar to the topological simplicity of groups. Naturally enough, abelian group actions are never simple except for trivial cases, Theorem 6.19. One simple ideal is the ideal of finite sets on many limit Fraissé structures, Theorem 6.5. Finally, in Section 6.1, I show how to rule out amorphous or infinite, Dedekind-finite sets from permutation models. The criterion uses a stratification of the ideal into an increasing union which exhibits a degree of
$\sigma $
-closure.
2 Notation and terminology
In this section, I show how to obtain a permutation model (a Fraenkel–Mostowski model in the terminology of [Reference Howard and Rubin1]) of the theory ZF with atoms from an object called a dynamical ideal. The construction is well-known; the section serves mostly to introduce suitable terminology.
Definition 2.1 ZFA, the set theory with atoms, is the theory with the following description:
-
(1) its language contains a binary relational symbol
$\in $
and a unary relational symbol
$\mathbb {A}$
for atoms; -
(2) its axioms include all usual axioms of ZF, except for the axiom of extensionality, which is stated only for sets which are not atoms;
-
(3) there are two additional axioms:
$\forall x\ \mathbb {A}(x)\to \forall y\ y\notin x$
and
$\exists y\ \forall x\ y\in x\leftrightarrow \mathbb {A}(x)$
(atoms form a set).
ZFCA is ZFA plus the axiom of choice.
The main issue in ZFA and ZFCA (about which its axioms say nothing) is the structure of its set of atoms. It is not difficult to build a model of ZFCA with a prescribed set of atoms.
Definition 2.2 Let X be a set. There is up to class isomorphism unique class model M of ZFCA satisfying the following demands:
-
(1)
$X=\mathbb {A}^M$
; -
(2) the membership relation of M is well-founded;
-
(3) for every
$m\in M,$
the collection
$\{n\in M\colon n\in ^Mm\}$
is a set as opposed to proper class; -
(4) for every set
$B\subseteq M,$
there is an element
$m\in M$
such that
$B=\{n\in M\colon n\in ^Mm\}$
.
The model M will be denoted by
$V[[X]]$
.
An explicit and well-known construction of the model can be found, for example, in [Reference Jech4, Lemma 15.47]. By an abuse of notation, the membership relation of
$V[[X]]$
will be denoted by
$\in $
. By another abuse of notation, I will identify X with the element of the model
$V[[X]]$
which contains exactly all the
$V[[X]]$
-atoms.
Definition 2.3 A set
$A\in V[[X]]$
is pure if
$V[[X]]\models $
the transitive closure of A contains no atoms. The class
$\{A\in V[[X]]\colon A$
is pure
$\}$
is called the pure part of
$V[[X]]$
and denoted by V.
It is immediate that the pure part of
$V[[X]]$
is definably isomorphic to the set-theoretic universe in which the model
$V[[X]]$
is built. In the construction of inner models of ZFA, group actions play a central role. The following definition records key notational elements.
Definition 2.4 Suppose that
$\Gamma \curvearrowright X$
is a group action.
-
(1)
$\Gamma \curvearrowright V[[X]]$
is the unique action extending the original one and satisfying
$\gamma \cdot A=\{\gamma \cdot B\colon B\in A\}$
for all
$\gamma \in \Gamma $
and
$A\in V[[X]]$
. -
(2) If
$A\in V[[X]]$
, then
$\mathrm {stab}(A)$
, the stabilizer of A, is the set
$\{\gamma \in \Gamma \colon \gamma \cdot A=A\}$
. -
(3) If
$a\subseteq X,$
then
$\mathrm {pstab}(a)$
, the pointwise stabilizer of x, is the set
$\{\gamma \in \Gamma \colon \forall x\in a\ \gamma \cdot x=x\}=\bigcap _{x\in a}\mathrm {stab}(x)$
.
Stabilizers and pointwise stabilizers are subgroups of
$\Gamma $
. The extension of the action to all of
$V[[X]]$
is an action of
$\Gamma $
by
$\in $
-automorphisms; it is not difficult to show by
$\in $
-recursion that the action
$\Gamma \curvearrowright V[[X]]$
fixes all pure elements. To construct an inner model of ZFA, an additional piece of data is needed.
Definition 2.5 A dynamical ideal is a tuple
$\Gamma \curvearrowright X, I,$
where
$\Gamma $
is a group acting on a set X and I is an ideal on the set X containing all singletons, invariant under the action. That is to say, for every
$a\in I$
and every
$\gamma \in \Gamma $
, the set
$\gamma \cdot a=\{\gamma \cdot x\colon x\in a\}$
belongs to I.
One point in this article is that the class of dynamical ideals is much broader than the examples normally discussed in connection with permutation models, and that there are tools to investigate even the more “exotic” examples.
Example 2.6 Let
$\mathcal {S}$
be a structure with countable universe X. Let
$\Gamma $
be the group of automorphisms of
$\mathcal {S}$
, acting on X by application. Let I be the ideal of finite subsets of X. Then,
$\Gamma \curvearrowright X, I$
is a dynamical ideal.
Example 2.7 Let X be a topological space, let
$\Gamma $
be the self-homeomorphism group acting on X by application, and let I be an ideal defined from the topology only:
-
(1) the ideal of nowhere dense sets;
-
(2) the ideal of sets with countable closure;
-
(3) the ideal of sets with zero-dimensional closure.
Then,
$\Gamma \curvearrowright X, I$
is a dynamical ideal.
Definition 2.8 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal. The associated permutation model
$W[[X]]$
is the transitive part of the class
$\{A\in V[[X]]\colon \exists b\in I\colon \mathrm {pstab}(b)\subseteq \mathrm {stab}(A)\}$
.
Note that the notation
$W[[X]]$
abstracts away from the group action and the ideal for the sake of brevity. This should not cause any confusion. The following is well-known [Reference Jech3, Chapter 4].
Fact 2.9
$W[[X]]$
is a model of Zermelo–Fraenkel set theory with atoms.
In the rest of this section, I derive several properties of the model
$W[[X]]$
which hold irrespective of the dynamical ideal used.
Proposition 2.10 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal.
-
(1) X and I both belong to the associated permutation model.
-
(2)
$V\subseteq W[[X]]$
. -
(3) (Support invariance) The relation
$\{\langle b, A\rangle \colon b\in I$
and
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(A)\}$
is invariant under the group action and as such belongs to the permutation model. -
(4) The permutation model is invariant under the group action.
Proof For (1), note that
$\{x\}\in I$
and
$\mathrm {pstab}(\{x\})=\mathrm {stab}(x)$
; in conclusion
$X\subseteq W[[X]]$
. Since X is invariant under the action,
$X\in W[[X]]$
. For every set
$a\in I$
,
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(a)$
, so
$a\in W[[X]]$
. Finally, since the ideal I is invariant under the action,
$\Gamma =\mathrm {stab}(I)$
holds and
$I\in W[[X]]$
as desired. (2) is clear as all pure sets are fixed by the group action.
For (3), suppose that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(A)$
and
$\gamma \in \Gamma $
is an element. To show that
$\mathrm {pstab}(\gamma \cdot b)\subseteq \mathrm {stab}(\gamma \cdot A)$
, let
$\delta \in \mathrm {pstab}(\gamma \cdot b)$
be an arbitrary element. Then,
$\gamma ^{-1}\delta \gamma \in \mathrm {pstab}(b)$
, so
$\gamma ^{-1}\delta \gamma \cdot A=A$
, and multiplying both sides by
$\gamma $
, get
$\delta \cdot (\gamma \cdot A)=\gamma \cdot A$
. (4) is an immediate corollary of the definition of the permutation model and (3).
In the permutation model, we view well-orderable sets as trivial: every structure on a well-orderable set is a copy of a structure in V. It will be useful to have a characterization of well-orderable sets.
Proposition 2.11 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal. The following are equivalent for every set
$A\in W[[X]]$
:
-
(1) A is well-orderable in
$W[[X]]$
; -
(2) there is a set
$b\in I$
such that
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(A)$
; -
(3)
$\mathcal {P}\mathcal {P}(A)\cap W[[X]]=\mathcal {P}\mathcal {P}(A)\cap V[[X]]$
; -
(4)
$\mathcal {P}\mathcal {P}(A)$
is well-orderable in
$W[[X]]$
.
The equivalence of (1) and (4) is exactly the feature of permutation models which sets them apart from most symmetric models of ZF obtained as submodels of generic extensions.
Proof For (1) implies (2), let R be a well-ordering of A in the permutation model, let
$b\in I$
be such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(R)$
, and by transfinite induction on R prove that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(B)$
for every
$B\in A$
. For (2) implies (3), note that
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(B)$
for every
$B\subseteq A$
and then
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(C)$
for every
$C\subseteq \mathcal {P}(A)\cap V[[X]]$
. For (3) implies (1), use the axiom of choice in
$V[[X]]$
to find a well-ordering on A and code it as the set of its initial segments (an element of
$\mathcal {P}\mathcal {P}(A)$
) to transfer it to
$W[[X]]$
.
Finally, (2) implies (4) since
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(\mathcal {P}\mathcal {P}(A))$
and then
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(R)$
for any relation R on
$\mathcal {P}\mathcal {P}(A)$
in
$V[[X]]$
, in particular for a well-ordering R on
$\mathcal {P}\mathcal {P}(A)$
obtained in
$V[[X]]$
using the axiom of choice there. (4) implies (1) trivially: the map
$B\mapsto \{\{ B\}\}$
is an injection from A to
$\mathcal {P}\mathcal {P}(A)$
in
$W[[X]]$
.
Finally, I discuss a natural closure-type property of a dynamical ideal which is necessary for the statement of certain characterization theorems.
Definition 2.12 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal.
-
(1) A set
$a\subseteq X$
is dynamically closed if for every
$x\notin a,$
there is
$\gamma \in \mathrm {pstab}(a)$
such that
$\gamma \cdot x\neq x$
. -
(2) The dynamical ideal is dynamically closed if every set in I is a subset of a dynamically closed set in I.
It is not hard to see that for every set
$a\subseteq X,$
there is the smallest set
$b\subseteq X,$
which is dynamically closed and
$a\subseteq b$
, namely,
$b=\{x\in X\colon \mathrm {pstab}(a)\subseteq \mathrm {stab}(x)\}$
; I will call b the dynamical closure of a. A brief diagram-chasing argument shows that the dynamical closure operator is invariant under the group action. For every dynamical ideal
$I,$
there is also the smallest dynamical ideal
$J,$
which is dynamically closed and
$I\subseteq J$
, namely, the ideal of all sets which are subsets of dynamical closures of sets in I. It is easy to check that the ideal J thus defined is invariant under the group action. I will call J the dynamical closure of I. The following is nearly trivial.
Proposition 2.13 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal, and let
$\Gamma \curvearrowright X, J$
be its dynamical closure.
-
(1) The two dynamical ideals generate the same permutation model
$W[[X]]$
. -
(2)
$J=\{a\in W[[X]]\colon a\subseteq X$
and
$W[[X]]\models a$
is well-orderable
$\}$
.
Proof For (1), work in the model
$V[[X]]$
, let A be any set, and note that there is a set
$b\in I$
such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(A)$
iff there is a set
$a\in J$
such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
. The left-to-right implication follows from the inclusion
$I\subseteq J$
. For the right-to-left implication, let
$a\in J$
be such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
and find a set
$b\in I$
such that
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(a)$
. Clearly,
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(A)$
holds. (1) follows.
For (2), suppose that
$a\subseteq X$
is a set in
$W[[X]]$
. If a is well-orderable, let
$\leq $
be a well-ordering on a in the model
$W[[X]]$
. Let
$b\in I$
be a set such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(\leq )$
. By transfinite induction on
$\leq $
argue that for every
$x\in a$
and every
$\gamma \in \mathrm {pstab}(b)$
,
$\gamma \cdot x=x$
. It follows that a is a subset of the dynamical closure of the set b, so
$a\in J$
. If, on the other hand,
$a\in J$
, then find a set
$b\in I$
such that
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(a)$
, observe that for any relation
$R\in V[[X]]$
on
$a \mathrm {pstab}(b)\subseteq \mathrm {stab}(R)$
, and conclude that in particular, the model
$W[[X]]$
contains every well-ordering on the set a found in the model
$V[[X]]$
.
Example 2.14 Let X be a Hausdorff topological space, let
$\Gamma $
be the group of self-homeomorphisms of X acting on X by application, and let
$a\subseteq X$
be a set. The topological closure is a subset of the dynamical closure of a. This is the reason why in this situation I consider only ideals generated by closed sets.
3 Axiom of well-ordered choice
The first common fragment of the axiom of choice under consideration in this article is the following.
Definition 3.1 [Reference Howard and Rubin1, Form 40]
The axiom of well-ordered choice is the statement that every well-ordered family of non-empty sets has a choice function.
The dynamical counterpart to the well-ordered axiom of choice is the following.
Definition 3.2 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal. The ideal has cofinal orbits if for every
$a\in I,$
there is
$b\in I$
which is a-large: for every
$c\in I,$
there is
$\gamma \in \mathrm {pstab}(a)$
such that
$c\subseteq \gamma \cdot b$
.
Theorem 3.3 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal.
-
(1) If the ideal has cofinal orbits, then the associated permutation model satisfies the axiom of well-ordered choice.
-
(2) If the ideal I is dynamically closed and the associated permutation model satisfies the axiom of well-ordered choice, then the ideal has cofinal orbits.
Proof For (1), let
$W[[X]]$
be the permutation model, and suppose that A is a well-orderable set of nonempty sets in
$W[[X]]$
. Use Proposition 2.11 to find a set
$a\in I$
such that
$\mathrm {pstab}(a)\subseteq \mathrm {pstab}(A)$
. Let
$b\in I$
be a set such that the
$\mathrm {pstab}(a)$
-orbit of b is cofinal in I. Now, we claim that every set
$B\in A$
contains a set
$C\in B$
such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(C)$
. To see this, let
$D\in B$
be an arbitrary set, and let
$d\in I$
be such that
$\mathrm {pstab}(d)\subseteq \mathrm {stab}(D)$
. Find a group element
$\gamma \in \mathrm {pstab}(a)$
such that
$d\subseteq \gamma \cdot b$
and let
$C=\gamma ^{-1}\cdot D$
; we claim that the set C works as required. First of all, it is clear that
$C\in B$
holds since
$\gamma $
(and
$\gamma ^{-1}$
) fixes every element of A; in particular, it fixes B. Second, a diagram-chasing argument shows that for every element
$\delta \in \mathrm {pstab}(b)$
,
$\gamma \delta \gamma ^{-1}\in \mathrm {pstab}(d)$
, so
$\gamma \delta \gamma ^{-1}\cdot D=D$
and
$\delta \cdot (\gamma ^{-1}\cdot D)=\gamma ^{-1}\cdot D$
as required.
Now, let f be any selector on A such that for every
$B\in A$
,
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f(B))$
holds; such a selector exists by the previous paragraph. It is immediate that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f)$
, so
$f\in W[[X]]$
and (1) follows.
For (2), suppose that the dynamical ideal is dynamically closed and
$W[[X]]$
satisfies well-ordered choice. Let
$a\in I$
be an arbitrary set. In
$W[[X]]$
, consider the set A of all well-orderings whose domain belongs to I. Note that for every set
$b\in I$
, every relation R on b in
$V[[X]]$
belongs to
$W[[X]]$
since
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(R)$
; in particular, b carries a well-ordering in
$W[[X]]$
. Let E be the
$\mathrm {pstab}(a)$
-orbit equivalence relation on A, and let B be the set
$A/E$
. Clearly,
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)\cap \mathrm {stab}(E)\cap \mathrm {stab}(B)$
, so
$A, E, B\in W[[X]]$
holds. In addition, for every E-class
$C\subseteq A$
,
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(C)$
, so B is even well-ordered in
$W[[X]]$
. By the axiom of well-ordered choice in
$W[[X]]$
, there is a selector f on B.
Let
$b\in I$
be such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f)$
and
$a\subseteq b$
. Use the dynamical closure assumption on the ideal to increase b if necessary so that
$\forall x\in X\setminus b\ \exists \gamma \in \mathrm {pstab}(b)\ \gamma \cdot x\neq x$
. I claim that b is a-large. Indeed, suppose that
$c\in I$
is a set. Let
$\leq $
be a well-ordering on c, let
$C\in B$
be the
$\mathrm {pstab}(a)$
-orbit of
$\langle c, \leq \rangle $
, and consider the value
$f(C)$
. Since
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f, C)$
,
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f(C))$
holds. Now,
$f(C)=\langle \gamma \cdot c, \gamma \cdot \leq \rangle $
for some
$\gamma \in \mathrm {pstab}(a)$
; since
$\gamma \cdot \leq $
is a well-ordering on
$\gamma \cdot c$
, a transfinite induction argument along it shows that
$\forall x\in \gamma \cdot c\ \mathrm {pstab}(b)\subseteq \mathrm {stab}(x)$
. Since b is dynamically closed,
$\gamma \cdot c\subseteq b$
. This concludes the proof that b is a-large; (2) follows.
There is a very natural concept intimately related to cofinal orbits.
Definition 3.4 A dynamical ideal
$\Gamma \curvearrowright X, I$
supports a cone measure if in the associated permutation model
$W[[X]],$
there is a set
$C\subseteq I$
which is cofinal with respect to inclusion and such that for every set
$D\subseteq C$
in
$W[[X]],$
there is
$a\in I$
such that the set
$\{b\in C\colon a\subseteq b\}$
is either a subset of D, or it is disjoint from D. The set C is referred to as a support of the cone measure.
In other words, the ideal supports a cone measure if in the associated permutation model, the cone filter on some cofinal subset of I is an ultrafilter. While I do not have an attractive restatement of this property, which does not refer to the permutation model, there is an implication toward the cofinal orbits.
Theorem 3.5 If a dynamical ideal
$\Gamma \curvearrowright X, I$
supports a cone measure, then it has cofinal orbits.
Proof Suppose that
$C\subseteq I$
is a cofinal set in the permutation model supporting a cone measure. Suppose that
$a\in I$
is any set; I must find an a-large set b. Enlarging a if necessary, assume that
$\mathrm {stab}(C)\subseteq \mathrm {pstab}(a)$
. Toward a contradiction, assume that there is no a-large set
$b\in I$
. Working in
$V[[X]]$
, by transfinite recursion on ordinal
$\alpha $
build sets
$b_\alpha \in C$
such that, writing
$B_\alpha $
for the
$\mathrm {pstab}(a)$
-orbit of
$b_\alpha $
, either
$\bigcup _{\beta \in \alpha }B_\beta \subseteq C$
is cofinal in I (in which case the construction terminates), or
$\bigcup _{\beta \in \alpha }B_\beta $
does not contain any superset of
$b_\alpha $
. In addition, require that
$b_\alpha \subseteq b_{\alpha +1}$
.
The construction clearly has to terminate at some point, since the sets
$B_\alpha \subseteq I$
are pairwise disjoint. Since there is no a-large set, no set
$B_\alpha $
is cofinal, therefore the termination stage must be a limit ordinal, call it
$\gamma $
. Consider the sets
$C_0=\bigcup \{B_\alpha \colon \alpha \in \gamma $
is even
$\}$
and
$C_1=\bigcup \{B_\alpha \colon \alpha \in \gamma $
is odd
$\}$
. The sets
$C_0$
and
$C_1$
are
$\mathrm {pstab}(a)$
-invariant subsets of C, therefore they belong to the permutation model. They are clearly disjoint. The requirement
$b_\alpha \subseteq b_{\alpha +1}$
implies that the downward closure of the sets
$C_0$
and
$C_1$
is the same. Since
$C_0\cup C_1\subseteq C$
is cofinal, it must be the case that the disjoint sets
$C_0, C_1\subseteq C$
are both cofinal, an impossibility if the cone filter on C is to be an ultrafilter.
Together with Theorem 3.3, Theorem 3.5 shows that in permutation models, the existence of cone measure on some cofinal subset of I implies the axiom of well-ordered choice. This is a curious implication, as its antecedent contradicts AC as soon as the ideal is not generated by a single set, while its decedent is a consequence of AC. I do not know if the reverse implication can fail for a dynamically complete ideal which does not contain the whole set X. All examples below support a cone measure, even though I identify its support only in the first one, where it relates to a famous theorem of geometric topology.
Example 3.6 Let X be any Euclidean space, let
$\Gamma $
be the Polish group of self-homeomorphisms of X, and let I be the ideal of bounded subsets of X. Then, I has cofinal orbits. In dimension one, this is [Reference Howard and Rubin1, Model N47], in which apparently the status of well-ordered choice has not been known. The dynamical ideal supports a cone measure on the set
$C=\{a\in I\colon \exists \gamma \in \Gamma \ \gamma \cdot a$
is the unit ball
$\}$
. To see that the cone filter on C is an ultrafilter, suppose that
$D\subseteq C$
is a set in the permutation model, and let
$a\in I$
be a set such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(D)$
. Enlarging the set a if necessary, assume that it is equal to the closed ball
$B_n$
of radius n around the origin for some number n. Let
$b_0, b_1\in C$
be some sets such that
$B_{n+1}\subseteq b_0\cap b_1$
. It will be enough to show that there is a homeomorphism
$\gamma \in \mathrm {pstab}(a)$
such that
$\gamma \cdot b_0=b_1$
: the invariance of the set D will then imply that D contains either all or no sets in C which contain
$B_{n+1}$
. Now, the annulus theorem [Reference Kirby6] shows that the sets
$b_0\setminus B_n$
and
$b_1\setminus B_n$
are both homeomorphic to the annulus
$B_{n+1}\setminus B_n$
. This allows a construction of homeomorphisms
$\gamma _0, \gamma _1\in \mathrm {pstab}(a)$
such that
$\gamma _0\cdot (B_{n+1}\setminus B_n)=b_0\setminus a$
and
$\gamma _1\cdot B_{n+1}\setminus B_n)=b_1\setminus a$
. The composition
$\gamma _1\gamma _0^{-1}\in \mathrm {pstab}(a)$
then transports
$b_0$
to
$b_1$
as required.
Example 3.7 [Reference Howard and Rubin1, Model N33]
Let
$X=\mathbb {Q}$
with its ordering, let
$\Gamma $
be the Polish group of all automorphisms of X, and let I be the ideal of bounded subsets of X. Then, I has cofinal orbits.
Example 3.8 Let
$X=\mathbb {Q}$
with its ordering, let
$\Gamma $
be the Polish group of all automorphisms of X, and let I be the ideal of nowhere dense subsets of X. Then, I has cofinal orbits.
Proof The argument consists of several simple back-and-forth constructions encapsulated in the following claims.
Claim 3.9 Let
$d_0, d_1\subseteq \mathbb {Q}$
be two sets such that both they and their complements are dense in
$\mathbb {Q}$
. Then, there is an order-preserving permutation
$\pi $
of
$\mathbb {Q}$
such that
$\pi "d_0=d_1$
.
Claim 3.10 Let
$a\subseteq \mathbb {Q}$
be a nowhere dense set. Then, a can be extended to a nowhere dense set which is in addition closed, coinitial, and cofinal in
$\mathbb {Q}$
, and such that no point of it is isolated from left or right.
Nowhere dense sets satisfying the properties spelled out in the last claim will be called good. They form the support of the cone measure in the permutation model.
Claim 3.11 Let
$d_0, d_1\subseteq \mathbb {Q}$
be two nowhere dense good sets. Then, there is an order-preserving permutation
$\pi $
of
$\mathbb {Q}$
such that
$\pi "d_0=d_1$
.
Proof Let
$Y_0$
be the linearly ordered set whose universe consists of elements of
$d_0$
and inclusion-maximal intervals of
$\mathbb {Q}$
disjoint from
$d_0$
and the ordering is the natural one inherited from
$\mathbb {Q}$
; the same for subscript
$1$
. The goodness of the set
$d_0$
implies that the linear ordering on
$Y_0$
is dense without endpoints,
$d_0\subseteq Y_0$
is dense, and so is
$Y_0\setminus d_0\subseteq Y_0$
. Claim 3.9 shows that there is an order-preserving bijection
$\theta \colon Y_0\to Y_1$
such that
$\theta "d_0=d_1$
. For each interval
$i\in Y_0\setminus d_0$
, let
$\pi _i\colon i\to \theta (i)$
be an order-preserving bijection. In the end,
$\pi =(\theta \restriction d_0)\cup \bigcup \{\pi _i\colon i\in Y_0\setminus d_0\}$
is the desired permutation of
$\mathbb {Q}$
.
Finally, let
$a\subseteq X$
be a nowhere dense set; I must produce an a-large nowhere dense set b. Enlarging a if necessary, I may assume that a is good. Write J for the set of all inclusion-maximal intervals of X disjoint from a. Let
$b\subseteq X$
be a good nowhere dense set such that
$a\subseteq b$
and in each
$i\in J,$
the set b is both coinitial and cofinal. I will show that b is a-large.
To prove this, let
$c\subseteq X$
be a nowhere dense set. Enlarging c if necessary, I may assume that it contains a, it is good, and in each interval
$i\in J,$
it is coinitial and cofinal. For each interval
$i\in J$
use Claim 3.11 to find an order-preserving permutation
$\theta _i$
of i such that
$\theta _i"(b\cap i)=c\cap i$
. Then,
$\pi =(\mathrm {id}\restriction a)\cup \bigcup \{\theta _i\colon i\in J\}$
is an order-preserving permutation of X which is constant on a and moves b to c.
Example 3.12 [Reference Howard and Rubin1, Model N12(
$\kappa$
)]
Let
$\kappa $
be an uncountable cardinal, let X be a set of cardinality at least
$\kappa $
, let
$\Gamma $
be the group of all permutations of X acting by application, and let
$I_\kappa $
be the ideal of subsets of X of cardinality smaller than
$\kappa $
. Then,
$\Gamma \curvearrowright X, I_\kappa $
has cofinal orbits iff
$\kappa $
is a successor cardinal.
Proof If
$\kappa $
is a successor cardinal,
$\kappa =\lambda ^+$
, then for any set
$a\in I_\kappa $
, any set b such that
$a\subseteq b$
and
$|b\setminus a|=\lambda $
has a cofinal orbit under the action of
$\mathrm {pstab}(a)$
. On the other hand, if
$\kappa $
is a limit cardinal, then given a set
$b\in I_\kappa $
, its orbit consists of sets of cardinality
$|b|$
only, but there are sets of cardinality greater than
$|b|$
in the ideal
$I_\kappa $
. Thus, in that case,
$I_\kappa $
fails to have cofinal orbits.
Example 3.13 Let X be a set and let I be an ideal on it. Say that I is uniform if there is an infinite cardinal
$\kappa $
such that I is generated by sets of cardinality
$\kappa $
, and for every set
$a\in I,$
there is a set
$b\in I$
of cardinality
$\kappa $
which is disjoint from a. If I is a uniform ideal on X and
$\Gamma $
is the group of all permutations of X with support in I acting on X by application, then
$\Gamma \curvearrowright X, I$
has cofinal orbits.
Proof Let
$a\in I$
be an arbitrary set, and let
$b\in I$
be a set disjoint from a of the uniform cardinality
$\kappa $
. It will be enough to show that the
$\mathrm {pstab}(a)$
-orbit of
$a\cup b$
is cofinal. To this end, let
$c\in I$
be an arbitrary set; enlarging c if necessary, we may assume that
$a\cup b\subseteq c$
. Let
$\pi \colon b\to c\setminus a$
be any bijection. Let
$d=c\setminus b$
. The uniformity assumption shows that there are pairwise disjoint sets
$d_n$
for
$n\in \omega $
such that
$d_0=d$
, all
$d_n$
for
$n>0$
are disjoint from c and have cardinality
$|d|$
, and
$\bigcup _nd_n\in I$
. For each
$n\in \omega ,$
let
$\pi _n\colon d_n\to d_{n+1}$
be a bijection. Then,
$\pi \cup \bigcup _n\pi _n$
is a permutation of a set in I disjoint from a. Let
$\gamma $
be the permutation of X extending
$\pi \cup \bigcup _n\pi _n$
by the identity outside of its domain. Then,
$\gamma \in \mathrm {pstab}(a)$
and
$c\subseteq \gamma \cdot (a\cup b)$
as desired.
Any ideal I on a countably infinite set X which contains an infinite set and is not generated by a single infinite set over the Fréchet ideal is uniform as witnessed by
$\kappa =\aleph _0$
.
Example 3.14 Let
$n\geq 1$
be a number, let
$X=\mathbb {R}^n$
, let I be the ideal of nowhere dense subsets of X, and let
$\Gamma $
be the group of self-homeomorphisms of X acting by application. Then, the dynamical ideal
$\Gamma \curvearrowright X, I$
has cofinal orbits. The
$0$
-large set is a variation of the Sierpinski carpet in n-dimensions. The Sierpinski carpets form a support for the cone measure in the permutation model [Reference Young8].
Example 3.15 Let
$X=\mathbb {R}^2$
, let I be the ideal of closed sets of dimension zero, and let
$\Gamma $
be the group of all self-homeomorphisms of X acting by application. Then,
$\Gamma \curvearrowright X, I$
has cofinal orbits; the Cantor sets in the plane form the support of the cone measure [Reference Young8].
Example 3.16 Let X be a completely metrizable space without isolated points, let
$\Gamma $
be its self-homeomorphism group acting by application, and let I be the ideal generated by countable closed subsets of X. The ideal does not have cofinal orbits: if
$b\in I$
is a closed set, it has countable Cantor–Bendixson rank
$\alpha $
, and its orbit consists of sets of rank
$\alpha $
only. However, there are sets in I of higher Cantor–Bendixson rank.
Now suppose that the space X is the Euclidean space. The axiom of well-ordered (in fact,
$\omega _1$
) choice fails in the associated permutation model. Consider the sequence
$\langle C_\alpha \colon \alpha \in \omega _1\rangle ,$
where
$C_\alpha $
is the set of closed countable subsets of X of Cantor–Bendixson rank
$\alpha $
. It is clear that the sequence is invariant under the group action and therefore belongs to the permutation model. I claim that the sequence has no selector in the permutation model. Suppose toward a contradiction that there is such a selector
$s=\langle a_\alpha \colon \alpha \in \omega _1\rangle $
, and let
$b\subseteq X$
be a countable closed set such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(s)$
. Select a countable ordinal
$\alpha $
greater than the Cantor–Bendixson rank of b, and a point
$x\in a_\alpha \setminus b$
. The homogeneity properties of the Euclidean space imply that the
$\mathrm {pstab}(b)$
-orbit of x contains a nonempty open set; in particular, it is uncountable. However, it should be a subset of the countable set
$a_\alpha $
, a contradiction.
4 The axiom of dependent choices
The axiom of dependent choices is one of the most commonly considered fragments of AC, partly because it allows an uneventful development of mathematical analysis and descriptive set theory. It is implied by well-ordered choice [Reference Jech2] and it implies countable choice.
Definition 4.1 [Reference Howard and Rubin1, Form 43]
The axiom of dependent choices, DC, is the statement that in every partial order, there is either a minimal element or an infinite strictly descending sequence.
There is an essentially equivalent restatement of DC in terms of dynamical properties of ideals. A version of this criterion for symmetric models has been considered by Karagila and Schilhan [Reference Karagila and Schilhan5].
Definition 4.2 A dynamical ideal
$\Gamma \curvearrowright X, I$
is DC-complete if for every sequence
$\langle a_n\colon n\in \omega \rangle $
of sets in the ideal
$I,$
there is a sequence
$\langle \gamma _n\colon n\in \omega \rangle $
of group elements such that
$\gamma _0\in \mathrm {pstab}(a_0)$
, for every
$n\in \omega $
and every
$x\in a_n \gamma _n\cdot x=\gamma _{n+1}\cdot x$
, and
$\bigcup _n\gamma _n\cdot a_n\in I$
holds.
Theorem 4.3 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal.
-
(1) If the ideal is DC-complete, then the associated permutation model satisfies DC.
-
(2) If the ideal is dynamically closed and the permutation model satisfies DC, then the ideal is DC-complete.
Proof For (1), assume that the ideal is DC-complete, and let
$\langle P, \leq \rangle $
be a poset in the permutation model
$W[[X]]$
with no minimal element. In the ambient model
$V[[X]]$
, pick an infinite strictly descending sequence
$\langle p_n\colon n\in \omega \rangle $
of elements of P. Pick an inclusion-increasing sequence
$\langle a_n\colon n\in \omega \rangle $
of sets in I such that
$\mathrm {pstab}(a_n)\subseteq \mathrm {stab}(P, \leq , p_n)$
, and use the DC-completeness assumption to find a sequence
$\langle \gamma _n\colon n\in \omega \rangle $
of group elements such that
$\gamma _0\in \mathrm {pstab}(a_0)$
, for every
$n\in \omega \gamma ^{-1}_{n+1}\gamma _n\in \mathrm {pstab}(a_n)$
, and
$b=\bigcup _n\gamma _n\cdot a_n\in I$
holds. It will be enough to show that the sequence
$\vec q=\langle \gamma _n\cdot p_n\colon n\in \omega \rangle $
is an infinite strictly decreasing sequence in P in the model
$W[[X]]$
.
To show that the sequence
$\vec q$
belongs to the permutation model, it is enough to argue that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(\vec q)$
. To see that, note that for every number
$n \mathrm {pstab}(a_n)\subseteq \mathrm {stab}(p_n)$
holds by the choice of
$a_n$
,
$\mathrm {pstab}(\gamma _n\cdot a_n)\subseteq \mathrm {stab}(\gamma _n\cdot p_n)$
by support invariance (Proposition 2.10(3)) and
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(\gamma _n\cdot a_n)$
as
$\gamma _n\cdot a_n\subseteq b$
. Thus, elements of
$\mathrm {pstab}(b)$
fix every entry of the sequence
$\vec q$
, so they fix the whole sequence
$\vec q$
.
To show that the sequence
$\vec q$
is a strictly descending sequence in P, first note that for every number n,
$\gamma _n\in \mathrm {pstab}(a_0)$
. (This is proved by induction on n, the base step being trivial, and the induction step relying on the identity
$\gamma _{n+1}=\gamma _n (\gamma _n^{-1}\gamma _{n+1})$
and the fact that
$\gamma _n^{-1}\gamma _{n+1}\in \mathrm {pstab}(a_n)\subseteq \mathrm {pstab}(a_0)$
holds.) It follows that the nth entry
$\gamma _n\cdot p_n$
of the sequence
$\vec q$
is in P, since
$\gamma _n\in \mathrm {pstab}(a_0)\subseteq \mathrm {stab}(P)$
and
$p_n\in P$
. Finally,
$p_{n+1}<p_n$
implies
$\gamma _n^{-1}\gamma _{n+1}\cdot p_{n+1}<\gamma _n^{-1}\gamma _{n+1}\cdot p_n=p_n$
, which inequality provides
$\gamma _{n+1}\cdot p_{n+1}<\gamma _n\cdot p_n$
. This shows that
$\vec q$
is in fact a strictly decreasing sequence in P.
For (2), assume that the ideal is dynamically closed, the permutation model satisfies DC, let
$\langle a_n\colon n\in \omega \rangle $
be a sequence of sets in the ideal I and work to find a sequence of group elements with the properties of Definition 4.2. Enlarging the sets
$a_n$
if necessary, assume that they are increasing with respect to inclusion. Pick a sequence
$\langle \leq _n\colon n\in \omega \rangle $
such that
$\leq _n$
is a well-ordering on
$a_n$
and
$\leq _{n+1}$
is an end-extension of
$\leq _n$
. Let T be the tree of all finite sequences
$t=\langle t(i)\colon i\in n\rangle $
such that n is a number and there exists a sequence (a witness for
$t\in T$
)
$\langle \gamma _i\colon i\in n\rangle $
such that
$\gamma _0\in \mathrm {pstab}(a_0)$
, for each
$i\in n-1 \gamma _{i+1}^{-1}\gamma _i\in \mathrm {pstab}(a_i)$
, and
$t(i)=\gamma _i\cdot \langle a_i, \leq _i\rangle $
.
Claim 4.4
$T\in W[[X]]$
.
Proof For every number
$i\in \omega $
, the pair
$\langle a_i, \leq _i\rangle $
belongs to
$W[[X]]$
, since all elements of
$\mathrm {pstab}(a_i)$
fix it. This means that for every group element
$\gamma \in \Gamma $
,
$\gamma \cdot \langle a_i, \leq _i\rangle $
is in the model
$W[[X]]$
. It in turn follows that elements of T are finite sequences of elements of the model
$W[[X]]$
. Thus,
$T\subseteq W[[X]]$
holds, and it will be enough to show that
$\mathrm {pstab}(a_0)\subseteq \mathrm {stab}(T)$
.
To this end, let
$t=\langle t(i)\colon i\in n\rangle \in T$
as witnessed by a sequence
$\langle \gamma _i\colon i\in n\rangle $
, and let
$\delta \in \mathrm {pstab}(a_0)$
be any element. It will be enough to show that
$\delta \cdot t(i)$
as witnessed by the sequence
$\langle \delta \gamma _i\colon i\in n\rangle $
. To see this, first note that
$\delta \cdot t(i)=\delta \gamma _i\cdot \langle a_i, \leq _i\rangle $
as the group
$\Gamma $
acts on
$W[[X]]$
by
$\in $
-automorphisms. Also note that
$\delta \gamma _0\in \mathrm {pstab}(a_0)$
as
$\mathrm {pstab}(a_0)\subseteq \Gamma $
is a subgroup, and
$(\delta \gamma _{i+1})^{-1}(\delta \gamma _i)=\gamma _{i+1}^{-1}\gamma _i\in \mathrm {pstab}(a_i)$
by the choice of the group elements
$\gamma _i$
. The claim follows.
Claim 4.5 T has no minimal element.
Proof If
$t=\langle t(i)\colon i\in n\rangle \in T$
is a sequence with a witness
$\langle \gamma _i\colon i\in n\rangle $
, then it can be extended by the pair
$\gamma _{n-1}\cdot \langle a_{n}, \leq _{n}\rangle $
and the resulting longer sequence will be in T as witnessed by
$\langle \gamma _i\colon i\in n\rangle ^\smallfrown \gamma _{n-1}$
.
By DC in the permutation model
$W[[X]]$
, the tree T has an infinite branch
$b\in W[[X]]$
, which is viewed as an infinite sequence such that for every
$n\in \omega $
,
$b\restriction n\in T$
.
Claim 4.6 There is an infinite sequence c such that for each
$n\in \omega $
,
$c\restriction n$
witnesses the statement
$b\restriction n\in T$
.
This sequence c need not be in the permutation model.
Proof The sequence c is built by recursion on n. Suppose that
$c\restriction n$
has been built, and it is a witness to
$b\restriction n\in T$
. Let
$\langle \delta _i\colon i\in n+1\rangle $
be a witness to
$b\restriction n+1\in T$
. It will be enough to show that
$c^\smallfrown \delta _n$
is a witness to
$b\restriction n+1\in T$
. The only nontrivial point is to prove that
$\delta _n c(n-1)^{-1}\in \mathrm {pstab}(a_{n-1})$
holds. To see this, note that
$\delta _n c(n-1)^{-1}=(\delta _n\delta _{n-1}^{-1})(\delta _{n-1}c(n-1)^{-1})$
and here the former parenthesis is in
$\mathrm {pstab}(a_n)$
as the
$\delta $
’s witness
$b\restriction n+1\in T$
, and the latter parenthesis is in
$\mathrm {pstab}(a_n)$
since it fixes
$\leq _n$
and
$\leq _n$
is a well-ordering on
$a_n$
.
Now, write
$\gamma _i=c(i)$
and consider the sets
$\gamma _i\cdot a_i$
, and the well-orderings
$\gamma _i\cdot \leq _i$
for every number
$i\in \omega $
. For each
$i\in \omega $
,
$\leq _{i+1}$
is a well-ordering which end-extends
$\leq _i$
. Acting on this statement with
$\gamma _i^{-1}\gamma _{i+1}$
(which fixes
$a_i$
pointwise and therefore fixes
$\leq _i$
) and then with
$\gamma _i$
, it becomes clear that
$\gamma _{i+1}\cdot \leq _{i+1}$
is a well-ordering which end-extends
$\gamma _i\cdot \leq _i$
. It follows that the set
$\bigcup _i\gamma _i\cdot a_i$
(which is in
$W[[X]]$
as the union of the first coordinates of the sequence b) is well-ordered by the relation
$\bigcup _i\gamma _i\cdot \leq _i$
(which is in
$W[[X]]$
as the union of the second coordinates of the sequence b). By the dynamical closure of the ideal I, it follows that the set
$\bigcup _i\gamma _i\cdot a_i$
belongs to the ideal I. Therefore, the sequence
$c=\langle \gamma _i\colon i\in \omega \rangle $
answers the demands of Definition 4.2, and the proof is complete.
Nonexamples of DC-completeness are easier to find than examples.
Example 4.7 If
$I=\bigcup _nI_n$
, where each collection
$I_n$
is invariant, closed under subset, and not equal to I, then the ideal is not DC-complete no matter what the group action is. To see that, consider a sequence
$\langle a_n\colon n\in \omega \rangle ,$
where for each
$n\in \omega $
,
$a_n\in I\setminus I_n$
holds.
Such will be the case for the ideal of finite sets regardless of the action or the underlying infinite set.
Example 4.8 Let X be a completely metrizable space without isolated points. Let
$\Gamma $
be the group of all self-homeomorphisms of X acting on X by application, and let I be the ideal of countable subsets of X with countable closure. For
$n\in \omega ,$
let
$a_n\subseteq X$
be a nonempty countable closed set such that for each n,
$a_n\subseteq a_{n+1}$
and no point of
$a_n$
is isolated in
$a_{n+1}$
. The closure of
$\bigcup _n a_n$
is a perfect subset of X, therefore uncountable. In addition, whenever
$\gamma _n$
for
$n\in \omega $
are self-homeomorphisms of the space X such that
$\forall n\ \forall x\in a_n\ \gamma _n\cdot x=\gamma _{n+1}\cdot x$
, then it is still the case that no point of
$\gamma _n\cdot a_n$
is isolated in
$\gamma _{n+1}\cdot a_{n+1}$
, so
$\bigcup _n\gamma _n\cdot a_n$
still has uncountable closure and is not in the ideal. It follows that the dynamical ideal
$\Gamma \curvearrowright X, I$
is not DC-complete. In the case of a Euclidean space X, DC fails in the permutation model
$W[[X]]$
as it is impossible to find in that model a sequence of sets
$\langle a_n\colon i\in I\rangle $
such that for each n,
$a_n\subseteq a_{n+1}$
and no point of
$a_n$
is isolated in
$a_{n+1}$
(cf. Examples 3.16 and 5.5).
My examples of DC-completeness are all implied by some stronger property.
Example 4.9 If I is a
$\sigma $
-ideal, then the ideal is DC-complete no matter what the group action, as for every sequence
$\langle a_n\colon n\in \omega \rangle $
of sets in I, the group elements
$\gamma _n=1$
will work as in Definition 4.2. In this case, it is not hard to show that the model
$W[[X]]$
is closed under countable sequences in
$V[[X]]$
, so the DC in
$W[[X]]$
follows from DC in
$V[[X]]$
.
Theorem 4.10 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal. If the ideal has cofinal orbits, then it is DC-complete.
Recall that in the important case of dynamically closed ideals, cofinal orbits are equivalent to well-ordered choice and DC-completeness is equivalent to dependent choices in the permutation model, so Theorem 4.10 is a natural counterpart to the well-known fact that well-ordered choice implies dependent choices [Reference Jech2].
Proof The proof depends on two simple properties of cofinal orbits.
Claim 4.11 The set
$\{\langle a, b\rangle \colon a, b\in I$
and b is a-large
$\}$
is
$\Gamma $
-invariant.
Proof Let b be a-large and
$\delta \in \Gamma $
. To show that
$\delta \cdot b$
is
$\delta \cdot a$
-large, let
$c\in I$
be arbitrary. Since b is a-large, there is
$\gamma \in \mathrm {pstab}(a)$
such that
$\gamma \cdot \delta ^{-1}\cdot c\subseteq b$
. Multiplying by
$\delta $
on both sides, we get
$\delta \gamma \delta ^{-1}\cdot c\subseteq \delta \cdot b$
. Since
$\gamma \in \mathrm {pstab}(a)$
,
$\delta \gamma \delta ^{-1}\in \mathrm {pstab}(\delta \cdot a)$
holds and the claim follows.
Claim 4.12 Let b be a-large and
$c\in I$
. Then, there is
$\gamma \in \mathrm {pstab}(a)$
such that
$\gamma \cdot c\subseteq b$
and b is
$\gamma \cdot c$
-large.
Proof Let
$d\in I$
be c-large; without loss
$c\subseteq d$
. Use the largeness assumption on b to find a group element
$\gamma \in \mathrm {pstab}(a)$
such that
$\gamma \cdot d\subseteq b$
. By Claim 4.11,
$\gamma \cdot d$
is
$\gamma \cdot c$
-large; since b is a superset of
$\gamma \cdot d$
, it follows that b is
$\gamma \cdot c$
-large as desired.
To show the DC completeness, suppose that
$\langle a_n\colon n\in \omega \rangle $
is a countable collection of elements of I increasing with respect to inclusion. Let b be a-large and aim to find group elements
$\gamma _n$
such that
$\forall x\in a_n\ \gamma _n(x)=\gamma _{n+1}(x)$
,
$\gamma _n\cdot a_n\subseteq b$
and b is
$\gamma _n\cdot a_n$
-large. Let
$\gamma _0=1$
. If
$\gamma _n$
has been found, consider the set
$\gamma _n^{-1}\cdot b$
, which by Claim 4.11 is
$a_n$
-large. Use Claim 4.12 to find
$\delta \in \mathrm {pstab}(a_n)$
such that
$\delta \cdot a_{n+1}\subseteq \gamma ^{-1}_n$
and
$\gamma ^{-1}_n\cdot b$
is
$\delta \cdot a_{n+1}$
-large. The group element
$\gamma _{n+1}=\gamma _n\delta $
works as required. In the end,
$\bigcup _n\gamma _n\cdot a_n$
is a subset of b and therefore belongs to the ideal I.
Example 4.13 [Reference Karagila and Schilhan5]
Let X be a countable dense linear ordering without endpoints, let
$\Gamma $
be the group of all its automorphisms acting by application, and let I be the ideal of nowhere dense sets. Then, in the associated permutation model, DC holds – in fact, by Example 3.8, the dynamical ideal has cofinal orbits, so the axiom of well-ordered choice holds in the permutation model.
5 Stratifying well-ordered choice
There is an obvious way of stratifying the axiom of well-ordered choice into statements indexed by well-ordered infinite cardinals.
Definition 5.1 [Reference Howard and Rubin1, Form 8]
The axiom of countable choice is the statement that every countable family of nonempty sets has a choice function. In general, if
$\kappa $
is an infinite cardinal, then the axiom of
$\kappa $
-choice,
$\mathrm {AC}_\kappa $
, is the statement that every family of cardinality
$\kappa $
consisting of nonempty sets has a choice function.
This fragment of AC has a clean counterpart among properties of dynamical ideals.
Definition 5.2 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal, and let
$\kappa $
be an infinite cardinal. Say that the dynamical ideal is dynamically
$\kappa $
-complete if for every set
$a\in I$
and every collection
$\langle b_\alpha \colon \alpha \in \kappa \rangle $
of sets in
$I,$
there are group elements
$\gamma _\alpha \in \mathrm {pstab}(a)$
for
$\alpha \in \kappa $
such that
$\bigcup _{\alpha \in \kappa }\gamma _\alpha \cdot b_\alpha \in I$
.
Theorem 5.3 Let
$\Gamma \curvearrowright X, I$
be a dynamical ideal and
$\kappa $
be an infinite cardinal.
-
(1) If the dynamical ideal is dynamically
$\kappa $
-complete then the associated permutation model satisfies the axiom of
$\kappa $
-choice. -
(2) If the dynamical ideal is dynamically closed and the associated permutation model satisfies the axiom of
$\kappa $
-choice, then the ideal is dynamically
$\kappa $
-complete.
Proof For (1), assume that the ideal is dynamically
$\kappa $
-complete and
$A=\langle A_\alpha \colon \alpha \in \kappa \rangle $
is a sequence of nonempty sets in the permutation model. Let
$a\in I$
be such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
. Outside of the permutation model, for each
$\alpha \in \kappa $
pick a set
$B_\alpha \in A_\alpha $
and a set
$b_\alpha \in I$
such that
$\mathrm {pstab}(b_\alpha )\subseteq \mathrm {stab}(B_\alpha )$
. Use the completeness assumption on the dynamical ideal to find elements
$\gamma _\alpha \in \mathrm {pstab}(a)$
for
$\alpha \in \kappa $
such that
$c=\bigcup _\alpha \gamma _\alpha \cdot b_\alpha \in I$
. Now, consider the sequence
$C=\langle \gamma _\alpha \cdot B_\alpha \colon \alpha \in \kappa \rangle $
. Since each
$\gamma _\alpha $
belongs to
$\mathrm {pstab}(a)$
, it is still the case that
$\gamma _\alpha \cdot B_\alpha \in A_\alpha $
. At the same time, for each
$\alpha \in \kappa\ \mathrm {pstab}(\gamma \cdot b_\alpha )\subseteq \mathrm {stab}(\gamma _\alpha \cdot B)$
holds by Proposition 2.10, so
$\mathrm {pstab}(c)\subseteq \mathrm {stab}(C)$
, C belongs to the permutation model, and it witnesses the axiom of
$\kappa $
-choice instance for the collection A.
For (2), suppose that the ideal is dynamically closed and the permutation model satisfies
$\kappa $
-choice. To argue for the dynamical
$\kappa $
-completeness, suppose that
$a, b_\alpha \colon \alpha \in \kappa $
are sets in the ideal. Let
$A_\alpha $
be the set of all well-orderings on sets of the form
$\gamma \cdot b_\alpha $
, where
$\gamma $
ranges over all elements of
$\mathrm {pstab}(a)$
, and let
$A=\langle A_\alpha \colon \alpha \in \kappa \rangle $
. Note that for every set of the form
$\gamma \cdot b_\alpha $
belongs to I, clearly
$\mathrm {pstab}(\gamma \cdot b_\alpha )$
fixes it pointwise, and therefore all relations on
$\gamma \cdot b_\alpha $
in
$V[[X]]$
, including well-orderings, belong to
$W[[X]]$
. Since
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A_\alpha )$
holds for every
$\alpha \in \kappa $
, it must be the case that
$A\in W[[X]]$
. Use
$\kappa $
-choice to find a choice function
$\langle \gamma _\alpha \cdot b_\alpha , \leq _\alpha \colon \alpha \in \kappa \rangle $
for A in the premutation model. It is easy to see that the set
$c=\bigcup _\alpha \gamma _\alpha \cdot b_\alpha $
is well-ordered by an amalgamation of the well-orders
$\leq _\alpha $
in the permutation model. By the dynamical closure assumption on I and Proposition 2.13(2), it follows that the group elements
$\gamma _\alpha $
for
$\alpha \in \kappa $
witness the dynamical
$\kappa $
-completeness.
The stratification effect stops at a clearly predetermined cardinal.
Theorem 5.4 Suppose that
$\Gamma \curvearrowright X, I$
is a dynamical ideal. If I is generated by
$\kappa $
many sets, then in the permutation model
$W[[X]]$
,
$\textrm {AC}_\kappa $
is equivalent to the well-ordered axiom of choice.
Proof The right-to-left implication is clear. For the right-to-left implication, by Proposition 2.13(1) without loss assume that I is dynamically closed. Suppose
$a\in I$
is a set. In
$V[[X]]$
, let
$b_\alpha \colon \alpha \in \kappa $
be a collection generating the ideal I. For each
$\alpha \in \kappa $
, let
$A_\alpha $
be the set of all pairs
$\langle \gamma \cdot b_\alpha , \leq \rangle ,$
where
$\gamma \in \mathrm {pstab}(a)$
and
$\leq $
is a well-ordering on
$\gamma \cdot b_\alpha $
. It is clear that the sequence
$A=\langle A_\alpha \colon \alpha \in \kappa \rangle $
belongs to the permutation model, as
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
. By
$\textrm {AC}_\kappa $
in the permutation model, there are elements
$\gamma _\alpha \in \mathrm {pstab}(a)$
and well-orderings
$\leq _\alpha $
for
$\alpha \in \kappa $
such that the sequence
$\langle \gamma _\alpha \cdot b_\alpha , \leq _\alpha \colon \alpha \in \kappa \rangle $
is a selector for A and belongs to the permutation model. The set
$c=\bigcup _\alpha \gamma _\alpha \cdot b_\alpha $
is well-orderable in the premutation model by an amalgamation of the well-orders
$\leq _\alpha $
. By the dynamical closure assumption and Proposition 2.13(2),
$c\in I$
holds. It is not hard to see that the set c witnesses the instance of cofinal orbits for the set
$a\in I$
. By Theorem 3.3, the axiom of well-ordered choice holds in the permutation model.
Thus, in the popular permutation models obtained from automorphisms of countable structures and the ideal of finite sets (Example 2.6), countable choice is in fact equivalent to well-ordered choice.
Example 5.5 Let X be the closed unit interval
$[0, 1]$
, let
$\Gamma $
be the group of orientation-preserving self-homeomorphisms of X acting by application, and let I be the ideal of closed countable subsets of X. Then, the ideal
$\Gamma \curvearrowright X, I$
is dynamically
$\aleph _0$
-complete, but not dynamically
$\aleph _1$
-complete.
Compare this with Examples 3.16 and 4.8: the associated permutation model satisfies the axiom of countable choice, but not the axiom of well-ordered choice or dependent choice. This example was improved by Young [Reference Young8] who showed that its conclusion holds for X an arbitrary Euclidean space.
Proof Let
$a, b_n\colon n\in \omega $
be countable closed subsets of X. Let J be the set of all inclusion-maximal open intervals disjoint from a. For each interval
$j\in J$
and every
$n\in \omega $
, find an open interval
$j(n)\subseteq j$
which is disjoint from
$b_n$
and its endpoints are still in j, and find an orientation-preserving self-homeomorphism
$h_{jn}\colon j\to j$
such that
$j\setminus h_{jn}(j(n))$
consists of one interval at each end of j, both of length less than
$2^{-n}$
. For each number
$n\in \omega $
, let
$\gamma _n=\mathrm {id}\restriction a\cup \bigcup _{j\in J}h_{jn}$
; I will show that these group elements work as required.
It will be enough to show that
$c=a\cup \bigcup _n\gamma _n\cdot b_n$
is a closed set, because it is clearly countable. Suppose then that
$\langle x_k\colon k\in \omega \rangle $
is a converging sequence of points in c with limit x, and work to show that
$x\in c$
. There are two cases.
Case 1. No interval
$j\in J$
contains a tail of the sequence. In this case, the limit x must be in the set a, completing the proof.
Case 2. Case 1 fails. Let
$j\in J$
be the unique interval containing a tail of the sequence. If the sequence has nonempty intersection with only finitely many sets
$\gamma _n\cdot b_n$
, then the limit must belong to one of those finitely many sets, completing the proof. If, on the other hand, the sequence has nonempty intersection with infinitely many sets
$\gamma _n\cdot b_n$
, then by the choice of the homeomorphisms
$h_{jn}$
, it must be the case that the limit is equal to one of the endpoints of j. Both of these endpoints are in the set a. The example has been demonstrated.
Example 5.6 [Reference Howard and Rubin1, Model N23]
Let
$\langle X, \leq \rangle $
be a countable dense linear order without endpoints, let
$\Gamma $
be its automorphism group, and let I be the ideal of those subsets of X which are well-ordered by
$\leq $
. The dynamical ideal
$\Gamma \curvearrowright X, I$
is dynamically
$\aleph _0$
-complete.
Proof Let
$a\in I$
and
$b_n$
for
$n\in \omega $
be sets in the ideal; I must produce automorphisms
$\gamma _n\in \mathrm {pstab}(a)$
for all
$n\in \omega $
such that
$a\cup \bigcup _n\gamma _n\cdot b_n\in I$
holds. Let U be the set of all open intervals of X which are disjoint from a and maximal such. Inside each interval
$i\in U$
pick points
$x_{in}$
for
$n\in \omega $
such that they form an increasing sequence cofinal in i, and automorphisms
$\gamma _{in}$
equal to identity on
$X\setminus i$
such that
$\gamma _{in}(\min (b_n\cap i))\geq x_{in}$
whenever
$b_n\cap i\neq 0$
. Let
$\gamma _n$
be the composition of all
$\gamma _{in}$
for
$i\in U$
; this makes sense since the automorphisms
$\gamma _{in}$
for
$i\in U$
have pairwise disjoint supports. I claim that the set
$c=a\cup \bigcup _n\gamma _n\cdot b_n$
is well-ordered as desired.
To see this, suppose toward a contradiction that
$\langle x_m\colon m\in \omega \rangle $
is a strictly decreasing sequence in c. By the well-ordering assumption on a, the points
$y_m=\min \{z\in a~\colon~z\geq x_m\}$
have to stabilize at some point; the tail of the sequence then belongs to the same open interval
$i\in U$
which borders on its right end at the eventually stable value of the points
$y_m$
. By the cofinal choice of the points
$x_{in}$
in i, there is an
$n\in \omega $
such that a tail of the sequence consists of elements of i which are smaller than
$x_{in}$
. However, this tail is then a subset of the set
$\bigcup _{k\in n}\gamma _k\cdot b_k$
. Since this is a finite union of well-ordered sets, it is itself well-ordered, and it cannot contain an infinite strictly decreasing sequence. A contradiction.
Example 5.7 [Reference Howard and Rubin1, Model N10]
Let
$\langle X, \leq \rangle $
be a countable dense linear order without endpoints, let
$\Gamma $
be its automorphism group, and let I be the ideal of those subsets of X which are well-ordered by
$\leq $
, bounded in X, and bounded below every element of X. The dynamical ideal
$\Gamma \curvearrowright X, I$
is dynamically
$\aleph _0$
-complete. The status of countable choice has apparently not been known in the associated permutation model.
Proof Let
$a\in I$
and
$b_n$
for
$n\in \omega $
be sets in the ideal; I must produce automorphisms
$\gamma _n\in \mathrm {pstab}(a)$
for all
$n\in \omega $
such that
$a\cup \bigcup _n\gamma _n\cdot b_n\in I$
holds. Let U be the set of all open intervals of X which are disjoint from a and maximal such. Note that the right endpoint of each interval
$i\in U$
belongs to a, except for the rightmost, unbounded interval in U; in any case, the sets
$b_n$
are all bounded in i. Inside each interval
$i\in U$
pick points
$x_{in}$
for
$n\in \omega $
such that they form an increasing sequence which is bounded and does not have a supremum in X, pick points
$y_{in}\in i$
such that
$b_n\cap i$
is bounded by
$y_{in}$
, and pick automorphisms
$\gamma _{in}$
equal to identity on
$X\setminus i$
such that
$\gamma _{in}(\min (b_n\cap i))\geq x_{in}$
whenever
$b_n\cap i\neq 0$
and
$\gamma _{in}(y_{in})=x_{in+1}$
. Let
$\gamma _n$
be the composition of all
$\gamma _{in}$
for
$i\in U$
; this makes sense since the automorphisms
$\gamma _{in}$
for
$i\in U$
have pairwise disjoint supports. I claim that the set
$c=a\cup \bigcup _n\gamma _n\cdot b_n$
is well-ordered and bounded below each point as desired.
For the well-ordering, suppose toward a contradiction that
$\langle x_m\colon m\in \omega \rangle $
is a strictly decreasing sequence in c. By the well-ordering assumption on a, the points
$y_m=\min \{z\in a\colon z\geq x_m\}$
have to stabilize at some point; the tail of the sequence then belongs to the same open interval
$i\in U$
which borders on its right end at the eventually stable value of the points
$y_m$
. By the choice of the points
$x_{in}$
in i, there is an
$n\in \omega $
such that a tail of the sequence consists of elements of i which are smaller than
$x_{in}$
. However, this tail is then a subset of the set
$\bigcup _{k\in n}\gamma _k\cdot b_k$
. Since this is a finite union of well-ordered sets, it is itself well-ordered, and it cannot contain an infinite strictly decreasing sequence. A contradiction.
For the boundedness, let
$z\in X$
be an arbitrary point. Since a is bounded below z, z is an internal point or the right-hand endpoint of some interval
$i\in U$
. If z is greater than all points
$x_{in}$
for
$n\in \omega $
, then as these points do not have a supremum in X, the sequence
$\langle x_{in}\colon n\in \omega \rangle $
is bounded below z, and so is the set c. If there is a number n such that
$z\leq x_{in}$
, then
$c\cap i$
below z is the union of the sets
$\gamma _k\cdot b_k$
for
$k\in n$
, each of which is bounded below z, so c is bounded below z again. The proof is complete.
Example 5.8 [Reference Howard and Rubin1, Model N21]
Let
$\kappa $
be an infinite regular cardinal. Let X be the structure
$(\kappa ^+)^{<\omega }$
ordered by reverse extension. Let
$\Gamma $
be the group of all automorphisms of X acting by application, and let I be the ideal generated by well-founded subtrees of X of cardinality at most
$\kappa $
. Then,
$\Gamma \curvearrowright X, I$
is a dynamically
$\kappa $
-complete ideal. In the permutation model, X witnesses the failure of DC, while
$\kappa $
-choice holds.
Proof Let
$a, b_\alpha $
for
$\alpha \in \kappa $
be sets in the ideal I; increasing them if necessary, I may assume that they are all well-founded trees. For every node
$x\in a$
and every
$\alpha \in \kappa $
, write
$c(\alpha , x)=\{y\in b_\alpha \setminus a\colon y$
is an immediate successor of
$x\}$
. For each
$\alpha \in \kappa ,$
choose
$\gamma _\alpha \in \mathrm {pstab}(a)$
to be an automorphism of X such that for every node
$x\in a$
, the sets
$\gamma _\alpha \cdot c(\alpha , x)$
for
$\alpha \in \kappa $
are pairwise disjoint. This is possible since the sets
$c(\alpha , x)$
have cardinality at most
$\kappa $
while the set of immediate successors of x has cardinality
$\kappa ^+$
. I claim that the tree
$a\cup \bigcup _\alpha \gamma _\alpha \cdot b_\alpha \subseteq X$
is well-founded. Indeed, any putative infinite branch v through it either must be a subset of a (an impossibility by the well-foundedness assumption on a) or the set
$v\cap a$
is finite and contains a longest element, call it x. If y is the immediate successor of x in v, then there is a unique number
$\alpha \in \kappa $
such that
$y\in \gamma _\alpha \cdot b_\alpha $
by the choice of the automorphisms
$\gamma _\alpha $
. This means that the branch v must be a subset of
$\gamma _\alpha \cdot b_\alpha $
, contradicting the assumed well-foundedness of
$b_\alpha $
.
6 Simplicity
One fragment of the axiom of choice for which an attractive dynamical criterion can be found is well-orderable closure.
Definition 6.1 [Reference Howard and Rubin1, Form 231]
Well-orderable closure is the statement that for every well-orderable set A consisting of well-orderable sets,
$\bigcup A$
is well-orderable.
This is often verified in permutation models as a consequence of the well-ordered axiom of choice (Section 3). In situations where this is not available, the following elegant criterion on dynamical ideals is helpful.
Definition 6.2 A dynamical ideal
$\Gamma \curvearrowright X, I$
is:
-
(1) simple if for every
$a\subseteq b\in I$
, the only normal subgroup of
$\mathrm {pstab}(a)$
containing
$\mathrm {pstab}(b)$
is
$\mathrm {pstab}(a)$
itself; -
(2) almost simple if for every set in I has a superset
$a\in I$
such that for every
$a\subseteq b\in I$
, the only normal subgroup of
$\mathrm {pstab}(a)$
containing
$\mathrm {pstab}(b)$
is
$\mathrm {pstab}(a)$
itself.
Clearly, every simple dynamical ideal is almost simple. While the weaker version is sufficient to imply well-orderable closure, the full simplicity has the advantage of being natural and closed under the subideal operation. One natural example of an almost simple ideal which is not simple is introduced in Example 6.18.
Theorem 6.3 Suppose that
$\Gamma \curvearrowright X, I$
is an almost simple dynamical ideal. Then, in the associated permutation model, a union of well-orderable set of well-orderable sets is well-orderable.
Clearly, every simple dynamical ideal is almost simple. While the weaker version is sufficient to imply well-orderable closure, the full simplicity has the advantage of being natural and closed under the subideal operation. One natural example of an almost simple ideal which is not simple is introduced in Example 6.17.
Proof Suppose that
$\Gamma \curvearrowright X, I$
is almost simple. Let A be a well-orderable set consisting of well-orderable sets in the permutation model. By Proposition 2.11, there is a set
$a\in I$
such that
$\mathrm {pstab}(a)\subseteq \mathrm {pstab}(A)$
. Enlarging a if necessary, I may assume that for every set
$b\in I,$
which is a superset of a, the only normal subgroup of
$\mathrm {pstab}(a)$
containing
$\mathrm {pstab}(b)$
is
$\mathrm {pstab}(a)$
itself. It will be enough to show that
$\mathrm {pstab}(a)\subseteq \mathrm {pstab}(\bigcup A)$
. In other words, given a set
$B\in A$
and
$C\in B$
, I must prove that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(C)$
. Let
$\delta \in \mathrm {pstab}(a)$
be any element and work to show that
$\delta \cdot C=C$
.
To prove this, use Proposition 2.11 again to find a set
$b\in I$
such that
$a\subseteq b$
and
$\mathrm {pstab}(b)\subseteq \mathrm {pstab}(B)$
. By the choice of the set a, there is a number
$n\in \omega $
and elements
$\gamma _m\in \mathrm {pstab}(a)$
and
$\delta _m\in \mathrm {pstab}(b)$
for
$m\in n$
such that
$\delta =\prod _{m\in n}\gamma _m^{-1}\delta _m\gamma _m$
. It will be enough to show that for every
$m\in n$
,
$\gamma _m^{-1}\delta _m\gamma _m\cdot C=C$
. Toward this, observe that
$\delta _m$
fixes all elements of B’ in particular, it fixes
$\gamma _m\cdot C$
. The proof is complete.
Simplicity is an attractive concept with an attractive conclusion. However, as in the case of simplicity of groups, it is not always easy to check. The first class of examples comes from model theory.
Definition 6.4 Let
$\mathcal {F}$
be a Fraissé class with disjoint amalgamation. Say that
$\mathcal {F}$
has hereditary canonical amalgamation if there is a function C which to each ordered pair of
$\mathcal {F}$
-structures
$\langle A, B\rangle $
in amalgamation position assigns a minimal disjoint amalgamation so that:
-
(1) C is invariant under isomorphism in both variables: if
$\phi \colon A\to A'$
and
$\psi \colon B\to B'$
are isomorphisms which agree on
$\mathrm {dom}(A)\cap \mathrm {dom}(B)$
, then there is an isomorphism of
$C(A, B)$
to
$C(A', B')$
extending
$\phi \cup \psi $
; -
(2) C is hereditary for substructures in the left variable: if
$A'$
is an induced substructure of A such that
$\mathrm {dom}(A)\cap \mathrm {dom}(B)\subseteq \mathrm {dom}(A')$
, then there is an isomorphism between
$C(A', B)$
and the algebraic closure of
$\mathrm {dom}(A')\cup \mathrm {dom}(B)$
in
$C(A, B)$
which is the identity on
$\mathrm {dom}(A')\cup \mathrm {dom}(B)$
.
Compared to the canonical amalgamation of Paolini and Shelah [Reference Paolini and Shelah7], the hereditary clause is added.
Theorem 6.5 Let
$\mathcal {F}$
be a Fraissé class with hereditary canonical disjoint amalgamation, let X be its limit structure, let
$\Gamma $
be the group of all automorphisms of X acting by application, and let I be the ideal of finite sets on X. Then,
$\Gamma \curvearrowright X, I$
is a simple dynamical ideal.
Proof As a matter of terminology, say that a finite set
$a\subseteq X$
is algebraically closed if it is closed under all functions of X;
$\mathrm {acl}(a)$
is the smallest algebraically closed subset of X containing a. Let C be the canonical amalgamation function on
$\mathcal {F}$
. Consider
$\Gamma $
as a Polish group with the usual automorphism group topology. Let
$a\subseteq b$
be finite subsets of X; I must prove that within
$\mathrm {pstab}(a)$
, the normal subgroup
$\Delta $
generated by
$\mathrm {pstab}(b)$
is equal to
$\mathrm {pstab}(a)$
itself. I may assume that the sets
$a, b$
are both algebraically closed. Since
$\Delta $
is a group generated by an open subset of
$\mathrm {pstab}(a)$
, it is open, therefore closed. Thus, it is enough to show that
$\Delta $
is dense in
$\mathrm {pstab}(a)$
.
To this end, let
$\pi \colon c\to d$
be any morphism between two finite subsets of X, both including a as a subset, both algebraically closed, and such that
$\pi \restriction a=\mathrm {id}$
. I must find an element of
$\Delta $
extending
$\pi $
. To do this, let
$e=\mathrm {acl}(b\cup c\cup d)$
. By the saturation properties of X, there must be a finite set
$f\subseteq X$
such that:
-
•
$f\cap e=a$
; -
• there is an isomorphism
$\theta \colon e\to f$
which is identity on a; -
•
$X\restriction \mathrm {acl}(e\cup f)$
is isomorphic to
$C(X\restriction e, X\restriction f)$
.
Let
$\delta \in \mathrm {pstab}(a)$
be an automorphism extending
$\theta $
. By the heredity and invariance properties of C, there is a morphism between the algebraic closures of
$c\cup f$
and
$d\cup f$
extending the function
$\pi \cup \mathrm {id}_f$
. Let
$\gamma \in \mathrm {pstab}(f)$
be any automorphism of X extending it. Now,
$\gamma \in \mathrm {pstab}(f)$
implies that
$\delta ^{-1}\gamma \delta \in \mathrm {pstab}(e)\subseteq \mathrm {pstab}(b)$
. It follows that
$\gamma =\delta (\delta ^{-1}\gamma \delta )\delta ^{-1}$
is an element of
$\Delta $
extending
$\pi $
as desired.
Nearly all permutation models associated with limits of Fraissé structures allow of a much more detailed analysis than just simplicity; this will appear in forthcoming work. For now, I will list only two very special examples.
Example 6.6 Let
$\mathcal {F}$
be the class of structures with no relations and no functions; hereditary canonical amalgamation obviously holds. Let X be its limit, the countable set with no structure. The associated model is [Reference Howard and Rubin1, Model N1]. In this model,
$[X]^{<\aleph _0}$
is a set of well-orderable sets without a selector, showing that the conclusion of Theorem 6.3 cannot be strengthened.
Example 6.7 The class of rational ultrametric spaces has hereditary canonical amalgamation. Given any two finite rational ultrametric spaces
$A, B$
in the amalgamation position with nonempty intersection, with their metrics denoted by
$d_A$
and
$d_B$
, respectively, define the metric d on
$\mathrm {dom}(A)\cup \mathrm {dom}(B)$
by letting
$d_A\cup d_B\subseteq d$
, and for points
$x\in \mathrm {dom}(A)\setminus \mathrm {dom}(B)$
and
$y\in \mathrm {dom}(B)\setminus \mathrm {dom}(A)$
, the distance
$d(x,y)$
is defined in two cases. If there is a point
$z\in \mathrm {dom}(A)\cap \mathrm {dom}(B)$
such that
$d_A(x, z)\neq d_B(z, y)$
, then set
$d(x, y)=\max \{d_A(x, z), d_B(z, y)\}$
, and if there is no such z, then let
$d(x, y)=\min \{d_A(z, y)\colon z\in \mathrm {dom}(A)\cap \mathrm {dom}(B)\}$
. It must be verified that the definition is sound and yields an ultrametric space. It is clear that such amalgamation is hereditary and canonical.
Example 6.8 The class of vector spaces over a fixed finite field has hereditary canonical amalgamation:
$C(A, B)$
will be the vector space with the underlying set
$\mathrm {dom}(A)\times \mathrm {dom}(B)$
modulo the equivalence relation E defined by
$\langle x, y\rangle \mathrel {E}\langle x', y,\rangle $
if
$x-x'$
and
$y'-y$
are identical elements of
$\mathrm {dom}(A)\cap \mathrm {dom}(B)$
. Addition and scalar multiplication are defined coordinatewise.
Example 6.9 Let
$\mathcal {F}$
be the set of finite structures with a function (coded as a relation) which from each unordered quadruple selects an unordered pair. Then,
$\mathcal {F}$
does not have canonical amalgamation: there is no isomorphism-invariant way to amalgamate disjoint sets A and B such that A has three elements and B has one.
Finally, the collection of relational Fraissé classes with hereditary canonical disjoint amalgamation is closed under superposition, which yields interesting classes, such as linearly ordered rational ultrametric spaces and the like.
Let me now turn to more set-theoretic examples of simple dynamical ideals.
Example 6.10 Let X be an ultrahomogeneous linear order, let
$\Gamma $
be the group of all automorphisms of X acting by application, and let I be the ideal of nowhere dense sets. Then,
$\Gamma \curvearrowright X, I$
is a simple dynamical ideal.
Proof The argument uses the following key claim.
Claim 6.11 Let
$a\subseteq X$
be a nowhere dense set, and let
$\gamma \in \Gamma $
be an automorphism whose orbits are both cofinal and coinitial in X. Then, there are
$\gamma _i\in \mathrm {pstab}(a)$
and
$\delta _i\in \Gamma $
for
$i\in 4$
such that
$\gamma =\prod _{i\in 4}\delta _i^{-1}\gamma _i\delta _i$
.
Proof Without loss of generality, assume that for all
$x\in X$
,
$\gamma \cdot x>x$
; the proof for
$\gamma \cdot x<x$
is symmetric. Let
$\langle x_n\colon n\in \mathbb {Z}\rangle $
be an increasing enumeration of one of the orbits. The ultrahomogeneity assumption shows that there are automorphisms
$\alpha _0, \alpha _1\in \Gamma $
such that
$a_0=\alpha _0\cdot a\subseteq \bigcup _n (x_{4n-1}, x_{4n+1})$
and
$a_1=\alpha _1\cdot a\subseteq \bigcup _n(x_{4n+1}, x_{4n+3})$
. I will express
$\gamma $
as a composition of four automorphisms in
$\mathrm {pstab}(a_0)\cup \mathrm {pstab}(a_1)$
. Since
$\mathrm {pstab}(a_0)=\alpha _0\mathrm {pstab}(a)\alpha _0^{-1}$
and
$\mathrm {pstab}(a_1)=\alpha _1\mathrm {pstab}(a)\alpha _1^{-1}$
, this will conclude the proof.
First, use the ultrahomogeneity assumption on X to argue that there is an automorphism
$\delta _0\in \mathrm {pstab}(a_0)$
fixing
$x_{4n}$
and such that
$\delta _0(x_{4n+1})=x_{4n+2}$
and
$\delta _0(x_{4n+2})=x_{4n+3}$
for all
$n\in \mathbb {Z}$
. Similarly, let
$\delta _1\in \mathrm {pstab}(a_1)$
be an automorphism fixing
$x_{4n+2}$
and
$x_{4n+3}$
and such that
$\delta _1(\delta _0(x_{4n+3}))=x_{4n+4}$
and
$\delta _1(x_{4n})=x_{4n+1}$
for all
$n\in \omega $
. Let
$\beta =\delta _1\delta _0$
and observe that
$\{x_n\colon n\in \mathbb {Z}\}$
is an orbit of
$\beta $
. Now, let
$\delta _2\in \mathrm {pstab}(a_0)$
be an automorphism which fixes the interval
$(x_{4n-1}, x_{4n+1})$
pointwise and on
$(x_{4n+1}, x_{4n+3})$
it is equal to
$\gamma \beta ^{-1}$
, this for all
$n\in \mathbb {Z}$
. Similarly, let
$\delta _3\in \mathrm {pstab}(a_1)$
be an automorphism which fixes the interval
$(x_{4n+1}, x_{4n+3})$
pointwise and on
$(x_{4n-1}, x_{4n+1})$
it is equal to
$\gamma \beta ^{-1}$
, this for all
$n\in \mathbb {Z}$
. Note that
$\delta _2$
and
$\delta _3$
have disjoint supports, therefore they commute and
$\delta _2\delta _3=\delta _3\delta _2=\gamma \beta ^{-1}$
. In consequence,
$\gamma =\delta _3\delta _2\delta _1\delta _0$
as desired.
Now, suppose that
$a\subseteq b$
are sets in the ideal I, let
$\gamma \in \mathrm {pstab}(a)$
, and work to show that
$\gamma $
belongs to the normal subgroup of
$\mathrm {pstab}(a)$
generated by
$\mathrm {pstab}(b)$
. Let U be the set of all intervals of X in which
$\gamma $
has an orbit which is both coinitial and cofinal in U. Note that such intervals do not have smallest or largest elements, therefore they are ultrahomogeneous themselves, and every orbit is both coinitial and cofinal in them. Note also that
$a\subseteq X\setminus \bigcup U$
and
$\gamma $
fixes all elements of
$X\setminus \bigcup U$
. Now, note that each interval
$u\in U$
is order-isomorphic to X; write
$\Gamma _u$
for its group of automorphisms. Apply the claim with u and
$\Gamma _u$
instead of X and
$\Gamma $
, and with the nowhere dense set
$a\cap u\subseteq u$
to find automorphisms
$\gamma _{iu}\in \mathrm {pstab}(a\cap u)$
in
$\Gamma _u$
and
$\delta _{iu}\in \Gamma _u$
for
$i\in 4$
such that
$\gamma \restriction u=\prod _{i\in 4}\delta _{iu}^{-1}\gamma _{iu}\delta _{iu}$
. Finally, for each
$i\in 4,$
let
$\gamma _i\in \Gamma $
be the union of all
$\gamma _{iu}$
for
$u\in U$
together with the identity on
$X\setminus \bigcup U$
, and similarly for
$\delta _i$
. It is clear that
$\gamma =\prod _{i\in 4}\delta _i^{-1}\gamma _i\delta _i$
, so
$\gamma \in \Delta $
as desired.
Example 6.12 [Reference Howard and Rubin1, Model N16]
Let
$\kappa $
be an uncountable cardinal, let X be a set of cardinality at least
$\kappa $
, let
$\Gamma $
be the group of all permutations of X acting by application, and let
$I_\kappa $
be the ideal of subsets of X of cardinality smaller than
$\kappa $
. Then,
$\Gamma \curvearrowright X, I_\kappa $
is a simple dynamical ideal. The status of well-orderable closure for
$\kappa $
of countable cofinality has apparently not been known.
Proof Let
$a\subseteq b$
be sets in
$I_\kappa $
, let
$\Delta $
be the normal subgroup of
$\mathrm {pstab}(a)$
generated by
$\mathrm {pstab}(b)$
, let
$\gamma \in \mathrm {pstab}(a)$
be an arbitrary group element, and work to show that
$\gamma \in \Delta $
. Let
$c\in I$
be a set containing b and such that c is closed under
$\gamma $
. Let
$\delta \in \mathrm {pstab}(a)$
be a group element such that
$\delta \cdot b\cap c=a$
. Then,
$(\gamma \restriction c)\cup (\mathrm {id}\restriction \delta \cdot b)$
is a function defined on a set of cardinality smaller than
$\kappa $
; let
$\alpha \in \mathrm {pstab}(a)$
be any permutation of X extending it.
Now,
$\alpha \in \mathrm {pstab}(\delta \cdot b)$
holds, so
$\delta ^{-1}\alpha \delta \in \mathrm {pstab}(b)$
holds, and
$\alpha =\delta (\delta ^{-1}\alpha \delta )\delta ^{-1}$
is an element of
$\Delta $
. At the same time,
$\alpha =\gamma $
on the set c, so
$\alpha ^{-1}\gamma \in \mathrm {pstab}(c)\subseteq \mathrm {pstab}(b)$
must hold. It follows that
$\gamma =\alpha (\alpha ^{-1}\gamma )$
belongs to
$\Delta $
as required.
Example 6.13 [Reference Howard and Rubin1, Model N21]
Let
$\kappa $
be an uncountable regular cardinal. Let
$X=\kappa ^{<\omega }$
partially ordered by reverse extension, let
$\Gamma $
be the group of all automorphisms of X acting by application, and let I be the ideal generated by well-founded subtrees of X of cardinality smaller than
$\kappa $
. Then,
$\Gamma \curvearrowright X, I$
is a simple dynamical ideal. The status of well-orderable closure in the associated permutation model apparently has not been known.
Proof Let
$a\subseteq b$
be sets in the ideal I. Since the dynamical closure of any subset of X is a subtree of X, I may assume that both a and b are in fact well-founded trees. Let
$\Delta $
be the normal subgroup of
$\mathrm {pstab}(a)$
generated by
$\mathrm {pstab}(b)$
and let
$\gamma \in \mathrm {pstab}(a)$
be an arbitrary automorphism of X; I must show that
$\gamma \in \Delta $
holds.
Let
$c\subseteq X$
be any tree of cardinality smaller than
$\kappa $
which contains b and which is closed under
$\gamma $
and its inverse. Let
$\delta \in \mathrm {pstab}(a)$
be an automorphism such that
$c\cap \delta \cdot b=a$
. Then, the map
$(\gamma \restriction c)\cup (\mathrm {id}\restriction \delta \cdot b)$
is an automorphism of a subtree of X of cardinality smaller than
$\kappa $
. As such, it can be extended to a full automorphism
$\alpha \in \mathrm {pstab}(a)$
. Then,
$\alpha \in \mathrm {pstab}(\delta \cdot b)$
, so
$\delta ^{-1}\alpha \delta \in \mathrm {pstab}(b)$
, and
$\alpha =\delta (\delta ^{-1}\alpha \delta )\delta ^{-1}\in \Delta $
. At the same time,
$\alpha =\gamma $
on the set c, so
$\alpha ^{-1}\gamma \in \mathrm {pstab}(c)\subseteq \mathrm {pstab}(b)$
must hold. It follows that
$\gamma =\alpha (\alpha ^{-1}\gamma )$
belongs to
$\Delta $
as required.
Last, but not least, the concept of a simple dynamical ideal has been formulated in such a way that it survives many common operations on ideals. I will state only the most obvious.
Example 6.14 A subideal of a simple dynamical ideal is simple.
In view of Example 6.10, this includes such dynamical ideals as the following.
Example 6.15 [Reference Howard and Rubin1, Model N23]
Let X be an ultrahomogeneous linear order, let
$\Gamma $
be the group of all automorphisms of X acting by application, and let I be the ideal of sets which are well-ordered by the linear order of X. Then,
$\Gamma \curvearrowright X, I$
is a simple dynamical ideal. The status of well-orderable closure in this model has apparently not been known.
Example 6.16 An increasing union of simple dynamical ideals is again simple.
Finally, a couple of natural examples of dynamical ideals which are not simple or almost simple.
Example 6.17 Let
$X=\mathbb {Q}$
with its natural ordering, let
$\Gamma $
be the Polish group of all automorphisms of X, and let I be the ideal of all bounded subsets of X. Then, I has cofinal orbits by Example 3.7, so the associated permutation model satisfies well-ordered choice by Theorem 3.3 and the well-ordered closure as well. However, it is not almost simple. To see this, for rational q write
$b_q$
for the set of all rationals smaller than q. Let
$a\subseteq X$
be any bounded set, denote its supremum by s, let
$q>s$
be any rational, and consider the set
$b=b_q$
. Then, the normal subgroup of
$\mathrm {pstab}(a)$
generated by
$\mathrm {pstab}(b)$
is equal to
$\bigcup _{r>s}\mathrm {pstab}(b_r)$
. However, it is not difficult to manufacture an element of
$\mathrm {pstab}(a)$
which fixes no rational larger than s.
Example 6.18 [Reference Howard and Rubin1, Model N51]
Let X be the set
$\mathcal {P}(\omega )$
equipped with the subset relation. Let
$\Gamma $
be the group of all automorphisms of X, and let I be the ideal of finite subsets of X. Then,
$\Gamma \curvearrowright X, I$
is an almost simple, not simple dynamical ideal. The status of well-orderable closure in the associated permutation model was apparently unknown.
Proof It is immediate that every element of
$\Gamma $
is determined by its action on singletons, so
$\Gamma $
is naturally isomorphic to
$S_\infty $
. The Boolean operations of union, intersection, and complement on X are invariant under the action.
To show that the dynamical ideal is not simple, let
$x\in X$
be any set containing exactly two elements. Let
$y_0, y_1$
be the singletons formed by these two elements and observe that
$\mathrm {pstab}(\{y_0, y_1\})$
is a proper normal subgroup of
$\mathrm {pstab}(\{x\})$
. To show that the dynamical ideal is almost simple, let
$a\subseteq X$
be a finite Boolean subalgebra such that for every finite set
$x\in a$
also contains all singletons formed by elements of a. It will be enough to show that for every finite Boolean algebra
$b\subseteq X$
containing a, the normal subgroup
$\Delta \subseteq \mathrm {pstab}(a)$
generated by
$\mathrm {pstab}(b)$
is equal to
$\mathrm {pstab}(a)$
.
To see this, for every infinite atom
$x\in a$
consider the group
$\Delta _x$
of all elements of
$\Gamma $
fixing each element
$\{n\}\in X$
for every
$n\in \omega \setminus x$
. Clearly,
$\Delta _x$
is naturally isomorphic to the permutation group on x, therefore to
$S_\infty $
; it is also a subset of
$\mathrm {pstab}(a)$
. The group
$\mathrm {pstab}(b)\cap \Delta _x$
is an uncountable subgroup of
$\Delta _x$
. Since the only uncountable normal subgroup of
$S_\infty $
is
$S_\infty $
itself, it must be the case that
$\Delta _x\subseteq \Delta $
holds. Finally, the group
$\mathrm {pstab}(a)$
is clearly generated by the union of the groups
$\Delta _x$
as x varies over all infinite atoms of a. It follows that
$\Delta =\mathrm {pstab}(a)$
as desired.
On the opposite end of the spectrum lurk the dynamical ideals associated with abelian groups. This is the content of the following theorem.
Theorem 6.19 Let
$\Gamma \curvearrowright X, I$
be an abelian dynamical ideal. Then, in the associated permutation model,
-
(1) every set is a union of a well-orderable collection of well-orderable sets;
-
(2) the axiom of choice for families of finite sets implies the full axiom of choice.
Proof For (1), let
$A\in W[[X]]$
be a set, and let
$a\in I$
be a set such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
. I need to produce a well-orderable set B such that B is well-orderable, every element of B is, and
$\bigcup B=A$
. To this end, let B be the set of all
$\mathrm {pstab}(a)$
-orbits of elements of A. Every element of B is
$\mathrm {pstab}(a)$
-invariant, so B belongs to the permutation model and it is well-orderable there by Proposition 2.11. Now, let
$C\in B$
be an arbitrary set, let
$D\in C$
be arbitrary, and let
$d\in I$
be such that
$a\subseteq d$
and
$\mathrm {pstab}(d)\subseteq \mathrm {stab}(D)$
. It will be enough to show that
$\mathrm {pstab}(d)$
fixes all elements of C – then, C is well-orderable in the permutation model by Proposition 2.11 again.
Thus, suppose that
$\gamma \in \mathrm {pstab}(d)$
is arbitrary. Let
$\delta \in \mathrm {pstab}(a)$
be arbitrary; I must show that
$\gamma \delta \cdot D=\delta \cdot D$
. To this end, use the commutativity of the group
$\Gamma $
to conclude that the left-hand side of the equation is equal to
$\delta \gamma \cdot D,$
which is equal to
$\delta \cdot D$
as
$\gamma \in \mathrm {stab}(D)$
. (1) follows.
For (2), in
$W[[X]]$
, consider the set A which contains every nonempty finite subset of X and every unordered pair of nonempty disjoint subsets of X. It will be enough to show that whenever f is a selector function on A and
$b\in I$
is a set such that
$\mathrm {pstab}(b)\subseteq \mathrm {stab}(f)$
, then
$\mathrm {pstab}(b)=\mathrm {pstab}(X)$
. To do this, fix f and b as assumed, and toward a contradiction assume that there are elements
$\gamma \in \mathrm {pstab}(b)$
and
$x\in X$
such that
$\gamma \cdot x\neq x$
. Write c for the orbit of x under
$\gamma $
and
$\gamma ^{-1}$
. There are two cases.
Case 1. The set
$c\subseteq X$
is finite. Then,
$c\in \mathrm {dom}(f)$
, both f and c are fixed by
$\gamma $
, but no element of c is. This must include the element
$f(c)\in c$
, contradicting the fact that the action by
$\gamma $
is an
$\in $
-automorphism of the permutation model.
Case 2. The set
$c\subseteq X$
is infinite. In such a case, define an equivalence relation E on X connecting elements
$y, z\in X$
if there is an even integer n such that
$y=\gamma ^n\cdot z$
. The equivalence relation E is invariant under the group action: whenever
$\delta \in \Gamma $
is arbitrary and
$y=\gamma ^n\cdot z,$
then
$\delta \cdot y=\delta \gamma ^n\cdot z=\gamma ^n\delta \cdot z$
, where the last equality follows from commutativity of the group
$\Gamma $
. It follows that E belongs to the permutation model. Consider the set d of the two E-equivalence classes represented in the set c. It is clear that
$d\in \mathrm {dom}(f)$
,
$\gamma $
fixes both f and d. It is also clear that
$\gamma $
flips the two elements of d, so it moves
$f(d)$
. This again contradicts the fact that the action by
$\gamma $
is an
$\in $
-automorphism of the permutation model.
Example 6.20 [Reference Howard and Rubin1, Model N2(LO)]
Let
$X=\omega \times \mathbb {Z}$
, let
$\Gamma =\mathbb {Z}^\omega $
be the abelian group acting on X by
$\gamma \cdot \langle n, z\rangle =\langle n, \gamma (n)+z\rangle $
, and let I be the ideal generated by the vertical sections of X. The axiom of choice fails in the associated permutation model; thus, there must be a collection of finite sets for which there is no choice function. To find it, for each
$n\in \omega ,$
let
$E_n$
be the equivalence relation on the nth vertical section of X defined by
$\langle n, z_0\rangle E_n\langle n, z_1\rangle $
if
$z_0-z_1$
is an even integer. Let
$Y_n$
be the set of the two
$E_n$
-equivalence classes. It is not difficult to see that in the permutation model,
$\langle Y_n\colon n\in \omega \rangle $
is a sequence of two-element sets without a choice function.
6.1 Dedekind finite and amorphous sets
In the broad field of definitions of finiteness, the following definitions stand out.
Definition 6.21 A set is Dedekind finite if it does not contain an injective image of
$\omega $
. A set is amorphous if it cannot be partitioned into two infinite sets.
Non-existence of amorphous or infinite, Dedekind finite sets is one of the more common fragments of the axiom of choice [Reference Howard and Rubin1, Form 9]. The purpose of this section is to provide a dynamical criterion related to the previous concepts which implies it.
Definition 6.22 A dynamical ideal
$\Gamma \curvearrowright X, I$
is said to be stratified if there are
$\Gamma $
-invariant ideals
$I_n$
on X for
$n\in \omega $
such that:
-
(1) I is the increasing union of all
$I_n$
’s; -
(2) for every
$n\in \omega $
and all sets
$a, b_m\colon m\in \omega $
in
$I_n$
, there are elements
$\gamma _m\in \mathrm {pstab}(a)$
such that
$\bigcup _m\gamma _m\cdot b_m\in I_{n+1}$
.
Theorem 6.23 Let
$\Gamma \curvearrowright X, I$
be a stratified dynamical ideal. In the associated permutation model, every set is either a countable union of finite sets or it contains an injective image of
$\omega $
.
In particular, the permutation model contains no amorphous sets. A countable union of finite sets can certainly be an infinite, Dedekind finite set. However, such an eventuality can be excluded if, for example, the ideals in the stratification of I are simple. Then, even the union is simple (Example 6.16), therefore, in the permutation model, a countable union of finite sets must be countable by Theorem 6.3.
Proof Let
$\{I_n\colon n\in \omega \}$
be the stratification of I. Let A be a set in the permutation model. Let
$a\in I$
be a set such that
$\mathrm {pstab}(a)\subseteq \mathrm {stab}(A)$
holds, and pick
$n\in \omega $
such that
$a\in I_n$
holds. For every number
$m\in \omega ,$
let
$A_m=\{B\in A\colon \exists b\in I_m\ \mathrm {pstab}(b)\subseteq \mathrm {stab}(B)\}$
. By the invariance of supports (Proposition 2.10), the sequence
$\langle A_m\colon m\in \omega \rangle $
belongs to the permutation model, and A is the increasing union of the sets
$A_m$
. It will be enough to show that if one of the sets
$A_m$
is infinite, then it contains an injective image of
$\omega $
.
Suppose then that
$m\geq n$
is such that
$A_m$
is infinite. Let
$B_k$
for
$k\in \omega $
be some injective k-tuples of elements of
$A_m$
. Note that since
$I_m$
is an ideal, for each
$k\in \omega ,$
there is a set
$b_k\in I_m$
such that
$\mathrm {pstab}(b_k)\subseteq \mathrm {stab}(B_k)$
. Use the stratification assumption to find group elements
$\gamma _k\in \mathrm {pstab}(a)$
such that
$c=\bigcup _{k\in \omega }\gamma _k\cdot b_k\in I_{m+1}$
. Consider the sequence
$C=\langle \gamma _k\cdot B_k\colon k\in \omega \rangle $
. By the invariance of supports (Proposition 2.10),
$\mathrm {pstab}(c)\subseteq \mathrm {stab}(C)$
, so C belongs to the permutation model. Since each
$\gamma _k$
fixes the set A, the sequence C consists of k-tuples of elements of A for each k. Clearly, the set
$\bigcup _k\mathrm {rng}(\gamma _k\cdot B_k)$
is an infinite countable subset of A as required.
Example 6.24 Let X be a countable dense linear ordering without endpoints. Let
$\Gamma $
be its automorphism group acting on X by application. Let
$\alpha>\omega $
be a countable ordinal closed under ordinal addition, and let
$I_\alpha $
be the ideal of subsets of X which are well-ordered of order type less than
$\alpha $
. If
$\alpha $
is closed under ordinal multiplication, then
$\Gamma \curvearrowright X, I_\alpha $
is a stratified dynamical ideal. The ideal is also simple by Example 6.10; in conclusion, in the associated permutation model, every infinite set contains an injective image of
$\omega $
.
Proof Let
$\langle \beta _n\colon n\in \omega \rangle $
be an increasing sequence of ordinals closed under ordinal addition, converging to
$\alpha $
, and such that
$\beta _{n+1}>(\omega \cdot \beta _n)\cdot \beta _n$
. Then,
$I_\alpha $
is the increasing union of
$I_{\beta _n}$
for
$n\in \omega $
. In addition, an inspection of the proof of Example 5.6 shows that Definition 6.22 holds for this stratification of
$I_\alpha $
.
Example 6.25 Let
$\kappa $
be an uncountable cardinal, let X be a set of cardinality at least
$\kappa $
, let
$\Gamma $
be the group of all permutations of X acting by application, and let
$I_\kappa $
be the ideal of subsets of X of cardinality smaller than
$\kappa $
. If
$\kappa $
has countable cofinality, then
$\Gamma \curvearrowright X, I$
is a stratified dynamical ideal. The ideal is simple by Example 6.12; in conclusion, in the associated permutation model, every infinite set contains an injective image of
$\omega $
.
Proof Just let
$\langle \lambda _n\colon n\in \omega \rangle $
be an increasing sequence of cardinals converging to
$\kappa $
. Then,
$I_\kappa $
is an increasing union of ideals
$I_{\lambda _n^+}$
for
$n\in \omega $
. Each of these dynamical ideals is
$\sigma $
-complete, and in fact has cofinal orbits by Example 3.12; thus, Definition 6.22 holds for this stratification of
$I_\kappa $
.
Example 6.26 In the fairly popular situation where I is generated by a countable increasing sequence of invariant sets,
$\Gamma \curvearrowright X, I$
is a stratified dynamical ideal. For example, when
$\mathbb {Z}$
acts on a countable set X and I is the ideal of finite sets, then there are two cases. Either there is an infinite orbit. In such a case, for any
$x\in X$
in the infinite orbit,
$\mathrm {stab}(x)=\{0\}$
and
$W[[X]]=V[[X]]$
; in this trivial case, the full axiom of choice holds in the associated permutation model. Or, all orbits are finite, and then X is an increasing union of countably many finite invariant sets.
