Calculus

Set Theory

Set Theory Logo

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.\]
Page 1 Page 2