# On Erdős–Dushnik–Miller theorem without AC

Amitayu Banerjee  Alfréd Rényi Institute of Mathematics, Reáltanoda utca
13-15, Budapest-1053, Hungary<EMAIL_ADDRESS>and  Alexa
Gopaulsingh  Department of Logic, Institute of Philosophy, Eötvös Loránd
University, Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

In $\mathsf{ZFA}$ (Zermelo-Fraenkel set theory with the Axiom of
Extensionality weakened to allow the existence of atoms), we prove that the
strength of the proposition $\mathsf{EDM}$ (“If $G=(V_{G},E_{G})$ is a graph
such that $V_{G}$ is uncountable, then for all coloring
$f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ either there is an uncountable set
monochromatic in color $0$, or there is a countably infinite set monochromatic
in color 1”) is strictly between $\mathsf{DC_{\aleph_{1}}}$ (where
$\mathsf{DC_{\aleph_{1}}}$ is Dependent Choices for $\aleph_{1}$, a weak
choice form stronger than Dependent Choices ($\mathsf{DC}$)) and Kurepa’s
principle (“Any partially ordered set such that all of its antichains are
finite and all of its chains are countable is countable”). Among other new
results, we study the relations of $\mathsf{EDM}$ with $\mathsf{BPI}$ (Boolean
Prime Ideal Theorem), $\mathsf{RT}$ (Ramsey’s Theorem), De Bruijn–Erdős
theorem for $n$-colorings, Kőnig’s Lemma and several other weak choice forms.
Moreover, we answer a part of a question raised by Lajos Soukup.

###### Key words and phrases:

Axiom of Choice, Infinite graphs, Erdős–Dushnik–Miller theorem, Ramsey’s
Theorem, Boolean Prime Ideal Theorem, Fraenkel-Mostowski models of
$\mathsf{ZFA}$

###### 2020 Mathematics Subject Classification:

03E25, 03E35, 05C63, 06A07.

##  1\. introduction

In 1941, Dushnik and Miller established the proposition “If $\kappa$ is an
uncountable cardinal, then for all coloring
$f:[\kappa]^{2}\rightarrow\\{0,1\\}$, either there is a set of cardinality
$\kappa$ monochromatic in color 0, or there is a countably infinite set
monochromatic in color 1” in $\mathsf{ZFC}$, and gave credit to Erdős for the
proof of the result for the case in which $\kappa$ is a singular cardinal—see
[7, Theorem 5.22 and footnote 6 on page 606]. The above result is uniformly
known as Erdős–Dushnik–Miller theorem. In $\mathsf{ZFC}$, the theorem applies
to prove the proposition “Every partially ordered set such that all of its
chains are finite and all of its antichains are countable is countable”
(abbreviated here as “$\mathsf{CAC^{\aleph_{0}}}$”) and Kurepa’s result on
partially ordered sets stated in the abstract (abbreviated here as
“$\mathsf{CAC_{1}^{\aleph_{0}}}$”). Kurepa [16] explicitly proved
$\mathsf{CAC_{1}^{\aleph_{0}}}$ in $\mathsf{ZFC}$ in response to Sierpiński’s
question [18, pages 190–191]. Banerjee [1] and Banerjee and Gyenis [3] studied
some relations of $\mathsf{CAC^{\aleph_{0}}}$ and
$\mathsf{CAC_{1}^{\aleph_{0}}}$ with weak forms of the Axiom of Choice
($\mathsf{AC}$). Recently, Tachtsis [19] investigated the deductive strength
of $\mathsf{CAC_{1}^{\aleph_{0}}}$ without $\mathsf{AC}$ in more detail. Among
various results, Tachtsis [19] proved that $\mathsf{CAC_{1}^{\aleph_{0}}}$
holds in $\mathsf{ZF+DC_{\aleph_{1}}}$111$\mathsf{ZF}$ denotes
Zermelo–Fraenkel set theory without $\mathsf{AC}$. Complete definitions of the
choice forms will be given in section 2. and $\mathsf{CAC_{1}^{\aleph_{0}}}$
holds in the Mostowski linearly ordered model (labeled as Model
$\mathcal{N}_{3}$ in [9]) as well as the basic Fraenkel model (labeled as
Model $\mathcal{N}_{1}$ in [9]). Inspired by the research work of [19], we
study the deductive strength of $\mathsf{EDM}$ without $\mathsf{AC}$. Let $X$
be a set. We note that without $\mathsf{AC}$, there are two definitions of
uncountable sets:

  1. (1)

$X$ is uncountable if $|X|\not\leq\aleph_{0}$ (i.e., there is no injection
from $X$ into $\aleph_{0}$).

  2. (2)

$X$ is uncountable if $\aleph_{0}<|X|$ (i.e., there is an injection from
$\aleph_{0}$ into $X$ and there is no injection from $X$ into $\aleph_{0}$).

We note that all the results in this paper are obtained with the first
definition of uncountable sets. Lajos Soukup asked the following question.

######  Question 1.1.

What is the relationship between $\mathsf{CAC_{1}^{\aleph_{0}}}$ and
$\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZF}$ and $\mathsf{ZFA}$?

Main result. Fix
$X\in\\{\mathsf{CAC_{1}^{\aleph_{0}}},\mathsf{CAC^{\aleph_{0}}}\\}$. The first
author proves that the strength of $\mathsf{EDM}$ is strictly between
$\mathsf{DC_{\aleph_{1}}}$ and $X$, and $\mathsf{CAC_{1}^{\aleph_{0}}}$ does
not imply $\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZFA}$ (cf. Theorems 4.1,
4.2, 4.4, Corollary 3.6).

Other results. The first author observes the following in $\mathsf{ZF}$:

  1. (1)

$\mathsf{CAC^{\aleph_{0}}}$ implies $\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}$
(Every countably infinite family of countably infinite sets has a choice
function). Thus $\mathsf{CAC^{\aleph_{0}}}$ is not provable in $\mathsf{ZF}$
(Proposition 3.4).

  2. (2)

$\mathsf{WOAM}$ (Every set is either well-orderable or has an amorphous
subset) implies $\mathsf{RT}$ for any locally countable connected graph
(Proposition 3.7).

  3. (3)

$\mathsf{EDM}$ is strictly stronger than $\mathsf{RT}$ (Theorem 4.1(3,4)).

  4. (4)

$\mathsf{WOAM}$ \+ $\mathsf{RT}$ implies $\mathsf{EDM}$ (Theorem 4.2(1)).

  5. (5)

$\mathsf{CAC^{\aleph_{0}}}+\mathsf{CAC_{1}^{\aleph_{0}}}$ \+
$\mathsf{A}$(Antichain Principle) does not imply $\mathsf{EDM}$ in
$\mathsf{ZFA}$ (Theorem 4.4).

###  1.1. The uniqueness of algebraic closures, and Łoś’s theorem

Pincus [9, Note 41] proved that the statement “If a field has an algebraic
closure, then it is unique up to isomorphism” [9, Form 233] does not imply
“there are no amorphous sets” in $\mathsf{ZFA}$. Recently, Tachtsis [21]
constructed a model of $\mathsf{ZFA}$+$\neg\mathsf{AC}$ to prove that
$\mathsf{AC^{LO}}$ (Every linearly ordered family of non-empty sets has a
choice function) does not imply $\mathsf{LT}$ (if $\mathcal{A}=\langle
A,\mathcal{R}^{\mathcal{A}}\rangle$ is a non-trivial relational
$\mathcal{L}$-structure over some language $\mathcal{L}$, and $\mathcal{U}$ be
an ultrafilter on a non-empty set $I$, then the ultrapower
$\mathcal{A}^{I}/\mathcal{U}$ and $\mathcal{A}$ are elementarily equivalent).

Other results. We observe the following:

  1. (1)

$\mathsf{AC^{LO}}$ \+ $\mathsf{EDM}$ \+ Form 233 does not imply $\mathsf{LT}$
in $\mathsf{ZFA}$ (Theorem 5.2).

###  1.2. Remarks

Blass [4] investigated the strength of $\mathsf{RT}$ in the hierarchy of
choice forms. In section 6, applying the above-mentioned results and mainly
inspired by the results of [4], we remark that $\mathsf{EDM}$ is independent
of each of $\mathsf{BPI}$, $\mathsf{KW}$ (Kinna-Wagner Selection Principle),
$\mathsf{AC_{WO}}$ (Axiom of Choice for non-empty, well-orderable sets),
“There are no amorphous sets”, $n$-coloring theorem (De Bruijn–Erdős theorem
for $n$-colorings), and $\mathsf{A}$ (Antichain Principle) in $\mathsf{ZFA}$.
Moreover, $\mathsf{LT}$ and $\mathsf{EDM}$ are mutually independent in
$\mathsf{ZF}$. In [19], Tachtsis proved that $\mathsf{CAC_{1}^{\aleph_{0}}}$
and $\mathsf{DT}$ (Dilworth’s theorem) are mutually independent in
$\mathsf{ZFA}$. A natural question which arises is about the relation of
$\mathsf{CAC^{\aleph_{0}}}$ and $\mathsf{EDM}$ with $\mathsf{DT}$. We also
remark that $\mathsf{DT}$ is independent of $\mathsf{EDM}$ and
$\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZFA}$.

##  2\. Basics and diagram of results

######  Definition 2.1.

Suppose $X$ and $Y$ are two sets. We write:

  1. (1)

$|X|\leq|Y|$ or $|Y|\geq|X|$, if there is an injection $f:X\rightarrow Y$.

  2. (2)

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

  3. (3)

$|X|<|Y|$ or $|Y|>|X|$, if $|X|\leq|Y|$ and $|X|\not=|Y|$.

  4. (4)

If $f:X\rightarrow Y$ is a function, then we denote “the range of $f$” by
$ran(f)$ and “the domain of $f$” by $dom(f)$.

######  Definition 2.2.

Let $(P,\leq)$ be a partially ordered set, or ‘poset’ in short. A subset
$D\subseteq P$ is a chain if $(D,\leq\restriction D)$ is linearly ordered. A
subset $A\subseteq P$ is an antichain if no two elements of $A$ are comparable
under $\leq$. The size of the largest antichain of $(P,\leq)$ is known as its
width. A subset $C\subseteq P$ is cofinal in $P$ if for every $x\in P$ there
is an element $c\in C$ such that $x\leq c$. A tree is a connected undirected
graph without circuits one of whose vertices is designated as the origin. We
note that a tree may also be defined as a poset $(P,<)$ with a least element
and with the property that for any element $x\in P$ the set of predecessors of
$x$ is a finite set that is linearly ordered by $<$. The number of vertices on
the unique path connecting a vertex $v$ with the origin is the level of $v$,
denoted by $l(v)$. A vertex $v^{\prime}$ is a successor of a vertex $v$ if $v$
and $v^{\prime}$ are connected by an edge and $l(v^{\prime})=l(v)+1$. A tree
is locally finite if each vertex has only finitely many successors. An
$\omega$-tree is a locally finite tree with at least one vertex in level $n$
for each $n\in\omega$ (cf. [9, Note 21]). An inﬁnite set $X$ is amorphous if
$X$ cannot be written as a disjoint union of two infinite subsets. A set $X$
is Dedekind-finite if $\aleph_{0}\not\leq|X|$. Otherwise, $X$ is Dedekind-
infinite. We say that a graph $G=(V_{G},E_{G})$ is locally countable if for
every $v\in V_{G}$, the set of neighbors of $v$ is countable. The graph $G$ is
connected if any two vertices are joined by a path of finite length.

######  Definition 2.3.

(A list of choice forms).

  1. (1)

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

  2. (2)

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

  3. (3)

The Kinna-Wagner Selection Principle, $\mathsf{KW}$ ([9, Form 15]): For every
set $M$ there is a function $f$ such that for all $A\in M$, if $|A|>1$ then
$\emptyset\neq f(A)\subsetneq A$.

  4. (4)

