# More on cardinality

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 $\mathbb{N}$ and $\mathbb{Q}$, but that there was no such bijection between $\mathbb{N}$ and $\mathbb{R}$. In this way we saw that $\mathbb{Q}$ and $\mathbb{R}$ 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 $A$ and $B$ we write $|A| = |B|$. If there is a one-to-one function from $A$ to $B$ we write $latex |A| \leq |B|$. If there is a one-to-one function from $A$ to $B$ but no bijection we write $|A| < |B|$.

Definition: Given a set $A$, the power set of $A$$\mathcal{P}(A)$ is the set of all subsets of $A$.

As an example, if $A$ is a finite set of size $n$ then $|\mathcal{P}(A)|=2^n$.

Proposition: There is no bijection between $A$ and $\mathcal{P}(A)$.

Proof: Assume for a contradiction that there exists a bijection,

$f: A \rightarrow \mathcal{P}(A)$

Consider the following set

$\mathcal{Z}:= \{ a \in A : a \notin f(a) \}$

Certainly $\mathcal{Z}$ is a a subset of $A$, and thus, since we have assumed that $f$ is a bijection, there must exist $x \in A$ such that $f(x)=\mathcal{Z}$. And now comes the contradiction, for we ask, is $x \in \mathcal{Z}$? If $x \in \mathcal{Z}$, then by definition of $\mathcal{Z}$ we have that $x \notin f(x)=\mathcal{Z}$, a contradiction. The only other option is that $x \notin \mathcal{Z}=f(x)$, but this means that $x \in \mathcal{Z}$, by the definition of $\mathcal{Z}$, a clear contradiction. Since it must be the case that either $x \in \mathcal{Z}$ or $x \notin \mathcal{Z}$, and both lead to a contradtion, we are done. $\Box$

Since there is no bijection between $A$ and $\mathcal{P}(A)$, and clearly there is a one-to-one map from $A$ into $\mathcal{P}(A)$, as each element of $A$ forms a singleton subset of itself, we have that $|A| < |\mathcal{P}(A)|$.

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,

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$