Comparing Cardinalities

We already know that two finite or infinite sets $$A$$ and $$B$$ have the same cardinality (that is, $$\left| A \right| = \left| B \right|$$) if there a bijection $$A \to B.$$ Now we want to learn how to compare sets of different cardinalities.

If $$A$$ and $$B$$ are finite sets , then the relation $$\left| A \right| \lt \left| B \right|$$ means that $$A$$ has fewer elements than $$B.$$ For infinite sets, we can define this relation in terms of functions.

We say that the cardinality of $$A$$ is less than the cardinality of $$B$$ (denoted by $$\left| A \right| \lt \left| B \right|$$) if there exists an injective function $$f : A \to B$$ but there is no surjective function $$f : A \to B.$$ This is illustrated by the following diagram:

The set $$A$$ has cardinality less than or equal to the cardinality of $$B$$ (denoted by $$\left| A \right| \le \left| B \right|$$) if there exists an injective function $$f : A \to B.$$ Note that in the case of a non-strict inequality, the function $$f$$ can be either surjective or non-surjective. If $$f$$ is surjective, then it is bijective and we have $$\left| A \right| = \left| B \right|.$$ Respectively, if $$f$$ is non-surjective, we get the strict relation $$\left| A \right| \lt \left| B \right|.$$

For example, compare the cardinalities of $$\mathbb{Q}$$ and $$\mathbb{R}$$. Let the mapping function be $$f\left( x \right) = x,$$ where $$x \in \mathbb{Q}.$$ It is clear that the function $$f$$ is injective. But it is not surjective, because given any irrational number in the codomain, say, the number $$\pi,$$ we have $$f\left( x \right) \ne \pi$$ for any $$x \in \mathbb{Q}.$$ Hence,

$\left| {\mathbb{Q}} \right| \lt \left| {\mathbb{R}} \right|.$

Since $$\left| {\mathbb{N}} \right| = \left| {\mathbb{Z}} \right| = \left| {\mathbb{Q}} \right| = {\aleph_0},$$ we obtain

${\aleph_0} \lt \left| {\mathbb{R}} \right|.$

Some other important facts about the cardinality of sets:

• If $$\left| A \right| \le \left| B \right|$$ and $$\left| B \right| \le \left| C \right|,$$ then $$\left| A \right| \le \left| C \right|$$ (transitivity property).
• If $$A \subseteq B,$$ then $$\left| A \right| \le \left| B \right|.$$
• If $$A$$ is an infinite set, then ${\aleph_0} = \left| \mathbb{N} \right| \le \left| A \right|.$

Solved Problems

Click or tap a problem to see the solution.

Example 1

Prove that the set of complex numbers $$\mathbb{C}$$ is uncountable.

Example 2

Let $$A$$ and $$B$$ be non-empty sets. Show that $$\left| A \right| \le \left| {A \times B} \right|.$$

Example 3

Prove that if a subset $$A \subseteq B$$ is uncountable, then the entire set $$B$$ is also uncountable.

Example 4

A finite set $$A$$ of $$n$$ elements has the property $\left| {\mathcal{P}\left( {{A^2}} \right)} \right| \gt \left| {\mathcal{P}\left( {\mathcal{P}\left( A \right)} \right)} \right|.$ Find the cardinality of $$A.$$

Example 1.

Prove that the set of complex numbers $$\mathbb{C}$$ is uncountable.

Solution.

The set of complex numbers is defined by

$\mathbb{C} = \left\{ {a + bi \mid a,b \in \mathbb{R}} \right\},$

where $$i = \sqrt { – 1}$$ is the imaginary unit.

Every real number $$a \in \mathbb{R}$$ can be mapped to the complex number $$a = a+0i$$ using the function $$f\left( x \right) = x + 0i.$$ The function $$f: \mathbb{R} \to \mathbb{C}$$ is injective, but not surjective. Therefore

$\left| \mathbb{R} \right| \le \left| \mathbb{C} \right|.$

Since $$\mathbb{R}$$ is uncountable, then the set $$\mathbb{C}$$ is also uncountable.

Example 2.

Let $$A$$ and $$B$$ be non-empty sets. Show that $$\left| A \right| \le \left| {A \times B} \right|.$$

Solution.

To construct an injection from $$A$$ to $$A \times B$$ we select an arbitrary element $$b_0 \in B.$$ The mapping function $$f: A \to A \times B$$ is given by

$f\left( a \right) = \left( {a,{b_0}} \right),$

where $$a \in A.$$

It is clear that the function $$f$$ is injective. Therefore

$\left| A \right| \le \left| {A \times B} \right|.$

Example 3.

Prove that if a subset $$A \subseteq B$$ is uncountable, then the entire set $$B$$ is also uncountable.

Solution.

Since $$A$$ is a subset of $$B,$$ then for any $$a \in A,$$ we have $$a \in B.$$ The mapping function $$f: A \to B$$ can be defined in the form

$f\left( a \right) = a.$

It is obvious that the function $$f$$ is injective. Then

$\left| A \right| \le \left| B \right|.$

By condition, the subset $$A$$ is uncountable, so $${\aleph_0} \lt \left| A \right|.$$ By the transitivity property, this yields

${{\aleph_0} \lt \left| A \right| \le \left| B \right|,}\;\; \Rightarrow {{\aleph_0} \lt \left| B \right|,}$

that is, the set $$B$$ is uncountable.

Example 4.

A finite set $$A$$ of $$n$$ elements has the property $\left| {\mathcal{P}\left( {{A^2}} \right)} \right| \gt \left| {\mathcal{P}\left( {\mathcal{P}\left( A \right)} \right)} \right|.$ Find the cardinality of $$A.$$

Solution.

Suppose $$A$$ has $$n$$ elements. Then the Cartesian square $$A^2$$ has $$n^2$$ elements. The cardinalities of the power sets are given by

${\left| {\mathcal{P}\left( {{A^2}} \right)} \right| = {2^{{n^2}}},\;\;}\kern0pt{\left| {\mathcal{P}\left( {\mathcal{P}\left( A \right)} \right)} \right| = {2^{{2^n}}}.}$

We find $$n$$ by solving the inequality

${{2^{{n^2}}} \gt {2^{{2^n}}},}\;\; \Rightarrow {{n^2} \gt {2^n},}$

where $$n \in \mathbb{Z}^{+}.$$

This inequality has a unique solution $$n = 3,$$ so $$\left| A \right| = 3.$$

We also calculate the cardinalities of the power sets:

${\left| {\mathcal{P}\left( {{A^2}} \right)} \right| = {2^{{n^2}}} }={ {2^9} }={ 512,}$

${\left| {\mathcal{P}\left( {\mathcal{P}\left( A \right)} \right)} \right| = {2^{{2^n}}} }={ {2^8} }={ 256.}$