2
$\begingroup$

I understand how we can show the existence of a choice function for any (finite or infinite) collection of (finite or infinite) subsets of, say, $\mathbb{N}$ or $\mathbb{Z}$ without using the axiom of choice, by showing that a well-ordering over the union of sets in the collection exists.

What I don't see though is how to do the same for what appears to be a much simpler case: a (possibly infinite) collection of finite sets, where nothing else is said about the sets other than that each of them is finite.

I would need to show a well-ordering exists over the union of those sets, but since they were not explicitly defined to be subsets of $\mathbb{N}$ or $\mathbb{Z}$, I first need to show the following, for example:

(i) there exists a surjection from $\mathbb{N}$ to $\bigcup X_i$ for an arbitrary collection of finite sets $X_i$

Correct so far?

Alternatively, I'm on the wrong track, and this is precisely a case that (unintuitively for me then) requires application of the axiom.

If so, I suppose I don't see why (i) wouldn't hold, when it seems that any definition within ZF of a finite number of elements is equivalent (in some sense to be made precise) to a finite subset of $\mathbb{N}$, so, given that the union of a collection of finite subsets of $\mathbb{N}$ is a subset of $\mathbb{N}$, the required well-ordering exists.

Improve this question
$\endgroup$
  • $\begingroup$ This requires choice, because it is possible for a countable union of finite sets to be uncountable (not to mention an arbitrary collection). Just think of the famous example of Russell's Socks. See math.stackexchange.com/questions/408636/… $\endgroup$ – Hayden May 19 '15 at 15:43
  • $\begingroup$ Of course, when I mean "possible", I mean in the sense that there is a model in which it occurs, assuming ZF is consistent. $\endgroup$ – Hayden May 19 '15 at 15:49
2
$\begingroup$

You're right. The axiom of choice is needed, albeit in a limited form.

It is consistent that there is a countable collection of pairs, $P_n$ such that there is no choice function from the $P_n$'s themselves. In particular, $\bigcup P_n$ is not a countable set, and in fact cannot even be linearly ordered.

But since it is consistent with $\sf ZF$ that the axiom of choice holds, we can't really give a proper and concrete definition for such a set. We can just prove that if $\sf ZF$ is consistent, then there is a model of $\sf ZF$ in which that happens, and other models of $\sf ZF$ in which it doesn't.

(By the way, you probably wanted to say that $\bigcup_i X_i$ is a countable union of finite sets; otherwise it's not true in $\sf ZFC$ either. Just look at $X_i=\{i\}$ for $i\in\Bbb R$, then $\bigcup_{i\in\Bbb R}X_i=\Bbb R$ and there is no surjection from $\Bbb N$ onto $\Bbb R$.)

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer, and the correction on the countable union as well. I'm still trying to understand though where the following informal argument falls apart, which to me seems to imply the well-ordering of a countable collection of pairs $P_n$: Each element of each pair $P$ can be associated with an element of $\mathbb{N}$, so we can represent each pair as set of (two) numbers. The (countable) union of these representations as numbers is a subset of $P_n$, hence a well-ordering exists. $\endgroup$ – Bert Zangle May 19 '15 at 16:30
  • $\begingroup$ @zanglebert But you had to choose such an injection into $\mathbb{N}$ for each $P_n$ (even ignoring the need for each injection to have an image disjoint from the others). That requires choice. $\endgroup$ – Hayden May 19 '15 at 17:27
  • $\begingroup$ @zanglebert: As Hayden said, there are many (read: more than one) injection. So which one do you use? And you have to pick one for infinitely many sets. And there lies the axiom of choice. If the union of the finite sets can be linearly ordered, then there is a canonical way of doing that, but who said that it could be, when not assuming choice? $\endgroup$ – Asaf Karagila♦ May 19 '15 at 17:28
1
$\begingroup$

This is closely related to König's lemma, which is equivalent in ZF to a choice principle for countable collections of finite sets. The Wikipedia article for König's lemma has a couple references. Quoting Wikipedia,

In particular, when the branching at each node is done on a finite subset of an arbitrary set not assumed to be countable, the form of König's lemma that says "Every infinite finitely branching tree has an infinite path" is equivalent to the principle that every countable set of finite sets has a choice function

Improve this answer
$\endgroup$
  • $\begingroup$ You can also show that this is equivalent to the statement that a countable union of finite sets is countable (the proof is simple; in one direction it is a consequence of the choice principle, allowing us to choose a linear ordering of each finite set, since there are only finitely many for each finite set; the other direction follows from the fact that you can show that every $\omega$-tree is countable and thus has a branch). $\endgroup$ – Asaf Karagila♦ Jun 1 '15 at 21:02

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.