The Axiom of Multiple Choice, $\mathsf{MC}$ ([9, Form 67]): Every family
$\mathcal{A}$ of non-empty sets has a multiple choice function, i.e., there is
a function $f$ with domain $\mathcal{A}$ such that for every
$A\in\mathcal{A}$, $\emptyset\neq f(A)\in[A]^{<\omega}$.

  5. (5)

$\mathsf{MC}^{\aleph_{0}}_{\aleph_{0}}$ ([9, Form 350]): Every denumerable,
i.e. countably infinite, family of denumerable sets has a multiple choice
function.

  6. (6)

$\mathsf{AC_{WO}}$ ([9, Form 60]): Every set of non-empty, well-orderable sets
has a choice function.

  7. (7)

$\mathsf{AC^{LO}}$ [9, Form 202]: Every linearly ordered set of non-empty sets
has a choice function.

  8. (8)

$\mathsf{PAC^{\aleph_{1}}_{fin}}$ (cf. [1]): Every $\aleph_{1}$-sized family
$\mathcal{A}$ of non-empty finite sets has an $\aleph_{1}$-sized subfamily
$\mathcal{B}$ with a choice function.

  9. (9)

$\mathsf{AC_{\aleph_{0}}^{\aleph_{0}}}$ [9, Form 32A]: Every denumerable
family of denumerable sets has a choice function. We recall that
$\mathsf{AC_{\aleph_{0}}^{\aleph_{0}}}$ is equivalent to
$\mathsf{PAC_{\aleph_{0}}^{\aleph_{0}}}$ [9, Form 32B] (Every denumerable
family $\mathcal{A}$ of denumerable sets has an infinite subfamily
$\mathcal{B}$ with a choice function).

  10. (10)

$\mathsf{AC_{fin}^{\aleph_{0}}}$ [9, Form 10]: Every denumerable family of
non-empty finite sets has a choice function.

  11. (11)

$\mathsf{AC_{n}^{-}}$ for each $n\in\omega\backslash\\{0,1\\}$ [9, Form
342($n$)]: Every infinite family $\mathcal{A}$ of $n$-element sets has a
partial choice function, i.e., $\mathcal{A}$ has an infinite subfamily
$\mathcal{B}$ with a choice function.

  12. (12)

$\mathsf{WOAM}$ [9, Form 133]: Every set is either well-orderable or has an
amorphous subset.

  13. (13)

The Principle of Dependent Choice, $\mathsf{DC}$([9, Form 43]): If $S$ is a
relation on a non-empty set $A$ and $(\forall x\in A)(\exists y\in A)(xSy)$
then there is a sequence $(a_{n})_{n\in\omega}$ of elements of $A$ such that
$(\forall n\in\omega)(a_{n}Sa_{n+1})$.

  14. (14)

$\mathsf{DC_{\kappa}}$ where $\alpha$ is the ordinal such that
$\kappa=\aleph_{\alpha}$ [9, Form 87($\alpha$)]: Let $S$ be a non-empty set
and let $R$ be a binary relation such that for every $\beta<\kappa$ and every
$\beta$-sequence $s=(s_{\epsilon})_{\epsilon<\beta}$ of elements of $S$ there
exists $y\in S$ such that $sRy$. Then there is a function $f:\kappa\rightarrow
S$ such that for every $\beta<\kappa$, $(f\restriction\beta)Rf(\beta)$. We
note that $\mathsf{DC_{\aleph_{0}}}$ is a reformulation of $\mathsf{DC}$.

  15. (15)

$\mathsf{DF=F}$ [9, Form 9]: Every Dedekind-finite set is finite.

  16. (16)

$\mathsf{W_{\aleph_{\alpha}}}$ (cf. [13, Chapter 8]): For every $X$, either
$|X|\leq\aleph_{\alpha}$ or $|X|\geq\aleph_{\alpha}$.

  17. (17)

[9, Form 233]: If a field has an algebraic closure, then it is unique up to
isomorphism.

  18. (18)

$\mathsf{WUT}$ [9, Form 231]: The union of a well-orderable collection of
well-orderable sets is well-orderable.

  19. (19)

$\mathsf{AC^{WO}_{fin}}$ [9, Form 122]: Every well-ordered set of non-empty
finite sets has a choice function.

  20. (20)

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

  21. (21)

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

  22. (22)

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

  23. (23)

The Antichain Principle, $\mathsf{A}$: Every poset has a maximal antichain.

  24. (24)

The $n$-coloring theorem, $\mathcal{P}_{n}$: If all finite subgraphs of a
graph $G$ are $n$-colorable then $G$ is $n$-colorable.

  25. (25)

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

  26. (26)

Ramsey’s Theorem, $\mathsf{RT}$ [9, Form 17]: For every infinite set $A$ and
for every partition of the set $[A]^{2}$ into two sets $X$ and $Y$, there is
an infinite subset $B\subseteq A$ such that either $[B]^{2}\subseteq X$ or
$[B]^{2}\subseteq Y$.222Equivalently, for every infinite graph $G=(V,E)$ and
for all $c:[V]^{2}\rightarrow 2$, there exists an infinite set $Y\subseteq V$
such that $[Y]^{2}$ is $c$-monochromatic.

  27. (27)

The Chain/Antichain Principle, $\mathsf{CAC}$ [9, Form 217]: Every infinite
poset has an infinite chain or an infinite antichain.

  28. (28)

Łoś’s theorem, $\mathsf{LT}$ ([9, Form 253]): If $\mathcal{A}=\langle
A,\mathcal{R}^{\mathcal{A}}\rangle$ is a non-trivial relational
$\mathcal{L}$-structure over some language $\mathcal{L}$, and $\mathcal{U}$ be
an ultrafilter on a non-empty set $I$, then the ultrapower
$\mathcal{A}^{I}/\mathcal{U}$ and $\mathcal{A}$ are elementarily equivalent.

######  Definition 2.4.

(A list of combinatorial statements).

  1. (1)

$\mathsf{EDM}$: If $G=(V_{G},E_{G})$ is a graph such that $V_{G}$ is
uncountable, then for all coloring $f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ either
there is an uncountable set monochromatic in color $0$, or there is a
countably infinite set monochromatic in color 1.

  2. (2)

$\mathsf{EDM^{\prime}}$: $\mathsf{EDM}$ restricted to graphs based on a well-
ordered set of vertices.

  3. (3)

$\mathsf{CAC^{\aleph_{0}}}$: Every poset such that all of its chains are
finite and all of its antichains are countable is countable.

  4. (4)

$(\mathsf{CAC^{\aleph_{0}}})^{\prime}$: $\mathsf{CAC^{\aleph_{0}}}$ restricted
to posets based on a well-ordered set of elements.

  5. (5)

$\mathsf{CAC_{1}^{\aleph_{0}}}$: Every poset such that all of its antichains
are finite and all of its chains are countable is countable.

  6. (6)

$(\mathsf{CAC_{1}^{\aleph_{0}}})^{\prime}$: $\mathsf{CAC_{1}^{\aleph_{0}}}$
restricted to posets based on a well-ordered set of elements.

  7. (7)

$\mathsf{CACT^{\aleph_{0}}}$: $\mathsf{CAC^{\aleph_{0}}}$ restricted to
$\omega$-trees.

  8. (8)

$(\mathsf{CACT^{\aleph_{0}}})^{\prime}$: $\mathsf{CAC^{\aleph_{0}}}$
restricted to $\omega$-trees based on a well-ordered set of elements.

  9. (9)

$\mathsf{CACT_{1}^{\aleph_{0}}}$: $\mathsf{CAC_{1}^{\aleph_{0}}}$ restricted
to $\omega$-trees.

  10. (10)

$(\mathsf{CACT_{1}^{\aleph_{0}}})^{\prime}$: $\mathsf{CAC_{1}^{\aleph_{0}}}$
restricted to $\omega$-trees based on a well-ordered set of elements.

  11. (11)

For a set $A$, Sym$(A)$ and FSym$(A)$ denote the set of all permutations of
$A$ and the set of all $\phi\in$ Sym$(A)$ such that $\\{x\in A:\phi(x)\neq
x\\}$ is finite. For a set $A$ of size at least $\aleph_{\alpha}$,
$\aleph_{\alpha}$Sym$(A)$ denote the set of all $\phi\in$ Sym$(A)$ such that
$\\{x\in A:\phi(x)\neq x\\}$ has cardinality at most $\aleph_{\alpha}$ (cf.
[20, section 2]).

###  2.1. Permutation models and Mostowski’s intersection lemma.

We start with a model $M$ of $\mathsf{ZFA+AC}$ where $A$ is a set of atoms,
$\mathcal{G}$ is a group of permutations of $A$ and $\mathcal{F}$ is a normal
filter of subgroups of $\mathcal{G}$. The Fraenkel–Mostowski model, or the
permutation model $\mathcal{N}$ with respect to $M$, $\mathcal{G}$ and
$\mathcal{F}$ is defined by the equality:

$\mathcal{N}=\\{x\in M:(\forall
t\in\mathsf{TC}(\\{x\\}))(sym_{\mathcal{G}}(t)\in\mathcal{F})\\}$

where for a set $x\in M$, $sym_{\mathcal{G}}(x)=\\{g\in\mathcal{G}\mid
g(x)=x\\}$ and $\mathsf{TC}(x)$ is the transitive closure of $x$ in $M$. If
$\mathcal{I}\subseteq\mathcal{P}(A)$ is a normal ideal, then
$\\{$fix${}_{\mathcal{G}}(E):E\in\mathcal{I}\\}$ generates a normal filter
(say $\mathcal{F}_{\mathcal{I}}$) over $\mathcal{G}$, where
fix${}_{\mathcal{G}}(E)=\\{\phi\in\mathcal{G}:\forall y\in E(\phi(y)=y)\\}$.
Let $\mathcal{N}$ be the permutation model determined by $M$, $\mathcal{G}$,
and $\mathcal{F}_{\mathcal{I}}$. We recall that $\mathcal{N}$ is a model of
$\mathsf{ZFA}$ (cf. [13, Theorem 4.1, page 46]). We say $E\in\mathcal{I}$ is a
support of a set $\sigma\in\mathcal{N}$ if fix${}_{\mathcal{G}}(E)\subseteq
sym_{\mathcal{G}}(\sigma$). We recall some terminologies from [5, sections
1,2]. Let $\Delta(E)=\\{\sigma:$ fix${}_{\mathcal{G}}(E)\subseteq
sym_{\mathcal{G}}(\sigma$)$\\}$ if $E\in\mathcal{I}$. We say that
$\mathcal{N}$ satisfies Mostowski’s intersection lemma if $\Delta(E\cap
F)=\Delta(E)\cap\Delta(F)$ for every $E,F\in\mathcal{I}$. In this paper,

  * •

We follow the labeling of the models from [9]. $\mathcal{N}_{1}$ is the basic
Fraenkel model, $\mathcal{N}_{2}$ is the second Fraenkel model,
$\mathcal{N}_{3}$ is the Mostowski linearly ordered model, and
$\mathcal{N}_{41}$ is a variation of $\mathcal{N}_{3}$ (cf. [9]).

  * •

Fix any $n\in\omega\backslash\\{0,1\\}$. We denote by
$\mathcal{N}_{HT}^{1}(n)$ the permutation model constructed in [10, Theorem
8].

######  Lemma 2.5.

An element $x$ of $\mathcal{N}$ is well-orderable in $\mathcal{N}$ if and only
if fix${}_{\mathcal{G}}(x)\in\mathcal{F}_{\mathcal{I}}$ (cf. [13, Equation
(4.2), page 47]). Thus, an element $x$ of $\mathcal{N}$ with support $E$ is
well-orderable in $\mathcal{N}$ if fix${}_{\mathcal{G}}(E)\subseteq$
fix${}_{\mathcal{G}}(x)$.

We refer the reader to [9, Note 103, pages 283–286] for the definition of the
terms “injective cardinality $|x|_{-}$ of $x$”, “injectively boundable
statement” and “boundable statement”.

######  Theorem 2.6.

