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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s