# 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$

## 4 responses to “More on cardinality”

1. So do you know how many infinities there are? Are they in bijection with the natural numbers?

• Hello Joe!

Good question! The answer depends on which set of axioms you choose to use. For example in Zermelo set theory the number of different sizes of infinity is aleph 0, but if you add the axiom of replacement then it can be shown that it is aleph 1.

2. if It would in more detail & with more images… I would have been better.

• Care to elaborate? I have intentionally tried to keep it brief.