(Pincus’ Transfer Theorem; cf. [17, Theorem 3A3]) If $\Phi$ is a conjunction
of injectively boundable statements which hold in the Fraenkel–Mostowski model
$V_{0}$, then there is a $\mathsf{ZF}$ model $V\supset V_{0}$ with the same
ordinals and cofinalities as $V_{0}$, where $\Phi$ holds.

######  Lemma 2.7.

(Brunner; cf. [6, Lemma 4.1]) Let $A$ be a set of atoms, $\mathcal{G}$ be a
group of permutations of $A$ and the filter $\mathcal{F}$ of subgroups of
$\mathcal{G}$ is generated by
$\\{$fix${}_{\mathcal{G}}(E):E\in[A]^{<\omega}\\}$. Let $\mathcal{N}$ be the
Fraenkel-Mostowski model determined by $A$, $\mathcal{G}$, and $\mathcal{F}$.
If $\mathcal{N}$ satisfies Mostowski’s intersection lemma where $A$ is
Dedekind-finite, then every set $x$ in $\mathcal{N}$ is either well-orderable
or there exists an infinite subset of $A$, which embeds into $x$.

###  2.2. Diagram

We summarize the main results using the first definition of uncountable sets.
Fix any $2\leq n\in\omega$. In Figure 1, known results are depicted with
dashed arrows, new implications or non-implications in $\mathsf{ZF}$ are
mentioned with simple black arrows, new non-implications in $\mathsf{ZFA}$ are
mentioned with thick dotted black arrows.

$\mathsf{AC}$$\mathsf{AC_{n}}$$\mathsf{AC_{n}^{-}}$“There are no amorphous
sets”$\mathsf{DC_{\aleph_{1}}}$$\mathsf{DC}$$\mathsf{EDM}$$X$ if
$X\in\\{\mathsf{BPI},\mathsf{KW},\mathsf{AC_{WO}},\mathcal{P}_{2},\mathsf{DT},\mathsf{WOAM},$
“Antichain Principle $(\mathsf{A})$”, $\mathsf{CS}$,
$\mathsf{MC}\\}$$\mathsf{RT}$+$\mathsf{WOAM}$$\mathsf{CAC}$+$\mathsf{WOAM}$$\mathsf{RT}$$\mathsf{CAC}$$\mathsf{AC_{fin}^{\aleph_{0}}}\sim$
“Kőnig’s
Lemma”$\mathsf{CACT_{1}^{\aleph_{0}}}$$\mathsf{CACT^{\aleph_{0}}}$$\mathsf{AC_{fin}^{\aleph_{0}}}$$\mathsf{CAC^{\aleph_{0}}}$$\mathsf{CAC_{1}^{\aleph_{0}}}$$\mathsf{AC_{\aleph_{0}}^{\aleph_{0}}}$$\mathsf{PAC_{fin}^{\aleph_{1}}}$

Figure 1. In the above figure, we denote “equivalent to” by $\sim$. We note
that $(\forall n\geq 3)$ $\mathcal{P}_{n}\sim\mathsf{BPI}$.

##  3\. Known and basic results

###  3.1. Known results

######  Fact 3.1.

($\mathsf{ZF}$) The following hold:

  1. (1)

$\mathsf{RT}$ holds for every infinite well-orderable set and if $\mathsf{RT}$
holds for an infinite set $Y$, then $\mathsf{RT}$ holds for any set
$X\supseteq Y$ [25, Theorem 1.7] and $\mathsf{DF=F}$ implies $\mathsf{RT}$
[9].

  2. (2)

$\mathsf{WOAM}$ implies $\mathsf{CUT}$ [15, Proposition 8(i)]. So,
$\mathsf{WOAM}$ implies “$\aleph_{1}$ is regular”.

  3. (3)

$\mathsf{CAC_{1}^{\aleph_{0}}}$ implies $\mathsf{CAC}$ [19, Theorem 4(11)] and
$\mathsf{CAC}$ implies $\mathsf{AC_{fin}^{\aleph_{0}}}$ [21, Lemma 4.4].

  4. (4)

$\mathsf{WOAM}+\mathsf{CAC}$ implies $\mathsf{CAC^{\aleph_{0}}_{1}}$ [19,
Theorem 8(1)].

  5. (5)

$\mathsf{CAC^{\aleph_{0}}_{1}}$ implies $\mathsf{PAC^{\aleph_{1}}_{fin}}$ and
$\mathsf{DC}$ does not imply $\mathsf{CAC^{\aleph_{0}}_{1}}$ [1, Theorem 4.5,
Corollary 4.6].

We recall the following result communicated to us by Tachtsis from [1].

######  Fact 3.2.

(cf. [1, Lemma 4.1, Corollary 4.2]) $(\mathsf{CAC_{1}^{\aleph_{0}}})^{\prime}$
holds in any permutation model.

###  3.2. Basic propositions

######  Proposition 3.3.

The following hold:

  1. (1)

“$\aleph_{1}$ is regular” implies $\mathsf{EDM^{\prime}}$ in $\mathsf{ZF}$.

  2. (2)

“$\aleph_{1}$ is regular” implies $(\mathsf{CAC^{\aleph_{0}}})^{\prime}$,
$(\mathsf{CACT_{1}^{\aleph_{0}}})^{\prime}$ as well as
$(\mathsf{CACT^{\aleph_{0}}})^{\prime}$ in $\mathsf{ZF}$.

  3. (3)

“$\aleph_{1}$ is regular”$+$ $\mathsf{AC_{fin}^{\aleph_{0}}}$ implies
$\mathsf{CACT_{1}^{\aleph_{0}}}$ and $\mathsf{CACT^{\aleph_{0}}}$ in
$\mathsf{ZF}$.

  4. (4)

$X$ holds in any permutation model if
$X\in\\{\mathsf{EDM^{\prime}},(\mathsf{CAC^{\aleph_{0}}})^{\prime},(\mathsf{CACT_{1}^{\aleph_{0}}})^{\prime},(\mathsf{CACT^{\aleph_{0}}})^{\prime}\\}$.

  5. (5)

$\mathsf{AC_{fin}^{\aleph_{0}}}$ implies $\mathsf{CACT_{1}^{\aleph_{0}}}$ and
$\mathsf{CACT^{\aleph_{0}}}$ in $\mathsf{ZF}$.

###### Proof.

(1). We modify the arguments due to Tachtsis from [1, Lemma 4.1]. Let
$G=(V_{G},E_{G})$ be a graph based on a well-ordered set of vertices. Fix a
well-ordering $\preceq$ of $V_{G}$. Let $f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ be
a coloring such that all sets monochromatic in color $0$ are countable and all
sets monochromatic in color $1$ are finite. By way of contradiction, assume
that $V_{G}$ is uncountable. We construct an infinite set monochromatic in
color $1$ in $G$ to obtain a contradiction. Since $V_{G}$ is well-ordered by
$\preceq$, we can construct (via transfinite induction) a maximal set
monochromatic in color $0$, $C_{0}$ say, without invoking any form of choice.
Since $C_{0}$ is countable, it follows that $V_{G}-C_{0}$ is uncountable and
for every vertex $v\in V_{G}-C_{0}$, there is $c\in C_{0}$ such that
$f(\\{v,c\\})=1$. We write $V_{G}-C_{0}=\bigcup\\{W_{p}:p\in C_{0}\\}$, where
$W_{p}=\\{v\in V_{G}-C_{0}:f(\\{v,p\\})=1\\}$. Since $V_{G}-C_{0}$ is
uncountable and $C_{0}$ is countable, it follows by “$\aleph_{1}$ is regular”
that $W_{p}$ is uncountable for some $p$ in $C_{0}$. Let $p_{0}$ be the least
(with respect to $\preceq$) such vertex of $C_{0}$. Next, we construct a
maximal set monochromatic in color $0$ in (the uncountable set) $W_{p_{0}}$,
$C_{1}$ say, and let (similarly to the above argument) $p_{1}$ be the least
(with respect to $\preceq$) vertex of $C_{1}$ such that the set
$W_{p_{1}}=\\{v\in W_{p_{0}}-C_{1}:f(\\{v,p_{1}\\})=1\\}$ is uncountable.
Continuing this process step by step and noting that the process cannot stop
at a finite stage, we obtain a countably infinite set of vertices
$\\{p_{n}:n\in\omega\\}$ monochromatic in color $1$, contradicting the
assumption that all sets monochromatic in color 1 are finite. Therefore,
$V_{G}$ is countable.

(2–5). Follows from (1) and the fact that the statement “$\aleph_{1}$ is a
regular cardinal” holds in every permutation model (cf. [8, Corollary 1]) and
$\mathsf{AC_{fin}^{\aleph_{0}}}$ is equivalent to “Every $\omega$-tree is
countable” in $\mathsf{ZF}$. ∎

######  Proposition 3.4.

($\mathsf{ZF}$) $\mathsf{CAC^{\aleph_{0}}}$ implies
$\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}$.

###### Proof.

Since $\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}$ is equivalent to its partial
version $\mathsf{PAC^{\aleph_{0}}_{\aleph_{0}}}$ (cf. Definition 2.3), it
suffices to show $\mathsf{PAC^{\aleph_{0}}_{\aleph_{0}}}$. Let
$\mathcal{A}=\\{A_{i}:i\in\omega\\}$ be a denumerable family of non-empty,
denumerable sets. Without loss of generality, assume that $\mathcal{A}$ is
disjoint. For the sake of contradiction, we assume that $\mathcal{A}$ has no
partial choice function. Deﬁne a binary relation $\leq$ on
$A=\bigcup\mathcal{A}$ as follows: for all $a,b\in A$, let $a\leq b$ if and
only if $a=b$ or $a\in A_{n}$, $b\in A_{m}$ and $n<m$. Clearly, $\leq$ is a
partial order on $A$. Since any two elements of $A$ are $\leq$-comparable if
and only if they belong to distinct $A_{i}$’s, and $\mathcal{A}$ has no
partial choice function, all chains in $(A,\leq)$ are finite. Next, if
$C\subset A$ is an antichain in $(A,\leq)$, then $C\subseteq A_{i}$ for some
$i\in\omega$. Thus, all antichains in $(A,\leq)$ are countable as $A_{i}$ is
denumerable for all $i\in\omega$. By $\mathsf{CAC^{\aleph_{0}}}$, $A$ is
countable (and hence well-orderable), contradicting $\mathcal{A}$’s having no
partial choice function. ∎

######  Proposition 3.5.

Let $A$ be a set of atoms. Let $\mathcal{G}$ be the group of permutations of A
such that either each $\eta\in\mathcal{G}$ moves only finitely many atoms or
there exists an $n\in\omega\backslash\\{0,1\\}$, such that for all
$\eta\in\mathcal{G}$, $\eta^{n}=1_{A}$. Let $\mathcal{N}$ be the permutation
model determined by $A$, $\mathcal{G}$, and a normal filter $\mathcal{F}$ of
subgroups of $\mathcal{G}$. Then the following hold:

  1. (1)

The Antichain Principle $\mathsf{A}$ holds in $\mathcal{N}$.

  2. (2)

If $\mathsf{WUT}$ holds in $\mathcal{N}$, then both
$\mathsf{CAC^{\aleph_{0}}}$ and $\mathsf{CAC_{1}^{\aleph_{0}}}$ hold in
$\mathcal{N}$.

  3. (3)

If $\mathsf{AC^{WO}_{fin}}$ holds and $\mathsf{AC_{\aleph_{0}}^{\aleph_{0}}}$
fails in $\mathcal{N}$, then $\mathsf{CAC_{1}^{\aleph_{0}}}$ holds and
$\mathsf{CAC^{\aleph_{0}}}$ fails in $\mathcal{N}$.

###### Proof.

Let $(P,\leq)$ be a poset in $\mathcal{N}$. Then the subgroup
$H=sym_{\mathcal{G}}((P,\leq))$ is an element of $\mathcal{F}$. Following the
proof of [19, Theorem 3], $Orb_{H}(p)=\\{\phi(p):\phi\in H\\}$ is an antichain
in $P$ for each $p\in P$ and $\mathcal{O}=\\{Orb_{H}(p):p\in P\\}$ is a well-
ordered partition of $P$.

(1). In $\mathcal{N}$, $\mathsf{CS}$ and $\mathsf{CWF}$ hold following the
methods of [11, Theorem 3.26] and [24, proof of Theorem 10 (ii)]. In [12], it
has been established that $\mathsf{CWF}$ is equivalent to $\mathsf{A}$ in
$\mathsf{ZFA}$. Thus $\mathsf{A}$ holds in $\mathcal{N}$.

We can observe a different argument to show that $\mathsf{A}$ holds in
$\mathcal{N}$ following the proof of [13, Theorem 9.2(2)] and the fact that
$Orb_{H}(p)$ is an antichain in $P$ for each $p\in P$.

(2). We show $\mathsf{CAC^{\aleph_{0}}}$ holds in $\mathcal{N}$. Let
$(P,\leq)$ be a poset in $\mathcal{N}$ such that all chains in $P$ are finite
and all antichains in $P$ are countable (and hence well-orderable). Now, $P$
can be written as a well-orderable disjoint union of antichains. Thus, $P$ is
well-orderable in $\mathcal{N}$ since $\mathsf{WUT}$ holds in $\mathcal{N}$.
So, we are done by Proposition 3.3(4). Similarly,
$\mathsf{CAC_{1}^{\aleph_{0}}}$ holds in $\mathcal{N}$ by Fact 3.2.

(3). Follows from Proposition 3.4 and the arguments of (2). ∎

######  Corollary 3.6.

$\mathsf{CS}+\mathsf{A}+\mathsf{DF=F}+\mathsf{AC^{WO}_{fin}}+\mathsf{CAC_{1}^{\aleph_{0}}}+\mathsf{DT}$
does not imply $\mathsf{MC_{\aleph_{0}}^{\aleph_{0}}}$ in $\mathsf{ZFA}$.
Consequently, $\mathsf{CAC_{1}^{\aleph_{0}}}$ does not imply
$\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZFA}$.

###### Proof.

Consider the permutation model (say $\mathcal{M}$) from [19, proof of Theorem
5(4)]. In order to describe $\mathcal{M}$, we start with a model $M$ of
$\mathsf{ZFA+AC}$ with a countably infinite set $A$ of atoms, which is written
as a disjoint union $\bigcup\\{B_{n}:n\in\omega\\}$, where
$|B_{n}|=\aleph_{0}$ for all $n\in\omega$. For each $n\in\omega$, let
$\mathcal{G}_{n}$ be the group of all even permutations of $B_{n}$ which move
only finitely many elements of $B_{n}$. Let $\mathcal{G}$ be the weak direct
product of the $\mathcal{G}_{n}$’s for $n\in\omega$. Consequently, every
permutation of $A$ in $\mathcal{G}$ moves only finitely many atoms. Let
$\mathcal{I}$ be the normal ideal of subsets of $A$ generated by all finite
unions of $B_{n}$. Let $\mathcal{F}$ be the normal filter on $\mathcal{G}$
generated by $\\{$fix${}_{\mathcal{G}}(E)$, $E\in\mathcal{I}\\}$ and
$\mathcal{M}$ be the permutation model determined by $M$, $\mathcal{G}$, and
$\mathcal{F}$. In $\mathcal{M}$, $\mathsf{AC^{WO}_{fin}}$, $\mathsf{DF=F}$,
and $\mathsf{CAC_{1}^{\aleph_{0}}}$ hold whereas
$\mathsf{MC_{\aleph_{0}}^{\aleph_{0}}}$ fails, and thus
$\mathsf{AC_{\aleph_{0}}^{\aleph_{0}}}$ fails (cf. [19, proof of Theorem
5(4)]). Since $\mathsf{AC^{WO}_{fin}}$ holds in $\mathcal{N}$, and $\\{a\in
A:g(a)\not=a\\}$ is finite for any $g\in\mathcal{G}$, $\mathsf{DT}$ holds in
$\mathcal{N}$ following the arguments of [23, Theorem 3.4] where Tachtsis
proved that $\mathsf{DT}$ holds in Lévy’s permutation model (labeled as Model
$\mathcal{N}_{6}$ in [9]). The rest follows from Proposition 3.5 and the fact
that if $g\in\mathcal{G}$, then $\\{a\in A:g(a)\not=a\\}$ is finite. ∎

######  Proposition 3.7.

($\mathsf{ZF}+\mathsf{WOAM}$) $\mathsf{RT}$ holds for any locally countable
connected graph $H=(V_{H},E_{H})$.

###### Proof.

If $V_{H}$ is well-orderable, the conclusion follows from Fact 3.1(1).
Otherwise, by $\mathsf{WOAM}$, there exists an amorphous subset
$V_{G}\subseteq V_{H}$. Fix some $r\in V_{G}$. Let $V_{0}=\\{r\\}$. For each
$n\in\omega\backslash\\{0\\}$, define $V_{n}=\\{v\in V_{G}:d_{G}(r,v)=n\\}$
where “$d_{G}(r,v)=n$” means there are $n$ edges in the shortest path joining
$r$ and $v$. By connectedness of $G$, $V_{G}=\bigcup_{n\in\omega}V_{n}$. Since
$V_{G}$ is amorphous, there is at most one $t\in\omega\backslash\\{0\\}$, such
that $V_{t}$ is infinite. As $V_{G}$ is amorphous, the power set
$\mathcal{P}(V_{G})$ of $V_{G}$ is Dedekind-finite, and thus, for some
$n_{0}\in\omega\backslash\\{0\\}$, $V_{n}=\emptyset$ for all $n\geq n_{0}$. As
$V_{G}$ is amorphous (and thus also infinite) and
$V_{G}=\bigcup_{n\in\omega}V_{n}$ is a disjoint union, there exists exactly
one $t<n_{0}$ such that $V_{t}$ is infinite. Then $V_{t}$ is countably
infinite since $|V_{t-1}|<\omega$, $G$ is locally countable, and the union of
a finite family of countable sets is countable in $\mathsf{ZF}$. As $V_{t}$ is
a countably infinite subset of the amorphous set $V_{G}$, which is impossible
(since $V_{G}$ is Dedekind-finite, being amorphous), we arrive at a
contradiction. ∎

##  4\. Erdős–Dushnik–Miller theorem and its variants

######  Theorem 4.1.

$(\mathsf{ZF}$) The following hold:

  1. (1)

$\mathsf{DC_{\aleph_{1}}}$ implies $\mathsf{EDM}$. In particular,
$\mathsf{W_{\aleph_{1}}}$ + $``\aleph_{1}$ is regular” implies $\mathsf{EDM}$.

  2. (2)

If
$X\in\\{\mathsf{CAC_{1}^{\aleph_{0}}},\mathsf{CAC^{\aleph_{0}}},\mathsf{PAC^{\aleph_{1}}_{fin}},\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}},\mathsf{CAC},\mathsf{AC_{fin}^{\aleph_{0}}}\\}$
then $\mathsf{EDM}$ implies $X$. So, $\mathsf{DC}$ does not imply
$\mathsf{EDM}$.

  3. (3)

$\mathsf{EDM}$ implies $\mathsf{RT}$.

  4. (4)

$\mathsf{DF=F}$ does not imply $\mathsf{CAC^{\aleph_{0}}}$. Consequently,
$\mathsf{RT}$ does not imply $\mathsf{CAC^{\aleph_{0}}}$ and $\mathsf{EDM}$.

###### Proof.

(1). Following Proposition 3.3 and the arguments of [19, Theorem 9(1,2)], we
can see that $\mathsf{DC_{\aleph_{1}}}$ implies $\mathsf{EDM}$ in
$\mathsf{ZF}$. In particular, let $G=(V_{G},E_{G})$ be a graph and
$f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ be a coloring such that all sets
monochromatic in color $0$ are countable and all sets monochromatic in color
$1$ are finite. By $\mathsf{W_{\aleph_{1}}}$, $\aleph_{1}\leq|V_{G}|$ or
$|V_{G}|\leq\aleph_{1}$. For the second case, $V_{G}$ is well-orderable, and
we are done by Proposition 3.3 since $\mathsf{DC_{\aleph_{1}}}$ implies
$\mathsf{W_{\aleph_{1}}}$ \+ “$\aleph_{1}$ is regular”. Otherwise, $V_{G}$ has
a subset $H$ with cardinality $\aleph_{1}$. Since $H$ is well-orderable, it is
countable by the arguments of Proposition 3.3; a contradiction.

(2). We prove $\mathsf{EDM}$ implies $\mathsf{CAC^{\aleph_{0}}}$. Let
$(P,\leq)$ be a poset satisfying the hypotheses of
$\mathsf{CAC^{\aleph_{0}}}$. Assume that $P$ is uncountable. Let
$G=(V_{G},E_{G})$ be a complete graph such that $V_{G}=P$ and
$f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ be a coloring such that $f\\{x,y\\}=1$ if
$x\leq y$ or $y\leq x$, and $f\\{x,y\\}=0$ otherwise. By $\mathsf{EDM}$,
either there is an uncountable set monochromatic in color $0$ (which is an
antichain in $(P,\leq)$) or there is a countably infinite set monochromatic in
color $1$ (which is a chain in $(P,\leq)$), a contradiction. Similarly, we can
prove $\mathsf{EDM}$ implies $\mathsf{CAC_{1}^{\aleph_{0}}}$. The rest follows
from Proposition 3.4 and Fact 3.1.

(3). Let $A$ be an infinite set such that $\mathsf{RT}$ fails for $A$. Let
$\\{X,Y\\}$ be a partition of $[A]^{2}$ such that there are no infinite
subsets $B$ of $A$ for which either $[B]^{2}\subseteq X$ or $[B]^{2}\subseteq
Y$. Let $G=(V_{G},E_{G})$ be a complete graph such that $V_{G}=A$ and
$f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ be a coloring such that $f\\{x,y\\}=1$ if
$\\{x,y\\}\in X$ and $f\\{x,y\\}=0$ if $\\{x,y\\}\in Y$. By assumption, all
sets monochromatic in color $i$ are finite for each $i\in\\{0,1\\}$. By
$\mathsf{EDM}$, $|V_{G}|\leq\aleph_{0}$ (since we are using the first
definition of uncountable sets), and thus $V_{G}=A$ is well-orderable. The
contradiction follows from the fact that $\mathsf{RT}$ holds for $A$ in
$\mathsf{ZF}$ (cf. Fact 3.1).

(4). Consider the model $\mathcal{N}_{41}$ from [9]. We start with a model $M$
of $\mathsf{ZFA+AC}$ where $A=\bigcup\\{B_{n}:n\in\omega\\}$ is a disjoint
union, where each $B_{n}$ is countably infinite and for each $n\in\omega$,
$(B_{n},\leq_{n})\cong(\mathbb{Q},\leq)$ (i.e., ordered like the rationals by
$\leq_{n}$). Let $\mathcal{G}$ be the group of all permutations on $A$ such
that for all $n\in\omega$, and all $\phi\in\mathcal{G}$, $\phi$ is an order
automorphism of $(B_{n},\leq_{n})$. Let $\mathcal{I}$ be the normal ideal of
subsets of $A$ which is generated by finite unions of $B_{n}$’s and
$\mathcal{F}$ be the normal filter on $\mathcal{G}$ generated by
$\\{$fix${}_{\mathcal{G}}(E)$, $E\in\mathcal{I}\\}$. Let $\mathcal{N}_{41}$ be
the Fraenkel–Mostowski model determined by $M$, $\mathcal{G}$, and
$\mathcal{F}$.

In $\mathcal{N}_{41}$, $\mathsf{DF=F}$ holds and
$\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}$ fails (cf. [22, Theorem 4], [9, Note
112]). Pincus [17] showed that $\mathsf{DF=F}$ is equivalent to

$\forall x(|x|_{-}\leq\omega\rightarrow$
$(\mathsf{Df}(x)\rightarrow\psi(x)$)),

where $\mathsf{Df}(x)\leftrightarrow\neg(\exists y)(y\subseteq
x\land|y|=\omega)$ and $\psi(x)=$“$x$ is finite” (we note that $\psi(x)$ is a
boundable formula). Thus, $\mathsf{DF=F}$ is injectively boundable.
Furthermore, $\neg\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}$ is boundable, and
hence injectively boundable. Since $\phi$ = “$\mathsf{DF=F}$ $\land$
$\neg\mathsf{AC^{\aleph_{0}}_{\aleph_{0}}}"$ is a conjunction of injectively
boundable statements, which has a $\mathsf{ZFA}$ model, it follows from
Theorem 2.6 that $\phi$ has a $\mathsf{ZF}$ model. By Proposition 3.4, we can
see that $\mathsf{DF=F}$ (and thus $\mathsf{RT}$) does not imply
$\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZF}$. ∎

######  Theorem 4.2.

The following hold:

  1. (1)

$\mathsf{WOAM+RT}$ implies $\mathsf{EDM}$ and $\mathsf{WOAM+CAC}$ implies
$\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZF}$. In particular, $\mathsf{EDM}$
does not imply “There are no amorphous sets” in $\mathsf{ZFA}$.

  2. (2)

Let $A$ be a set of atoms, $\mathcal{G}$ be any group of permutations of $A$,
and the filter $\mathcal{F}$ of subgroups of $\mathcal{G}$ is generated by
$\\{$fix${}_{\mathcal{G}}(E):E\in[A]^{<\omega}\\}$. Let $\mathcal{N}$ be the
permutation model determined by $A$, $\mathcal{G}$, and $\mathcal{F}$. If
$\mathcal{N}$ satisfies Mostowski’s intersection lemma where $A$ is Dedekind-
finite, and $\mathsf{RT}$ holds in $\mathcal{N}$, then $\mathsf{EDM}$ holds in
$\mathcal{N}$.

  3. (3)

$\mathsf{EDM}$ holds in $\mathcal{N}_{3}$. Consequently, $\mathsf{EDM}$
implies none of $\mathsf{WOAM}$, $\mathsf{CS}$, and $\mathsf{A}$(Antichain
Principle) in $\mathsf{ZFA}$.

###### Proof.

(1). Assume that $\mathsf{WOAM}$ \+ $\mathsf{RT}$ is true. Let
$G=(V_{G},E_{G})$ be a graph and $f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ be a
coloring such that all sets monochromatic in color $0$ are countable, and all
sets monochromatic in color $1$ are finite. If $V_{G}$ is well-orderable then
we are done by Proposition 3.3 and the fact that $\mathsf{WOAM}$ implies
‘$\aleph_{1}$ is regular’ in $\mathsf{ZF}$ (cf. Fact 3.1(2)). Assume $V_{G}$
is not well-orderable. By $\mathsf{WOAM}$, $V_{G}$ has an amorphous subset,
say $A$. Define the following partition of $[A]^{2}$:

$X=\\{\\{a,b\\}\in[A]^{2}:f\\{a,b\\}=0\\}$,
$Y=\\{\\{a,b\\}\in[A]^{2}:f\\{a,b\\}=1\\}$.

Since $(A,E_{G}\restriction A)$ is an infinite graph where all sets
monochromatic in color $1$ are finite, there is no infinite subset
$B^{\prime}\subseteq A$ such that $[B^{\prime}]^{2}\subseteq Y$. By
$\mathsf{RT}$, there is an infinite subset $B\subseteq A$ such that
$[B]^{2}\subseteq X$. So $(A,E_{G}\restriction A)$ has an infinite set
monochromatic in color $0$, say $C$. By assumption, $C$ is a countably
infinite subset of $A$. This contradicts the fact that $A$ is amorphous.

Similarly, $\mathsf{WOAM+CAC}$ implies $\mathsf{CAC^{\aleph_{0}}}$ in
$\mathsf{ZF}$ following Proposition 3.3. The rest follows from the fact that
$\mathsf{WOAM+RT}$ \+ “There exists an amorphous set” is true in the basic
Fraenkel model $\mathcal{N}_{1}$ (cf. [4, 9]).

(2). In $\mathcal{N}$, assume $G=(V_{G},E_{G})$ and
$f:[V_{G}]^{2}\rightarrow\\{0,1\\}$ as in the proof of (1). If $V_{G}$ is
well-orderable then we are done by Proposition 3.3. Otherwise, by Lemma 2.7,
there exists a bijection from an infinite subset $A^{\prime}$ of $A$ onto some
$H\subset V_{G}$ under the given assumptions. Define the following partition
of $[H]^{2}$ as in the proof of (1):
$X=\\{\\{a,b\\}\in[H]^{2}:f\\{a,b\\}=0\\}$,
$Y=\\{\\{a,b\\}\in[H]^{2}:f\\{a,b\\}=1\\}$. By $\mathsf{RT}$ and following the
arguments of (1), there is a countably infinite subset $C$ of $H$. Thus
$A^{\prime}$ is Dedekind-infinite in $\mathcal{N}$ since $|H|=|A^{\prime}|$.
Consequently, the set $A$ of atoms is Dedekind-infinite in $\mathcal{N}$,
which contradicts the fact that $A$ is a Dedekind-finite set in $\mathcal{N}$.

(3). We recall the definition of $\mathcal{N}_{3}$ from [9]. We start with a
model $M$ of $\mathsf{ZFA+AC}$ with a countably infinite set $A$ of atoms
using an ordering $\leq$ on $A$ chosen so that $(A,\leq)$ is order-isomorphic
to the set $\mathbb{Q}$ of the rational numbers with the usual ordering. Let
$\mathcal{G}$ be the group of all order automorphisms of $(A,\leq)$ and
$\mathcal{F}$ be the normal filter on $\mathcal{G}$ generated by the subgroups
$\\{\text{fix}_{\mathcal{G}}(E),E\in[A]^{<\omega}\\}$. Let $\mathcal{N}_{3}$
be the Fraenkel–Mostowski model determined by $M$, $\mathcal{G}$, and
$\mathcal{F}$. The rest follows from (2), and the following known facts about
$\mathcal{N}_{3}$:

  1. (i)

$\mathcal{N}_{3}$ satisfies Mostowski’s intersection lemma (cf. [13]).

  2. (ii)

$\mathsf{RT}$ is true in $\mathcal{N}_{3}$ (cf. [25, Theorem 2.4]).

  3. (iii)

The set of atoms $A$ is a Dedekind-finite set in $\mathcal{N}_{3}$.

  4. (iv)

$\mathsf{WOAM}$ fails in $\mathcal{N}_{3}$ (cf. [9]).

  5. (v)

$\mathsf{CS}$ and $\mathsf{LW}$ (Every linearly ordered set can be well
ordered) fail in $\mathcal{N}_{3}$ [19, Theorem 7] and $\mathsf{A}$ implies
$\mathsf{LW}$ in $\mathsf{ZFA}$ [13, Theorem 9.1].

∎

######  Proposition 4.3.

($\mathsf{ZF}$) The statements $\mathsf{EDM^{n}}$ (“If $G=(V_{G},E_{G})$ is a
graph such that $V_{G}$ is uncountable, then for all coloring
$f:[V_{G}]^{2}\rightarrow n$ either there is an uncountable set
$X_{1}\subseteq V_{G}$ monochromatic in color $i_{1}$ or there is a countably
infinite set $X_{2}\subseteq V_{G}$ monochromatic in color $i_{2}$ for some
$i_{1},i_{2}\in n$ such that $i_{1}\neq i_{2}$”) are equivalent for all
integers $n\geq 2$. Moreover, $\mathsf{EDM^{n}}$ implies $\mathsf{RT}$ for all
$n\in\omega\backslash\\{0,1\\}$.

###### Proof.

Since any $f:[V_{G}]^{2}\rightarrow n$ maps $[V_{G}]^{2}$ to $m$ if $m>n\geq
2$, $\mathsf{EDM^{m}}$ implies $\mathsf{EDM^{n}}$ under these circumstances.
We prove that $\mathsf{EDM^{n}}$ implies $\mathsf{EDM^{n+1}}$ for $n\geq 2$.
The rest follows by mathematical induction. Let $f:[V_{G}]^{2}\rightarrow n+1$
be a coloring where $V_{G}$ is uncountable. Let $f_{1}:[V_{G}]^{2}\rightarrow
n$ be given by $f_{1}(A)=min(f(A),n-1)$. By $\mathsf{EDM^{n}}$, either there
is an uncountable set $X_{1}\subseteq V_{G}$ that is $f_{1}$-monochromatic in
color $i_{1}$, or there is a countably infinite set $X_{2}\subseteq V_{G}$
that is $f_{1}$-monochromatic in color $i_{2}$ for some $i_{1},i_{2}\in n$
such that $i_{1}\neq i_{2}$. Fix $k\in\\{1,2\\}$. If $i_{k}\leq n-2$, then
$f[X_{k}]^{2}=i_{k}\in n+1$.

Case (i): Let $i_{1}=n-1$, then $f(A)\in\\{n,n-1\\}$ for all
$A\in[X_{1}]^{2}$. Define $f_{2}:[X_{1}]^{2}\rightarrow 2$ by
$f_{2}(A)=n-f(A)$. By $\mathsf{EDM^{2}}$ (which follows from
$\mathsf{EDM^{n}}$), either there is an uncountable set $Y_{1}\subseteq X_{1}$
that is $f_{2}$-monochromatic in color $j$, or there is a countably infinite
set $Y_{2}\subseteq X_{1}$ that is $f_{2}$-monochromatic in color $1-j$ where
$j\in\\{0,1\\}$. Thus either $f[Y_{1}]^{2}=n-j\in n+1$ or
$f[Y_{2}]^{2}=n-1+j\in n+1$.

Case (ii): Let $i_{2}=n-1$, then $f(A)\in\\{n,n-1\\}$ for all
$A\in[X_{2}]^{2}$. Define the following partition of $[X_{2}]^{2}$:

$X=\\{\\{a,b\\}\in[X_{2}]^{2}:f\\{a,b\\}=n\\}$,
$Y=\\{\\{a,b\\}\in[X_{2}]^{2}:f\\{a,b\\}=n-1\\}$.

By $\mathsf{RT}$ (which follows from $\mathsf{EDM^{2}}$, see the arguments of
Theorem 4.1(3)), there is a countably infinite subset $B\subseteq X_{2}$ such
that either $[B]^{2}\subseteq X$ or $[B]^{2}\subseteq Y$. Thus either
$f[B]^{2}=n\in n+1$ or $f[B]^{2}=n-1\in n+1$.

This completes the proof of the first assertion. Following Theorem 4.1(3),
$\mathsf{EDM^{2}}$ implies $\mathsf{RT}$. Thus, $\mathsf{EDM^{n}}$ implies
$\mathsf{RT}$ for all $n\in\omega\backslash\\{0,1\\}$. ∎

######  Theorem 4.4.

Fix any $n\in\omega\backslash\\{0,1\\}$ and
$X\in\\{\mathsf{CAC^{\aleph_{0}}},\mathsf{CAC_{1}^{\aleph_{0}}},\mathsf{CS}\\}$.
There is a model $\mathcal{M}$ of $\mathsf{ZFA}$ where $X$ holds but
$\mathsf{AC_{n}^{-}}$ and the statement “there are no amorphous sets” fail.
Moreover, the following hold in $\mathcal{M}$:

  1. (1)

$\neg\mathsf{EDM}$ and $\neg\mathsf{EDM^{k}}$ for each $k\geq 2$.

  2. (2)

Antichain Principle $\mathsf{A}$.

###### Proof.

