# Cardinality

([itex]1) [/itex]2 | [itex]3 ([/itex]4) | [itex]5 ([/itex]6)

You may have noticed that in our examples of injections , there are always at least as many elements in as there are in . Similarly, surjections always map to smaller sets, and bijections map to sets of the same size.

This insight lets us use functions to compare the sizes of sets in a way that applies to infinite sets as well as finite sets. We give some definitions here.

The cardinality of a set (written ) is the size of the set. However, for the time being, we will not use this definition by itself. Doing so will encourage you to write proofs about cardinality that don't apply to infinite sets.

Instead, we will only define relationships between the cardinalities of sets; these definitions come from the intuitive relationship between sizes and 'jectivity described above.

Definition:
If and are sets, then means that there exists an injection
Definition:
If and are sets, then means that there exists a surjection
If and are sets, then means that there exists a bijection