Countability and cardinality

Equinumerous sets

Two sets, $A$ and $B$, are equinumerous (same cardinality) if there is a bijection that maps $A$ to $B$. This is denoted $A \cong B$.

Finite, countable and uncountable sets

Consider $F_1 = \{0\}, F_2 = \{0,1\}, F_3 = \{0,1,2\}, ... , F_n = \{x \in \mathbb{N} : x < n\}$.
$F_i \cong F_j$ if and only if $i=j$.

A set $S$ is finite if $S \cong F_i$ for some $i$.
A set is countably infinite is $S \cong \mathbb{N}$
A set is countable if it is finite or countably infinite.

$\mathbb{N}$ is used as the definition of countably infinite. Consider the set of all even integers - $\{x \in \mathbb{N}: x \text{ is even}\}$. This set is equinumerous to $\mathbb{N}$ because there exists a bijective function which maps $\mathbb{N}$ to the set. This function is $f(n) = 2n$.

The set of integers, $\mathbb{Z}$, is countably infinite. This can be shown by considering pairs of $(i,j)$ where $i$ is the "index" of $j$ in $\mathbb{Z}$. This would give $(0,0), (1,1), (2,-1), (3,2),...(i, j)$. Every $j \in \mathbb{Z}$ is given an index $i \in \mathbb{N}$. This is bijective as each $i$ maps to exactly one $j$ and there are no values of $j$ which do not have a value of $i$. Therefore $\mathbb{N} \cong \mathbb{Z}$.

If there is no bijective mapping from $\mathbb{N}$ to a set and it isn't finite, it is uncountable.

Cardinality of power sets

If $S$ is a set, $S \not\cong 2^S$. Given this, $2^\mathbb{N} \not\cong \mathbb{N}$. Therefore $2^\mathbb{N}$ is uncountable.