Consider the permutation model $\mathcal{N}_{HT}^{1}(n)$ constructed by
Halbeisen–Tachtsis in the proof of [10, Theorem 8] where $\mathsf{AC_{n}^{-}}$
fails. Let $M$ be a model of $\mathsf{ZFA+AC}$ where $A$ is a countably
infinite set of atoms written as a disjoint union
$\bigcup\\{A_{i}:i\in\omega\\}$ where for all $i\in\omega$,
$A_{i}=\\{a_{i_{1}},a_{i_{2}},...,a_{i_{n}}\\}$ and $|A_{i}|=n$. The group
$\mathcal{G}$ is defined in [10] in a way so that if $\eta\in\mathcal{G}$,
then $\eta$ only moves finitely many atoms and for all $i\in\omega$,
$\eta(A_{i})=A_{k}$ for some $k\in\omega$. Let $\mathcal{F}$ be the normal
filter generated by $\\{$fix${}_{\mathcal{G}}(E):E\in[A]^{<\omega}\\}$ where
$\mathcal{I}=[A]^{<\omega}$ is the normal ideal. The model
$\mathcal{N}_{HT}^{1}(n)$ is the permutation model determined by $M$,
$\mathcal{G}$, and $\mathcal{F}$. The set of atoms $A$ is amorphous in
$\mathcal{N}_{HT}^{1}(n)$ (cf. the proof of [10, Theorem 8]). Banerjee [1, 3]
observed that $\mathsf{CAC^{\aleph_{0}}}$, $\mathsf{CS}$, and
$\mathsf{CAC_{1}^{\aleph_{0}}}$ hold in $\mathcal{N}_{HT}^{1}(n)$ (cf.
Proposition 3.5 as well).

(1). Follows from Theorem 4.1(3), Proposition 4.3, and the fact that
$\mathsf{RT}$ fails in $\mathcal{N}_{HT}^{1}(n)$ (cf. [25]).

(2). Follows from Proposition 3.5 since if $\eta\in\mathcal{G}$, then $\eta$
only moves finitely many atoms. ∎

######  Remark 4.5.

The referee communicated that neither $\mathsf{CACT^{\aleph_{0}}}$ nor
$\mathsf{CACT_{1}^{\aleph_{0}}}$ is provable in $\mathsf{ZF}$. Consider the
second Fraenkel model $\mathcal{N}_{2}$ of [9], in which the set $A$ of atoms
is a countable disjoint union of pairs so that
$A=\bigcup\\{A_{n}:n\in\omega\\}$ where $|A_{n}|=2$ for all $n\in\omega$ and,
for all $n,m\in\omega$ with $n\not=m$, $A_{n}\cap A_{m}=\emptyset$;
$\mathcal{G}$ is the group of all permutations of $A$ which fix $A_{n}$ for
every $n\in\omega$, and $\mathcal{F}$ is the normal filter on $\mathcal{G}$
generated by the subgroups fix${}_{\mathcal{G}}(E),E\in[A]^{<\omega}$. Let

$P=\\{\emptyset\\}\bigcup\\{f:f$ is a choice function for $\\{A_{i}:i\leq
n\\}$ for some $n\in\omega\\}$.

Define a partial order $\leq$ on $P$ by stipulating, for all $p,q\in P$,
$p\leq q$ if and only if $p\subseteq q$. It is clear that
$(P,\leq)\in\mathcal{N}_{2}$ (because
$Sym_{\mathcal{G}}((P,\leq))=\mathcal{G}\in\mathcal{F}$). Furthermore,
$(P,\leq)$ is an $\omega$-tree (with $\emptyset$ as its root), whose chains
are all finite since the family $\mathcal{A}=\\{A_{n}:n\in\omega\\}$, which is
countable in $\mathcal{N}_{2}$, does not have a partial choice function in
$\mathcal{N}_{2}$. Following the proof of [26, Theorem 2.11], we can see that
all antichains in $P$ are finite in $\mathcal{N}_{2}$. For the sake of
contradiction, assume that $U$ is an infinite antichain in $P$. Let
$E\in[A]^{<\omega}$ be a support of $U$. Without loss of generality assume
that $E=\bigcup_{i\leq k}A_{k}$ for some $k\in\omega$. Let

$V=\\{p\in P:dom(p)=\\{A_{0},...,A_{k}\\}\land\exists f\in U(p\subsetneq
f)\\}$.

Since $U$ is infinite and $\prod_{i\leq k}A_{i}$ is finite, we have that
$V\neq\emptyset$ and there is an element $p_{0}\in V$ such that $Y:=\\{f\in
U:p_{0}\subsetneq f\\}$ is infinite. This yields the existence of at least two
elements $f$ and $g$ of $Y$ such that $dom(f)\subsetneq dom(g)$. Let

$M=\\{m\in\omega:A_{m}\in dom(f)\cap dom(g)$ and $f(A_{m})\neq g(A_{m})\\}$.

Then for all $m\in M$, we have $m>k$. Let $\phi$ be the permutation of $A$
which swaps $f(A_{m})$ and $g(A_{m})$ for all $m\in M$, and fixes all the
other atoms. Clearly, $\phi\in$ fix${}_{\mathcal{G}}(E)$. Since $E$ is a
support of $U$, we have $\phi(U)=U$. Thus $\phi(f)\in U$. However,
$\phi(f)=g\restriction dom(f)$, so $\phi(f)\subsetneq g$. This contradicts the
fact that $U$ is an antichain in $P$. Thus, every antichain in $P$ is finite.

However, $P$ is not countable in $\mathcal{N}_{2}$, and thus
$\mathsf{CACT^{\aleph_{0}}}$ and $\mathsf{CACT_{1}^{\aleph_{0}}}$ are both
false in $\mathcal{N}_{2}$. Now, since $\neg\mathsf{CACT^{\aleph_{0}}}$ and
$\neg\mathsf{CACT_{1}^{\aleph_{0}}}$ are boundable and have a permutation
model, it follows from the Jech–Sochor First Embedding Theorem (see [13,
Theorem 6.1]) that they have a symmetric $\mathsf{ZF}$-model.

##  5\. Łoś’s theorem, and the uniqueness of algebraic closures

We recall a fact that we need in order to prove Theorem 5.2.

######  Fact 5.1.

If $\mathcal{K}$ is an algebraically closed field, if $\pi$ is a non-trivial
automorphism of $\mathcal{K}$ satisfying $\pi^{2}=1_{\mathcal{K}}$, and if
$i=\sqrt{-1}\in\mathcal{K}$, then $\pi(i)=-i\neq i$ (cf. [9, Note 41]).

######  Theorem 5.2.

$(\mathsf{ZFA})$ The following hold:

  1. (1)

$\mathsf{AC^{LO}}$ \+ Form 233 neither implies $\mathsf{LT}$ nor implies
$\mathsf{W_{\aleph_{1}}}$.

  2. (2)

$\mathsf{AC^{LO}}$ \+ Form 233 \+ $\mathsf{EDM}$ neither implies $\mathsf{LT}$
nor implies $\mathsf{W_{\aleph_{2}}}$.

###### Proof.

(1). We consider the permutation model $\mathcal{N}$ given in the proof of
[21, Theorem 4.7] where $\mathsf{AC^{LO}}$ holds and $\mathsf{LT}$ fails. We
start with a model $M$ of $\mathsf{ZFA+AC}$ with an $\aleph_{1}$-sized set $A$
of atoms so that $A=\bigcup\\{A_{i}:i<\aleph_{1}\\}$ where
$|A_{i}|=\aleph_{0}$ for all $i<\aleph_{1}$, and $A_{i}\cap A_{j}=\emptyset$
for all $i,j<\aleph_{1}$ with $i\not=j$. Let $\mathcal{G}$ be the group of all
permutations $\phi$ of $A$ such that $\forall i<\aleph_{1},\exists
j<\aleph_{1},\phi(A_{i})=A_{j}$, and $\phi$ moves only $\aleph_{0}$ atoms. Let
$\mathcal{F}$ be the normal filter of subgroups of $\mathcal{G}$ generated by
fix${}_{\mathcal{G}}(E)$, where
$E=\bigcup\\{A_{i}:i\in\mathcal{I}\\},\mathcal{I}\in[\aleph_{1}]^{<\aleph_{1}}$.
The model $\mathcal{N}$ is the permutation model determined by $M$,
$\mathcal{G}$ and $\mathcal{F}$. We note that, if $x\in\mathcal{N}$, then
there exists $E=\bigcup\\{A_{i}:i\in\mathcal{I}\\}$ for some
$\mathcal{I}\in[\aleph_{1}]^{<\aleph_{1}}$ such that
fix${}_{\mathcal{G}}(E)\subseteq Sym_{\mathcal{G}}(x)$. Any such set
$E\subseteq A$ is called a support of $x$.

######  claim 5.3.

Form 233 holds in $\mathcal{N}$.

###### Proof.

Fix a field $\mathcal{K}^{\prime}$ in $\mathcal{N}$. Let $\mathcal{K}$ be an
algebraic closure of $\mathcal{K}^{\prime}$ in $\mathcal{N}$ with support
$E=\bigcup\\{A_{i}:i\in K\\}$ for some $K\in[\aleph_{1}]^{<\aleph_{1}}$. We
show that $\mathcal{K}$ is well-orderable in $\mathcal{N}$. Otherwise, there
is a $x\in\mathcal{K}$ and a $\phi\in$ fix${}_{\mathcal{G}}(E)$ with
$\phi(x)\neq x$. Under such assumptions, Tachtsis constructed a permutation
$\psi\in$ fix${}_{\mathcal{G}}(E)$ such that $\psi(x)\neq x$ but $\psi^{2}$ is
the identity mapping (cf. the proof of $\mathsf{LW}$ (every linearly ordered
set can be well-ordered [9, Form 90]) in $\mathcal{N}$ from [21, claim 4.10]).
The permutation $\psi$ induces an automorphism of $\mathcal{K}$ and we can
therefore apply Fact 5.1 to conclude that $\psi(i)=-i\neq i$ for some
$i=\sqrt{-1}\in\mathcal{K}$.

In order to obtain a contradiction, we prove that for every $\pi\in$
fix${}_{\mathcal{G}}(E)$, $\pi(i)=i$ for every $i=\sqrt{-1}\in\mathcal{K}$.
Fix an $i=\sqrt{-1}\in\mathcal{K}$. It is enough to show that $E$ is a support
of $i$. We note that $i$ is a solution to the equation $x^{2}+1=0$ all of
whose coefficients are fixed by any $\eta\in$ fix${}_{\mathcal{G}}(E)$. So if
$\eta\in$ fix${}_{\mathcal{G}}(E)$, then $\eta(i)$ is also a solution to
$x^{2}+1=0$. Suppose $E$ is not a support of $i$. We follow the subsequent
three steps to complete the proof.

Step 1: We follow the ideas due to Tachtsis from [25, proof of Lemma 1] to
show that if $x\in\mathcal{N}$ and $E_{1},E_{2}$ are supports of $x$, then
$E_{1}\cap E_{2}$ is a support of $x$, i.e., $\mathcal{N}$ satisfies
Mostowski’s intersection lemma by making the minor, necessary, modifications.

Let $x\in\mathcal{N}$ and $E_{1}=\bigcup\\{A_{i}:i\in
K_{1}\\},E_{2}=\bigcup\\{A_{i}:i\in K_{2}\\}$, where
$K_{1},K_{2}\in[\aleph_{1}]^{<\aleph_{1}}$, be two supports of $x$. Let
$\phi\in$ fix${}_{\mathcal{G}}(E_{1}\cap E_{2})$, where $E_{1}\cap
E_{2}=\bigcup\\{A_{i}:i\in K_{1}\cap K_{2}\\}$. We will show that $\phi(x)=x$.
In particular, we construct three permutations $\rho_{1}\in$
fix${}_{\mathcal{G}}(E_{1})$, $\rho_{2}\in$ fix${}_{\mathcal{G}}(E_{2})$, and
$\phi^{\prime}\in$ fix${}_{\mathcal{G}}(E_{1}\cup E_{2})$ such that
$\phi=\rho^{-1}_{1}\rho^{-1}_{2}\phi^{\prime}\rho_{2}\rho_{1}$. Then
$\phi(x)=\rho^{-1}_{1}\rho^{-1}_{2}\phi^{\prime}\rho_{2}\rho_{1}(x)=x$, and we
are done.

