Proving Set Theory: Showing B is a Subset of S(n)

In summary, the assumption that for every infinite subset B' of B there is some n for which B' intersect S(n) is infinite is not true, and so B is not a subset of any S(N).
  • #1
moo5003
207
0

Homework Statement



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

The Attempt at a Solution



I'm a little stuck on even starting this proof (not to mention from just thinking about it I can't 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 don't know how to proceed. Any suggestions on how to start this proof would be greatly appreciated.
 
Physics news on Phys.org
  • #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:
  • #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:
  • #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.
 

1. What is Set Theory?

Set Theory is a branch of mathematics that deals with the study of sets, which are collections of objects. It is used to define relationships between different sets and to analyze the properties of these sets.

2. What does it mean for B to be a Subset of S(n)?

When we say that B is a subset of S(n), it means that all the elements in B are also elements of S(n). In other words, B is a smaller set that is contained within the larger set S(n).

3. How do you prove that B is a Subset of S(n)?

To prove that B is a subset of S(n), you need to show that every element in B is also an element of S(n). This can be done by using the definition of a subset, which states that if every element in one set is also in another set, then the first set is a subset of the second set.

4. What are the different methods of proving set theory?

There are several methods of proving set theory, including direct proof, proof by contradiction, and proof by mathematical induction. Direct proof involves using logical steps to show that a statement is true. Proof by contradiction involves assuming the opposite of what you are trying to prove and showing that it leads to a contradiction. Proof by mathematical induction is a method used to prove statements about a set of numbers that follow a specific pattern.

5. Why is it important to prove set theory?

Proving set theory is important because it helps to establish the validity of mathematical statements and theories. Set theory is the foundation of many mathematical concepts and is essential for solving problems in various fields such as computer science, physics, and engineering. Proving set theory also helps to ensure the accuracy and consistency of mathematical reasoning and arguments.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
1
Views
533
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
463
  • Calculus and Beyond Homework Help
Replies
1
Views
454
  • Calculus and Beyond Homework Help
Replies
3
Views
467
Replies
2
Views
259
  • Calculus and Beyond Homework Help
Replies
10
Views
831
  • Calculus and Beyond Homework Help
Replies
3
Views
504
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top