Countable and Uncountable Sets

On the Finite Sets page we defined what it meant for a set $S$ to be finite and infinite.

We will now look at another important definition for the number of elements in a set.

Definition: A set $S$ is said to be Countably Infinite or Denumerable if there exists a bijection $f: \mathbb{N} \to S$.

Definition: A set $S$ is said to be Countable if it is either a finite set or a countably infinite set. A set $S$ is said to be Uncountable otherwise.

Let's first look at an example of a countably infinite set. Consider the set of even natural numbers $\mathbb{N}_{\mathrm{even}} := \{ 2n : n \in \mathbb{N} \} = \{ 2, 4, 6, ... \}$ We can find a bijection $f : \mathbb{N} \to S$ with the formula $f(n) = 2n$, so we can say that $S_{\mathrm{even}}$ is countably infinite and thus also countable. Similarly, the set of odd natural numbers is also countably infinite.

Of course, there are sets that are not countable, for example, the set of real numbers $\mathbb{R}$, that is, there does not exist a bijection that maps $\mathbb{N}$ onto $\mathbb{R}$. We will prove this later on.