Register to reply

Axiom of Choice

by moo5003
Tags: axiom, choice
Share this thread:
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
Final pieces to the circadian clock puzzle found
A spray-on light show on four wheels: Darkside Scientific
How an ancient vertebrate uses familiar tools to build a strange-looking head
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?
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.

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