1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Axiom of Choice

  1. Apr 14, 2008 #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. Apr 15, 2008 #2
    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. Apr 16, 2008 #3
    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. Apr 16, 2008 #4
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook