# 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:

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|.$