Construction of Proof: Zorn's lemma implies Axiom of choice

Question

I have come across the prove that [Zorn's Lemma ==> AC] but am confused about the central statement, namely that we can take a set of all choice functions on subsets of X (lets just call it X, I mean the collection of sets we want to prove AC on).

If what we are trying to show is the existence of a choice function on our set X, how can we assume the existence of such a function for subsets of X? References would also be much appreciated

This is the Set of which I cannot prove the existence

The original proof is in German, but this is the link https://de.wikibooks.org/wiki/Beweisarchiv:_Mengenlehre:_Lemma_von_Zorn

Answer 1

You can always choose from a single non-empty set. This requires only Existential Instantiation, which is a rule of first-order logic. So, if $A$ is a non-empty set, that means that $\exists x(x\in A)$ is a true statement, and therefore we can add a new constant symbol $a$ and the axiom $a\in A$. Therefore, $\{\langle A,a\rangle\}$ is a choice function from the family $\{A\}$.

So, certainly, every singleton subset of $X$ admits a choice function. The same argument actually shows that given any $Y\subseteq X$ that admits a choice function and $A\in X$, $Y\cup\{A\}$ also admits a choice function: either $A\in Y$ in which case $Y=Y\cup\{A\}$, or else use Existential Instantiation to get a choice function on $Y$ and an element of $A$ and do as above.

So, if there was a maximal choice function, which is what Zorn's Lemma provides us with, it has to be defined on the entirety of $X$, otherwise, by the above argument, its domain can be extended, contradicting the maximality claim.

Answer 2

It often happens that we can specify a certain property without being able to prove that anything has that property.

So if $U$ is a collection of subsets of a set $X$, we can say that a choice function $c$ for $U$ is a function $U \to X$ such that for all $A \in U$, $f(A) \in A$. Formally, the set $C$ of all choice functions for $U$ can be defined thus: $$ C = \{c: U \to X \mid \forall A \in U. c(A) \in A\} $$

My $C$ is the set $F$ in your linked image if you unwind the definition of $U \to X$ (the set of functions from $U$ to $X$). It is can be seen to be non-empty by the axiom of comprehension.

The set $C$ may or not be empty: it certainly is empty if $\emptyset \in U$. It can be proved without using $AC$ not to be empty if $\emptyset \not\in U$ and $U$ is finite. AC says that it is always non-empty if $\emptyset \not\in U$.

Answer 3

At the beginning of the proof you don't know that such a choice function exists for all subsets of X, but you know that it at least exists for some (for example, even without the axiom of choice you can prove easily that, there is a choice function for all finite subsets of X). Using the fact that choice functions exist on some subsets and that these choice functions satisfy Zorn's Lemma, you get a choice function for X (and thus, actually all subsets of X have choice functions, but you only know this after the proof).