Theorem 5.3: No set is equivalent to a proper subset of itself.

Proof: Suppose there is a set which is equivalent to a proper subset of itself. Since all sets we are considering are finite, such a set would have a cardinality which would be a natural number n1. Then

{ n < n1 | There is a set with n elements which is equivalent to a proper subset of itself}

would be a nonempty set of natural numbers, and by Theorem 5.1, the Well Ordering Principle, it would have a smallest element no. That would mean that there would be a set S with no elements which was equivalent to a proper subset of itself, say S1.

and there is a function

which is one to one and onto by Definition 3.8.

Since the empty set has no proper subsets, S is not empty. Let

and let

Define

by

g(x1) = x2

g(x2) = x1

and

g(x) = x

for all other x in S. Then g is one to one and onto, so by Theorem 3.4

is one to one and onto and

fg(x2) = x2.

Define

So = S - {x2}

and

S2 = S1 - {x2}

S2 is a proper subset of S0, and fg restricted to S0 will define a one to one correspondence between S0 and S2. But, by Theorem 4.9, S0 has fewer elements than S which was the smallest set which was equivalent to a proper subset, and that is a contradiction.