Set Theory — Cardinality, Countability

GRE Math Subject · Axiom Academy

LESSON Set Theory — Cardinality, Countability Finite and infinite sets, cardinality, countability, and Cantor's diagonal argument The cardinality of a set S, denoted |S| , is a measure of its size. For finite sets: |S| is simply the number of elements. For infinite sets: We need a different approach. We use bijections (one-to-one and onto functions). Definition: Two sets have the same cardinality if there exists a bijection between them. Example: ℕ (natural numbers) and 2ℕ (even numbers) have the same cardinality: The function f(n) = 2n is a bijection: 1 → 2, 2 → 4, 3 → 6, 4 → 8, ... Both sets are "the same size" in an infinite sense! A set is countably infinite if there exists a bijection with ℕ (the natural numbers). Intuition: We can list the elements in a sequence: a₁, a₂, a₃, a₄, ... ℤ (integers): Bijection is 0, 1, -1, 2, -2, 3, -3, ... ℚ (rationals): Can be enumerated by Cantor's diagonal method Any finite union of countable sets ℕ × ℕ (pairs of natural numbers) Cardinal notation: ℵ₀ (aleph-null) denotes the cardinality of countably infinite sets. Key fact: ℵ₀ + ℵ₀ = ℵ₀ and ℵ₀ × ℵ₀ = ℵ₀ A set is uncountable if no bijection with ℕ exists. For any set S, the power set P(S) (set of all subsets) has strictly larger cardinality than S. Consequence: There is no largest infinite cardinal. The hierarchy continues: ℵ₀ Cantor's Diagonal Argument proves that the real numbers are uncountable. Suppose ℝ is countable (or even (0,1) is countable) . Then we can list all reals:

This is the written version of the interactive lesson above. See the full GRE Math Subject course.