To this end, we first let $\mathcal{A}=\\{A_{i}:i<\aleph_{1}\\}$ and, for a
set $x\subseteq A$, we let $tr(x)=\\{i\in\aleph_{1}:A_{i}\cap
x\neq\emptyset\\}$. Put $W=\\{a\in A:\phi(a)\neq a\\}$ and
$W^{*}=\bigcup\\{A_{i}:i\in tr(W)\\}$. Note that, from the definition of
$\mathcal{G}$, $W$ is countable, and thus so is $W^{*}$. Let
$\mathcal{U},\mathcal{V}$ be two disjoint subsets of $\mathcal{A}$ such that
each of the sets $U=\bigcup\mathcal{U}$ and $V=\bigcup\mathcal{V}$ is disjoint
from $E_{1}\cup E_{2}\cup W^{*}$, $tr(U)$ has the same order type as
$K_{2}\backslash K_{1}$ and $tr(V)$ has the same order type as $(K_{1}\cup
tr(W))\backslash K_{2}$. Consider two bijections $f:U\rightarrow
E_{2}\backslash E_{1}$ and $g:V\rightarrow(E_{1}\cup W^{*})\backslash E_{2}$
so that, if $i\in tr(U)$ and $j\in tr(V)$, then $f[A_{i}]\in\\{A_{k}:k\in
K_{2}\backslash K_{1}\\}$ and $g[A_{j}]\in\\{A_{k}:k\in(K_{1}\cup
tr(W))\backslash K_{2}\\}$. We define

$\rho_{1}=\prod_{u\in U}(u,f(u))$ and $\rho_{2}=\prod_{v\in V}(v,g(v))$,

i.e., each one of $\rho_{1}$ and $\rho_{2}$ as a product of disjoint
transpositions. Define
$\phi^{\prime}=\rho_{2}\rho_{1}\phi\rho^{-1}_{1}\rho^{-1}_{2}$. We can see
that $\rho_{1}\in$ fix${}_{\mathcal{G}}(E_{1})$ and $\rho_{2}\in$
fix${}_{\mathcal{G}}(E_{2})$. In order to see that $\phi^{\prime}\in$
fix${}_{\mathcal{G}}(E_{1}\cup E_{2})$, let $e\in E_{1}\cup E_{2}$. We
consider three cases $e\in E_{2}\backslash E_{1}$ or $e\in E_{1}\cap E_{2}$ or
$e\in E_{1}\backslash E_{2}$. In each one of these cases, we can see that
$\phi^{\prime}(e)=e$. This completes the proof of step 1.

Let $E^{\prime}$ be a support of $i$ and let $F=E^{\prime}\backslash E$. Then
$F\neq\emptyset$ (since $E$ is not a support of $i$) and $F\cap E=\emptyset$.
Without loss of generality, we may assume that $E\subsetneq E^{\prime}$.

Step 2: Using step 1, we prove that if $\phi,\phi^{\prime}\in$
fix${}_{\mathcal{G}}(E)$ and $\phi(F)\cap\phi^{\prime}(F)=\emptyset$, then
$\phi(i)\neq\phi^{\prime}(i)$. For the sake of contradiction assume that
$\phi,\phi^{\prime}\in$ fix${}_{\mathcal{G}}(E)$ such that
$\phi(F)\cap\phi^{\prime}(F)=\emptyset$ and $\phi(i)=\phi^{\prime}(i)$. Then
$(\phi^{\prime})^{-1}\phi(i)=i$. Since $E^{\prime}$ supports $i$, we have
$(\phi^{\prime})^{-1}\phi(E^{\prime})$ supports
$(\phi^{\prime})^{-1}\phi(i)=i$. By step 1,
$(\phi^{\prime})^{-1}\phi(E^{\prime})\cap E^{\prime}$ supports $i$. However,
$(\phi^{\prime})^{-1}\phi(E^{\prime})\cap E^{\prime}=E$ since
$\phi(F)\cap\phi^{\prime}(F)=\emptyset$ and $\phi,\phi^{\prime}\in$
fix${}_{\mathcal{G}}(E)$, which contradicts the assumption that $E$ is not a
support of $i$.

Step 3: Using step 2 and the features of $\mathcal{N}$, we can observe that
there is a set $S=\\{\phi_{k}(i):k\in\omega\\}$ in $\mathcal{N}$ such that for
every $k\in\omega$, $\phi_{k}\in$ fix${}_{\mathcal{G}}(E)$, and for all
$k,l\in\omega$, if $k\neq l$ then $\phi_{k}(i)\neq\phi_{l}(i)$.

In particular, we consider a denumerable collection $\\{B_{i}:i\in\omega\\}$
of subsets of $A\backslash(E\cup F)$ where $B_{i}=\bigcup\\{A_{j}:j\in
K_{i}\\}$ for some $K_{i}\in[\aleph_{1}]^{<\aleph_{1}}$ such that
$|K_{i}|=|tr(F)|$ for every $i\in\omega$, and $B_{i}\cap B_{j}=\emptyset$ if
$i\neq j$. For every $k\in\omega$, let $H_{k}:F\rightarrow B_{k}$ be a
bijection such that, for every $i\in tr(F)$, $H_{k}[A_{i}]=A_{j}$ for some
$j\in K_{k}$, and also let $\phi_{k}=\prod_{a\in F}(a,H_{k}(a))$. Then
$\phi_{k}(F)=B_{k}$. Fix any $k,l\in\omega$ such that $k\neq l$. By step 2,
$\phi_{k}(i)\neq\phi_{l}(i)$ since $B_{k}\cap B_{l}=\emptyset$. Since,
$E^{\prime}$ is a support of $i$, $\phi_{k}(E^{\prime})$ is a support of
$\phi_{k}(i)$ for every $k\in\omega$. Then
$\bigcup_{k\in\omega}\phi_{k}(E^{\prime})$ is a support of
$S=\\{\phi_{k}(i):k\in\omega\\}$ since the set of supports is closed under
countable unions. Consequently, the set $S$ is in $\mathcal{N}$ and $S$ is
infinite (in fact, countably infinite).

So, the equation $x^{2}+1=0$ has infinitely many solutions in $\mathcal{K}$,
which is a contradiction. Thus, $E$ is a support of $i$.

Since $\mathcal{K}$ is well-orderable in $\mathcal{N}$, we can use transfinite
induction without using any form of choice to finish the proof. ∎

######  claim 5.4.

$W_{\aleph_{1}}$ fails in $\mathcal{N}$.

###### Proof.

First, we show that (Sym($A$)) = $\aleph_{0}$Sym($A$) in $\mathcal{N}$. For
the sake of contradiction, assume
$f\in($Sym$(A))\backslash\aleph_{0}$Sym($A)$. Let
$E=\bigcup\\{A_{i}:i\in\mathcal{I}\\},\mathcal{I}\in[\aleph_{1}]^{<\aleph_{1}}$
be a support of $f$. Then there exists $i\in\aleph_{1}\backslash\mathcal{I}$
such that $a\in A_{i}$, $b\in A\backslash(E\cup\\{a\\})$ and $b=f(a)$. Let
$b\in A_{i}$. Consider $\phi\restriction A_{i}$ such that $\phi\restriction
A_{i}$ moves every atom in $A_{i}$ except $b$ and $\phi\restriction
A\backslash A_{i}=1_{A\backslash A_{i}}$. Clearly, $\phi\in\mathcal{G}$. Also,
$\phi(b)=b$, $\phi\in$ fix${}_{\mathcal{G}}(E)$, and hence $\phi(f)=f$. Thus

$(a,b)\in
f\implies(\phi(a),\phi(b))\in\phi(f)\implies(\phi(a),b)\in\phi(f)=f$.

So $f$ is not injective; a contradiction. If $b\in A\backslash(E\cup A_{i})$,
then consider $\phi\restriction A_{i}$ such that $\phi\restriction A_{i}$
moves every atom in $A_{i}$ and $\phi\restriction A\backslash
A_{i}=1_{A\backslash A_{i}}$. Again $\phi\in\mathcal{G}$, and we easily obtain
a contradiction.

We note that $|A|\not\leq\aleph_{1}$ in $\mathcal{N}$. In order to show that
$W_{\aleph_{1}}$ fails, we prove that there is no injection
$f:\aleph_{1}\rightarrow A$. Assume there exists such an $f$ and suppose
$\\{y_{n}\\}_{n\in\aleph_{1}}$ is an enumeration of the elements of
$Y=f(\aleph_{1})$. We can use transfinite recursion, without using any form of
choice, to construct a bijection $h:Y\rightarrow Y$ such that $h(x)\neq x$ for
any $x\in Y$. Define $g:A\rightarrow A$ as follows: $g(x)=h(x)$ if $x\in Y$,
and $g(x)=x$ if $x\in A\backslash Y$. Clearly $g\in$ Sym($A$)$\backslash$
$\aleph_{0}$Sym($A$), and hence Sym($A$) $\neq$ $\aleph_{0}$Sym($A$); a
contradiction. ∎

(2). Consider the permutation model of (1) (say $\mathcal{N}$) by replacing
$\aleph_{0}$ and $\aleph_{1}$ with $\aleph_{1}$ and $\aleph_{2}$ respectively.
Following the arguments of [21, Theorem 4.7], we can see that
$\mathsf{AC^{LO}}$ holds in $\mathcal{N}$, but $\mathsf{LT}$ fails. By the
arguments of the previous proof, $\mathsf{W_{\aleph_{2}}}$ fails and Form 233
holds in $\mathcal{N}$. Moreover, $\mathsf{DC_{\aleph_{1}}}$ holds since
$\mathcal{I}$ is closed under $<\aleph_{2}$ unions (cf. [13, the arguments in
the proof of Theorem 8.3 (i)]). Consequently, $\mathsf{EDM}$ holds by Theorem
4.1(1). ∎

##  6\. Concluding remarks and questions

###  6.1. Remarks

(1). Recently, Banerjee [2] and Karagila [14] proved that if $V$ is a model of
$\mathsf{ZFC}$, then $\mathsf{DC}_{\aleph_{1}}$ can be preserved in the
symmetric extension $\mathcal{N}$ of $V$ (symmetric submodel of a forcing
extension where $\mathsf{AC}$ can consistently fail) if the forcing notion
$\mathbb{P}$ is either $\aleph_{2}$-distributive or $\aleph_{2}$-c.c.,
$\mathcal{G}$ is any group of automorphisms of $\mathbb{P}$, and the normal
filter $\mathcal{F}$ of subgroups over $\mathcal{G}$ is $\aleph_{2}$-complete.
By Theorem 4.1, $\mathsf{EDM}$ holds in $\mathcal{N}$.

(2). By Theorems 4.1(1,3), and the facts that $\mathsf{DC_{\aleph_{1}}}$ does
not imply $\mathsf{LT}$ and $\mathsf{LT}$ does not imply $\mathsf{RT}$ in
$\mathsf{ZF}$ (cf. [21, Theorems 4.3, 4.13]), $\mathsf{LT}$ and $\mathsf{EDM}$
are mutually independent in $\mathsf{ZF}$.

(3). Fix $X\in\\{\mathsf{BPI},\mathsf{KW},\mathsf{AC_{WO}}$, 2-coloring
theorem, “There are no amorphous sets”$\\}$. Blass [4] proved that
$\mathsf{RT}$ is false in the basic Cohen model (Model $\mathcal{M}_{1}$ in
[9]) where $X$ holds. Following Theorem 4.1(3), $X$ does not imply
$\mathsf{EDM}$ in $\mathsf{ZF}$. On the other hand, $X$ fails in
$\mathcal{N}_{1}$. Thus $\mathsf{EDM}$ and $X$ are mutually independent in
$\mathsf{ZFA}$ by Theorem 4.2(1).

