Mathematics.

infinite sets

Countable and Uncountable Sets

Set Theory30 minDifficulty4 out of 10

You should know: cardinality

Overview

A set is countable if it is finite or can be put in a bijection with the natural numbers ℕ (i.e., its elements can be listed in an infinite sequence x₁, x₂, x₃, ...); such infinite countable sets are called countably infinite and have cardinality ℵ₀. A set that cannot be so listed is uncountable. The integers ℤ and the rationals ℚ are both countably infinite despite seeming 'denser' than ℕ, while the real numbers ℝ are uncountable, as Cantor proved with his diagonal argument — establishing that infinite sets come in genuinely different sizes.

Intuition

A set is countable exactly when you can, in principle, write down a never-ending list that eventually reaches every element — first, second, third, and so on forever. Surprisingly this works even for the rationals, which look far denser than the integers: arrange all fractions p/q in a grid by numerator and denominator, then snake diagonally through the grid, and every rational eventually gets a position in the list. Real numbers defeat every such attempt: given ANY proposed complete list of reals between 0 and 1, Cantor's diagonal argument builds a new real number that differs from the n-th listed number in its n-th decimal digit — so it can't be anywhere on the list. No list can ever be complete, which is exactly what 'uncountable' means.

Formal Definition

Definition

A set A is countable if there exists an injection A → ℕ (equivalently, a surjection ℕ → A when A is nonempty); it is countably infinite if additionally there is a bijection A ↔ ℕ.

A is countable  ⟺  ∃f:A↪N (injective)A \text{ is countable} \iff \exists f: A \hookrightarrow \mathbb{N} \text{ (injective)}
Definition of countable
∣Z∣=∣Q∣=∣N∣=ℵ0|\mathbb{Z}| = |\mathbb{Q}| = |\mathbb{N}| = \aleph_0
The integers and rationals are countably infinite
∣R∣=2ℵ0>ℵ0|\mathbb{R}| = 2^{\aleph_0} > \aleph_0
The reals are uncountable (Cantor's diagonal argument)
A countable union of countable sets is countable\text{A countable union of countable sets is countable}
Closure property

Worked Examples

  1. Interleave 0, then alternate positive and negative integers: 0, 1, -1, 2, -2, 3, -3, ...

    0,1,−1,2,−2,3,−3,…0, 1, -1, 2, -2, 3, -3, \ldots

  2. This defines a bijection f: ℕ → ℤ, e.g. f(2k)=k, f(2k-1)=-k for k≥1, f(0)=0, so every integer appears exactly once.

    f(n)={n/2n even−(n+1)/2n oddf(n) = \begin{cases} n/2 & n \text{ even} \\ -(n+1)/2 & n \text{ odd}\end{cases}

Answer: ℤ is countably infinite: |ℤ| = |ℕ| = ℵ₀.

Practice Problems

Difficulty 3/10

Is the set of all finite-length strings over the alphabet {0,1} countable or uncountable?

Difficulty 4/10

Which of the following sets is uncountable?

Difficulty 7/10

Explain, using a countability argument, why there must exist real numbers that no finite mathematical description (formula, algorithm, etc.) can define.

Quiz

The rational numbers ℚ are:
Cantor's diagonal argument is used to prove:
A countable union of countable sets is:

Summary

  • A set is countable if it is finite or can be listed in a sequence matching ℕ (bijection with ℕ, cardinality ℵ₀); otherwise it is uncountable.
  • ℤ and ℚ are both countably infinite despite appearing denser than ℕ; a countable union of countable sets stays countable.
  • ℝ is uncountable — Cantor's diagonal argument shows no list can enumerate all real numbers, proving |ℝ| > |ℕ| and that infinities come in different sizes.

References

  1. WebsiteWikipedia — Countable set