# Comparing Cardinalities

## 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}}},\;\;\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.$