Axiom of Choice

by moo5003
Tags: axiom, choice
moo5003 is offline
Apr14-08, 06:47 PM
P: 207
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.
Phys.Org News Partner Science news on
Internet co-creator Cerf debunks 'myth' that US runs it
Astronomical forensics uncover planetary disks in Hubble archive
Solar-powered two-seat Sunseeker airplane has progress report
johnshade is offline
Apr15-08, 03:32 PM
P: 13
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 is offline
Apr16-08, 01:13 AM
P: 207
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 is offline
Apr16-08, 09:38 AM
P: 13

Axiom of Choice

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.

Register to reply

Related Discussions
Do you believe in the Axiom of Choice? General Math 9
Axiom of choice, yay! Set Theory, Logic, Probability, Statistics 2
Axiom of choice Set Theory, Logic, Probability, Statistics 3
the axiom of choice. Help!!! General Math 9
The Axiom of Choice Set Theory, Logic, Probability, Statistics 9