Axiom of Choice & Equivalents

Proof. Assume AC and let $X$ consist of pairwise disjoint nonempty sets. Take a choice function $f$ for $X$ and put $T=\{f(A):A\in X\}$, a set by replacement. For $A\in X$ we have $f(A)\in T\cap A$, so the intersection is nonempty. If $x,y\in T\cap A$ then $x=f(B)$ and $y=f(C)$ for some $B,C\in X$; since $x\in A\cap B$ and the family is pairwise disjoint, $B=A$, and likewise $C=A$, so $x=f(A)=y$. Hence $T\cap A$ is a singleton.

Conversely assume the transversal principle and let $Y$ be any set of nonempty sets. The family is not assumed disjoint, so disjointify it: put

whose members are nonempty and pairwise disjoint, since an element of $\{A\}\times A$ records $A$ in its first coordinate. Let $T$ be a transversal. For each $A\in Y$ the intersection $T\cap (\{A\}\times A)$ is a single pair $(A,a_A)$ with $a_A\in A$, and $f=\{(A,a_A):A\in Y\}$ is a choice function for $Y$.∎

Proof. $(1)\Rightarrow (2)$. Let $g:B\to A$ be onto. For each $a\in A$ the fibre $g^{-1}(a)=\{b\in B:g(b)=a\}$ is nonempty precisely because $g$ is onto, and it is a set by separation inside $B$. Let $X=\{g^{-1}(a):a\in A\}$ and let $f$ be a choice function for $X$. Define

Then $s(a)\in g^{-1}(a)$, which says exactly $g(s(a))=a$. So $s$ is a section.

$(2)\Rightarrow (1)$. Let $X$ be a set of nonempty sets. Put

a set by separation, and let $g:B\to X$ be the first projection $g(A,a)=A$. It is onto, because each $A\in X$ is nonempty and so contributes at least one pair. Let $s$ be a section. Then $s(A)$ is a pair whose first coordinate is $A$, say $s(A)=(A,a_A)$ with $a_A\in A$, and $A\mapsto a_A$ is a choice function for $X$.∎

Proof. Only the positive half is proved here; the first claim is an independence result of Cohen's kind, quoted in Independence from ZF. If every member of $X$ is a two-element subset of a linearly ordered $(L,<)$, then each $A\in X$ has a $<$ -least element, so $f(A)={\min }_{<}A$ is well defined by an explicit formula, and separation inside $X\times L$ produces $f$ as a set.∎

Proof. Induct on $n=|X|$, proving the statement "every family of exactly $n$ nonempty sets has a choice function" for all $n\in \mathbb{N}$.

Base case $n=0$. Then $X=\varnothing$ and the empty function $f=\varnothing$ has domain $\varnothing =X$ and satisfies the condition vacuously.

Inductive step. Suppose every family of $n$ nonempty sets has a choice function, and let $|X|=n+1$. Since $X$ is nonempty, fix a member $A\in X$ — this is one application of "a nonempty set has an element", which is a consequence of the definition of nonemptiness in first-order logic, not an axiom. Because $A$ itself is nonempty, fix $a\in A$, again one application. Now $X^{\prime }=X\setminus \{A\}$ has exactly $n$ members, all nonempty, so by the inductive hypothesis it has a choice function $g$. Put

Then $f$ is a function with domain $X^{\prime }\cup \{A\}=X$, and $f(B)\in B$ for every $B\in X$: for $B\in X^{\prime }$ because $g$ is a choice function, and for $B=A$ by the choice of $a$. This completes the induction.∎

Proof. Apply the theorem Finite choice to $X=\{(1,A_1),\dots ,(n,A_n)\}$ viewed as an indexed family; the resulting choice function is precisely an element of the product. Alternatively, induct on $n$ directly: for $n=1$ nonemptiness of $A_1$ gives an element, and given $(a_1,\dots ,a_n)$ in the product of the first $n$ and any $a_{n+1}\in A_{n+1}$, the tuple $(a_1,\dots ,a_{n+1})$ lies in the larger product.∎

Proof. Every nonempty subset of a well-ordered set has a least element, and that least element is unique. So $f(i)={\min }_{<}{A}_i$ is given by an explicit formula $\phi (i,w)$ saying "$w\in A_i$ and no element of $A_i$ is $<w$ ". Separation applied to $I\times W$ with $\phi$ produces $f$ as a set, and the uniqueness of minima makes it a function.∎

Proof. For any $A\in C$ and any $a\in A$ we have $a\in \bigcup C=U$, so $A\subseteq U$; hence $U$ bounds $C$ in the power set. The second clause is then immediate from the definition of an upper bound in $P$, which requires the bound to be a member of $P$.∎

Proof. Nonemptiness holds since $\varnothing \in P$, which also handles the empty chain. Let $C$ be a nonempty chain in $P$ and $U=\bigcup C$. To show $U\in P$ it suffices, by finite character, to show every finite $F\subseteq U$ lies in $P$. Write $F=\{x_1,\dots ,x_k\}$ and pick $A_i\in C$ with $x_i\in A_i$ — finitely many picks, legitimate in ZF by the theorem Finite choice. Since $C$ is a chain, the finite set $\{A_1,\dots ,A_k\}$ is linearly ordered by inclusion and so has a largest member $A_j$. Then $F\subseteq A_j\in P$, and every subset of a member of $P$ is in $P$ because all of its finite subsets are finite subsets of that member. Hence $F\in P$, and therefore $U\in P$. By the proposition Unions bound chains of subsets, $U$ is an upper bound in $P$.∎

Proof. Let $I_0\subseteq V$ be linearly independent — for the first claim take $I_0=\varnothing$, which is independent vacuously. Let

ordered by inclusion.

$P$ is nonempty: $I_0\in P$.

Chains have upper bounds. Let $C\subseteq P$ be a nonempty chain and $U=\bigcup C$. Certainly $U\supseteq I_0$. To see $U$ is independent, take a finite subset $\{v_1,\dots ,v_k\}\subseteq U$ and scalars ${\lambda }_1,\dots ,{\lambda }_k\in K$ with ${\sum }_i{\lambda }_i{v}_i=0$. Each $v_i$ lies in some $A_i\in C$; finitely many choices, so no AC is used beyond the theorem Finite choice. As $C$ is a chain, the finite family $A_1,\dots ,A_k$ has a largest member $A$, and all the $v_i$ lie in $A$. But $A$ is linearly independent, so every ${\lambda }_i=0$. Since a linear dependence involves only finitely many vectors, $U$ is independent, so $U\in P$ and bounds $C$ by the proposition Unions bound chains of subsets. The empty chain is bounded by $I_0$.

Zorn gives a maximal $B\in P$. We claim $\mathrm{span}(B)=V$. Suppose not, and take $w\in V\setminus \mathrm{span}(B)$. We show $B\cup \{w\}$ is independent, contradicting maximality. Let $\mu w+{\sum }_{i=1}^k{\lambda }_i{b}_i=0$ with $b_i\in B$ distinct. If $\mu \ne 0$ then $w=-{\mu }^{-1}{\sum }_i{\lambda }_i{b}_i\in \mathrm{span}(B)$, contrary to the choice of $w$; so $\mu =0$, and then ${\sum }_i{\lambda }_i{b}_i=0$ forces every ${\lambda }_i=0$ by independence of $B$. Hence $B\cup \{w\}\in P$ strictly contains $B$, contradicting maximality. Therefore $\mathrm{span}(B)=V$ and $B$ is a basis containing $I_0$.∎

Proof. Let $P$ be the set of proper ideals of $R$ containing $I$, ordered by inclusion.

Nonempty: $I\in P$.

Chains have upper bounds. Let $C$ be a nonempty chain in $P$ and $U=\bigcup C$. First, $U$ is an ideal: if $x,y\in U$ then $x\in J_1$ and $y\in J_2$ for some $J_1,J_2\in C$, and as $C$ is a chain one contains the other, say $J_1\subseteq J_2$; then $x,y\in J_2$, so $x-y\in J_2\subseteq U$, and $rx\in J_1\subseteq U$ for any $r\in R$. Second, $U$ is proper: every $J\in C$ is proper, so $1\notin J$ for each $J$ — here is where the identity is used — and hence $1\notin U$, so $U\ne R$. Third, $U\supseteq I$. Thus $U\in P$ bounds $C$.

Zorn gives a maximal element $M$ of $P$. By construction $M$ is a proper ideal containing $I$, and it is maximal among proper ideals containing $I$. It is in fact maximal among all proper ideals: if $M\subseteq J⊊R$ with $J$ an ideal, then $J\supseteq M\supseteq I$, so $J\in P$, and maximality of $M$ in $P$ gives $J=M$.∎

