We write \(S_1 \backsim\ S_2\) if there’s a bijection \(f: S_1 \rightarrow S_2\).

A set \(S\) is called countable is \(S \backsim\ T\) for some \(T \subset \mathbb{N}\).

The set \(\mathbb{Z}\) is countable, and \(\mathbb{Z} \backsim\ \mathbb{N}\). A bijaction \(f: \mathbb{N} \rightarrow \mathbb{Z}\) is given by \(f(n) = (-1)^n \lceil n/2\rceil\).

Summary:

  • \(\mathbb{N}, \mathbb{Z}, \mathbb{Q}\) are countable, \(\mathbb{R}, \mathbb{C}\) are uncountable.
  • Finite sets are always countable!
  • Infinite sets may be either countable or uncountable.
  • If an infinite set is countable, it has the same cardinality as the natural numbers.

https://www.youtube.com/watch?v=sT9hAmaot8U

https://www.youtube.com/watch?v=fRhdpyaOhEo