(4). Fix $X\in\\{\mathsf{A},\mathsf{WOAM},\mathsf{CS}\\}$. We can see that $X$
and $\mathsf{EDM}$ are mutually independent in $\mathsf{ZFA}$. Following
Theorem 4.4 and the fact that $X$ holds in
$\mathcal{N}_{HT}^{1}(2),$333Tachtsis proved $\mathsf{WOAM}$ holds in
$\mathcal{N}_{HT}^{1}(2)$, see [25, Lemma 2]. $X$ does not imply
$\mathsf{EDM}$ in $\mathsf{ZFA}$. The other direction follows from Theorem
4.2(3).

(5). Consider the permutation model $\mathcal{M}$ from Corollary 3.6 where
$\mathsf{CAC^{\aleph_{0}}}$ fails (and thus $\mathsf{EDM}$ fails by Theorem
4.1) and $\mathsf{DT}$ holds. Secondly, we consider the permutation model
$\mathcal{V}$ from [19, Theorem 9(4)] where $\mathsf{DT}$ fails and
$\mathsf{DC_{\aleph_{1}}}$ holds, and hence $\mathsf{EDM}$ and
$\mathsf{CAC^{\aleph_{0}}}$ hold as well. Thus if
$X\in\\{\mathsf{EDM},\mathsf{CAC^{\aleph_{0}}}\\}$, then $X$ and $\mathsf{DT}$
are mutually independent in $\mathsf{ZFA}$.

(6). Following the arguments of [19, Theorem 4(11)] due to Tachtsis (where he
proved that $\mathsf{CAC_{1}^{\aleph_{0}}}$ implies $\mathsf{CAC}$ in
$\mathsf{ZF}$) we can see that $\mathsf{CAC^{\aleph_{0}}}$ implies
$\mathsf{CAC}$ in $\mathsf{ZF}$. By Theorem 4.1(4), $\mathsf{CAC}$ does not
imply $\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZF}$ since $\mathsf{DF=F}$
implies $\mathsf{CAC}$ in $\mathsf{ZF}$.

(7). The referee remarked that
$\mathsf{CACT_{1}^{\aleph_{0}}}+\mathsf{CACT^{\aleph_{0}}}\not\rightarrow\mathsf{CAC}$
in $\mathsf{ZFA}$. In particular, by [19, Theorem 6] due to Tachtsis,
$\mathsf{AC_{WO}}$ (i.e., the axiom of choice for families of non-empty, well-
orderable sets) does not imply $\mathsf{CAC}$ in $\mathsf{ZFA}$, and thus
neither does $\mathsf{AC_{fin}^{\aleph_{0}}}$ imply $\mathsf{CAC}$ in
$\mathsf{ZFA}$. This, together with Proposition 3.3(5) yields
$\mathsf{CACT_{1}^{\aleph_{0}}}+\mathsf{CACT^{\aleph_{0}}}$ does not imply
$\mathsf{CAC}$ in $\mathsf{ZFA}$.

(8). In the second Fraenkel model $\mathcal{N}_{2}$,
$\mathsf{AC_{fin}^{\aleph_{0}}}$ fails but $\mathsf{MC}$ holds. By Theorem
4.1, if
$X\in\\{\mathsf{EDM},\mathsf{CAC_{1}^{\aleph_{0}}},\mathsf{CAC^{\aleph_{0}}}\\}$
then $\mathsf{MC}$ does not imply $X$ in $\mathsf{ZFA}$. Since $\mathsf{MC}$
fails in $\mathcal{N}_{1}$, $\mathsf{EDM}$ and $\mathsf{MC}$ are mutually
independent in $\mathsf{ZFA}$ by Theorem 4.2.

###  6.2. Questions

######  Question 6.1.

Does $\mathsf{CAC^{\aleph_{0}}}$ imply $\mathsf{CAC_{1}^{\aleph_{0}}}$ in
$\mathsf{ZF}$ or in $\mathsf{ZFA}$?

######  Question 6.2.

Does $\mathsf{BPI}+\mathsf{DC}$ imply $\mathsf{EDM}$ in $\mathsf{ZF}$ or in
$\mathsf{ZFA}$?

######  Question 6.3.

Does $\mathsf{WOAM}$ imply $\mathsf{CAC^{\aleph_{0}}}$ in $\mathsf{ZF}$ or in
$\mathsf{ZFA}$?

######  Question 6.4.

Does $\mathsf{AC^{LO}}$ imply $\mathsf{EDM}$ in $\mathsf{ZFA}$?

######  Question 6.5.

Does $\mathsf{EDM}$ hold in Brunner/Pincus’s Model ($\mathcal{N}_{26}$ in
[9])?

######  Question 6.6.

Does either of $\mathsf{CACT^{\aleph_{0}}}$ and
$\mathsf{CACT_{1}^{\aleph_{0}}}$ implies $\mathsf{AC_{fin}^{\aleph_{0}}}$ in
$\mathsf{ZF}$ or in $\mathsf{ZFA}$?

######  Question 6.7.

Does $\mathsf{AC_{fin}^{\aleph_{0}}}$ hold in Pincus’s Model $X$
($\mathcal{N}_{34}$ in [9])?

##  7\. Acknowledgements

The authors would like to thank Prof. Lajos Soukup and Prof. Eleftherios
Tachtsis for several discussions concerning Kurepa’s result
($\mathsf{CAC_{1}^{\aleph_{0}}}$) and its variants, which have been the chief
motivation for us in continuing the research on this intriguing topic. The
authors are grateful to the anonymous referee for reading the manuscript in
detail and for providing several comments and suggestions which improved the
quality and the exposition of the paper. We are especially thankful to the
referee for Remark 4.5, Remark 6.1(7), and for outlining the three main steps
in the proof of claim 5.3, which gave us the motivation to fill in the
details.

## References

  * [1] A. Banerjee,  Maximal independent sets, variants of chain/antichain principle and cofinal subsets without $\mathsf{AC}$,  Comment. Math. Univ. Carolin.,  to appear.  arXiv preprint: https://arxiv.org/abs/2009.05368v2.
  * [2] A. Banerjee,  Combinatorial properties and dependent choice in symmetric extensions based on Lévy collapse,  Arch. Math. Logic  62 (2023),  369–399.  DOI: https://doi.org/10.1007/s00153-022-00845-3.
  * [3] A. Banerjee and Z. Gyenis,  Chromatic number of the product of graphs, graph homomorphisms, Antichains and cofinal subsets of posets without $\mathsf{AC}$,  Comment. Math. Univ. Carolin.  62 (2021),  no. 3,  361-382.  DOI: https://doi.org/10.14712/1213-7243.2021.028.
  * [4] A. Blass,  Ramsey’s theorem in the hierarchy of choice principles,  J. Symbolic Logic  42 (1977),  no. 3,  387–390.  DOI: https://doi.org/10.2307/2272866.
  * [5] N. Brunner,  Products of Compact Spaces in the Least Permutation Model,  Z. Math. Log. Grundl. Math.  31 (1985),  no. 25-28,  441-448.  DOI: https://doi.org/10.1002/malq.19850312507.
  * [6] N. Brunner,  Dedekind-Endlichkeit und Wohlordenbarkeit,  Monatsh. Math.  94 (1982),  no. 1,  9-31.  DOI: https://doi.org/10.1007/BF01369079.
  * [7] B. Dushnik and E. W. Miller,  Partially Ordered Sets,  American Journal of Mathematics  63 (1941),  no. 3,  600-610.  DOI: https://doi.org/10.2307/2371374.
  * [8] P. Howard, K. Keremedis, J. E. Rubin, A. Stanley and E. Tachtsis,  Non-constructive Properties of the Real Numbers,  Math. Logic Quart.  47 (2001),  no. 3,  423-431.  https://doi.org/10.1002/1521-3870(200108)47:3<423::AID-MALQ423>3.0.CO;2-0.
  * [9] P. Howard and J. E. Rubin,  Consequences of the Axiom of Choice,  Math. Surveys Monogr. 59, Amer. Math. Soc., Providence, RI, 1998.  DOI: http://dx.doi.org/10.1090/surv/059.
  * [10] L. Halbeisen and E. Tachtsis,  On Ramsey Choice and Partial Choice for infinite families of $n$-element sets,  Arch. Math. Logic  59 (2020),  no. 5-6,  583–606.  DOI: https://doi.org/10.1007/s00153-019-00705-7.
  * [11] P. Howard, D.I. Saveliev and E. Tachtsis,  On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements,  Math. Logic Quart.  62 (2016),  no. 3,  155-176.  DOI: https://doi.org/10.1002/malq.201400089.
  * [12] P. Howard, D.I. Saveliev and E. Tachtsis,  On the existence of cofinal well-founded subsets of posets without $\mathsf{AC}$,  Preprint.
  * [13] T.J. Jech,  The Axiom of Choice,  Stud. Logic Found. Math. 75, North-Holland, Amsterdam, 1973.
  * [14] A. Karagila,  Preserving Dependent Choice,  Bull. Polish Acad. Sci. Math.  67 (2019),  no. 1,  19-29.  DOI: https://doi.org/10.4064/ba8169-12-2018,  MR 3947821
  * [15] K. Keremedis, E. Tachtsis and E. Wajch,  Several results on compact metrizable spaces in $\mathsf{ZF}$,  Monatsh. Math.  196 (2021),  no. 1,  67–102. https://doi.org/10.1007/s00605-021-01582-0.
  * [16] G. Kurepa,  On two problems concerning ordered sets,  Glasnik Mat.-Fiz. Astronom. Društvo Mat. Fiz. Hrvatske Ser. II  13 (1958),  229–234.
  * [17] D. Pincus,  Zermelo–Fraenkel consistency results by Fraenkel–Mostowski methods,  J. Symbolic Logic  37 (1972),  no. 4,  721–743.  DOI: https://doi.org/10.2307/2272420.
  * [18] W. Sierpiński,  Cardinal and ordinal numbers,  Państwowe Wydawnictwo Naukowe, Warsaw  (1958).
  * [19] E. Tachtsis,  On a theorem of Kurepa for partially ordered sets and weak choice,  Monatsh. Math.  199 (2022),  no. 3,  645–669.  DOI: https://doi.org/10.1007/s00605-022-01751-9.
  * [20] E. Tachtsis,  On the existence of permutations of infinite sets without fixed points in set theory without choice,  Acta Math. Hungar.  157 (2019),  no. 2,  281–300.  DOI: https://doi.org/10.1007/s10474-018-0869-9.
  * [21] E. Tachtsis,  Łoś’s theorem and the axiom of choice,  Math. Logic Quart.  65 (2019),  no. 3,  280-292.  DOI: https://doi.org/10.1002/malq.201700074.
  * [22] E. Tachtsis,  On the existence of almost disjoint and MAD families without $\mathsf{AC}$,  Bull. Polish Acad. Sci. Math.  67 (2019),  no. 2,  101-124.  DOI: https://doi.org/10.4064/ba8148-3-2019.
  * [23] E. Tachtsis,  Dilworth’s decomposition theorem for posets in $\mathsf{ZF}$,  Acta Math. Hungar.  159 (2019),  no. 2,  603-617.  DOI: https://doi.org/10.1007/s10474-019-00967-w.
  * [24] E. Tachtsis,  On the Minimal Cover Property and Certain Notions of Finite,  Arch. Math. Logic  57 (2018),  no. 5-6,  665-686.  DOI: https://doi.org/10.1007/s00153-017-0595-y.
  * [25] E. Tachtsis,  On Ramsey’s Theorem and the existence of Infinite Chains or Infinite Anti-Chains in Infinite Posets,  J. Symbolic Logic  81 (2016),  no. 1,  384-394.  DOI: https://doi.org/10.1017/jsl.2015.47.
  * [26] E. Tachtsis,  On Martin’s Axiom and Forms of Choice,  Math. Logic Quart.  62 (2016),  no. 3,  190-203.  DOI:https://doi.org/10.1002/malq.201400115.