Calculus

Set Theory

Set Theory Logo

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:

Injective but not surjective function.
Figure 1.

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.}\]