Axiom of Choice

  1. 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.
     
  2. jcsd
  3. 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?
     
    Last edited: Apr 15, 2008
  4. 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.
     
    Last edited: Apr 16, 2008
  5. 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.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook