- #1
StatOnTheSide
- 93
- 1
Homework Statement
Statement: A set F can never be equivalent to its proper subset E
This statement appears in Halmos's Naive set theory in the chapter 13. Arithmatic. He arrives at this statement through the following steps
0. In the previous chapter, he proves the recusrsion theorem which states that "If a is an element of a set X, and if f is a function from X into X, then there exists a function u from ω, the set of natural numbers, into X such that u(0) = a and such that u{n+) = f(u(n)) for all n in ω."
1. In this chapter, he first defines equivalence between two sets E and F. Two sets E and F, not necessarily subsets of a natural number, are equivalent if there exists a one-to-one correspondence between them.
2. He then shows that every proper subset of a natural number is equivalent to some natural number.
3. He then states that the set of natural numbers can be put in one-to-one correspondence with the set of non-zero natural numbers.Just define f(n)=n[itex]^{+}[/itex], the successor of n.
4. He then states and proves that a natural number is not equivalent to its proper subset.
5. He then defines a finite set as any set which can be put in one-to-one correspondence with a natural number. Othewise the set is said to be infinite.
6. He then states and proves that a finite set can be equivalent to at most one natural number.
At this point, he suddenly states that "We may infer that a finite set is never equivalent to a proper subset; in other words, as long as we stick to finite sets, the whole is always greater than any of its parts."
Homework Equations
The Attempt at a Solution
I can see that if E is a proper subset of F, and if E is equivalent to m and F to n, then (as shown in the book) m can be shown to be equivalent to n. I have the proof that if two natural numbers are equivalent, they are equal. But beyond this point, I cannot see how you can arrive at a contradiction or something.
In other words, how Halmos "inferred" that a proper subset can never be equivalent to itself is not clear to me. I am quite sure that we have to use some or all of the theorems above to arrive at this statement. I am not sure how though.
I would really really appreciate your input in this matter. Please help.
Thanks in advance!
Last edited: