Comparing Cardinalities
Solved Problems
Example 1.
Prove that the set of complex numbers \(\mathbb{C}\) is uncountable.
Solution.
The set of complex numbers is defined by
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
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
where \(a \in A.\)
It is clear that the function \(f\) is injective. Therefore
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
It is obvious that the function \(f\) is injective. Then
By condition, the subset \(A\) is uncountable, so \({\aleph_0} \lt \left| A \right|.\) By the transitivity property, this yields
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
We find \(n\) by solving the inequality
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: