Vocab Recap

  • Injective Function - One to One relation
  • Surjective Function - Ever element is part of a mapping
  • Ever element is part of a mapping AND the function is a one-to-one relation

Let $A$ and $B$ be finite sets and $f: A \rightarrow B$ a function.

  • If $|A| > |B|$ then $f$ is NOT injective
  • If $|A| = |B|$ and $f$ is injective, then $f$ is surjective
  • If $|A| = |B|$ and $f$ is surjective, then $f$ is injective

Let $A$ and $B$ be finite sets and $f: A \rightarrow B$ a function

  • $|f(A)| \leq |A| $
  • If $|f(A)| = |A|$, then $f$ is injective
  • If $f$ is injective, then $|f(A)| = = |A|$ and $|A| \leq |B|$
  • If $f$ is surjective, $|f(A)| = |B|$ and $|A| \geq |B|$
  • If $f$ is bijection, then $|A| = |B|$

Infinite Sets?

The cardinality of infinite sets can be compared.

Let $A$ and $B$ be any sets, we define:

  • $|A| \leq |B|$ iff there is an injection $f: A \rightarrow B$
    • (equivalently a surjection $f: B \rightarrow A$)
  • It follows that $|A| = |B|$ iff there exists a bijection $f: A \rightarrow B$

Hilbert Hotel

  • Imagine a hotel with $\mathbb{N}$ many rooms, all occupied
  • A new guest, “David” arrives
  • Can we find a room for “David”?
  • Simple, for every guest in room $n$ move them to room $n+1$
  • Put “David” in room $0$

Formally, we have defined a bijective function:

\[ f: \mathbb{N} \cup \{\textrm{David}\} \rightarrow \mathbb{N}\\ f(\textrm{David}) = 0\\ \textrm{for } n \in \mathbb{N}, f(n) = n + 1\\ \textrm{So, } |\mathbb{N} \cup \{\textrm{David}\}| = |\mathbb{N}| \]

For any finite set $S$, we have $|\mathbb{N} \cup S| = |\mathbb{N}|$
But what about infinite sets?

The infinite bus

If an infinite bus comes, we can move guests to occupy even numbered rooms, leaving odd numbered rooms available for the bus.
For $n \in \mathbb{N}$, $f(n) = 2n$

Negatives?

If the bus containes negative integers, this gives the following bijection of $f: \mathbb{Z} \rightarrow \mathbb{N}$

  • For $n \in \mathbb{N}$, $f(n) = 2n$
  • For $n \in \mathbb{N}$ \ ${0}$, $f(-n) = 2n - 1$
  • $|\mathbb{Z}| = |\mathbb{N}|$

The infinite bus bus

What if an infinite number of buses arrives?

If an infinite number of busses arrive, we can assign each guest a room number as so:

  • Each guest currently in the hotel will move to room $2^n$ where $n$ is their current room number
  • Each guest from bus 1 will go to room $3^n$ where $n$ is their seat number
  • Each guest from bus 2 will go to room $5^n$ where $n$ is their seat number…
  • And so on, since there is an infinite number of prime numbers, this will work

Countable Infinite Sets

A set $A$ is said to be countably infinite if $|A| = |\mathbb{N}|$

  • $\mathbb{Z}$ and $\mathbb{N} \times \mathbb{N}$ are both countably infinite
  • So is $\mathbb{Z} \times \mathbb{N}$
  • If $A$ and $B$ are countably infinite, so is $A \times B$

What about $\mathbb{Q}$? - $|\mathbb{N}| \leq |\mathbb{Q}|$ because $\mathbb{N} \subseteq \mathbb{Q}$ - Function $f: \mathbb{Q} \rightarrow \mathbb{Z} \times \mathbb{N}$ such that $f\left(\frac{p}{q}\right) = (p, q)$ Therefore $|\mathbb{Q}| = |\mathbb{N}|$

What about $\mathbb{R}$? - $|\mathbb{N}| \leq |\mathbb{R}|$ because $\mathbb{N} \subseteq \mathbb{R}$ - If $|\mathbb{N}| = |\mathbb{R}|$, then we can accomodate everyone on interval $(0, 1)$ in Hilbert’s Hotel

It is also important to see Cantor’s Diagonalisation Argument

Examples

Prove that $\mathbb{N} \cup {a, b, c, d}$ is infinitely countable

Prove that $\mathbb{N} \times {a, b, c, d}$ is infinitel countable