Proof. By the theorem Krull's theorem, $R$ has a maximal ideal $M$ (take $I=\{0\}$, which is proper since $1\ne 0$). The quotient $R/M$ is a commutative ring with identity in which, by maximality of $M$, the only ideals are $\{0\}$ and the whole ring; a commutative ring with $1\ne 0$ and no proper nonzero ideals is a field, since for $x\ne 0$ the ideal $(x)$ must be everything, giving $xy=1$ for some $y$. The quotient map $R\to R/M$ is the required surjection.∎

Proof. This is the proposition Choice from a single infinite family with structure with $W=S$: send each nonempty $A\subseteq S$ to its unique $<$ -least element. Uniqueness makes the resulting relation a function, and separation inside $\mathcal{P}(S)\times S$ makes it a set.∎

Proof. Let $S$ be a set. Consider partial well-orderings of $S$: pairs $(A,{<}_A)$ where $A\subseteq S$ and ${<}_A$ is a well-order of $A$. Formally, such a pair is an element of $\mathcal{P}(S)\times \mathcal{P}(S\times S)$, so the collection

is a set by separation. Order $P$ by end-extension: $(A,{<}_A)⪯(B,{<}_B)$ if $A\subseteq B$, the order ${<}_B$ restricted to $A$ is ${<}_A$, and every element of $B\setminus A$ is ${<}_B$ -above every element of $A$. The last clause is essential and is what makes the union of a chain well-ordered; without it the lemma below fails.

$⪯$ is a partial order. Reflexivity and antisymmetry are immediate; for transitivity, if $(A,{<}_A)⪯(B,{<}_B)⪯(C,{<}_C)$ then ${<}_C$ restricted to $A$ is ${<}_A$, and an element of $C\setminus A$ lies either in $B\setminus A$, hence above all of $A$, or in $C\setminus B$, hence above all of $B\supseteq A$.

$P$ is nonempty: $(\varnothing ,\varnothing )\in P$.

Chains have upper bounds. Let $C=\{(A_i,{<}_i){\}}_{i\in I}$ be a nonempty chain in $P$. Put $A={\bigcup }_i{A}_i$ and $<={\bigcup }_i{<}_i$, a relation on $A$. It is a linear order: given $x,y\in A$ with $x\in A_i$, $y\in A_j$, one of $(A_i,{<}_i),(A_j,{<}_j)$ extends the other, so both lie in a single $A_k$ and are comparable under ${<}_k$, hence under $<$; and the compatibility clause makes the comparisons consistent across the chain.

It is a well-order. Let $\varnothing \ne T\subseteq A$. Pick $t\in T$ — one element, no choice needed — and $i$ with $t\in A_i$. The set $T\cap A_i$ is a nonempty subset of the well-ordered $(A_i,{<}_i)$, so it has a ${<}_i$ -least element $m$. We claim $m$ is $<$ -least in $T$. Let $s\in T$ be arbitrary. If $s\in A_i$ then $m{\le }_{i}s$ by the choice of $m$, so $m\le s$. If $s\notin A_i$ then $s\in A_j$ for some $j$ with $(A_i,{<}_i)⪯(A_j,{<}_j)$ — using that $C$ is a chain and $s\notin A_i$ — and then $s\in A_j\setminus A_i$, so $s$ is above every element of $A_i$, in particular above $m$. Either way $m\le s$. Hence $(A,<)\in P$, and it end-extends every member of the chain, since each $A_i$ is an initial segment of $A$ by exactly the same argument. The empty chain is bounded by $(\varnothing ,\varnothing )$.

Apply Zorn. Let $(M,{<}_M)$ be a maximal element of $P$. If $M\ne S$, pick $s\in S\setminus M$ — one element again — and extend ${<}_M$ to $M\cup \{s\}$ by putting $s$ strictly above everything in $M$. The result is still a well-order: a nonempty subset either meets $M$, and then its least element is the ${<}_M$ -least element of its intersection with $M$, or it is $\{s\}$, whose least element is $s$. And it end-extends $(M,{<}_M)$ by construction. This contradicts maximality, so $M=S$ and ${<}_M$ well-orders $S$.∎

Proof. Let $X$ be a set of nonempty sets and put $S=\bigcup X$, a set by the union axiom. By hypothesis fix a well-order $<$ of $S$. Every $A\in X$ is a nonempty subset of $S$, so it has a unique $<$ -least element ${\min }_{<}A$. Define

