## 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 (2)

January 25, 2009

There are a few additional remarks on the Schröder-Bernstein theorem worth mentioning. I will expand on some of them later, in the context of descriptive set theory.

The dual Schröder-Bernstein theorem (dual S-B) is the statement “Whenever $A,B$ are sets and there are surjections from $A$ onto $B$ and from $B$ onto $A,$ then there is a bijection between $A$ and $B$.”

* This follows from the axiom of choice. In fact, ${\sf AC}$ is equivalent to: Any surjective function admits a right inverse. So the dual S-B follows from choice and the S-B theorem.

* The proofs of S-B actually show that if one has injections $f:A\to B$ and $g:B\to A$, then one has a bijection $h:A\to B$ contained in $f\cup g^{-1}$. So the argument above gives the same strengthened version of the dual S-B. Actually, over ${\sf ZF}$, this strengthened version implies choice. This is in Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375-381.

* If $j : {}x \to y$ is onto, then there is $k:{\mathcal P}(y)\to {\mathcal P}(x)$ 1-1, so if there are surjections in both directions between $A$ and $B$, then ${\mathcal P}(A)$ and ${\mathcal P}(B)$ have the same size. Of course, this is possible even if $A$ and $B$ do not.

Open question. (${\sf ZF}$) Does the dual Schröder-Bernstein theorem imply the axiom of choice?

* The dual S-B is not a theorem of ${\sf ZF}$.