Home / Courses / Intro to Proofs / Unit 9

Intro to Proofs Unit 9: Cardinality and Countability

Cardinality measures the size of sets, including infinite ones, by matching elements with bijections. Some infinite sets, like ℕ, ℤ and ℚ, are countable, while others, like ℝ and P(ℕ), are strictly larger.

Covers: Equal cardinality and bijections, Finite and countably infinite sets, Countability of ℤ, ℚ and ℕ × ℕ, Cantor's diagonal argument, Cantor's theorem and power sets, Schröder–Bernstein theorem, Countable unions and uncountable sets

Study guide

Two sets have the same cardinality, |A| = |B|, if there is a bijection between them. For finite sets this matches counting. For infinite sets it gives surprising results: ℕ = {1, 2, 3, ...} and the even positive integers have the same size via n ↦ 2n, and ℕ and ℕ − {1, 2, 3} match via n ↦ n + 3. A set is countably infinite if it has a bijection with ℕ, meaning its elements can be listed a₁, a₂, a₃, ... with each appearing exactly once. A set is countable if it is finite or countably infinite, and uncountable otherwise.

Many sets that look bigger than ℕ are countable. ℤ is listed as 0, 1, −1, 2, −2, .... ℕ × ℕ is listed along diagonals m + n = 2, 3, 4, ..., each of which is finite; the formula f(m, n) = 2ᵐ⁻¹(2n − 1) is an explicit bijection to ℕ. Since each rational is a/b, ℚ is countable too. Useful closure facts: subsets of countable sets are countable, finite products of countable sets are countable, and countable unions of countable sets are countable. So the set of integer polynomials, and hence the set of algebraic numbers, is countable.

The real numbers are uncountable. Cantor's diagonal argument assumes the reals in (0, 1) are listed as r₁, r₂, ..., then builds d whose nth digit differs from the nth digit of rₙ, using digits like 5 and 6 to avoid the 0.4999... = 0.5 ambiguity. Then d is on no list position, a contradiction. Every interval has the same cardinality as ℝ: x ↦ a + (b − a)x maps (0, 1) onto (a, b), and tan(π(x − ½)) maps (0, 1) onto ℝ. Because ℚ is countable, the irrationals must be uncountable; because the algebraic numbers are countable, transcendental numbers must exist.

Cantor's theorem says |A| < |P(A)| for every set A. Given any f: A → P(A), the set S = {a ∈ A : a ∉ f(a)} cannot equal any f(s), since then s ∈ S exactly when s ∉ S. So P(ℕ) is uncountable, and there is no largest cardinality. To show two sets have the same size without building a bijection directly, use the Schröder–Bernstein theorem: injections A → B and B → A guarantee a bijection. For example, x ↦ x/2 + 1/4 and inclusion show |[0, 1]| = |(0, 1)|.

Key ideas

• |A| = |B| means there is a bijection between A and B.
• A countably infinite set can be listed as a sequence using every element once.
• ℤ, ℚ and ℕ × ℕ are countable; ℝ, every interval and P(ℕ) are not.
• Countable unions of countable sets are countable.
• The diagonal argument builds a number that differs from every listed number.
• Cantor's theorem: every set is strictly smaller than its power set.
• Schröder–Bernstein: injections both ways give a bijection.

Formulas and rules

Common mistakes

• Assuming a set that properly contains ℕ must be bigger than ℕ.
• Thinking the diagonal argument also proves ℚ is uncountable.
• Treating 'countable' as meaning 'countably infinite', forgetting finite sets.
• Giving a function that is injective but not onto when a bijection is required.
• Forgetting to check that each map in a Schröder–Bernstein argument lands inside its target set.

Before the test, make sure you can

• Prove two sets have the same cardinality by giving an explicit bijection.
• Show ℤ, ℕ × ℕ and ℚ are countable.
• Write out Cantor's diagonal argument for the uncountability of (0, 1).
• Prove Cantor's theorem using the set S = {a : a ∉ f(a)}.
• Apply the Schröder–Bernstein theorem with two injections.
• Use closure facts to decide whether a set is countable or uncountable.
• Explain why the irrationals and transcendental numbers are uncountable.

Words to know

Cardinality

The size of a set; |A| = |B| when a bijection exists.

Finite set

A set that is empty or in bijection with {1, 2, ..., n} for some n.

Countably infinite

In bijection with ℕ; the elements can be listed a₁, a₂, a₃, ....

Countable

Finite or countably infinite.

Uncountable

Infinite but not countable, such as ℝ.

ℵ₀ (aleph-null)

The cardinality of ℕ, the smallest infinite cardinal.

Diagonal argument

Cantor's proof that ℝ is uncountable, building a number that differs from each listed one.

Cantor's theorem

For every set A, there is no surjection A → P(A), so |A| < |P(A)|.

Schröder–Bernstein theorem

If injections A → B and B → A exist, then |A| = |B|.

Hilbert's hotel

The idea that an infinite set can match a proper subset of itself, such as n ↦ n + 1.

Algebraic number

A root of a nonzero polynomial with integer coefficients.

Transcendental number

A real number that is not algebraic, such as π or e.

Continuum

The cardinality of ℝ, equal to |P(ℕ)|.

Characteristic function

For S ⊆ A, the function equal to 1 on S and 0 elsewhere; it links P(A) with 0-1 functions.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.