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