uniqueness of cardinality
The cardinality of a set is unique.
We will verify the result for finite sets only. Suppose is a finite set with cardinality and . Then there exist bijections and . Since is a bijection, it is invertible, and is a bijection. Then the composition is a bijection from to . We will show by induction on that . In the case we have , and it must be that as well, whence . Now let , and suppose that, for all , the existence of a bijection implies . Let and suppose is a bijection. Let , and notice that . Since is onto there exists some such that . There are two cases to consider. If , then we may define by for all , which is clearly a bijection, so by the inductive hypothesis , and thus . Now suppose , and define by
We first show that is one-to-one. Let , where . First consider the case where neither nor is equal to . Then, since is one-to-one, we have
In the case , again because is one-to-one, we have
Similarly it can be shown that, if , , so is one-to-one. We now show that is onto. Let . If , then we may take to have . If , then, because is onto, there exists some such that , so . Thus is onto, and our inductive hypothesis again gives , hence . So by the principle of induction, the result holds for all . Returning now to our set and our bijection , we may conclude that , and consequently that the cardinality of is unique, as desired. ∎
There does not exist a bijection from a finite set to a proper subset of itself.
Without a loss of generality we may assume the proper subset is nonempty, for if the set is empty then the corollary holds vacuously. So let be as above with cardinality , a proper subset of with cardinality , and suppose is a bijection. By hypothesis there exist bijections and ; but then is a bijection from to , whence by the preceding result , contrary to assumption. ∎
The corollary is also known more popularly as the pigeonhole principle.
|Title||uniqueness of cardinality|
|Date of creation||2013-03-22 16:26:52|
|Last modified on||2013-03-22 16:26:52|
|Last modified by||mathcam (2727)|