Cardinality

From CS2800 wiki

You may have noticed that in our examples of injections [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], there are always at least as many elements in [math]B [/math] as there are in [math]A [/math]. 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 [math]A [/math] (written [math]|A| [/math]) 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 [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] means that there exists an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
Definition:
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |B| [/math] means that there exists a surjection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} |B| [/math] means that there exists a bijection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]