This is a set by separation. It is a function: for each $A\in X$ there is exactly one such $a$, existence because $<$ well-orders $S$ and $A\ne \varnothing$, uniqueness because two least elements of a linearly ordered set are comparable and hence equal. And $f(A)={\min }_{<}A\in A$, so $f$ is a choice function for $X$.∎

Proof. The sketch in Why AC implies Zorn's lemma gives AC $\Rightarrow$ Zorn, the theorem Zorn's lemma implies the well-ordering theorem gives Zorn $\Rightarrow$ WO, and the theorem The well-ordering theorem implies AC gives WO $\Rightarrow$ AC. A cycle of implications makes all three equivalent: any one of them implies the next going round, and going round far enough reaches every other.∎

Proof. Well-order $A$ and $B$, giving order isomorphisms with ordinals $\alpha$ and $\beta$ respectively. Ordinals are comparable: for any two ordinals, one is an initial segment of the other or they are equal. If $\alpha \le \beta$, the inclusion of $\alpha$ as an initial segment of $\beta$ transports to an injection $A\to B$; otherwise the same argument gives $B\to A$.∎

Proof. Regard $\mathbb{R}$ as a vector space over $\mathbb{Q}$. By the theorem Every vector space has a basis it has a basis $B$, a Hamel basis, and $|B|\ge 2$ since $\mathbb{R}$ is not $1$ -dimensional over $\mathbb{Q}$ — it is uncountable while $\mathbb{Q}b$ is countable. Fix distinct $b_1,b_2\in B$ and define $g$ on the basis by $g(b_1)=1$, $g(b)=0$ for all other $b\in B$, extending $\mathbb{Q}$ -linearly. Then $g$ is additive by linearity. It is not $x\mapsto cx$: such a map has $g(b_2)/g(b_1)=b_2/b_1\ne 0$, while our $g$ has $g(b_2)=0$ and $g(b_1)=1$. Density of the graph follows because the graph contains the $\mathbb{Q}$ -span of the two points $(b_1,1)$ and $(b_2,0)$, which is a dense $\mathbb{Q}$ -subspace of ${\mathbb{R}}^2$ since those points are $\mathbb{R}$ -linearly independent.∎

Proof. Full proofs of all ten equivalences are beyond the chapter, and we prove only the two that were not established elsewhere, leaving the rest to the references. Items 1, 2, 3, 6 and 9 were proved above, in the corollary The cycle closes, the theorem AC is equivalent to every surjection splitting, the theorem Every vector space has a basis with Blass's converse quoted, and the definition of AC respectively; item 4 has its forward direction in the theorem Comparability of cardinals.

AC implies the Hausdorff maximal principle (7). Let $C_0$ be a chain in a poset $(P,\le )$ and let $Q$ be the set of chains of $P$ containing $C_0$, ordered by inclusion. The union of a chain of chains is a chain: two elements of the union lie in members of the chain-of-chains, one of which contains the other, so they lie in a common chain and are comparable. Hence $Q$ satisfies Zorn's hypotheses, and a maximal element of $Q$ is a maximal chain containing $C_0$.

The Hausdorff maximal principle implies Zorn's lemma. Let $(P,\le )$ satisfy Zorn's hypotheses and let $M$ be a maximal chain, which exists by (7) applied to the empty chain. Let $u$ be an upper bound of $M$. Then $u$ is maximal in $P$: if $u<x$ then $M\cup \{x\}$ is a chain — every element of $M$ is $\le u<x$ — strictly containing $M$, contradicting maximality of $M$.∎

Proof. This is a summary of the proofs already given rather than a new argument, but the correspondences are exact. Clause 1 is the content of the proposition Well-orderable sets have canonical choice and of the theorem The well-ordering theorem implies AC. Clause 2 is the content of the theorem Zorn's lemma implies the well-ordering theorem, where the partial objects are partial well-orders and the maximal one is a well-order of everything. Clause 3 is what is used in the sketch of AC $\Rightarrow$ Zorn, where a single application of AC fixes all the strict upper bounds in advance so that the recursion afterwards is deterministic.∎

Proof. Define an equivalence relation on $[0,1]$ by

It is an equivalence relation: reflexive since $0\in \mathbb{Q}$, symmetric since $\mathbb{Q}$ is closed under negation, transitive since it is closed under addition. Its classes are the sets $([0,1])\cap (x+\mathbb{Q})$, and they partition $[0,1]$ into pairwise disjoint nonempty sets.

The one use of AC. By the proposition Transversal form of AC applied to this partition, there is a set $V\subseteq [0,1]$ containing exactly one element of each class.

Let $Q=\mathbb{Q}\cap [-1,1]$, a countably infinite set, and enumerate it as $q_0,q_1,q_2,\dots$. Consider the translates $V_n=V+q_n$. Two claims.

The $V_n$ are pairwise disjoint. Suppose $x\in V_n\cap V_m$. Then $x=v+q_n=w+q_m$ with $v,w\in V$, so $v-w=q_m-q_n\in \mathbb{Q}$, which means $v\sim w$. Since $V$ meets each class exactly once, $v=w$, and then $q_n=q_m$, so $n=m$.

The union is trapped between two intervals:

For the left inclusion, let $x\in [0,1]$. Its class contains a unique $v\in V$, and $v\in [0,1]$ too, so $q=x-v$ is rational and lies in $[-1,1]$, hence $q=q_n$ for some $n$ and $x=v+q_n\in V_n$. For the right inclusion, each $V_n\subseteq [0,1]+[-1,1]=[-1,2]$.

Now suppose, for contradiction, that $V$ is measurable, and let $c=\lambda (V)$. By translation invariance every $V_n$ is measurable with $\lambda (V_n)=c$. By countable additivity applied to the disjoint family $(V_n)$, and monotonicity applied to the two inclusions,

Examine the middle sum. If $c=0$ then ${\sum }_{n}c=0$, contradicting $1\le 0$. If $c>0$ then ${\sum }_{n}c=\infty$, since it is a sum of infinitely many copies of a fixed positive number, contradicting $\infty \le 3$. Both cases are impossible, so $V$ is not measurable.

For the final sentence: the argument used only the three properties in the definition Lebesgue measure, the properties used, so any measure with those properties defined on every subset of $\mathbb{R}$ would face the same contradiction.∎

Proof. AC $\Rightarrow$ DC. Given $R$ as in the definition, apply AC to the family $(\{y:xRy\}{)}_{x\in S}$ of nonempty sets to get $h$ with $xRh(x)$. Pick any $x_0\in S$ and define $x_{n+1}=h(x_n)$ by ordinary recursion on $\mathbb{N}$, which is a theorem of ZF once the function $h$ is fixed.

DC $\Rightarrow$ CC. Let $(A_n{)}_{n\in \mathbb{N}}$ be nonempty. Let $S$ be the set of finite sequences $(a_0,\dots ,a_{k-1})$ with $a_i\in A_i$, which is nonempty as it contains the empty sequence, and let $sRt$ mean that $t$ extends $s$ by one term. Every $s$ of length $k$ has such a $t$, since $A_k\ne \varnothing$. DC yields a sequence of finite sequences each extending the last; whether they all extend the empty sequence is arranged by discarding an initial segment and re-indexing, and the union of the resulting chain is a choice function on $(A_n)$.

Non-reversal is not proved here; it is a forcing result. Jensen and others produced models of ZF + DC in which AC fails, and models of ZF + CC in which DC fails.∎

Proof. Each $A_n$ is countable, meaning the set $E_n$ of surjections $\mathbb{N}\to A_n$ is nonempty — assume each $A_n$ nonempty, discarding empties changes nothing. Apply CC to the countable family $(E_n{)}_{n\in \mathbb{N}}$ to obtain a single function $n\mapsto e_n$ with $e_n:\mathbb{N}\to A_n$ onto. Now define $F:\mathbb{N}\times \mathbb{N}\to {\bigcup }_n{A}_n$ by $F(n,k)=e_n(k)$. It is onto: any $x$ in the union lies in some $A_n$ and equals $e_n(k)$ for some $k$. Since $\mathbb{N}\times \mathbb{N}$ is countable, the union is countable.

The negative half is Feferman and Levy's 1963 forcing construction, quoted not proved: they built a model of ZF in which $\mathbb{R}$ is a countable union of countable sets, so that even this apparently innocent theorem fails outright.∎

Proof. We give the argument in the form that makes the mechanism visible, working in a setting where subsets are not assumed to be decidable. Let $p$ be a proposition and put