Countably infinite and uncountable sets

Countably infinite set

A set S is countably infinite if there is a one-to-one correspondence (bijection) between S and the set of natural numbers N = {0, 1, 2, ...}. Equivalently, its elements can be listed in an infinite sequence s₀, s₁, s₂, ... in which every element appears. A set is countable if it is finite or countably infinite.

Examples

• The even natural numbers: f(n) = 2n.
• The integers Z: list 0, 1, −1, 2, −2, 3, −3, ... (f(n) = (n+1)/2 for odd n, −n/2 for even n).
• N × N and the rationals Q (listed by dovetailing along diagonals).
• Σ*, the set of all strings over a finite alphabet: list by length, then alphabetically.

Uncountable set

An infinite set that is not countable, i.e. no bijection with N exists, is uncountable.

Examples: the set of real numbers in [0, 1], and the power set 2^N of the natural numbers.

Proof for 2^N (diagonalization). Suppose all subsets of N were listed as S₀, S₁, S₂, ... Define D = { i : i ∉ Sᵢ }. For each i, D and Sᵢ differ on the element i, so D is different from every Sᵢ. But D is a subset of N, so it should be in the list, a contradiction. Hence 2^N is uncountable.

Importance. The set of all programs (strings) is countable, but the set of all languages over Σ (subsets of Σ*) is uncountable. So some languages have no Turing machine at all.