## 502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in ${{\sf ZF}:}$

1. The axiom of choice: Every set can be well-ordered.
2. Every collection of nonempty set admits a choice function, i.e., if ${x\ne\emptyset}$ for all ${x\in I,}$ then there is ${f:I\rightarrow\bigcup I}$ such that ${f(x)\in x}$ for all ${x\in I.}$
3. Zorn’s lemma: If ${(P,\le)}$ is a partially ordered set with the property that every chain has an upper bound, then ${P}$ has maximal elements.
4. Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set ${S}$ such that ${|S\cap x|=1}$ for all ${x}$ in the family.
5. Any set is a well-ordered union of finite sets of bounded size, i.e., for every set ${x}$ there is a natural ${m,}$ an ordinal ${\alpha,}$ and a function ${f:\alpha\rightarrow{\mathcal P}(x)}$ such that ${|f(\beta)|\le m}$ for all ${\beta<\alpha,}$ and ${\bigcup_{\beta<\alpha}f(\beta)=x.}$
6. Tychonoff’s theorem: The topological product of compact spaces is compact.
7. Every vector space (over any field) admits a basis.

## 580 -Some choiceless results (4)

January 29, 2009

Let me begin with a remark related to the question of whether $\aleph(X)\preceq {\mathcal P}^2(X)$. We showed that this is the case if $X\sim Y^2$ for some $Y$, or if $X$ is Dedekind-finite.

Theorem. The axiom of choice is equivalent to the statement that any Dedekind-infinite cardinal is a square.

Proof. Let $X$ be a set. Assuming that every D-infinite cardinal is a square, we need to show that $X$ is well-orderable. We may assume that $\omega\preceq X$. Otherwise, replace $X$ with $X\cup\omega$. Let $\kappa=\aleph(X)$. Assume that $X\sqcup\kappa$ is a square, say $X\sqcup\kappa\sim Y^2$. Then $\kappa\preceq Y^2$. By Homework problem 2, $\kappa\preceq Y$, so $Y\sim \kappa\sqcup Z$ for some $Z$, and $X\sqcup \kappa\sim Y^2\sim\kappa^2\sqcup 2\times\kappa\times Z\sqcup Z^2\succeq\kappa\times Z$.

Lemma. Suppose $A,B,C$ are D-infinite sets and $\lambda$ is an (infinite) initial ordinal. If $\lambda\times A\preceq B\cup C$ then either $\lambda\preceq B$ or $A\preceq C$.

Proof. Let $f:\lambda\times A\to B\sqcup C$ be an injection. If there is some $a\in A$ such that $f(\cdot,a):\lambda\to B$ we are done, so we may assume that for all $a\in A$ there is some $\alpha\in\lambda$ such that $f(\alpha,a)\in C$. Letting $\alpha_a$ be the least such $\alpha$, the map $a\mapsto f(\alpha_a,a)$ is an injection of $A$ into $C$. ${\sf QED}$

By the lemma, it must be that either $\kappa\preceq X$ or else $Z\preceq\kappa$. The former is impossible since $\kappa=\aleph(X)$, so $Z$ is well-orderable, and thus so is $Y$, and since $Y\sim Y^2\succeq X$, then $X$ is well-orderable as well. ${\sf QED}$