Axiom of Choice

moo5003

1. The problem statement, all variables and given/known data

Assume that S is a function with domain w such that S(n) is a subset of S(n^+) for each n in w. (Thus S is an increasing sequence of sets.) Assume that B is a subset of the union of S(n)'s for all n such that for every infinite subset B' of B there is some n for which B' intersect S(n) is infinite. Show that B is a subset of some S(n).

Elements of Set Theory, Enderton H.
Page 158 Question: 25

3. The attempt at a solution

I'm a little stuck on even starting this proof (not to mention from just thinking about it I cant seem to reason why it should be true).

I know I need to use the axiom of choice (Its in the axiom of choice chapter). I'm leaning toward a proof by contradiction though I dont know how to proceed. Any suggestions on how to start this proof would be greatly appreciated.

johnshade

Try this; I think it's a possible direction. Suppose the assumption (i.e. that for every infinite subset B' of B there is some n for which B' intersect S(n) is infinite) is true, but B is not a subset of any S(N). Then for any S(n), Ex (x is an element of B but x is not an element of S(n). Try constructing a subset B* of B as follows:

Let B*= {C(0), C(1)...} where:

C(0) is an element of B but not S(0).

Now look for the first S(n) such that C(0) is in S(n). Let C(1) be an element of B that is not in S(1). Show that (i) there will always be such a first S(n); (ii) there will always be such a C(1) and (iii) C(1) is not = C(0).

Repeat and look at the set of all C(n)s. Is it infinite? Does it satisfy the assumption?

moo5003

I'm trying to set up your proof, though it assumes that B is infinite. If B is finite how would I say with rigor that there must be some maximum S(n) therebye making B = S(n) for some n?

I think I have worked out the proof as you described. I'll work out the wording and post it when I get the chance.

johnshade

Remember that since B is a subset of U(S(n)), every element of B must be an element of some S(n). So if B is finite, it must be a subset of some finite union of S(n)s. And what do you know about a finite union of S(n)s where the sequence S(n) is increasing and infinite? (By the way, as the problem is stated, it's not necessary that B = S(n) for some n, and in general there's no reason I can see why it should be.)

There's probably a way to make this easier with Zorn's Lemma, but I'm too rusty/lazy to set it up.