Prove that the proper subset E of a finite set F can never be equivalent to F.

[StatOnTheSide]

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$^{+}$, 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!

 

[micromass]

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$^{+}$, 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!

What can be said about $F\setminus E$. It is not empty, so it is equivalent to a natural number k. What do you know about the relationship between m, n and k?? Did Halmos prove a result in this direction?

 

[StatOnTheSide]

That is a very interesting direction Micromass. I will try to think about it in that direction.

Halmos makes this statement sort of casually. He does not give any solid reason as to why we can infer that a proper subset can never be equivalent to the set.

Thanks very much for the clue once again Micromass. I will try to think in that direction.

 

[StatOnTheSide]

I was going through Enderton's book and he has the solution to this problem. It essentially invloves the lemma that if a finite set F is equivalent to its subset E, then then the number n to which F is equivalent to is equivalent to its proper subset. This violates an existing theorem which states that that can never happen. Hence F can never be equivalent to its proper subset E.

I assumed that a proper subset E of a finite set F is also finite. It can be proven though.
If F is equivalent to n, then let f:F->n be the one to one correspondence. Then f restricted to E will be a subset of n and hence, equivalent to a natural number k belonging to n. Hence E is also finite and so is every proper subset of a finite set.

I would greatly appreicate any feedback on this.

Also, I have found that in Halmos's book, he keeps mentioning statements and then he says that the proof is straightforward or that it can be inferred from another theorem. He rarely proves such theorems. I spend an awful amount of time trying to figure out the proof by myself. Is this an effective way to study?

I noticed that Hracebeck and Jeck also does the exact same thing. They give exercises which are difficult. Is it a trivial thing to prove that if m<n, then a.m<a.n given that a>0? He gives this as an exercise problem in arithmatic and I am still not sure how to go about proving it.

Hence my question in general is that do you guys SOLVE everything before you move on or do you move on and figure out the solutions later or not even that? Please advise me as to how I should go about studying set theory in the light of all that I said above.

 

[blue_raver22]

To prove that a proper subset E of a finite set F can never be equivalent to F, we must first understand the definition of equivalence between two sets. As mentioned in the statement, two sets E and F are equivalent if there exists a one-to-one correspondence between them. This means that every element in E can be paired with a unique element in F, and vice versa.

Now, let's assume that E is equivalent to F. This means that there exists a one-to-one correspondence between E and F. But since F is a finite set, it can be put in one-to-one correspondence with a natural number, as stated in step 5. This natural number, let's say n, is also equivalent to F.

But then, according to the recursion theorem (step 0), if a is an element of a set X and f is a function from X into X, there exists a function u from ω, the set of natural numbers, into X such that u(0) = a and u{n+) = f(u(n)) for all n in ω.

Now, if we consider the function f(n) = n+, the successor of n, and apply it to the natural number n, we get n+. But this contradicts the fact that n is equivalent to F, as shown in step 4.

Therefore, our assumption that E is equivalent to F leads to a contradiction. Hence, a proper subset E of a finite set F can never be equivalent to F, as stated in the statement.