# Transfinite Induction and the Axiom of Choice

My question is essentially this: Why does the principle of transfinite induction not suffice to show the axiom of choice when the sets to be chosen from are indexed by a well ordered set?

I have read that one can prove the axiom of finite choice from simple induction. You induct on the size of the system of sets you are choosing from and pick an element from each set. I understand this. However, my grasp of the details is sketchy.

1) Why does standard induction alone not suffice to show the axiom of choice for systems of countable sets? Doesn't induction show the truth of the statement for all natural numbers, and therefore for any system of sets that can be indexed by the natural numbers (countable sets)? I know this to be false, but I do not know why.

2) Why can't the above "proof" that induction implies the AoC for countable sets not be repaired by using transfinite induction? Isn't this the purpose of transfinite induction, to allow one to induct on sets of infinite size? Shouldn't transfinite induction suffice to prove the axiom of choice for any system of sets indexed by a well-ordered set?

I am reading Jech right now, but my knowledge of ordinals and transfinite induction is very, very poor, so I would greatly prefer answers with a great amount of explanation and hand-holding.

-

The problem is that you also do a "meta" induction when proving choice for a finite number of sets and this "meta" induction fails in the transfinite or countable case.

To be more clear, the proof of choice for a number of sets sets usually goes something like this (I'm assuming choice is "the product of nonempty sets is nonempty").

Base case is vacuously true (you're given one nonempty set and want to prove it's nonempty).

Next, assume inductively that for any nonempty sets $X_1,...,X_n$, the product $X_1\times...\times X_n$ is nonempty. Now, given $n+1$ sets, $X_1,...,X_{n+1}$, you want to show their product is nonempty. By the induction hypothesis, there is an element $y\in X_1\times....\times X_n$. Also, there is an element $x_{n+1}\in X_{n+1}$ by assumption. Then $\{\{y,x_{n+1}\}, x_{n+1}\} = (y, x_{n+1})$ is an element of the product.

On the meta level, what you're saying by unraveling the induction is "I have $n+1$ sets $X_1,...,X_{n+1}$, and I know there is an element (which is itself a set because we're doing set theory!) in each $X_i$ which I'll call $x_i$. By using the axiom of pairing once, I can form the set $\{x_1,x_2\}$. By using it again, I can form the set $\{\{x_1,x_2\}, x_1\}$, which is the definition of $(x_1,x_2)$. Using the axiom of pairing two more times, I can form $(x_1, x_2, x_3)$. In general (i.e., by induction), by using the axiom of pairing $2(n+1)$ times, I can form the set $(x_1,x_2,...,x_{n+1})$. This set (element) is a member of $X_1\times...\times X_{n+1}$, and hence this product is nonempty!"

What goes wrong as soon as you try to adapt this to the countable or larger setting is on the meta level. Essentially, you'd have to apply the pairing axiom countably (or more) times to create the set $(x_1,...)$ which "should" be in $X_1\times...\times$. But naive set theory has taught us that just because we think something "should" be a set, doesn't mean it should (see, for example, Russel's Paradox). Thus, we at least cannot trust this proof to work in countable or larger settings. Of course, the failure of this approach doesn't mean there is NO way of proving choice from $ZF$, but it's known from other methods that you cannot prove choice from $ZF$ alone.

-
In reference to your last paragraph, what exactly is wrong with applying the axiom of pairing countably many times? I know it is wrong, but why exactly? Why is the "should" in quotes? – Foo Oct 18 '10 at 1:10
It all goes back to the fact that you're interpreting set theory in the framework of first order logic. In first order logic, you only allow formula and proofs of finite length. Here, a "proof" is just a finite sequence of formula where each one is either an axiom (of set theory or first order logic) or follows from previous ones by modus ponens. It's in this framework when you say things like "You can't prove choice from ZF", meaning, there is no "proof" as above using only the axioms of ZF and first order logic, whose final conclusion is AC. – Jason DeVito Oct 18 '10 at 1:14
Of course, this just changes the question to "why does first order logic only use finite length stuff?" or "why do we interpret it in the framework of first order logic instead of some other kind of logic". (Now we're getting well out of my knowledge!) My understanding is that the answer is that we know of many theorems (Godel's compactness theorem, Downward Lowenheim-Skolem, etc) which apply in first order logic but not necessarily in other logics. These theorems are used quite a bit as a way of constructing new models of set theory from old ones, crucial to proving independence results. – Jason DeVito Oct 18 '10 at 1:18
@JasonDeVito I was reading the question and this answer of yours with great interest. I still don't understand why using the axiom of pairing a countable number of times is necessary for the proof in question: all that is needed in the proof of the inductive step is that the axiom of pairing be legittimately used an arbitrary number of times, and this itself can be proven by induction. In other words, I can't see how the problem raised in your last paragraph really applies to the proof in you preceding ones, which to me looks completely sound! – Emilio Ferrucci May 6 '12 at 13:58
@Emilio: The inductive proof works fine for a finite number of times, as you said, but does not work for countable or larger things. Hence, the product of a finite number of nonempty sets is always nonempty, but a product of an infinite number of nonempty sets may be empty. Hence, the axiom of choice automatically holds when trying to pick an element out of a finite number of sets, but for countable or more choices, we need an explicit axiom allowing us to do it. – Jason DeVito May 6 '12 at 22:23

1) Why does standard induction alone not suffice to show the axiom of choice for systems of countable sets? Doesn't induction show the truth of the statement for all natural numbers, and therefore for any system of sets that can be indexed by the natural numbers (countable sets)? I know this to be false, but I do not know why.

As Jason DeVito points out in the comments to his answer, just because something holds for all natural numbers $n$ doesn't mean that it holds for the set $\mathbb{N}$ of natural numbers itself: For a trivial example, every natural number $n$ is finite, yet $\mathbb{N}$ itself is infinite.

2) Why can't the above "proof" that induction implies the AoC for countable sets not be repaired by using transfinite induction? Isn't this the purpose of transfinite induction, to allow one to induct on sets of infinite size? Shouldn't transfinite induction suffice to prove the axiom of choice for any system of sets indexed by a well-ordered set?

A proof by ordinary induction has two parts: a base case and a successor step. A proof by transfinite induction has three parts: a base case, a successor step, and a limit step. The limit step says that for an infinite stage (technically, an ordinal number) $\lambda$, if the property $P$ holds at every stage $\alpha < \lambda$, then it holds at stage $\lambda$. For many properties $P$, the base case and successor step hold but the limit step fails. To revisit the trivial example from above, let's try to prove that every set is finite. Let $P(\alpha)$ be the statement "every set of size $\alpha$ is finite," and let us try to prove that $P(\alpha)$ holds for all $\alpha$ by transfinite induction. In this example the base case and successor step hold trivially, but the induction will fail at the very first limit step.

For the less trivial example of the axiom of choice, let $P(\alpha)$ be the statement "every sequence of sets of length $\alpha$ has a choice function." As suggested in the question, the base case and induction step are trivial. But the limit step fails again: Let $(A_i : i \in \mathbb{N})$ be an infinite sequence of sets and suppose by the induction hypothesis that for every finite $n$, the proper initial segment $(A_i : i < n)$ of the sequence has a choice function. The natural attempt to define a choice function $f$ for $(A_i : i \in \mathbb{N})$ would be to take choice functions $f_n$ for $(A_i : i < n)$ and combine them in some way. But first we would have to choose a choice function $f_n$ for each finite $n$, which is just as hard as the original problem! So transfinite induction doesn't help us at all.

-