In a previous post (entitled ‘A word on cardinality – diagonal arguments‘) I discussed the idea of different sizes of infinity. We saw that two sets were the of same size, or ‘cardinality’, if there was a bijection between them. I showed that there was a bijection between and , but that there was no such bijection between and . In this way we saw that and have different cardinality. A natural question now might be, are there any other sizes of infinity? It is that question that this post addresses.
If there is a bijection beween sets and we write . If there is a one-to-one function from to we write $latex |A| \leq |B|$. If there is a one-to-one function from to but no bijection we write .
Definition: Given a set , the power set of , is the set of all subsets of .
As an example, if is a finite set of size then .
Proposition: There is no bijection between and .
Proof: Assume for a contradiction that there exists a bijection,
Consider the following set
Certainly is a a subset of , and thus, since we have assumed that is a bijection, there must exist such that . And now comes the contradiction, for we ask, is ? If , then by definition of we have that , a contradiction. The only other option is that , but this means that , by the definition of , a clear contradiction. Since it must be the case that either or , and both lead to a contradtion, we are done.
Since there is no bijection between and , and clearly there is a one-to-one map from into , as each element of forms a singleton subset of itself, we have that .
We can now use this proposition to answer our original question in quite a spectacular manner. Not only are there more then the two cardinalities of infinity that we have previously seen, there are actually infinitely many! Indeed we obtain a hierarchy of infinities,