29
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This question is not very clear? What is your specific method of proof of the axiom of choice that you're trying to understand why fails? $\endgroup$
    – Timothy
    Apr 12, 2018 at 18:47

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
14
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 18, 2010 at 1:14
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 18, 2010 at 1:18
  • 2
    $\begingroup$ @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. $\endgroup$ May 6, 2012 at 22:23
  • 1
    $\begingroup$ @Emilio: Proving something for an arbitrary large but finite thing is different from proving something for an infinite thing. Consider the statement "n is finite", where we take as "finite", for example, "does not surject on $\mathbb{N}$". You could probably prove by induction that "n is finite" for all natural numbers $n$. It does not follow that an $\mathbb{N}$ is finite, of course. $\endgroup$ May 7, 2012 at 0:05
  • 1
    $\begingroup$ @Jason I wouldn't worry about which answer the OP accepts. It looks like he/she and others found your answer useful. I just thought there should also be an answer explicitly addressing part 2 of the question regarding transfinite induction, because without doing so, it's difficult to give a rigorous answer beyond "induction just doesn't work that way." $\endgroup$ Jul 6, 2014 at 20:33
15
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hello, thanks for your answer. Regarding the last part of your answer, could you please tell me that why it is 'hard" to choose a choice function $f_n$ for each $n$ ? and in fact, why should I choose a function for each $n$ ? I think that for example, if we are considering the proof for $n$ given it is true for all $i< n$, then by simply set $f_n(i) = f_(n-1)(i)$ for $i \lt n$ and $f_n(i) = x$ where $x arbitrary \in A_n$ (we know that $A_n$ is not empty). Then we are good, there exists a choice function for the "next value". $\endgroup$ Jul 4, 2023 at 17:35
  • $\begingroup$ When you say "we are good, there exists a choice function for the next value" you are saying there is no problem with the successor step of the induction. I agree. There is only a problem with the limit step of the induction. What follows from the base case and successor step is just that for every natural number n there is a choice function for $(A_i : i < n)$. Rephrasing slightly, for every natural number n there is a choice function $f$ for $(A_i : i < n)$. However, it would be misleading to say that for every natural number n there is a choice function $f_n$ for $(A_i : i < n)$... $\endgroup$ Aug 3, 2023 at 3:44
  • $\begingroup$ because the notation $f_n$ only makes sense if you have a function $n \mapsto f_n$ that assigns to each natural number n a particular choice of choice function for $(A_i : i < n)$, i.e. it only makes sense if you have an infinite sequence of choice functions $(f_n : i \in \mathbb{N})$. If we had such a sequence, its union $F = \bigcup_{i \in \mathbb{N}} f_i$ would be a choice function for $(A_i : i \in \mathbb{N})$, completing the limit step. But to show the existence of such a sequence $(f_n : i \in \mathbb{N})$ in the first place, you would still need the axiom of choice. $\endgroup$ Aug 3, 2023 at 4:35
  • $\begingroup$ To summarize: the axiom of choice is needed to justify the existence of an infinite sequence consisting of arbitrary choices (whereas for choices following some rule, we could use the axiom of replacement instead.) The last part of my answer described a method that superficially appears to avoid relying on the axiom of choice, but it only appears that way because it uses notation suggesting that an infinite sequence exists without actually showing that does (which is the step the axiom of choice would be needed for.) $\endgroup$ Aug 3, 2023 at 4:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .