Suppose at each step $n$ of a proof by induction, we have a set $X_n$. Also, $X_{n} \subseteq X_{n+1}$. Is induction enough to give us $\bigcup_{n \in \mathbb{N}} X_n$? Or rather, when is it enough?

For example, in the proof of Konigs' Lemma, the answer is no. In it, we are trying to prove that an tree with countably infinite vertices and finite levels has a path of infinite length. At each step of the induction, we have a path of length $n$. We can see this as a set $X_n$ of nodes of the tree. The next path/set $X_{n+1}$ is chosen such that $X_n \subseteq X_{n+1}$. To get the path of infinite length, $\bigcup_{n \in \mathbb{N}} X_n$, we need the axiom of countable choice.

On the other hand, in the proof of the uniqueness of the Rado graph, for each $n$, we have a graph homomorphism from a vertex set $V_n$ to another set of vertices $W$, $\varphi_n: V_n \to W$, such that $V_{n} \subseteq V_{n+1}$. Then, we union these $\varphi = \bigcup_{n \in \mathbb{N}} \varphi_n$ to get an isomorphism between the two graphs with vertex sets $V$ and $W$ respectively. This does not require the axiom of choice.

What is the key difference between these two examples that makes one require the axiom of choice while the other doesn't?

  • $\begingroup$ In the proof of König's lemma, at each step, you have many candidates for $X_n$, and it matters which one you "choose". Moreover the set of candidates for $X_{n+1}$ will depend on your "choice" of $X_n$. $\endgroup$ – Zhen Lin Jul 14 '14 at 23:10
  • $\begingroup$ That's the key point between talking about "infinite" and "countably infinite" (or "well-orderably infinite") in the context of $\sf ZF$. $\endgroup$ – Asaf Karagila Jul 14 '14 at 23:24
  • $\begingroup$ @ZhenLin: but in the proof of the uniqueness of the Rado graph, we also have many candidates for $V_n$ don't we? And the set of candidates for $V_{n+1}$ depends on our "choice" of $V_n$. $\endgroup$ – Jean Valjean Jul 15 '14 at 1:47
  • 1
    $\begingroup$ @Jean: But you can always pick $V_{n+1}$ to be the least one possible, in some canonical well-ordering of finite subsets of the graph (which exists, since the graph is countable). $\endgroup$ – Asaf Karagila Jul 15 '14 at 4:44
  • $\begingroup$ @AsafKaragila: yeah. and for Konigs lemma, IF the tree has countably infinite many vertices, we can do the same, and so no choice needed (even though we still have many candidates, which depends on our choice). the difference is when we allow the tree to have uncountable number of vertices. and that is the key difference here isn't it? $\endgroup$ – Jean Valjean Jul 15 '14 at 12:42

If your sequence is given, then $\bigcup_{n\in\omega}X_n$ exists, yes. It is enough. If you have an inductive definition which goes from a given $X_n$ to $X_{n+1}$, then induction itself is not enough to give you the wanted sequence, and therefore its union. You need to show that you can get "through the induction" using very particular choices, which amounts to proving that the sequence that you want exists.

And more generally if you have a sequence of sets, this really means that there is a function whose domain is $\omega$ (or some other index set) and its range is some family of sets. By replacement axioms the range of the function is a set as well, and by the axiom of union, its union exists.

Therefore if you have $X_n$ for $n\in\omega$, then $\bigcup_{n\in\omega}X_n$ is a set as well.

Note that the difficulty where the axiom of choice gets into the proofs is that the induction may not have a "clear choice". For example, you can't always take the least possible "next step" if the set of options is not well-ordered. And the axiom of choice allows you to chuck all that into a choice function which guides the way you choose the next step.

In the two examples that you brought up, the key difference is that in Rado graph we assume that the graph is countable. So we have a well-ordering of its vertices to give us the choice we need.

If Koenig's lemma is phrased as "Every countable tree ..." then you don't need the axiom of choice either, and if you formulate Rado graph as something which doesn't include explicitly countability (or can prove it directly), then the axiom of choice will also be needed. In particular one can arrange for a random graph which embeds every finite graph, whose cardinality is not well-orderable, and in fact Dedekind-finite.

  • $\begingroup$ Looks like thats my mistake. Konig's Lemma for trees with countably infinite vertices can be proven without choice. Thanks! (ref: en.wikipedia.org/wiki/…) By the way, this is an amazing explanation! $\endgroup$ – Jean Valjean Jul 15 '14 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.