I have a question stemming from Jech's book on the axiom of choice., chapter 1 exercise 2. We are asked to show that a family of sets of natural numbers has a choice function. Now the version of the axiom of choice we are given in this chapter is the following: let F be a family of sets X. Then there exists an f(X) for every such X in F.

  1. I can't decide whether he means the more general countable case, or the more particular finite case. But if finite, I would think he would say so. And it would be an inductive proof. But if countable, I would think he would present the countable axiom of choice (axiom of dependent choice) in that chapter. But he doesn't do that either.

  2. The proof I have, for the finite case, is an induction on the cardinality of the family F.

Basis: |F| = 1, I.e. There is one set in the family. Since the family is finite, regardless of whether |X| for X in F is countable or finite, we can e.g. order X so that X has a Least element and that element will be the choice function on X (this follows from the fact that there exists a bijection between a finite or countable set and the naturals which are strictly ordered). .

Induction step: Suppose claim holds for m, to show m+1. Then F has m choice functions or {f(X1) ... f(Xm)}, as |F| = m. Now let F be a subfamily of F', and suppose for contradiction that F' has no choice function f', with |F'| = m + 1. Now if a choice function f' for F' did exist, it would agree with f for subfamily F, and there is such an f by hypothesis. But this latter contradicts the fact that F' has no choice function at all, and so for no subfamily could there be an f' agreeing with f. .

This proof looks like it could be correct to me, but I'm not entirely sure it's adequate for the claim at hand -- I took my best guess and went with it.


No, your idea is not enough.

For two reasons.

  1. Proof for every finite case does not imply the proof for the countable case.
  2. There are collections of sets of natural numbers which are uncountably infinite.

HINT: Note that $<$ is a well-order on the natural numbers, therefore every non-empty set has a least element. Now you can define, uniformly, a choice function for all the non-empty subsets of $\Bbb N$.

  • 1
    $\begingroup$ The second reason points to the fact that no induction should be used. At all. $\endgroup$ – Asaf Karagila Jan 26 '14 at 23:17
  • 1
    $\begingroup$ No, you're going at it the wrong way. The fact that each set is finite or countable doesn't mean that there is a choice function. Just use the definition of a well-ordering, you already have - but you wrapped it up in a lot of unnecessary (and somewhat mistaken) claims at first. $\endgroup$ – Asaf Karagila Jan 26 '14 at 23:37
  • 1
    $\begingroup$ No, you're still doing it wrong. The well-ordering principle (for the natural numbers, using the statement "every set can be well-ordered" is using the axiom of choice directly) doesn't say that every set of natural numbers can be well-ordered. It says that every non-empty set of natural numbers has a least element. That's what you need. It is consistent without the axiom of choice that there is a countable family of pairs without a choice function, that is a family which can be well-ordered, and each of its members can be well-ordered and yet the family does not admit a choice function. $\endgroup$ – Asaf Karagila Jan 28 '14 at 22:58
  • 1
    $\begingroup$ No, take $F$ to be the collection of all non-empty sets then $Z=\Bbb N$. You don't want that. What you do want is a choice function. There is a formulation of the axiom of choice where given a family of sets there is $T$ meeting each of those at exactly one point, but you have to require that the family is made of pairwise disjoint sets. $\endgroup$ – Asaf Karagila Jan 28 '14 at 23:15
  • 1
    $\begingroup$ You don't need to define $Z$. At all. Again, in a lot of cases this $Z$ is actually $\Bbb N$ itself. What use is it in that case? You just define $F$. Directly. $F(X)=\min X$. $\endgroup$ – Asaf Karagila Jan 29 '14 at 1:18

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.