Axiom of choice and Proofs

Question

I would like an example where the axiom of choice is used to prove something relatively simple. May someone provide an example, please? I’d like to know where the axiom has been used in the proof. Thanks

Answer 1

I guess the most basic classical example (apart from the usual applications of Zorn's Lemma) is proving that if $X$ and $Y$ are sets and $f:X\to Y$ is a surjective map, then there exists $g:Y\to X$ such that $f\circ g$ is the identity on $Y$.

The proof goes: For every $y\in Y,$ choose $g(y)\in f^{-1}(\{y\})$ (this set is non-empty by surjectivity). Now, by definition $f(g(y))=y$. Without the axiom of choice you cannot simultaneously choose the $g(y)$'s to construct a well-defined map.

Answer 2

Theorem (AC) Every infinite set has a countably infinite subset.

Proof Sketch 1 Let $X$ be any infinite set and $f$ be a function on $P(X)\setminus\{\varnothing\}$ such that $f(Y)\in Y.$ Then define a sequence $\langle a_n:n\in \omega\rangle$ by recursion: $$ a_{n+1} = f(X\setminus\{a_0,\ldots,a_n\}).$$ Since $X$ is infinite, $X\setminus\{a_0,\ldots,a_n\}$ is never empty, and we can see by construction the $a_n$ are all distinct, so $\{a_n:n\in\omega\}$ is a countably infinite subset of $X.$

Proof Sketch 2 Let $\langle x_\alpha:\alpha<\beta\rangle$ be a transfinite enumeration of $X.$ Then $\{x_\alpha:\alpha<\omega\}$ is a countably infinity subset of $X.$

The first uses the axiom of choice when we assume that $f$ exists. The second uses the axiom of choice when we assume a transfinite enumeration of $X$ exists.

(Really proof 1 is just the start of the proof from AC that a transfinite enumeration exists, so these are the same proof in spirit.)

The intuition is that we just choose one element, then another, then another, and so on until we have picked out a countably infinite subset. Really, this naive argument is using a weaker form of choice called dependent choice and can be easily turned into a rigorous proof from dependent choice.

The theorem is actually significantly weaker than even dependent choice, but that requires less straightforward arguments to see.

Answer 3

If $p$ is equivalent to the axiom of choice, each implies the other, so AC implying $p$ might suit your purpose. The example I'll pick is any set $X$ is well-orderable.

Let $f$ denote a choice function on the non-empty subsets of $X$. For any ordinal $\alpha$, define $\iota(\alpha):=f(X\setminus\{\iota(\beta)|\beta\in\alpha\})$, so $\iota(\emptyset)=f(X),\,\iota(\{\emptyset\})=f(X\setminus\{\iota(0)\})$ etc. We thus inject ordinals into $X$ until the values $\iota$ has assumed comprise all of $X$. This must happen eventually, because ordinals don't form a set and, by replacement, can't be injected into one. But if $\alpha$ is the least ordinal for which $\iota(\alpha)$ is undefined because we'd be trying to compute $f(\emptyset)$, the codomain of $\iota$ is just $\alpha$. Because we've bijected $X$ with $\alpha$, we've also well-ordered it.

Answer 4

If you have two non-empty sets $A$ and $B$, and you have $a\in A, b\in B$, then their cartesian product $A\times B$ obviously contains the tuple $(a,b)$, hence is non empty. Surprisingly, such a statement for products with infinitely many factors needs the axiom of choice.

Statement. The cartesian product of arbitrarily many non-empty sets is non-empty.

Proof. (Sketch)

To show that the product is non-empty, we have to find an element in it. But if $(X_i)_{i\in I}$ is a family of sets, then any tuple in $\prod_{i\in I} X_i$ has to contain one element from each of the $X_i$. Hence, we need the existence of such a choice which is provided by the axiom of choice.

$\square$

And the axiom of choice is actually equivalent to that statement.

Answer 5

There are plenty of standard theorems which invoke some variant of the Axiom of Choice (AC). For example, the Baire Category Theorem requires what is known as the Axiom of Dependent Choice (the strongest form of AC accepted by constructive mathematics). For the full Axiom of Choice implying a mathematical proposition there is Tychonoff's Theorem (wikipedia actually has a really cool proof of this theorem implying AC) or:

Statement. Let $\{f_\alpha : \alpha \in A\}$ be an equicontinuous and uniformly bounded family of real-valued functions defined on a metric space $M$. Then $f(x):=\sup_{\alpha \in A} \{f_\alpha (x) \}$ is continuous on $M$.

See my post here.

Answer 6

Claim. Suppose that $\{A_n\mid n\in\Bbb N\}$ is a family of sets such that $|A_n|=2$ for all $n$, then $A=\bigcup_{n\in\Bbb N}A_n$ is countable.

Proof. For each $n$, choose $a_n\in A_n$, and let $b_n$ be such that $A_n=\{a_n,b_n\}$. Now take the map $2n\mapsto a_n$ and $2n+1\mapsto b_n$. This is a surjection from $\Bbb N$ onto $A$, and therefore $A$ is countable. $\square$

The proof can be extended for $A_n$ to be any other size of countable set (finite or infinite), but the above is the simplest case. And indeed, it is also necessary, since it is consistent that the axiom of choice fails and there is such a family whose union is not countable.