Primary reference: Chapter 14 (Cardinality of Sets) of Book of Proof by Richard Hammack

richardhammack.github.io

Content covered in this unit includes:

• The definitions (in reference to a function) of injective (or one-to-one), surjective (or onto), and bijective (or one-to-one correspondence).
• Proving that a particular function is injective or surjective (or both).
• Definitions pertaining to comparing cardinality of sets:
  • If $A$ and $B$ are sets, then $|A| = |B|$ if there exists a bijection (i.e. a one-to-one correspondence) between $A$ and $B$.
  • If $A$ and $B$ are sets, then $|A| \leq |B|$ if there exists an injection from $A$ to $B$
  • If $A$ and $B$ are sets, then $|A| < |B|$ if there exists an injection from $A$ to $B$ but no bijection between $A$ and $B$ (i.e. if $|A| \leq |B|$ but $|A| \neq |B|$).
• The fact that $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|$, but $|\mathbb{R}| > |\mathbb{N}|$.
• The fact that $|\mathscr{P}(X)| > |X|$ for any set $X$.
• The definitions of countable, countably infinite, and uncountable.
• The fact that if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$ (this is called the Cantor-Bernstein-Schröder theorem).