Jech's axiom of choice, problem 2 first chapter

Question

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.

Answer 1

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$.