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, |A| = |B|) if there is a bijection AB. Now we want to learn how to compare sets of different cardinalities.

If A and B are finite sets , then the relation |A| < |B| 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 |A| < |B|) if there exists an injective function f : AB but there is no surjective function f : AB. 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:

See solved problems on Page 2.

Page 1 Page 2