On a theorem of Kurepa for partially ordered sets and weak choice

Abstract

In set theory without the Axiom of Choice (${\mathsf {AC}}$), we investigate the open problem of the relative strength of the proposition “Every partially ordered set such that all of its antichains are finite and all of its chains are countable is countable”, which was established by G. Kurepa [On two problems concerning ordered sets. Glasnik Mat.-Fiz. Astronom. Društvo Mat. Fiz. Hrvatske Ser. II 13, 229–234 (1958)] within ${\mathsf {ZFC}}$ (Zermelo–Fraenkel set theory plus the ${\mathsf {AC}}$). Among various results, positive and independence ones, we show that Kurepa’s result can be proved in an axiomatic system which is weaker than ${\mathsf {ZFC}}$, namely in ${\mathsf {ZF}}$ + ${\mathsf {DC}}_{\aleph _{1}}$ (where ${\mathsf {DC}}_{\aleph _{1}}$ is Dependent Choices for $\aleph _{1}$—a weak choice principle stronger than Dependent Choices (${\mathsf {DC}}$)). We also address similar open problems for certain weak forms of Kurepa’s proposition. Furthermore, the results of the paper answer several questions left open in A. Banerjee [Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC. arXiv:2009.05368v2], as well as an open question from P. Howard and J. E. Rubin [Consequences of the Axiom of Choice. Mathematical Surveys and Monographs 59, Amer. Math. Soc., Providence, RI (1998)].

1 Introduction

In 1958, Kurepa [17] proved the proposition on partially ordered sets stated in the abstract, answering the corresponding question raised by Sierpiński [19, pp. 190–191].¹ Kurepa’s result is (in our opinion) of significant interest from both a combinatorial and an order-theoretical perspective and since its proof was conducted in ${\mathsf {ZFC}}$, this fact readily emerges natural and intriguing questions on its possible interrelation with ${\mathsf {AC}}$ and weak forms of ${\mathsf {AC}}$.

Of course, one would first be concerned with the problem of whether Kurepa’s result can be established without using any form of choice (that is, if ${\mathsf {ZF}}$ proves this proposition) and, if the answer is in the negative, then it would be important to determine whether it implies ${\mathsf {AC}}$ (which is something that one may hardly expect). In case the above proposition is not provable in ${\mathsf {ZF}}$ and is not equivalent to ${\mathsf {AC}}$ (in ${\mathsf {ZF}}$ or in ${\mathsf {ZFA}}$—complete definitions will be given in Sect. 2), then the open problem of its placement in the hierarchy of weak choice principles, which are more than 300 (see Howard and Rubin [9]), comes up.

Besides the investigation on which weak choice principles (or conjunctions of weak choice principles) suffice to prove Kurepa’s result, or which principles are deduced from this result, it is also important to address the open problem of its connection with other order-theoretic and combinatorial statements such as the celebrated Dilworth’s theorem or the Chain–Antichain Principle, to name a few. This would certainly shed more light on the relative strength of Kurepa’s proposition and contribute to new information and results in the area. For recent research on Dilworth’s theorem, the Chain–Antichain Principle, and weak choice principles the reader is referred to Tachtsis [20, 21].

Now, the only source of information (known to us) on Kurepa’s result and choice principles is a quite recent paper by Banerjee [1]. Among other results, the author proves in that paper that the proposition of discourse is not provable in ${\mathsf {ZF}}$ and is not equivalent to ${\mathsf {AC}}$ in ${\mathsf {ZFA}}$.

The above paper by Banerjee has been the chief motivation for us in continuing the research on this intriguing topic. We fill in several gaps in information about the strength of Kurepa’s result and certain weaker and formally weaker forms of it; and thus also answering various questions left open in [1]. For example, among many other results, we establish the following:

• 1. The statement “Every partially ordered set such that all of its antichains are finite and all of its chains are countable has a maximal chain” in conjunction with the Principle of Dependent Choices (${\mathsf {DC}}$) implies Kurepa’s proposition (Theorem 4(7));²

• 2. ${\mathsf {DC}}_{\aleph _{1}}$ implies Kurepa’s proposition, but the implication is not reversible in ${\mathsf {ZFA}}$ (Theorem 9[(1), (5)]);

• 3. The Axiom of Multiple Choice does not imply Kurepa’s proposition in ${\mathsf {ZFA}}$, and hence neither does “Every partially ordered set has a maximal antichain” (Theorem 5(2));

• 4. The statement “Every partially ordered set of finite width such that all of its chains are countable is countable” is weaker than Dilworth’s theorem in ${\mathsf {ZFA}}$ (Theorems 4(8), 9(4));

• 5. Kurepa’s and Dilworth’s theorems are mutually independent in ${\mathsf {ZFA}}$ (Theorems 4(17), 9(4));

• 6. Kurepa’s proposition implies the Chain–Antichain Principle (Theorem 4[(1), (11)]);

• 7. “Every set is either well orderable or has an amorphous subset” + Chain–Antichain Principle implies Kurepa’s proposition, and the implication is not reversible in ${\mathsf {ZFA}}$ (Theorem 8[(1), (3)]);

• 8. The statement “Every partially ordered set such that all of its antichains are finite and all of its chains are countable is Dedekind-infinite” is:

  • (a) equivalent to the Chain–Antichain Principle (Theorem 4(11));

  • (b) weaker than Kurepa’s proposition in ${\mathsf {ZF}}$ (Theorem 4(13));

  • (c) not implied by the axiom of choice for families of non-empty, countable sets in ${\mathsf {ZFA}}$ (Theorem 6). The latter independence result settles (in ${\mathsf {ZFA}}$) the open problem of Howard and Rubin [9] whether or not the above weak choice principle implies the Chain–Antichain Principle.

2 Notation and terminology

Definition 1

• 1. ZF denotes the Zermelo–Fraenkel set theory without AC.

• 2. ZFC denotes the ${\mathsf {ZF}}+{\mathsf {AC}}$ set theory.

• 3. ZFA denotes the ${\mathsf {ZF}}$ set theory with the Axiom of Extensionality weakened to allow the existence of atoms.

• 4. As usual, $\omega$ denotes the set of natural numbers.

• 5. For any set X, $[X]^{<\omega }$ denotes the set of finite subsets of X and, for $n\in \omega$, $[X]^{n}$ denotes the set of n-element subsets of X.

Definition 2

Let X and Y be sets. We write:

• 1. $|X|\le |Y|$, if there is an injection $f:X\rightarrow Y$;

• 2. $|X|=|Y|$, if there is a bijection $f:X\rightarrow Y$;

• 3. $|X|<|Y|$, if $|X|\le |Y|$ and $|X|\ne |Y|$.

Definition 3

Let $(P,\le )$ be a partially ordered set. (We will henceforth write ‘poset’ instead of ‘partially ordered set’.)

A set $C\subseteq P$ is called a chain in P, if $(C,\le \upharpoonright C)$ is linearly ordered.

A set $A\subseteq P$ is called an antichain in P, if no two distinct elements of A are comparable under $\le$.

The supremum of the cardinalities of antichains in P is called the width of P.

An antichain A in P which is $\subseteq$-maximal among the antichains in P is called a maximal antichain in P.

A chain C in P which is $\subseteq$-maximal among the chains in P is called a maximal chain in P.

A set $D\subseteq P$ is called cofinal in P if for every $x\in P$ there is $d\in D$ such that $x\le d$.

An element p of P is called minimal if for all $q\in P$, $(q\le p)\rightarrow (q=p)$.

An element p of P is called maximal if for all $q\in P$, $(p\le q)\rightarrow (q=p)$.

A set $W\subseteq P$ is called well-founded if every non-empty subset V of W has a $\le$-minimal element.

Definition 4

Let X be a set.

X is called denumerable if $|X|=\aleph _{0}$ (where $\aleph _{0}$ is the first infinite, well-ordered cardinal, i.e. $\aleph _{0}=\omega$).

X is called countable if it is finite or denumerable.

X is called uncountable if $|X|\not \le \aleph _{0}$.

X is called Dedekind-finite if $\aleph _{0}\not \le |X|$. Otherwise, X is called Dedekind-infinite.

If X is infinite, then X is called amorphous if it cannot be written as a disjoint union of two infinite subsets.

Definition 5

• 1. The Axiom of Choice, ${\mathsf {AC}}$ (Form 1 in [9]): Every family of non-empty sets has a choice function.

• 2. ${\mathsf {AC}}_{\le \aleph _{0}}$ (Form [85 A] in [9]): Every family of non-empty, countable sets has a choice function.

• 3. ${\mathsf {AC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$: Every denumerable family $\mathcal {A}=\{A_{i}:i\in \omega \}$ of non-empty, countable sets for which there is a function f such that, for every $i\in \omega$, f(i) is a linear order on $A_{i}$, has a choice function.

• 4. van Douwen’s choice principle, $\mathsf {vDCP}^{\aleph _{0}}$ (Form 119 in [9]): Every denumerable family $\mathcal {A}=\{A_{i}:i\in \omega \}$ for which there is a function f such that, for every $i\in \omega$, f(i) is a linear order on $A_{i}$ of type $\omega ^{*}+\omega$ (the usual ordering of the integers), has a choice function.

• 5. ${\mathsf {AC}}_{\mathsf {fin}}$ (Form 62 in [9]): Every family of non-empty, finite sets has a choice function.

• 6. ${\mathsf {AC}}_{\mathsf {WO}}$ (Form 60 in [9]): Every family of non-empty, well-orderable sets has a choice function.

• 7. ${\mathsf {AC}}^{\mathsf {LO}}$ (Form 202 in [9]): Every linearly ordered family of non-empty sets has a choice function.

• 8. ${\mathsf {AC}}^{\mathsf {WO}}$ (Form 40 in [9]): Every well-ordered family of non-empty sets has a choice function.

• 9. ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$ (Form 10 in [9]): Every denumerable family of non-empty, finite sets has a choice function.

• 10. ${\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}$ (where $\aleph _{1}$ is the first uncountable, well-ordered cardinal): Every $\aleph _{1}$-sized family $\mathcal {A}$ of non-empty finite sets has an $\aleph _{1}$-sized subfamily $\mathcal {B}$ with a choice function.³

• 11. Let $n\in \omega \setminus \{0,1\}$.

  ${\mathsf {AC}}_{n}^{\mathsf {LO}}$ (Form 33(n) in [9]): Every linearly ordered family of n-element sets has a choice function.

  ${\mathsf {AC}}_{n}^{\aleph _{0}}$ (Form 288(n) in [9]): Every denumerable family of n-element sets has a choice function.

  $\mathsf {PAC}_{n}^{\aleph _{0}}$ (Form 373(n) in [9]): For every denumerable family $\mathcal {A}$ of n-element sets there exists an infinite subfamily $\mathcal {B}$ of $\mathcal {A}$ with a choice function. (A choice function for $\mathcal {B}$ is called a partial choice function for $\mathcal {A}$.).

• 12. The Axiom of Multiple Choice, ${\mathsf {MC}}$ (Form 67 in [9]): For every family $\mathcal {A}$ of non-empty sets there is a function f with domain $\mathcal {A}$ such that, for every $x\in \mathcal {A}$, f(x) is a non-empty finite subset of x. (f is called a multiple choice function for $\mathcal {A}$.)

• 13. ${\mathsf {MC}}_{{\aleph _{0}}}^{{\aleph _{0}}}$ (Form 350 in [9]): Every denumerable family of denumerable sets has a multiple choice function.

• 14. ${\mathsf {LW}}$ (Form 90 in [9]): Every linearly ordered set can be well ordered.

• 15. The Boolean Prime Ideal Theorem, ${\mathsf {BPI}}$ (Form 14 in [9]): Every Boolean algebra has a prime ideal.

• 16. The Countable Union Theorem, $\mathsf {CUT}$ (Form 31 in [9]): The union of a countable family of countable sets is countable.

• 17. $\mathsf {WUT}$ (Form 231 in [9]): The union of a well orderable family of well orderable sets is well orderable.

• 18. The Principle of Dependent Choices, ${\mathsf {DC}}$ (Form 43 in [9]): Let X be a non-empty set and let $\mathrel {R}$ be a binary relation on X such that $(\forall x\in X)(\exists y\in X)(x\mathrel {R}y)$. Then there exists a sequence $(x_{n})_{n\in \omega }$ of elements of X such that $x_{n}\mathrel {R}x_{n+1}$ for all $n\in \omega$.

• 19. Let $\kappa$ be an infinite well-ordered cardinal number. The Principle of Dependent Choices for $\kappa$, ${\mathsf {DC}}_{\kappa }$ (Form 87($\kappa$) in [9]): Let S be a non-empty set and let $\mathrel R$ be a binary relation such that for every $\alpha <\kappa$ and every $\alpha$-sequence $s=(s_\xi )_{\xi <\alpha }$ of elements of S there exists $y\in S$ such that $s\mathrel R y$. Then there is a function $f:\kappa \rightarrow S$ such that for every $\alpha <\kappa$, $(f\upharpoonright \alpha )\mathrel R f(\alpha )$.

  (Note that ${\mathsf {DC}}_{\aleph _{0}}$ is a reformulation of ${\mathsf {DC}}$.)

• 20. $\mathsf {W}_{\aleph _{1}}$ (Form 71(1) in [9]): $\forall x(|x|\le \aleph _{1}\vee \aleph _{1}\le |x|)$.

• 21. $\mathsf {WOAM}$ (Form 133 in [9]): Every set is either well orderable or has an amorphous subset.

• 22. $\mathsf {DF=F}$ (Form 9 in [9]): Every Dedekind-finite set is finite.

• 23. $\mathsf {LDF=F}$ (Form 185 in [9]): Every linearly ordered, Dedekind-finite set is finite.

• 24. Ramsey’s Theorem, $\mathsf {RT}$ (Form 17 in [9]): If A is an infinite set and $[A]^{2}$ is partitioned into two sets X and Y, then there is an infinite subset $B\subseteq A$ such that either $[B]^{2}\subseteq X$ or $[B]^{2}\subseteq Y$.

• 25. The Chain–Antichain Principle, $\mathsf {CAC}$ (Form 217 in [9]): Every infinite poset has either an infinite chain or an infinite antichain.

• 26. $\mathsf {CWF}$: Every poset has a cofinal well-founded subset.

• 27. $\mathsf {CS}$: Every poset without a maximal element has two disjoint cofinal subsets.

• 28. Dilworth’s Theorem, $\mathsf {DT}$: If $(P,\le )$ is a poset of width k for some $k\in \omega$, then P can be partitioned into k chains.

Definition 6

• K1: Every poset such that all of its antichains are finite and all of its chains are countable is countable. (Kurepa’s Theorem.)

• K1*: Every poset of finite width such that all of its chains are countable is countable.

• K2: Every poset such that all of its antichains are finite and all of its chains are countable is well-orderable.

• K2*: Every poset of finite width such that all of its chains are countable is well-orderable.

• K3: Every infinite poset such that all of its antichains are finite and all of its chains are countable is Dedekind-infinite.

• K3*: Every infinite poset of finite width such that all of its chains are countable is Dedekind-infinite.

• K4: Every poset such that all of its antichains are finite and all of its chains are countable has a maximal chain.

• K4*: Every poset of finite width such that all of its chains are countable has a maximal chain.

The statements $\hbox {K}i$ ($i=2,3,4$) and $\hbox {K}i^{*}$ ($i=1,\ldots ,4$) of Definition 6 are introduced in this paper.

2.1 Terminology for Fraenkel–Mostowski models

For the reader’s convenience, we provide a brief account of the construction of Fraenkel–Mostowski models of ${\mathsf {ZFA}}$; a detailed account can be found in Jech [13, Chapter 4].

One starts with a model M of ${\mathsf {ZFA}}+{\mathsf {AC}}$ which has A as its set of atoms. Let G be a group of permutations of A and also let $\mathcal {F}$ be a filter on the lattice of subgroups of G which satisfies the following:

$$\begin{aligned} (\forall a\in A)(\exists H\in \mathcal {F})(\forall \phi \in H)(\phi (a)=a) \end{aligned}$$

and

$$\begin{aligned} (\forall \phi \in G)(\forall H\in \mathcal {F})(\phi H\phi ^{-1}\in \mathcal {F}). \end{aligned}$$

Such a filter $\mathcal {F}$ of subgroups of G is called a normal filter on G. Every permutation of A extends uniquely to an $\in$-automorphism of M by $\in$-induction, and for any $\phi \in G$, we identify $\phi$ with its (unique) extension. If $x\in M$ and H is a subgroup of G, then ${{\,\mathrm{\mathrm{fix}}\,}}_{H}(x)$ denotes the (pointwise stabilizer) subgroup $\{\phi \in H:\forall y\in x(\phi (y)=y)\}$ of H and ${{\,\mathrm{\mathrm{Sym}}\,}}_{H}(x)$ denotes the (stabilizer) subgroup $\{\phi \in H:\phi (x)=x\}$ of H.

An element x of M is called $\mathcal {F}$-symmetric if ${{\,\mathrm{\mathrm{Sym}}\,}}_{G}(x)\in \mathcal {F}$ and it is called hereditarily $\mathcal {F}$-symmetric if x and all elements of its transitive closure are $\mathcal {F}$-symmetric.

Let $\mathcal {N}$ be the class which consists of all hereditarily $\mathcal {F}$-symmetric elements of M. Then $\mathcal {N}$ is a model of ${\mathsf {ZFA}}$ and $A\in \mathcal {N}$ (see Jech [13, Theorem 4.1, p. 46]); it is called the Fraenkel–Mostowski model, or the permutation model, determined by M, G and $\mathcal {F}$.

Many permutation models of ${\mathsf {ZFA}}$ are constructed via certain ideals of subsets of the set A of atoms. Let M, A and G be as above. A family $\mathcal {I}$ of subsets of A is called a normal ideal if it satisfies the following conditions:

• (i) $\emptyset \in \mathcal {I}$;

• (ii) if $E\in \mathcal {I}$ and $F\subseteq E$, then $F\in \mathcal {I}$;

• (iii) if $E,F\in \mathcal {I}$ then $E\cup F\in \mathcal {I}$;

• (iv) if $\pi \in G$ and $E\in \mathcal {I}$, then $\pi [E]\in \mathcal {I}$;

• (v) for each $a\in A$, $\{a\}\in \mathcal {I}$.

If $\mathcal {I}\subseteq \mathcal {P}(A)$ is a normal ideal, then $\{{{\,\mathrm{\mathrm{fix}}\,}}_{G}(E):E\in \mathcal {I}\}$ is a filter base for some normal filter $\mathcal {F}$ on G. Let $\mathcal {N}$ be the permutation model which is determined by M, G and $\mathcal {F}$. By the above discussion, for every $x\in \mathcal {N}$ there exists $E\in \mathcal {I}$ such that ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)\subseteq {{\,\mathrm{\mathrm{Sym}}\,}}_{G}(x)$. Under these circumstances, we call E a support of x.

3 Known and preliminary results

We start by listing some known facts about certain choice principles given in Definition 5.

Fast 1

• 1. In ${\mathsf {ZFA}}$, ${\mathsf {AC}}$ is equivalent to “Every chain in a poset is contained in a maximal chain” (the so-called Maximal Chain Theorem). This renowned result was firstly proved by Hausdorff [5] in 1914 using transfinite induction. In 1951, Frink [2] gave a very elegant proof of the Maximal Chain Theorem which does not involve the notion of a well-ordering. Let us observe here that ${\mathsf {AC}}$ is (in ${\mathsf {ZFA}}$) also equivalent to “Every poset has a maximal chain”. (($\leftarrow$) Let $\mathcal {A}$ be a family of non-empty sets. Let $\mathbb {P}=\{f:\exists \mathcal {B}\subseteq \mathcal {A}(f$ is a choice function for $\mathcal {B})\}$. Define a partial order $\le$ on $\mathbb {P}$ by $f\le g\leftrightarrow f\subseteq g$ for all $f,g\in \mathbb {P}$. If $\mathcal {C}$ is a maximal chain in $\mathbb {P}$, then $\bigcup \mathcal {C}$ is a choice function for $\mathcal {A}$.)

• 2. ${\mathsf {AC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}} \leftrightarrow {\mathsf {PAC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$, where the latter principle is the partial version of the former one. (($\leftarrow$) Let $\mathcal {A}=\{A_{i}:i\in \omega \}$ be a denumerable family of non-empty, countable sets, and also let, for $i\in \omega$, $\le _i$ be a linear order on $A_{i}$. For every $i\in \omega$, let $B_i=\prod _{j\le i}A_{j}$. Since every member of $\mathcal {A}$ is countable, so is $B_{i}$ for all $i\in \omega$. Using the linear orders $\le _{i}$ ($i\in \omega$), we may linearly order $B_{i}$, e.g. by the lexicographic order. If $\mathcal {B}=\{B_{i}:i\in \omega \}$ has a partial choice function, then via an easy induction we may define a choice function for $\mathcal {A}$.)

• 3. ${\mathsf {AC}}_{{\mathsf {fin}}}^{\aleph _{0}}\leftrightarrow {\mathsf {PAC}}_{{\mathsf {fin}}}^{\aleph _{0}}$ (see [9, Form 10]).)

• 4. $\forall n\in \omega \setminus \{0,1\}({\mathsf {AC}}_{n}^{\mathsf {LO}})$ is equivalent to “$\forall n\in \omega \setminus \{0,1\}$(the union of a linearly orderable family of n-element sets is linearly orderable), see [21].

• 5. $\forall n\in \omega \setminus \{0,1\}(\mathsf {PAC}_{n}^{\aleph _{0}})\nrightarrow \forall n\in \omega \setminus \{0,1\}({\mathsf {AC}}_{n}^{\aleph _{0}})$ in ${\mathsf {ZF}}$, see [3].

• 6. Each of ${\mathsf {LW}}$, ${\mathsf {AC}}^{\mathsf {LO}}$, ${\mathsf {MC}}$ is equivalent to ${\mathsf {AC}}$ in ${\mathsf {ZF}}$, but none of them are equivalent to ${\mathsf {AC}}$ in ${\mathsf {ZFA}}$, see [8] (for ${\mathsf {AC}}^{\mathsf {LO}}$), [13, Theorems 9.1, 9.2]. Furthermore, ${\mathsf {AC}}^{\mathsf {LO}}\leftrightarrow {\mathsf {LW}}\wedge {\mathsf {AC}}^{{\mathsf {WO}}}$, see [8].

• 7. $\mathsf {WOAM}\rightarrow \mathsf {CUT}$, see [15].

• 8. $\mathsf {CAC}$ for infinite, well orderable posets is provable in ${\mathsf {ZF}}$, see (for example) [20, Proof of Claim 5].

• 9. $\mathsf {DF}=\mathsf {F}\rightarrow \mathsf {RT}\rightarrow {\mathsf {PAC}}_{\mathsf {fin}}$ and $\mathsf {RT}\rightarrow {\mathsf {CAC}}\rightarrow {\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$, see [16, 20].

• 10. $\mathsf {CAC}$ is weaker than $\mathsf {RT}$ in ${\mathsf {ZF}}$, see [20].

• 11. In ${\mathsf {ZFA}}$, ${\mathsf {MC}}\rightarrow \mathsf {CWF}\rightarrow {\mathsf {LW}}$. The first implication has been established in [11], while the second one in [22]. Moreover, in [11], it has been established that (in ${\mathsf {ZFA}}$) $\mathsf {CWF}$ is equivalent to “Every poset has a maximal antichain”. A proof that the latter principle lies in strength between ${\mathsf {MC}}$ and ${\mathsf {LW}}$ can be found in [13, Theorem 9.1].

• 12. In ${\mathsf {ZFA}}$, ${\mathsf {MC}}\rightarrow \mathsf {CS}$, but the implication is not reversible, see [10].

• 13.

  • (a) ([21]) $\mathsf {DT}$ for well orderable posets with finite width is provable in ${\mathsf {ZF}}$.

  • (b) ([21]) ${\mathsf {BPI}}\rightarrow \mathsf {DT}\rightarrow \forall n\in \omega \setminus \{0,1\}({\mathsf {AC}}_{n}^{\mathsf {LO}})$. The first implication is not reversible in ${\mathsf {ZFA}}$.

  • (c) ([21]) ${\mathsf {AC}}^{\mathsf {WO}}\nrightarrow {\mathsf {DT}}$ in ${\mathsf {ZFA}}$.

  • (d) ([21]) $\mathsf {RT}$ and $\mathsf {DT}$, and $\mathsf {CAC}$ and $\mathsf {DT}$ are mutually independent in ${\mathsf {ZF}}$.

• 14. ${\mathsf {BPI}}\rightarrow {\mathsf {AC}}_{\mathsf {fin}}$, but the implication is not reversible in ${\mathsf {ZF}}$, see [9].

• 15. In every Fraenkel–Mostowski model, ${\mathsf {AC}}_{\mathsf {fin}}\leftrightarrow {\mathsf {AC}}_{\mathsf {WO}}$, see [7].

• 16. For every infinite, well-ordered cardinal $\kappa$, ${\mathsf {DC}}_{\kappa }\rightarrow \mathsf {W}_{\kappa }$, see [13, Theorem 8.1(b)]. Furthermore, for infinite, well-ordered cardinals $\lambda <\kappa$, ${\mathsf {DC}}_{\kappa }\rightarrow {\mathsf {DC}}_{\lambda }$, see [13, Theorem 8.1(a)]. In particular, ${\mathsf {DC}}_{\aleph _{1}}\rightarrow {\mathsf {DC}}\rightarrow \mathsf {CUT}$.

Theorem 1

([12]) Let $\mathcal {N}$ be a Fraenkel–Mostowski model which is determined by a group G of permutations of the set A of atoms, and a normal filter $\mathscr {F}$ of subgroups of G which is generated by some filter base $\mathscr {B}$ (of subgroups of G). If $\mathcal {N}$ satisfies the following condition:

• (*) for every $x\in \mathcal {N}$ and for every $B\in \mathscr {B}$ which does not support x (i.e. $B\setminus {{\,\mathrm{\mathrm{Sym}}\,}}_{G}(x)\ne \emptyset$), there exists $\gamma \in B\setminus {{\,\mathrm{\mathrm{Sym}}\,}}_{G}(x)$ of finite order,

then ${\mathsf {LW}}$ is true in $\mathcal {N}$. In particular, if every element of G has finite order, or if G is a subgroup of ${{\,\mathrm{\mathrm{FSym}}\,}}(A)$ (the group of all finitary permutations of A), then $\mathcal {N}\models {\mathsf {LW}}$.

Theorem 2

([12]) Assume that the set A of atoms of the ground model M of ${\mathsf {ZFA}}+{\mathsf {AC}}$ is a union of a disjoint, denumerable family $\{A_{n}:n\in \omega \}$, where each $A_{n}$ is denumerable. For each $n\in \omega$, let $\mathscr {G}_{n}$ be a group of permutations of $A_{n}$, and also let G be the weak direct product of the $\mathscr {G}_{n}$’s, i.e. $(g_{n})_{n\in \omega }\in G$ if and only if for every $n\in \omega$, $g_{n}\in \mathscr {G}_{n}$, and $g_n=\mathrm {id}_{A_{n}}$ (the identity mapping on $A_{n}$) for all but finitely many $n\in \omega$. Let I be the ideal which is generated by all unions $\bigcup \{A_{n}:n\in E\}$, $E\in [\omega ]^{<\omega }$. Let $\mathcal {M}$ be the Fraenkel–Mostowski model determined by M, G and I.

Let $\mathscr {G}$ be the unrestricted direct product of $\mathscr {G}_{n}$ ($n\in \omega$), and also let $\mathcal {N}$ be the Fraenkel–Mostowski model determined by M, $\mathscr {G}$ and I. Then $\mathcal {N}=\mathcal {M}$.

Theorem 3

Let $\mathcal {N}$ be a Fraenkel–Mostowski model which is determined by a group G of permutations of the set A of atoms, and a normal filter $\mathscr {F}$ of subgroups of G. If every element of G has finite order, or if G is a subgroup of ${{\,\mathrm{\mathrm{FSym}}\,}}(A)$, and if $\mathcal {N}\models {\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}$, or if $\mathcal {N}\models \mathsf {WUT}$ (and thus $\mathcal {N}\models \mathsf {CUT}$), then every poset $(P,\le )\in \mathcal {N}$ such that all antichains in P are finite, is well orderable in $\mathcal {N}$.⁴

Proof

Assume the hypotheses on $\mathcal {N}$. Let $(P,\le )$ be a poset in $\mathcal N$ such that all of its antichains are finite, and also let $H={{\,\mathrm{\mathrm{Sym}}\,}}_{G}((P,\le ))$. As $(P,\le )\in \mathcal {N}$, we have $H\in \mathscr {F}$.

We assert that, for every $p\in P$, the H-orbit, ${{\,\mathrm{\mathrm{Orb}}\,}}_H(p)$, of p (i.e. the set ${{\,\mathrm{\mathrm{Orb}}\,}}_H(p)=\{\phi (p):\phi \in H\}$) is an antichain in P. Indeed, fix $p\in P$ and assume, by way of contradiction, that ${{\,\mathrm{\mathrm{Orb}}\,}}_H(p)$ is not an antichain. Hence, for some $\pi ,\rho \in H$, $\pi (p)$ and $\rho (p)$ are comparable, say $\pi (p)<\rho (p)$. Letting $\sigma =\rho ^{-1}\pi$, we have $\sigma (p)<p$ and (by our hypotheses on G) $\sigma ^{k}=\mathrm {id}_A$ for some $k\in \omega$. However,

$$\begin{aligned} p=\sigma ^{k}(p)<\sigma ^{k-1}(p)<\cdots<\sigma ^{2}(p)<\sigma (p)<p, \end{aligned}$$

and thus $p<p$, which is a contradiction. Similarly, one obtains a contradiction if $\rho (p)<\pi (p)$. Hence, ${{\,\mathrm{\mathrm{Orb}}\,}}_H(p)$ is an antichain in P.

Now, the collection ${\mathcal {O}}=\{{{\,\mathrm{\mathrm{Orb}}\,}}_H(p):p\in P\}$ is a partition of P, which is well orderable in $\mathcal N$ since $H\subseteq {{\,\mathrm{\mathrm{Sym}}\,}}_{G}({{\,\mathrm{\mathrm{Orb}}\,}}_H(p))$ for all $p\in P$, and thus ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(\mathcal {O})\in \mathscr {F}$.⁵ Furthermore, by the observation of the previous paragraph and our hypotheses on P, every set in $\mathcal {O}$ is finite. Thus, by ${\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}$ or $\mathsf {WUT}$ in $\mathcal {N}$, we conclude that P is well orderable in $\mathcal {N}$. This completes the proof of the theorem. $\square$

4 Main results

We start with a result on relationships between the order-theoretic principles of Definition 6.

Theorem 4

The following hold:

• 1. K1 $\rightarrow$ P for all $P\in \{K i:1\le i\le 4\}\cup \{K i^{*}:1\le i\le 4\}$.

• 2. K2 $\rightarrow$ P for all $P\in \{K i:2\le i\le 4\}\cup \{K i^{*}:2\le i\le 4\}$.

• 3. Ki $\rightarrow$ $\hbox {Ki}^{*}$ for all $i=1,\ldots ,4$.

• 4. K1* $\rightarrow$ K2* $\rightarrow$ K3* $+$ K4*.

• 5. K2 $+$ $\mathsf {CUT}\rightarrow$ K1.⁶

• 6. K2 $+$ “$\aleph _{1}$ is regular” $\rightarrow$ K1. Hence, in every Fraenkel–Mostowski model, $K2\leftrightarrow K1$ (see also [1, Corollary 4.2]).⁷

• 7. K4 $+$ ${\mathsf {DC}}$ $\rightarrow$ K1.

• 8. $\mathsf {DT}$ $\rightarrow$ K1*. Hence, by Fact 1(13)(b), ${\mathsf {BPI}}$ $\rightarrow$ K1*.

• 9. K1* $\leftrightarrow$ K2*.

• 10. K4* $+$ $\mathsf {CUT}\rightarrow$ K1*.

• 11. K3 $\leftrightarrow$ $\mathsf {CAC}$. Hence, by (1), $K1 \rightarrow K2 \rightarrow \mathsf {CAC}$ and, by Fact 1(9), ${\mathsf {DF}}={\mathsf {F}}\rightarrow K3\rightarrow {\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$.

• 12. K1 $\rightarrow$ K2 $\rightarrow$ ${\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}+{\mathsf {AC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$. Hence, K1 $\rightarrow$ K2 $\rightarrow$ $\mathsf {vDCP}^{\aleph _{0}}$. Also, K4 $\rightarrow {\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}$.

• 13. ([1, Corollary 4.6]) ${\mathsf {DC}}\nrightarrow {\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}$ in ${\mathsf {ZF}}$. Hence, by (1) and (12), ${\mathsf {DC}}\nrightarrow$ $\hbox {K}i$ ($i=1,2,4$) in ${\mathsf {ZF}}$. Furthermore, by (11), ${\mathsf {DC}}\rightarrow$ K3 and K3 $\nrightarrow$ K2 in ${\mathsf {ZF}}$.

• 14. K4 $\rightarrow$ ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$.

• 15. For all $i\in \{1,\ldots ,4\}$, $\hbox {K}i^{*}$ $\rightarrow$ $\forall n\in \omega \setminus \{0,1\}(\mathsf {PAC}_{n}^{\aleph _{0}})$.

• 16. K3 $\nrightarrow$ K4* in ${\mathsf {ZFA}}$ (and thus $\mathsf {CAC}$ $\nrightarrow$ K4* in ${\mathsf {ZFA}}$). Hence, K3 (and thus $\mathsf {CAC}$) implies none of Ki and Ki* ($i=1,2,4$) in ${\mathsf {ZFA}}$.

• 17. $\mathsf {DT}$ $\nrightarrow$ Ki ($i=1,\ldots ,4$) in ${\mathsf {ZFA}}$. Hence, by (4) and (8), Ki$^{*}$ $\nrightarrow$ Kj for all $i,j=1,\ldots ,4$ in ${\mathsf {ZFA}}$.

Proof

(1)–(4) These are straightforward.

(5) Assume K2 $+$ $\mathsf {CUT}$. Let $(P,\le )$ be a poset satisfying the hypotheses of K1. By K2, let $\preceq$ be a well-ordering on P. By way of contradiction, assume that P is uncountable. We will construct an infinite antichain in P (and thus contradicting P’s having only finite antichains). Since P is well-ordered by $\preceq$, we may effectively (i.e. without using any choice form) construct via transfinite induction a maximal chain in P, $V_0$ say. As $V_0$ is countable, $P\setminus V_{0}$ is uncountable and (since $V_0$ is a maximal chain) every element of $P\setminus V_{0}$ is $\le$-incomparable to some element of $V_0$. Thus, $P\setminus V_{0} = \bigcup \{W_{p} : p\in V_{0}\}$, where $W_{p}=\{q\in P\setminus V_{0}:q$ is incomparable to $p\}$. Since $P\setminus V_{0}$ is uncountable and $\mathsf {CUT}$ is true, $W_{p}$ is uncountable for some $p\in V_{0}$. Let $p_0={\preceq }-\min \{p\in V_{0}:W_{p}$ is uncountable$\}$.

Using $\preceq$ again, construct a maximal chain in $W_{p_{0}}$, $V_1$ say, and let (similarly to the above argument) $p_1={\preceq }-\min \{p\in V_1:W_{p}$ is uncountable$\}$, where $W_{p}=\{q\in W_{p_{0}}\setminus V_{1}:q$ is incomparable to $p\}$.

Continuing in this fashion by mathematical induction (and noting that the process cannot stop at a finite stage), we obtain a denumerable antichain $\{p_{n}: n\in \omega \}$ in P, which is a contradiction. Hence, P is countable, as required.

(6) This can be proved similarly to (5).

(7) Assume that K4 $+$ ${\mathsf {DC}}$ is true. Let $(P,\le )$ be a poset such that all of its antichains are finite and all of its chains are countable. By way of contradiction, we assume that P is uncountable. Let U be the set of all finite sequences,

$$\begin{aligned} (C_{0},p_{0},U_{p_{0}},C_{1},p_{1},U_{p_{1}},\ldots ,C_{n},p_{n},U_{p_{n}}) \end{aligned}$$

such that:

(i) $C_{0}$ is a maximal chain in P, $p_{0}\in C_{0}$, and $U_{p_0}=\{p\in P\setminus C_{0}:p$ is incomparable with $p_{0}\}$ is uncountable;

(ii) for $i\in \{1,2,\ldots ,n\}$, $C_{i}$ is a maximal chain in $U_{p_{i-1}}$, $p_{i}\in C_{i}$, and $U_{p_i}=\{p\in U_{p_{i-1}}\setminus C_{i}:p$ is incomparable with $p_{i}\}$ is uncountable.

Since P is uncountable and ${\mathsf {DC}}$ (and hence $\mathsf {CUT}$) holds, we may follow the first part of the proof of (5) in order to show that there exists a triple $(C_0,p_0,U_{p_0})$ which satisfies (i). Hence, $U\ne \emptyset$.

We define a binary relation R on U by: for every $\mathbf {u},\mathbf {v}\in U$,

$$\begin{aligned} \mathbf {u}\mathrel {R}\mathbf {v}\Leftrightarrow \mathbf {u}\subsetneq \mathbf {v}. \end{aligned}$$

Again, as in the proof of (5), we may show that for every $\mathbf {u}\in U$ there exists $\mathbf {v}\in U$ such that $\mathbf {u}\mathrel {R}\mathbf {v}$. By ${\mathsf {DC}}$, applied to (U, R), we obtain a sequence $(C_i,p_i,U_{p_i})_{i\in \omega }$ such that $(C_0,p_0,U_{p_{0}})$ satisfies (i) and, for $i\in \omega \setminus \{0\}$, $(C_{i},p_{i},U_{p_{i}})$ satisfies (ii). But then, $\{p_{i}:i\in \omega \}$ is a denumerable antichain in P, contradicting P’s having only finite antichains. Hence, P is countable, as required.

(8) Assume $\mathsf {DT}$. Let $(P,\le )$ be a poset satisfying the hypotheses of K1*. Let $k\in \omega$ be the width of P. By $\mathsf {DT}$, P can be partitioned into k many chains. Since all chains in P are countable, P is countable as a union of finitely many countable sets. Thus, K1* is true.

(9) Assume K2*. Let $(P,\le )$ be a poset satisfying the hypotheses of K1*. By K2*, P is well-orderable and, by Fact 1(13)(a), $\mathsf {DT}$ is true for P. Hence, by the proof of (8), P is countable. Therefore, K1* is true.

(10) Working similarly to (5), one shows that, under K4* $+$ $\mathsf {CUT}$, every uncountable poset, in which all chains are countable, has arbitrarily large, finite antichains. Hence, K1* is true.

(11) Assume K3. Let $(P,\le )$ be an infinite poset. If all chains and all antichains in P are finite, then by K3, P has a denumerable subset, Q say. By Fact 1(8), $(Q,{\le \upharpoonright } Q)$ has either an infinite chain or an infinite antichain, contradicting our hypothesis on P.

Assume $\mathsf {CAC}$. Let $(P,\le )$ be a poset satisfying the hypotheses of K3. If P is finite, then there is nothing to show. So, assume P is infinite. Since all antichains in P are finite, $\mathsf {CAC}$ yields that P has an infinite chain, Q say. As all chains in P are countable, Q is denumerable, and hence P is Dedekind-infinite. Thus, K3 is true.

(12) “$\hbox {K}i$ $\rightarrow$ ${\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}$ ($i=1,2,4$)” can be proved similarly to [1, Theorem 4.5: K1 $\rightarrow$ ${\mathsf {WAC}}_{\mathsf {fin}}^{\aleph _{1}}$], and thus we refer the reader to [1] for the details.

K2 $\rightarrow$ ${\mathsf {AC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$: Assume K2. By Fact 1(2), it suffices to show that ${\mathsf {PAC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$ is true. Let $\mathcal {A}=\{A_{i}:i\in \omega \}$ be a denumerable family of non-empty, countable sets and, for each $i\in \omega$, let $\le _{i}$ be a linear order on $A_{i}$. By way of contradiction, assume that $\mathcal {A}$ has no partial choice function.

Let $A=\bigcup \mathcal {A}$ and also let $\preceq$ be a binary relation on A defined by: for $x,y\in A$,

$$\begin{aligned} x\preceq y\Leftrightarrow \exists i\in \omega (x,y\in A_i\wedge x\le _{i} y). \end{aligned}$$

It is easy to see that $\preceq$ is a partial order on A such that all antichains in A are finite (since any two elements of A are $\preceq$-incomparable if and only if they belong to distinct $A_{i}$’s and $\mathcal {A}$ has no partial choice function) and all chains in A are countable (since if $C\subset A$ is a chain in A, then $C\subseteq A_{i}$ for some $i\in \omega$ and $A_{i}$ is countable).

By K2, A is well orderable, contradicting $\mathcal {A}$’s having no partial choice function. Thus, ${\mathsf {AC}}_{{\mathsf {DLO}},\le \aleph _{0}}^{\aleph _{0}}$ is true, as required.

(14) Assume K4. By Fact 1(3), it suffices to show that every denumerable family of non-empty, finite sets has a partial choice function. By way of contradiction, assume that there exists a denumerable family $\mathcal {A}=\{A_{i}:i\in \omega \}$ of non-empty, finite sets without a partial choice function. Let $A=\bigcup \mathcal {A}$. Define a binary relation $\prec$ on A by: for $x,y\in A$,

$$\begin{aligned} x\prec y\Leftrightarrow \exists i,j\in \omega (i<j\wedge x\in A_i\wedge y\in A_j). \end{aligned}$$

Then, $\preceq =\prec \cup \{(x,x):x\in A\}$ is easily seen to be a partial order on A such that all chains and all antichains are finite. Indeed, a subset D of A is an antichain if and only if $D\subseteq A_i$ for some $i\in \omega$, and hence every antichain is finite. On the other hand, since $\mathcal {A}$ has no partial choice function, the definition of $\preceq$ yields that the chains in $(A,\preceq )$ are exactly the finite choice functions of $\mathcal {A}$. Thus, by K4, $(A,\preceq )$ has a maximal chain, which is impossible. Hence, ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$ is true, as required.

(15) This can be proved similarly to (14), and thus we leave it to the interested reader.

(16) For our independence result, we will use a Fraenkel–Mostowski model constructed by Tachtsis [21]. Let us recall the description of the model. Fix $n\in \omega \setminus \{0,1\}$. We start with a model M of ${\mathsf {ZFA}}$ $+$ ${\mathsf {AC}}$ with a set of atoms, $A=\bigcup \{A_{q}:q\in \mathbb {Q}\}$ (where $\mathbb {Q}$ is the set of rational numbers), which is a disjoint union of the n-element sets $A_{q}=\{a_{q1},a_{q2},\ldots ,a_{qn}\}$ ($q\in \mathbb {Q}$). Let G be the group of all permutations $\pi$ of A with the following two properties:

• 1. for all $q\in \mathbb {Q}$ there exists $r\in \mathbb {Q}$ such that $\pi (A_{q})=A_{r}$;

• 2. for all $q,q'\in \mathbb {Q}$, $q<q'$, if and only if, $A_{r}=\pi (A_{q})$, $A_{r'}=\pi (A_{q'})$ and $r<r'$ (where < is the usual dense linear order on $\mathbb {Q}$).

Hence, the elements of G permute the copies $A_{q}$ ($q\in \mathbb {Q}$) of the natural number n preserving the linear ordering $\le$ on $\mathbb {Q}$, and then permute each $A_{q}$ independently. Let $\mathcal {F}$ be the (normal) filter of subgroups of G which is generated by the pointwise stabilizers ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, where $E=\bigcup \{A_{q}:q\in S\}$ for some bounded set $S\subset \mathbb {Q}$. (Note that the set of all those $E\subset A$ is a normal ideal.) Let $\mathcal {V}$ be the Fraenkel–Mostowski model determined by M, G and $\mathcal {F}$.

In [21], it was shown that ${\mathsf {AC}}^{\mathsf {WO}}$ is true in $\mathcal {V}$ (and that $\mathsf {DT}$ is false in $\mathcal {V}$). Since ${\mathsf {AC}}^{\mathsf {WO}}$ implies $\mathsf {CAC}$ (in fact, ${\mathsf {AC}}^{\mathsf {WO}}\rightarrow {\mathsf {DC}}\rightarrow \mathsf {DF=F}\rightarrow \mathsf {CAC}$—see [9, 13]), it follows (by part (11) of this theorem) that K3 is true in $\mathcal {V}$.

We show that K4* is false in $\mathcal {V}$. Firstly, we define a binary relation $\prec$ on A by: for $x,y\in A$,

$$\begin{aligned} x\prec y\Leftrightarrow \exists q,r\in \mathbb {Q}(q<r\wedge x\in A_q\wedge y\in A_r). \end{aligned}$$

Let $\preceq =\prec \cup \{(x,x):x\in A\}$. Then $\preceq$ is a partial order on A, which is in $\mathcal {V}$ since ${{\,\mathrm{\mathrm{Sym}}\,}}_{G}(\preceq )=G\in \mathcal {F}$. Similarly to the proof of (14), all antichains in A are finite. Moreover, the width of A is n.

We assert that all chains in A are countable in $\mathcal {V}$. Fix a chain $C\subset A$ which is in $\mathcal {V}$. Let $E=\bigcup \{A_{q}:q\in S\}$, for some bounded $S\subset \mathbb {Q}$, be a support of C. We assert that $C\subseteq E$. If not, then there is a $q\in \mathbb {Q}\setminus S$ such that $C\cap A_{q}\ne \emptyset$ (and note that $A_q\cap E=\emptyset$). Since C is a chain, $|C\cap A_{q}|=1$. Consider the n-cycle $\phi =(a_{q1},a_{q2},\ldots ,a_{qn})$; hence, $\phi$ fixes all atoms outside of $A_q$, and thus $\phi \in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$. As E is a support of C and $\phi \in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, we have $\phi (C)=C$. However, $\phi \upharpoonright A_q$ has no fixed points and since $|C\cap A_q|=1$, we conclude that $\phi (C)\ne C$, which is a contradiction.

Therefore, $C\subseteq E$, and since E is countable in $\mathcal {V}$ (E is a support of each of its elements, so E is well orderable in $\mathcal {V}$, and since it is countable in the ground model M, it is also countable in $\mathcal {V}$), it follows that C is countable in $\mathcal {V}$, as required.

Finally, in view of the previous argument and the fact that $A=\bigcup \{A_{q}:q\in \mathbb {Q}\}$, it readily follows that $(A,\preceq )$ has no maximal chains. Thus, K4* is false in the model $\mathcal {V}$, finishing the proof.

(17) In Tachtsis [21], it was shown that $\mathsf {DT}$ is true in Lévy’s permutation model $\mathcal {N}6$ in [9]. Since ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$ is false in $\mathcal {N}6$ (see [9]),⁸ it follows (by (1), (2), (11), and (14)) that $\hbox {K}i$ is false in $\mathcal {N}6$ for all $i=1,\ldots ,4$. $\square$

Theorem 5

The following hold:

• 1. For every $i\in \{1,2,4\}$, ${\mathsf {AC}}^{\mathsf {WO}}\nrightarrow$ (Ki $\vee$ Ki*) in ${\mathsf {ZFA}}$.

• 2. For every $i\in \{1,2,3,4\}$, ${\mathsf {MC}}\nrightarrow$ (Ki $\vee$ Ki*) in ${\mathsf {ZFA}}$.

• 3. In ${\mathsf {ZFA}}$, ${\mathsf {MC}}+{\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}} \rightarrow {\mathsf {DF}}=\mathsf {F}\rightarrow \mathsf {CAC}$. Hence, by Theorem 4(10), in ${\mathsf {ZFA}}$, ${\mathsf {MC}}+{\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}\rightarrow$ K3.⁹

• 4. ${\mathsf {LW}}$ $+$ $\mathsf {DF=F}$ $+$ ${\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}$ $+$ K1 $\nrightarrow$ ${\mathsf {MC}}_{\aleph _{0}}^{\aleph _{0}}$ in ${\mathsf {ZFA}}$. Hence, the previous conjunction (and thus $\hbox {K}i$ and K$i^{*}$ for all $i=1,\ldots ,4$) neither implies $\mathsf {CUT}$ in ${\mathsf {ZFA}}$.

Proof

(1) This follows from the proof of Theorem 4(16).

(2) In the Second Fraenkel Model—Model $\mathcal {N}2$ in [9]—${\mathsf {MC}}+\lnot \mathsf {PAC}_{2}^{\aleph _{0}}$ is true (see [9]). Hence, by Theorem 4, it follows that Ki $\vee$ K$i^{*}$ is false in $\mathcal {N}2$ for all $i=1,\ldots ,4$.

(3) Assume ${\mathsf {MC}}+{\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$. Fix an infinite set X. By Lévy’s characterization of ${\mathsf {MC}}$ [18] (${\mathsf {MC}}$ is equivalent to “Every set has a well orderable partition into finite sets”), X has a partition $\mathcal {P}=\{P_{\xi }:\xi <\kappa \}$, $\kappa$ an infinite, well-ordered cardinal, such that $0<|P_{\xi }|<\aleph _{0}$ for all $\xi <\kappa$.

By ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$, $Y=\bigcup \{P_{n}:n<\omega \}$ is a denumerable subset of X. Thus, X is Dedekind-infinite.

The implication “$\mathsf {DF=F}\rightarrow \mathsf {CAC}$” follows from Fact 1(9).

(4) We will use a Fraenkel–Mostowski model constructed by Howard and Tachtsis [12]. Let us recall the description of the model. We start with a model M of ${\mathsf {ZFA}}+{\mathsf {AC}}$ with a denumerable set A of atoms, which is written as a union of a denumerable, disjoint family of denumerable sets,

$$\begin{aligned} A=\bigcup \{B_{n}:n\in \omega \},\text { where } B_{n}=\{a_{i,n}:i\in \omega \}. \end{aligned}$$

For every $n\in \omega$, let $\mathscr {G}_n$ be the group of even permutations of $B_n$, i.e. $\mathscr {G}_{n}$ consists of all elements $\gamma$ of ${{\,\mathrm{\mathrm{FSym}}\,}}(B_{n})$ which are an even permutation of their (finite) support $\{a\in B_n:\gamma (a)\ne a\}$. Let G be the unrestricted direct product of the $\mathscr {G}_n$’s. Let I be the (normal) ideal of subsets of A which is generated by all finite unions of $B_n$ ($n\in \omega$). Let $\mathscr {U}$ be the Fraenkel–Mostowski model determined by A, G and the normal filter $\mathcal {F}$ on G generated by the subgroups ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, $E\in I$.

In [12, Sect. 6], the following was shown:

$$\begin{aligned} \mathscr {U}\models {\mathsf {LW}}+\mathsf {DF=F}+{\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}+\lnot {\mathsf {MC}}_{\aleph _{0}}^{\aleph _{0}}. \end{aligned}$$

By Theorem 2, we have that $\mathscr {U}$ is equal to the model determined by A and $\mathcal {F}$, but using the weak direct product, $\mathscr {G}$ say, of the $\mathscr {G}_n$’s as the group of permutations of A. Call this model by $\mathcal {N}$. Since $\mathscr {G}\subseteq {{\,\mathrm{\mathrm{FSym}}\,}}(A)$, and $\mathcal {N}\models {\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}$, it follows, by Theorem 3, that every poset in $\mathcal {N}$ such that all of its antichains are finite in $\mathcal {N}$, is well orderable in $\mathcal {N}$. Hence, K2 is true in $\mathcal {N}$, and thus, by Theorem 4(6), K1 is also true in $\mathcal {N}$. This completes the proof. $\square$

Remark 1

We would like to point out here that with regard to the model $\mathscr {U}$ of the proof of Theorem 5, a stronger result than ‘$\mathscr {U}\models \mathsf {DF=F}$’ was established in [23]. In particular, in [23], it was shown that Form 214 in [9]: “For every family $\mathcal {A}$ of infinite sets, there is a function f with domain $\mathcal {A}$ such that, for every $x\in \mathcal {A}$, f(x) is a denumerable subset of x” is true in $\mathscr {U}$. It is known that $\mathsf {DF=F}$ is weaker than Form 214 in ${\mathsf {ZF}}$, see [9, Model $\mathcal {M}2$, p. 148] for a ${\mathsf {ZF}}$-model of ${\mathsf {AC}}^{\mathsf {WO}}+\lnot$ Form 214 (and thus of $\mathsf {DF=F}+\lnot$ Form 214).

Corollary 1

The following hold:

• 1. For every $i\in \{1,2,3,4\}$, “Every poset has a maximal antichain” $\nrightarrow$ (Ki $\vee$ Ki*) in ${\mathsf {ZFA}}$. Hence, $\mathsf {CWF}$ $\nrightarrow$ (Ki $\vee$ Ki*), ${\mathsf {LW}}$ $\nrightarrow$ (Ki $\vee$ Ki*) in ${\mathsf {ZFA}}$, for all $i=1,\ldots ,4$.

• 2. For every $i\in \{1,2,3,4\}$, $\mathsf {CS}$ $\nrightarrow$ (Ki $\vee$ Ki*) in ${\mathsf {ZFA}}$.

Proof

The results follow from Theorem 5(2) and Fact 1[(11), (12)]. $\square$

Remark 2

In order to provide further insight and ideas on models of ${\mathsf {ZFA}}$ lacking the principles Ki, let us present another Fraenkel–Mostowski model in which ${\mathsf {MC}}$ (and thus ${\mathsf {LW}}$) is true, but Ki is false for all $i=1,\ldots ,4$. The model was introduced (to the best of our knowledge) by Herrlich, Howard and Tachtsis [6, proof of Theorem 12] and, as the reader will soon realize, it is a natural setting for the failure of the $\hbox {K}i$’s due to the description of the atoms, the group and the normal filter of supports which determine the model. Let us also note that the status of either ${{\mathsf {MC}}}$ and ${\mathsf {LW}}$ in this model was undetermined until now, and thus we contribute to new information about this interesting model.

We start with a model M of ${\mathsf {ZFA}}+{\mathsf {AC}}$, whose atoms are identified with the elements of $2^{<\omega }$ (in order to simplify the definition of the group G), i.e. with finite, non-empty sequences of 0’s and 1’s. Let A be the set of the atoms. We may view A as two infinite binary trees, the one having $\langle 0\rangle$ as its root and the other having $\langle 1\rangle$ as its root. The set A is partially ordered by the extension of sequences, i.e., for $t,s\in A$, $t\le s$ if and only if t is an initial segment of s. Let G be the group of all order automorphisms of $(A,\le )$, that is, if $t\in A$ and $\phi \in G$, then t and $\phi (t)$ have the same length and if $s\in A$ and $t\le s$, then $\phi (t)\le \phi (s)$. The normal ideal of supports is $[A]^{<\omega }$. Let $\mathcal {N}$ be the Fraenkel–Mostowski model determined by M, G and the normal filter $\mathcal {F}$ generated by the subgroups ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, $E\in [A]^{<\omega }$.

Note that $\le \in \mathcal {N}$ since ${{\,\mathrm{\mathrm{Sym}}\,}}_{G}(\le )=G\in \mathcal {F}$. For each $t \in A$, we denote the length of (the sequence indexing the atom) t by ln(t). For each $n\in \omega \setminus \{0\}$, let

$$L_{n}=\{t\in A:\ln (t)=n\},$$

and also let $\mathcal {L}=\{L_{n}:n\in \omega \}$. Using standard Fraenkel–Mostowski techniques, one may easily verify that $\mathcal {L}$ is a denumerable partition of A in $\mathcal {N}$ (comprising non-empty, finite sets) and that $\mathcal {L}$ has no partial choice function in $\mathcal {N}$. Hence, ${\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$ is false in $\mathcal {N}$, and consequently (by Theorem 4[(10), (13)]) Ki is false in $\mathcal {N}$ for all $i=1,\ldots ,4$.

Of course, one may directly show that in the infinite poset $(A,\le )$ all chains and all antichains are finite, so $\mathsf {CAC}$ is false for $(A,\le )$ (and thus K1, K2, K3 are also false for $(A,\le )$) and A has no maximal chains, so K4 is also false for $(A,\le )$. Since G comprises all order automorphisms of $(A,\le )$ and supports are the finite subsets of A, it is easy to verify that all chains in A are finite. On the other hand, assume, by way of contradiction, that A has an infinite antichain in $\mathcal {N}$, D say. Let $E\in [A]^{<\omega }$ be a support of D. Since D is infinite, there exists $d\in D$ such that, for all $e\in E$, $\ln (e)<\ln (d)$. Furthermore, as D is an antichain, there exists $a\in A\setminus D$ with $\ln (a)=\ln (d)$, and note that if $x\in D$ and $\ln (e)<\ln (x)$ for all $e\in E$, then $x'\in D$, where $x'$ satisfies $x'\ne x$, $\ln (x')=\ln (x)$ and $x',x$ differ only in their last coordinates (so $d'\in D$ and $a'\not \in D$).

By the above observation, it follows that every element of $\{x\in A\setminus D:\ln (x)=\ln (d)\}$ is extended by some element of D. But then, as D is infinite, there must exist at least two elements of D which are comparable, contradicting D’s being an antichain. Hence, D is finite.

That ${\mathsf {MC}}$ is true in the model $\mathcal {N}$, can be proved in much the same way as the fact that ${\mathsf {MC}}$ is true in the Second Fraenkel Model (Model $\mathcal {N}2$ in [9]), see [13, Theorem 9.2(i), p.134]. In particular, one shows that the G-orbit of every element of $\mathcal {N}$ is finite, and hence every $x\in \mathcal {N}$ is a disjoint union of a well orderable family of finite sets (since $x\in \mathcal {N}$ is the union of the ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$-orbits of its elements, where $E\in [A]^{<\omega }$ is a support of x). We take the liberty to leave the details as an easy exercise for the reader.

Since ${\mathsf {MC}}$ is true in $\mathcal {N}$, so is ${\mathsf {LW}}$ (see Fact 1(11)). However, we consider it interesting in its own right to elucidate on the model $\mathcal {N}$ and give a self-contained proof of ‘$\mathcal {N}\models {\mathsf {LW}}$’. To achieve this goal, the plan is to use Theorem 1, but due to the definition of the group G, a direct argument within the model $\mathcal {N}$ which verifies condition (*) stated in the above theorem is not easy. (And note that there are infinitely many elements of G which do not have finite order—in contrast to the Second Fraenkel Model where all elements of the corresponding group G have order 2.) So in order to simplify the argument, we will first modify the definition of G, but we will keep the ideal of finite supports, and then prove that the resulting Fraenkel–Mostowski model satisfies ${\mathsf {LW}}$ and is equal to $\mathcal {N}$; thus obtaining that $\mathcal {N}\models {\mathsf {LW}}$.

Recalling that, for every $n\in \omega \setminus \{0\}$, $L_{n}=\{t\in A:\ln (t)=n\}$, we let $\mathscr {G}$ be the set of all $\phi \in G$ which have the following property:

• (#) There exists $m\in \omega \setminus \{0\}$ such that, for every $s\in L_{m}$ and every $n>m$, if $t=(t_1,t_2,\ldots ,t_n)\in L_{n}$ is any extension of s, then

  $$\begin{aligned} \phi (t)=\phi (s){\frown }(t_{m+1},\ldots ,t_{n}), \end{aligned}$$

so $\phi (t)$ has the same $m+1, \ldots ,n$ coordinates as t. For example, assume $\phi \in \mathscr {G}$ satisfies (#) for $m=2$. Suppose that, for $s=(0,0)$, $\phi (s)=(1,1)$. If t is any proper extension of s, e.g. $t=(t_1,t_2,t_3,t_4)=(0,0,1,0)$, then $\phi (t)=(1,1,1,0)=\phi (s){\frown }(t_3,t_4)$. Also, note that if, for $s\in L_{m}$, $\phi (s)=s$, then for every $n>m$ and every $t\in L_{n}$ extending s, we have $\phi (t)=t$.

It is not hard to verify that $\mathscr {G}$ is a (proper) subgroup of G such that each of its elements has finite order. To see the second assertion, fix a non-identity element $\phi$ of $\mathscr {G}$. There exists $m\in \omega \setminus \{0\}$ satisfying (#) for $\phi$, and for which $\phi ^{*}=\phi \upharpoonright L_{m}\ne \mathrm {id}_{L_{m}}$. Since $L_m$ is finite (in particular, $|L_{m}|=2^{m}$) and $\phi ^{*}$ is a permutation of $L_{m}$, it follows that $\phi ^{*}$ has finite order, k say, for some $k\in \omega \setminus \{0\}$. This, together with the fact that m satisfies (#) for $\phi$, easily yields $\phi$ has order k.

Let $\mathscr {V}$ be the Fraenkel–Mostowski model determined by M (the same ground model as with $\mathcal {N}$), $\mathscr {G}$ and $\mathcal {F}$ (the finite support normal filter on $\mathscr {G}$).

Since every element of $\mathscr {G}$ has finite order, the second part of Theorem 1 yields $\mathscr {V}\models {\mathsf {LW}}$. To complete the proof, we need to show that $\mathscr {V}=\mathcal {N}$.

We will prove by $\in$-induction that, for every $x\in M$, $\varPhi (x)$ is true, where

$$\begin{aligned} \varPhi (x):\ x \in \mathscr {V}\Leftrightarrow x \in \mathcal {N}. \end{aligned}$$

Clearly $\varPhi (x)$ is true, if $x = \emptyset$, or if $x\in A$. Assume $y \in M$ and that for all $x \in y$, $\varPhi (x)$ is true. We will show that $\varPhi (y)$ is true. Assume $y \in \mathscr {V}$. Then the following hold:

• (1) y has a support $E\in [A]^{<\omega }$ relative to the group $\mathscr {G}$ (i.e., for every $\psi \in {{\,\mathrm{\mathrm{fix}}\,}}_{\mathscr {G}}(E)$, $\psi (y)=y$);

• (2) for every $x \in y$, $x \in \mathscr {V}$ ($\mathscr {V}$ is a transitive class);

• (3) for every $x \in y$, $x \in \mathcal {N}$ (by (2) and the induction hypothesis).

We assert that E is a support of y relative to the group G. It suffices to show that, for all $\phi \in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$ and for all $x \in y$, $\phi (x) \in y$ (since then $\phi (y) =y$ follows from “$\phi (y) \subseteq y$ and $\phi ^{-1}(y) \subseteq y$”).

To this end, let $\phi \in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$ and let $x \in y$. By (3), x has a support $E'\in [A]^{<\omega }$ relative to G. Let $m_0=\max \{m\in \omega \setminus \{0\}:(E\cup E')\cap L_{m}\ne \emptyset \}$. Hence, for every $a\in E\cup E'$, either $a\in L_{m_{0}}$ or there is a proper extension of a in $L_{m_{0}}$.

The permutation $\phi$ may not be in $\mathscr {G}$ (recall $\mathscr {G}\subsetneq G$), but we construct a permutation $\phi ' \in {{\,\mathrm{\mathrm{fix}}\,}}_{\mathscr {G}}(E)$ which agrees with $\phi$ on $E'$ as follows: For each $a \in E'$, the set $\{ \phi ^n(a) : n \in \mathbb Z \}$ is finite since A is identified with $2^{<\omega }$ and $\phi$ preserves the lengths of the elements of $2^{<\omega }$ (indexing atoms). Therefore, since $E'$ is finite, so is $D = \bigcup \{\{ \phi ^n(a) : n \in \mathbb Z \}:a \in E'\}$. Furthermore, $E'\subseteq D\subseteq \bigcup \{L_{n}:1\le n\le m_{0}\}$ and D is closed under $\phi$.

We define a mapping $\phi ': A \rightarrow A$ by:

$$\begin{aligned} \phi '(a) = {\left\{ \begin{array}{ll} \phi (a), &{} \text{ if } a \in \bigcup \{L_{n}:1\le n\le m_{0}\}; \\ \phi ((a_1,\ldots ,a_{m_{0}})){\frown }(a_{m_{0}+1},\ldots ,a_{n}), &{} \text{ if } a\in L_{n} \text{ for } \text{ some } n > m_{0}. \end{array}\right. } \end{aligned}$$

Then the following hold:

• (4) $\phi '\in \mathscr {G}$ (since $\phi '\in G$ and $m_{0}$ satisfies (#) for $\phi '$);

• (5) $\phi '$ fixes E pointwise (since $\phi$ fixes E pointwise);

• (6) $\phi '$ agrees with $\phi$ on $E'$.

By (4) and (5), $\phi ' \in {{\,\mathrm{\mathrm{fix}}\,}}_{\mathscr {G}}(E)$, so (by (1)) $\phi '(y) = y$. It follows that $\phi '(x) \in y$. Moreover, (6), together with the facts that $\phi ,\phi '\in G$ ($\phi '\in \mathscr {G}\subset G$) and $E'$ being a support of x relative to G, gives $\phi '(x) = \phi (x)$, and hence $\phi (x) \in y$, as required.

Conversely, assume that $y \in \mathcal {N}$ and that y has a support $E'$ relative to G. Then $E'$ is a support of y relative to $\mathscr {G}$ since $\mathscr {G}\subset G$. By the induction hypothesis, every element of y is in $\mathscr {V}$, and so $y \in \mathscr {V}$. This completes the inductive step.

Thus, $\mathscr {V}=\mathcal {N}$, as required.

It is unknown whether any of ${\mathsf {BPI}}$, ${\mathsf {AC}}_{\mathsf {fin}}$, and ${\mathsf {AC}}_{\le \aleph _{0}}$ imply $\hbox {K}i$ for some $i=1,\ldots ,4$; in particular, in Howard and Rubin [9], it is mentioned as unknown whether any of ${\mathsf {BPI}}$, ${\mathsf {AC}}_{\mathsf {fin}}$, and ${\mathsf {AC}}_{\le \aleph _{0}}$ imply $\mathsf {CAC}$, which (by Theorem 4(11)) is equivalent to K3. We address this open problem here and provide a negative answer (in the forthcoming Theorem 6) for ${\mathsf {AC}}_{\le \aleph _{0}}$ (and thus for ${\mathsf {AC}}_{\mathsf {fin}}$) in the setting of ${\mathsf {ZFA}}$, that is, we show ${\mathsf {AC}}_{\le \aleph _{0}}\nrightarrow$ Ki in ${\mathsf {ZFA}}$, for all $i=1,\ldots ,4$. Hence, our independence result also resolves (in ${\mathsf {ZFA}}$) the part of the above open problem of [9] concerning ${\mathsf {AC}}_{\mathsf {fin}}$, ${\mathsf {AC}}_{\le \aleph _{0}}$ and ${\mathsf {CAC}}$.

Let us also point out here that it is natural to inquire on the relationship of ${\mathsf {AC}}_{\le \aleph _{0}}$ with the $\hbox {K}i$’s, and especially with K4, in view of Frink’s proof [2] of the extension of chains in posets to maximal chains, which uses only Zermelo’s formulation of ${\mathsf {AC}}$ (and not the notion of a well ordering), as well as in view of the fact that all chains in the posets of interest are countable.

Finally, we recall that ${\mathsf {BPI}}\rightarrow {\mathsf {AC}}_{\mathsf {fin}}$ and, by Theorem 4(8), ${\mathsf {BPI}}\rightarrow$ K1*. However, it is an open problem whether or not ${\mathsf {BPI}}$ implies ${\mathsf {AC}}_{\le \aleph _{0}}$ (see [9]). We also note that, in view of the above implication and Fact 1(15), if a Fraenkel–Mostowski model satisfies ${\mathsf {BPI}}$, then it also satisfies ${\mathsf {AC}}_{\le \aleph _{0}}$.

For the independence result of the subsequent Theorem 6, we will need some terminology and a lemma (which are specific instances of general terminology and results) from [14]—see also [13, Sect. 7.2, Lemma 7.5 and p. 103].

Definition 7

Let $\mathcal {K}$ be the class of all structures $(P,<,\prec )$, where P is a non-empty, countable set, < is a partial ordering on P and $\prec$ is a linear ordering on P. A structure $(P,<,\prec )\in \mathcal {K}$ is called:

(a) universal if every finite structure $(Q,<^{*},\prec ^{*})\in \mathcal {K}$ (i.e. Q is finite) can be embedded in $(P,<,\prec )$;

(b) homogeneous if whenever $E_1$ and $E_2$ are finite subsets of P, and i is an isomorphism of $(E_1,<,\prec )$ and $(E_2,<,\prec )$, then i can be extended to an automorphism of $(P,<,\prec )$.

For the existence of a countable universal homogeneous structure in $\mathcal {K}$, the reader is referred to [14] and [13, Sect. 7.2, Lemma 7.6].

Lemma 1

Let $\mathcal {K}$ be as in Definition 7 and also let $(P,<,\prec )\in \mathcal {K}$ be a (countable) universal homogeneous structure. If $(E,<^{*},\prec ^{*})$ is a finite structure in $\mathcal {K}$, $E_0\subseteq E$, and if $e_0$ is an embedding of $(E_0,<^{*},\prec ^{*})$ into $(P,<,\prec )$, then there is an embedding e of $(E,<^{*},\prec ^{*})$ into $(P,<,\prec )$ which extends $e_0$.

Theorem 6

${\mathsf {AC}}_{\mathsf {WO}}\nrightarrow$ $\hbox {K}i$ in ${\mathsf {ZFA}}$, for all $i=1,\ldots ,4$. In particular, by Theorem 4(11), ${\mathsf {AC}}_{\mathsf {WO}}\nrightarrow \mathsf {CAC}$ in ${\mathsf {ZFA}}$.

Proof

For our independence result, we will use a Fraenkel–Mostowski model by Mathias and Pincus, which is labeled as Model $\mathcal {N}5$ in [9]. The description of the model is as follows: Let the set A of atoms be denumerable, and let < and $\prec$ be a partial and a linear ordering on A (so $(A,<,\prec )\in \mathcal {K}\cap M$, where M is the ground model of ${\mathsf {ZFA}}+{\mathsf {AC}}$) such that $(A,<,\prec )$ is a universal homogeneous structure. Let G be the group of all automorphisms of $(A,<,\prec )$ (i.e. G comprises all bijections $\phi :A\rightarrow A$ which preserve both < and $\prec$). Let $\mathcal {F}$ be the normal filter on G generated by the subgroups ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, $E\in [A]^{<\omega }$. $\mathcal {N}5$ is the Fraenkel–Mostowski model determined by A, G and $\mathcal {F}$.

We have $<,\prec \in \mathcal {N}5$ since ${{\,\mathrm{\mathrm{Sym}}\,}}_{G}(<)={{\,\mathrm{\mathrm{Sym}}\,}}_{G}(\prec )=G\in \mathcal {F}$. Furthermore, it is known that $\mathcal {N}5\models {\mathsf {AC}}_{\le \aleph _{0}}$ (see [9]). Since ${\mathsf {AC}}_{\le \aleph _{0}}\rightarrow {\mathsf {AC}}_{\mathsf {fin}}$, it follows, by Fact 1(15), that

$$\begin{aligned} \mathcal {N}5\models {\mathsf {AC}}_{\mathsf {WO}}. \end{aligned}$$

We show that, in $\mathcal {N}5$, all antichains and all chains in the infinite poset $(A,<)$ are finite and that every (finite) chain in $(A,<)$ can be extended.

Claim

In $\mathcal {N}5$, all antichains and all chains in $(A,<)$ are finite.

Proof

Let $Z\subseteq A$ be an antichain in $(A,<)$, which is in $\mathcal {N}5$. Let $E\in [A]^{<\omega }$ be a support of Z. We assert that $Z\subseteq E$. If not, then let $a\in Z\setminus E$. Let b be an element of $\mathcal {N}5$ which is not in A. Let $U=E\cup \{a,b\}$. We define two binary relations $<^{*}$ and $\prec ^{*}$ on U as follows:

(a) $<^{*}\upharpoonright E\cup \{a\}=<\upharpoonright E\cup \{a\}$; for every $x\in E$, b is $<^{*}$-related to x iff a is <-related to x and, in this case, b is $<^{*}$-related to x exactly as a is <-related to x; and $a<^{*}b$.

(b) $\prec ^{*}\upharpoonright E\cup \{a\}=\prec \upharpoonright E\cup \{a\}$; for every $x\in E$, b is $\prec ^{*}$-related to x exactly as a is $\prec$-related to x (recall that $\prec$ is a linear ordering on A, so a is $\prec$-related to x for all $x\in E$); and $a\prec ^{*}b$.

It is reasonably clear that $<^{*}$ and $\prec ^{*}$ are, respectively, a partial and a linear ordering on U. Let $j_{0}$ be the identity mapping on $E\cup \{a\}$. Then $j_{0}$ is an embedding of $(E\cup \{a\}, <^{*},\prec ^{*})$ into $(A,<,\prec )$. Hence, by Lemma 1, $j_{0}$ can be extended to an embedding j of $(U,<^{*},\prec ^{*})$ into $(A,<,\prec )$. Thus, $j(b)\in A$, $a=j_{0}(a)=j(a)<j(b)$ and $a\prec j(b)$ since $a<^{*}b$, $a\prec ^{*} b$, and j is an embedding.

Now we consider the following two finite substructures of $(A,<,\prec )$:

$$\begin{aligned}&V_{0}=(E\cup \{a\},<,\prec ),\\&V_{1}=(E\cup \{j(b)\},<,\prec ). \end{aligned}$$

We define a mapping $k_{0}:V_{0}\rightarrow V_{1}$ by:

$$\begin{aligned} k_{0}(x) = {\left\{ \begin{array}{ll} x, &{} \text{ if } x \in E; \\ j(b), &{} \text{ if } x=a. \end{array}\right. } \end{aligned}$$

By definition of $<^{*}$ and $\prec ^{*}$ on U and the fact that j is an embedding, it follows that $k_{0}$ is an isomoprhism of $V_{0}$ and $V_{1}$. Since $(A,<,\prec )$ is homogeneous, $k_{0}$ can be extended to an automorphism of $(A,<,\prec )$, k say.

We have $k\in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, so since E is a support of Z, $k(Z)=Z$. Furthermore,

$$\begin{aligned} a\in Z\Rightarrow k(a)\in k(Z)\Rightarrow j(b)\in Z. \end{aligned}$$

However, $a<j(b)$, which is impossible since $a,j(b)\in Z$ and Z is an antichain in $(A,<)$. We have thus reached a contradiction, and hence $Z\subseteq E$, as asserted. Therefore, every antichain in $(A,<)$, which is in $\mathcal {N}5$, is finite, as required.

The second assertion about the chains in $(A,<)$ being finite can be proved similarly to the above argument, so we only provide a sketch of the proof.

Let $C\subseteq A$ be a chain in $(A,<)$, which is in $\mathcal {N}5$. Let $E\in [A]^{<\omega }$ be a support of C. We assert that $C\subseteq E$ (and thus C is finite). Assume the contrary. Let $a\in C\setminus E$ and also let $b\in \mathcal {N}5\setminus A$. Let $U=E\cup \{a,b\}$ and define a partial ordering $<^{*}$ and a linear ordering $\prec ^{*}$ on U as follows:

(c) $<^{*}\upharpoonright E\cup \{a\}=<\upharpoonright E\cup \{a\}$; for every $x\in E$, b is $<^{*}$-related to x iff a is <-related to x and, in this case, b is $<^{*}$-related to x exactly as a is <-related to x; and a, b are $<^{*}$-incomparable.

(d) $\prec ^{*}\upharpoonright E\cup \{a\}=\prec \upharpoonright E\cup \{a\}$; for every $x\in E$, b is $\prec ^{*}$-related to x exactly as a is $\prec$-related to x; and $a\prec ^{*}b$.

Now let $j_{0},j,V_{0},V_{1},k_{0},k$ be defined as in the first part of the proof. As in that part, $k\in {{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, so $k(C)=C$ since E is a support of C. Furthermore, as $a\in C$, we have $j(b)\in C$. However, a and j(b) are <-incomparable, contradicting C’s being a chain in $(A,<)$. Thus, $C\subseteq E$, as asserted, and as C was arbitrary, we conclude that all chains in $(A,<)$ which are in $\mathcal {N}5$ are finite.

The above arguments complete the proof of the claim. $\square$

Claim

Every chain in $(A,<)$, which is in $\mathcal {N}5$, can be extended.

Proof

Let $C\subseteq A$ be a chain in $(A,<)$, which is in $\mathcal {N}5$. By the first claim, we know that C is finite. Let $b\in \mathcal {N}5\setminus A$, and also let $D=C\cup \{b\}$.

We define two binary relations $<^{*}$ and $\prec ^{*}$ on D as follows:

(e) $<^{*}=<\upharpoonright C\cup \{(x,b):x\in C\}$.

(f) $\prec ^{*}=\prec \upharpoonright C\cup \{(x,b):x\in C\}$.

Clearly, $<^{*}$ and $\prec ^{*}$ are linear orderings on D. Let $j_{0}$ be the identity mapping on C. Then $j_{0}$ is an embedding of $(C,<^{*},\prec ^{*})$ into $(A,<,\prec )$. Hence, by Lemma 1, $j_{0}$ can be extended to an embedding j of $(D,<^{*},\prec ^{*})$ into $(A,<,\prec )$. Thus, $j(b)\in A$ and, for every $x\in C$, $x=j(x)<j(b)$. Let $C'=C\cup \{j(b)\}$. Then $C'$ is a chain in $(A,<)$ which properly extends C. Furthermore, $C'\in \mathcal {N}5$ since $C'\in [A]^{<\omega }$, and thus $C'$ is a support of itself.

The above arguments complete the proof of the claim. $\square$

By the first claim and Theorem 4(11), we conclude that K3 is false in $\mathcal {N}5$, and thus (by Theorem 4[(1), (2)]) so are K1 and K2. Moreover, by the above two Claims, we deduce that K4 is false in $\mathcal {N}5$. Therefore, Ki is false in $\mathcal {N}5$ for all $i=1,\ldots ,4$, finishing the proof of the theorem. $\square$

Remark 3

Using similar ideas as in the argument for the second Claim of the proof of Theorem 6, one may show that, in the Fraenkel–Mostowski model $\mathcal {N}5$, every antichain in the poset $(A,<)$, which is in $\mathcal {N}5$, can be extended. Hence, the set of the cardinalities of antichains in $(A,<)$ is unbounded and, as all antichains of $(A,<)$ in $\mathcal {N}5$ are finite (by the first Claim of the proof of Theorem 6), the width of $(A,<)$ is (in $\mathcal {N}5$) equal to $\omega$, and thus is infinite.

As already mentioned, it is unknown whether or not ${\mathsf {BPI}}$ implies Ki for some $i=1,\ldots ,4$. The so-called Mostowski Linearly Ordered Model—Model $\mathcal {N}3$ in [9]—satisfies ${\mathsf {BPI}}$ (see Halpern [4]), and thus it is natural to investigate the status of Ki ($i=1,\ldots ,4$) in $\mathcal {N}3$. We show in the next theorem that K1 is true in $\mathcal {N}3$. Since (by Theorem 4(11)) K3 $\leftrightarrow$ $\mathsf {CAC}$, we also obtain that $\mathsf {CAC}$ is true in $\mathcal {N}3$. (Recall that K1 implies $\hbox {K}i$ and $\hbox {K}i^{*}$ for all $i=1,\ldots ,4$.)

Let us note that the status of $\mathsf {CAC}$ in $\mathcal {N}3$ is mentioned as unknown in [9], so our result fills the gap in the missing information.

Theorem 7

The following hold:

• 1. K1 is true in the Mostowski Linearly Ordered Model $\mathcal {N}3$ in [9]. In particular, $\mathsf {CAC}$ is true in $\mathcal {N}3$.

• 2. K1 implies none of $\mathsf {LDF=F}$, ${\mathsf {LW}}$, $\mathsf {CWF}$, and $\mathsf {CS}$ in ${\mathsf {ZFA}}$.

Proof

(1) For the reader’s convenience, we first recall the description of $\mathcal {N}3$. We start with a model M of ${\mathsf {ZFA}} + {\mathsf {AC}}$ with a denumerable set A of atoms using an ordering $\le$ on A chosen so that $(A,\le )$ is order-isomorphic to the set $\mathbb {Q}$ of the rational numbers with the usual ordering. Let G be the group of all order automorphisms of $(A,\le )$. Let $\mathcal {F}$ be the normal filter on G generated by the subgroups ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, $E\in [A]^{<\omega }$. $\mathcal {N}3$ is the Fraenkel–Mostowski model determined by M, G and $\mathcal {F}$.

In $\mathcal {N}3$, $(A,\le )$ is a Dedekind-finite, linearly ordered set, and $\mathsf {WUT}$ is true (see [9, 13, Sect. 4.5]); hence, $\mathsf {CUT}$ is also true in $\mathcal {N}3$. Furthermore, in Tachtsis [20, Theorem 2.4], it was shown that $\mathcal {N}3$ satisfies $\mathsf {RT}$ (Ramsey’s Theorem), and thus (by Fact 1(9)) also satisfies $\mathsf {CAC}$ (which is equivalent to K3).

We show that K2 is true in $\mathcal {N}3$. Then, by Theorem 4(5) (or 4(6)), we will obtain that $\mathcal {N}3\models$ K1, and thus $\mathcal {N}3\models$ Ki $\wedge$ K$i^{*}$, for all $i=1,\ldots ,4$. We will use the following lemma from [10].

Lemma 2

([10, Lemma 3.17]) Every set in $\mathcal {N}3$ is either well orderable or contains a copy of a bounded open interval in the ordering of A.

Now let $(P,\preceq )$ be a poset in $\mathcal {N}3$ such that, in $\mathcal {N}3$, all antichains in P are finite and all chains in P are countable. We assert that P is well orderable in $\mathcal {N}3$. Assume the contrary. By Lemma 2, there is a set $X\subseteq P$ and two atoms $a,b\in A$ with $a<b$ such that $X\in \mathcal {N}3$ and, in $\mathcal {N}3$, $|X|=|(a,b)|$. Hence, X is infinite and, since all antichains in $(X,\preceq \upharpoonright X)$ are finite and $\mathsf {CAC}$ is true in $\mathcal {N}3$, there is an infinite chain in $(X,\preceq \upharpoonright X)$, C say, which is in $\mathcal {N}3$. By our assumption on P, we infer that C is a denumerable subset of X. This, together with $|X|=|(a,b)|$, yields (a, b) is Dedekind-infinite in $\mathcal {N}3$, and thus so is the set A of atoms. But this contradicts A’s being Dedekind-finite in $\mathcal {N}3$. Thus, P is well orderable in $\mathcal {N}3$, as asserted.

By the above arguments, we conclude that K2 is true in $\mathcal {N}3$, finishing the proof of (1).

(2) The result follows from (1) and the following facts:

(a) $\mathsf {LDF=F}$ is false for the infinite, Dedekind-finite, linearly ordered set A of atoms of $\mathcal {N}3$; hence, ${\mathsf {LW}}$ is also false in $\mathcal {N}3$, and thus (by Fact 1(11)) so is $\mathsf {CWF}$.

(b) $\mathsf {CS}$ is false in $\mathcal {N}3$, as shown by Howard, Saveliev and Tachtsis [10, Theorem 3.9(1)]. $\square$

Theorem 8

The following hold:

• 1. $\mathsf {WOAM}+\mathsf {CAC}\rightarrow K1$. Hence, $\mathsf {WOAM}+K3\rightarrow K1$.

• 2. K1 is true in the Basic Fraenkel Model $\mathcal {N}1$ in [9]. Hence, K1 $\nrightarrow$ “There are no amorphous sets” in ${\mathsf {ZFA}}$.

• 3. K1 $\nrightarrow \mathsf {WOAM}$ in ${\mathsf {ZFA}}$.

Proof

(1) Assume that ${\mathsf {WOAM}}+{\mathsf {CAC}}$ is true. Let $(P,\le )$ be a poset such that all of its antichains are finite and all of its chains are countable. We assert that P is well orderable. Assume the contrary. By ${\mathsf {WOAM}}$, P has an amorphous subset, A say. Since $(A,\le \upharpoonright A)$ is an infinite poset such that all of its antichains are finite, it follows, by ${\mathsf {CAC}}$, that A has an infinite chain, C say. By our hypothesis that all chains in P are countable, we have that C is a denumerable subset of A. But this contradicts the fact that A is amorphous. Therefore, P is well orderable, as asserted.

By the above arguments, we conclude that K2 is true. Furthermore, since (by Fact 1(7)) $\mathsf {WOAM}\rightarrow \mathsf {CUT}$, Theorem 4(5) yields K1 is also true.

(2) This follows from (1) and the fact that $\mathsf {WOAM}$ $+$ $\mathsf {CAC}$ $+$ “There exists an amorphous set” is true in $\mathcal {N}1$ (see [9]).

(3) By Theorem 7(1), K1 is true in the Mostowski Linearly Ordered Model $\mathcal {N}3$. On the other hand, it is known that ${\mathsf {WOAM}}$ is false in $\mathcal {N}3$ (see [9]). The above two facts yield the required independence result. $\square$

Remark 4

With regards to Theorem 8(2), a different argument of the statement ‘K1 holds in the Basic Fraenkel Model’ can be found in [1, Remark 4.4]. But as an application of the fact ‘$\mathsf {WOAM}+\mathsf {CAC}\rightarrow$ K1 in ${\mathsf {ZF}}$’, the proof of Theorem 8(2) is itself interesting.

Theorem 9

The following hold:

• 1. $\mathsf {W}_{\aleph _{1}}+\mathsf {CUT}\rightarrow K1$. Hence, by Fact 1(16),

  $$\begin{aligned} {\mathsf {DC}}_{\aleph _{1}}\rightarrow K1. \end{aligned}$$

• 2. $\mathsf {W}_{\aleph _{1}}$ $+$ “$\aleph _{1}$ is regular” $\rightarrow K1$. Hence, in every Fraenkel–Mostowski model, $\mathsf {W}_{\aleph _{1}}\rightarrow K1$.

• 3. $\mathsf {W}_{\aleph _{1}}\rightarrow$ K3.

• 4. K1 does not imply ${\mathsf {AC}}_{2}^{\mathsf {LO}}$ in ${\mathsf {ZFA}}$, and hence neither does it imply ${\mathsf {AC}}_{\mathsf {fin}}$ (and hence ${\mathsf {AC}}_{\le \aleph _{0}}$) and $\mathsf {DT}$.

• 5. ${\mathsf {BPI}}+K1\nrightarrow {\mathsf {DC}}\vee \mathsf {W}_{\aleph _{1}}$ in ${\mathsf {ZFA}}$. Hence (in view of Fact 1(16)), $K1\nrightarrow {\mathsf {DC}}_{\aleph _{1}}$ in ${\mathsf {ZFA}}$.

Proof

(1) Assume that $\mathsf {W}_{\aleph _{1}}+\mathsf {CUT}$ is true. Fix a poset $(P,\le )$ such that all of its antichains are finite and all of its chains are countable. By $\mathsf {W}_{\aleph _{1}}$, $\aleph _{1}\le |P|$ or $|P|\le \aleph _{1}$. In the first case, P has a subset Q with cardinality $\aleph _{1}$. Hence, Q is well orderable, and thus by the proof of Theorem 4(5), we deduce that the poset $(Q,\le \upharpoonright Q)$ is countable, which is impossible. Therefore, the first of the above two possibilities cannot occur, so $|P|\le \aleph _{1}$, and thus P is well orderable. Again, invoking the proof of Theorem 4(5), we conclude that P is countable. Since $(P,\le )$ was arbitrary, we infer that K1 is true.

(2) This can be proved similarly to (1), taking into account the proof of Theorem 4(6).

(3) This is straightforward.

(4) We will use a Fraenkel–Mostowski model constructed in [13, Proof of Theorem 8.3]. The set A of atoms has cardinality $\aleph _{2}$ and it is a disjoint union of $\aleph _{2}$ pairs: $A=\bigcup \{P_{\xi }:\xi <\aleph _{2}\}$, where $|P_{\xi }|=2$ for all $\xi <\aleph _{2}$ and $P_{\nu }\cap P_{\xi }=\emptyset$ for every two distinct $\nu ,\xi <\aleph _{2}$. Let G be the group of all permutations $\phi$ of A such that $\phi (P_{\xi })=P_{\xi }$ for all $\xi <\aleph _{2}$. Let $\mathcal {F}$ be the normal filter on G generated by the subgroups ${{\,\mathrm{\mathrm{fix}}\,}}_{G}(E)$, $E\subset A$ and $|E|<\aleph _{2}$. Let $\mathscr {V}$ be the Fraenkel–Mostowski model determined by A, G and $\mathcal {F}$.¹⁰

Jech [13, Proof of Theorem 8.3] proves that ${\mathsf {DC}}_{\aleph _{1}}$ is true in $\mathscr {V}$, and hence (by (1) of this theorem) K1 is true in $\mathscr {V}$. On the other hand, the family $\{P_{\xi }:\xi <\aleph _{2}\}$ has no choice function in $\mathscr {V}$ (see [13]), and thus ${\mathsf {AC}}_{2}^{\mathsf {LO}}$ is false in $\mathscr {V}$. By Fact 1(13)(b), we conclude that $\mathsf {DT}$ is also false in the model $\mathscr {V}$.

(5) By Theorem 7(1), K1 is true in the Mostowski Linearly Ordered Model $\mathcal {N}3$ in [9]. The conclusion now follows from the fact that $\mathcal {N}3\models {\mathsf {BPI}}+\lnot {\mathsf {DC}}+\lnot \mathsf {W}_{\aleph _{1}}$ (see [9]). $\square$

Remark 5

We note that Theorems 5(1) and 9(1) provide a new proof of the known fact that ${\mathsf {AC}}^{\mathsf {WO}}$ does not imply ${\mathsf {DC}}_{\aleph _{1}}$ or $\mathsf {W}_{\aleph _{1}}$ in ${\mathsf {ZFA}}$ set theory. For the direct proof of the latter ${\mathsf {ZFA}}$-independence result, which is transferable into ${\mathsf {ZF}}$, the reader is referred to Jech [13, Theorem 8.9].

5 Summary of results

We summarize main results of the paper in the form of a diagram—Diagram 1 below—and a list of further implications/non-implications. Some clarifications about Diagram 1 are in order:

• 1. A dashed arrow from $\mathsf {A}$ to $\mathsf {B}$ means that $\mathsf {A}$ implies $\mathsf {B}$, but the implication is not reversible in ${\mathsf {ZFA}}$.

• 2. If proposition $\mathsf {A}$ is equivalent to proposition $\mathsf {B}$, then we use a thick left-right arrow between $\mathsf {A}$ and $\mathsf {B}$,

• 3. A negated left-right arrow between two principles means that those principles are independent of each other in ${\mathsf {ZFA}}$.

• 4. Some implications/non-implications between certain principles in Diagram 1 are known and corresponding references can be found either in Fact 1 of Sect. 2 or in Howard–Rubin [9] or in Jech [13].

List of further results:

• 1. K2 $+$ P $\rightarrow$ K1, where $P\in \{\mathsf {CUT},{{\,\mathrm{\mathrm{cf}}\,}}(\aleph _{1})=\aleph _{1}\}$ (where ‘${{\,\mathrm{\mathrm{cf}}\,}}(\aleph _{1})=\aleph _{1}$’ abbreviates ‘$\aleph _{1}$ is regular’).

• 2. $\mathsf {W}_{\aleph _{1}}+P$ $\rightarrow$ K1, where $P\in \{\mathsf {CUT},{{\,\mathrm{\mathrm{cf}}\,}}(\aleph _{1})=\aleph _{1}\}$.

• 3. $\mathsf {W}_{\aleph _{1}}\rightarrow$ K3 ($\leftrightarrow \mathsf {CAC}$).

• 4. $\mathsf {WOAM}+\mathsf {CAC}\rightarrow$ K1. Hence, $\mathsf {WOAM}$ $+$ K3 $\rightarrow$ K1.

• 5. K4 $+$ ${\mathsf {DC}}$ $\rightarrow$ K1.

• 6. K4* $+$ $\mathsf {CUT}$ $\rightarrow$ K1*. (We recall here that, by Tachtsis [21, Theorem 3.4], $\mathsf {DT}\nrightarrow {\mathsf {AC}}_{\mathsf {fin}}^{\aleph _{0}}$ in ${\mathsf {ZFA}}$, and thus $\mathsf {DT}\nrightarrow$ K4* $+$ $\mathsf {CUT}$ in ${\mathsf {ZFA}}$.)

• 7. K1 $\nrightarrow \mathsf {W}_{\aleph _{1}}\vee \mathsf {CUT}$ in ${\mathsf {ZFA}}$.

• 8. K1 $\nrightarrow \mathsf {WOAM}$ in ${\mathsf {ZFA}}$.

• 9. ${\mathsf {BPI}}$ $+$ K1 $\nrightarrow {\mathsf {DC}}$ in ${\mathsf {ZFA}}$.

• 10. ${\mathsf {LW}}+\mathsf {DF=F}+{\mathsf {AC}}_{\mathsf {fin}}^{\mathsf {WO}}+$ K1 $\nrightarrow {\mathsf {MC}}_{\aleph _{0}}^{\aleph _{0}}$ in ${\mathsf {ZFA}}$.

• 11. $\mathsf {CS}\nrightarrow$ K1 and K1 $\nrightarrow \mathsf {CS}$ in ${\mathsf {ZFA}}$, and thus K1 implies none of $\mathsf {LDF=F}$, ${\mathsf {LW}}$, and $\mathsf {CWF}$ in ${\mathsf {ZFA}}$.

6 Open questions

• 1. Does either of K2 and K4 imply K1?

• 2. Does ${\mathsf {BPI}}$ imply Ki for some $i=1,\ldots ,4$?

• 3. Does ${\mathsf {AC}}^{\mathsf {LO}}$ imply (in ${\mathsf {ZFA}}$) Ki for some $i=1,\ldots ,4$? (Recall that, in ${\mathsf {ZF}}$, ${\mathsf {AC}}^{\mathsf {LO}}$ is equivalent to ${\mathsf {AC}}$.)

• 4. Does $\mathsf {WOAM}$ imply Ki for some $i=1,\ldots ,4$?

• 5. Does $\mathsf {W}_{\aleph _{1}}$ imply Ki for some $i=1,2,4$?

• 6. Does ${\mathsf {MC}}+\mathsf {CAC}$ imply Ki for some $i=1,2,4$?

• 7. Is there a model of ${\mathsf {ZFA}}$ or of ${\mathsf {ZF}}$ in which K4* is true but K1* is false?

• 8. Does either of ${\mathsf {BPI}}+{\mathsf {DC}}$ and ${\mathsf {BPI}}+{\mathsf {AC}}^{\aleph _{0}}$ imply K1? (Where ${\mathsf {AC}}^{\aleph _{0}}$ is the Axiom of Countable Choice (Form 8 in [9]): Every denumerable family of non-empty sets has a choice function.)