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:

See solved problems on Page 2.

Page 1 Page 2