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 A → B. 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 : A → B but there is no surjective function f : A → B. This is illustrated by the following diagram:
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,
Since \(\left| {\mathbb{N}} \right| = \left| {\mathbb{Z}} \right| = \left| {\mathbb{Q}} \right| = {\aleph_0},\) we obtain
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|.\]