Technopedia

The technologist’s encyclopedia

Set theory

Set theory is the standard foundational language for mathematics: every mathematical object — numbers, functions, spaces, measures — can be coded as a set, and every mathematical argument can be carried out in the axiomatic system ZFC (Zermelo–Fraenkel set theory with the axiom of choice). It is relevant whenever you need to reason about size (how many elements a set has, even when infinite), about order (the length of a process that never terminates), or about what a theory can and cannot prove.

Authoritative sources

Brief history

Sets and membership

Definition. A set is a collection of objects; the only primitive relation is membership, written x ∈ A (”x is an element of A”). A set is determined entirely by its elements: two sets are equal exactly when they have the same members.

Details

The whole of mathematics is built from one idea: a thing is whatever its members are. There is no hidden “container” — the set {1, 2, 3} is the same object as {3, 1, 2}, and {1, 1, 2} is the same as {1, 2} (repetition and order do not matter).

Example. Let A = {1, 2, 3} and B = {2, 4}. Then 2 ∈ A and 2 ∈ B, but 4 ∉ A. The set A ∩ B = {2} collects exactly the elements shared by both.

The picture below shows membership and the basic set operations as regions of a plane.

U (universe) A B A∩B A∪B = the shaded region; A∩B = the overlap

The ZFC axioms are the rules that say which sets may exist and how they are built. The ten standard axioms are:

  1. Extensionality — a set is determined by its elements.
  2. Empty set — there exists a set with no elements, ∅.
  3. Pairing — for any a, b there is a set {a, b}.
  4. Union — the union of the elements of a set of sets exists.
  5. Power set — the set of all subsets of a set exists.
  6. Infinity — there exists an infinite set (one containing ∅ and closed under x ↦ x ∪ {x}).
  7. Separation (subset) — any definable subcollection of a set is a set.
  8. Replacement — the image of a set under a definable function is a set.
  9. Foundation (regularity) — every non-empty set has an element disjoint from it; no set is a member of itself, and there are no infinite descending ∈-chains.
  10. Choice — given a family of non-empty sets, one can pick one element from each.

Axioms 1–9 form ZF; adding 10 gives ZFC. Separation is what blocks Russell’s paradox: you may form {x ∈ A : x ∉ x} for a given set A, but you may not form “the set of all sets that are not members of themselves.”

Example problem

Let A = {1, 2, 3} and B = {2, 3, 4}. Find A ∪ B, A ∩ B, and A ∖ B.

Solution

A ∪ B = {1, 2, 3, 4} (everything in either), A ∩ B = {2, 3} (in both), and A ∖ B = {1} (in A but not in B).

Cardinality

Definition. Two sets are equipotent (have the same cardinality) when there is a bijection between them. The cardinality of a set is its “size.” Cantor’s diagonal argument shows |ℕ| < |ℝ|: the infinite sizes are not all equal.

Details

For finite sets, size is just a number. For infinite sets, “how many” must be defined by pairing off: A and B are the same size if you can match every element of A to exactly one element of B with none left over. This is a bijection.

Example. The naturals and the evens have the same size: the map n ↦ 2n is a bijection ℕ → 2ℕ. So an infinite set can be the same size as one of its proper parts — the hallmark of infinity.

Cantor’s diagonal argument proves |ℝ| > |ℕ|. Suppose, for contradiction, that every real in (0, 1) could be listed as r₁, r₂, r₃, …, each written in binary. Build a new real s whose n-th digit is the opposite of the n-th digit of rₙ. Then s differs from r₁ in the first digit, from r₂ in the second, and so on — so s is on no line of the list, contradicting the assumption that the list was complete.

The animation below walks through the diagonal: the highlighted cell is the n-th digit of rₙ, and the struck digit is the flipped one that defines s.

r₁ r₂ r₃ r₄ r₅ 01010 10101 00110 11001 01100 s 11011 = diagonal, flipped s differs from rₙ in digit n, so s is on no line of the list.

The argument generalizes: for any set A, the power set 𝒫(A) (the set of all subsets of A) is strictly larger,

∣A∣<∣P(A)∣|A| < |\mathcal{P}(A)|

Writing this as 2^κ = |𝒫(κ)| — the cardinality of the power set of a set of size κ — gives an endless ladder of ever-larger infinite sizes:

ℵ₀ 2^ℵ₀ 2^(2^ℵ₀) each arrow is a strict increase (Cantor): κ < 2^κ

The smallest infinite cardinal is ℵ₀ (the size of ℕ); the size of ℝ is 2^ℵ₀, called the continuum and denoted 𝔠.

Authoritative sources

Example problem

Show that |ℕ × ℕ| = |ℕ| by exhibiting a bijection.

Solution

Pair (m, n) with the prime-power code 2^m · 3^n; unique factorization makes this injective, and its image is an infinite subset of ℕ, so by the same “infinite subset of ℕ has size ℵ₀” fact it is a bijection onto its image. Hence the countable product of countable sets is countable.

Ordinals

Definition. An ordinal is a set that is well-ordered by membership and equals the set of its predecessors. Ordinals extend counting into the transfinite: 0, 1, 2, …, ω, ω+1, …, ω·2, …, ω^ω, … They measure the length of well-ordered processes and the strength of induction and recursion.

Details

A cardinal answers “how many”; an ordinal answers “in what order.” Every finite ordinal is just a natural number, but ordinals keep going past all of them. The first infinite ordinal is ω, the order type of the naturals 0, 1, 2, … After exhausting one copy of ω you can start another: ω+1 is “ω then one more,” and ω·2 is two copies of ω end to end.

Example. The order 0, 1, 2, …, ω, ω+1, ω+2, … has order type ω+1. It is not the same order type as ω: in ω+1 there is a last element (ω is the first “limit” point), whereas ω has no last element. Two ordinals can have the same cardinality (|ω+1| = ℵ₀) but different order — that is the whole point of distinguishing them.

The number line below lays out the first few ordinals, with the limit ordinal ω marked where the finite ones run out.

0 1 2 … ω ω+1 ω·2 … ω^ω finite ordinals, then the first limit ordinal ω, then ω+1, ω·2, …, ω^ω

Ordinals support transfinite induction and transfinite recursion: to prove a property for all ordinals, prove it holds at 0, is preserved by taking a successor (α ↦ α+1), and is preserved at limit ordinals (from all smaller ordinals). This is the engine behind defining operations on all ordinals, such as ordinal addition, multiplication, and exponentiation.

Authoritative sources

Example problem

Is ω + 1 equal to 1 + ω? Justify.

Solution

No. ω+1 is the order type “0, 1, 2, … then one more,” which has a last element. But 1+ω is “one then 0, 1, 2, …,” which is order-isomorphic to ω itself (just relabel). So 1+ω = ω ≠ ω+1: ordinal addition is not commutative.

Independence and large cardinals

Definition. A statement is independent of ZFC when it is neither provable nor refutable from the ZFC axioms. The continuum hypothesis (CH) — “there is no infinite cardinal strictly between ℵ₀ and 2^ℵ₀” — is the canonical example.

Details

Cantor asked whether 2^ℵ₀ = ℵ₁ (the next cardinal after ℵ₀). This is the continuum hypothesis. For decades it was thought to be decidable, until:

Together these show CH is independent of ZFC: ZFC alone cannot settle it. This is a concrete instance of Gödel’s incompleteness theorems (see Mathematical logic).

Because ZFC leaves such questions open, set theory studies stronger axioms — large cardinals (cardinals with special closure properties, e.g. inaccessible, measurable, or Woodin cardinals) — that decide more statements and organize the consistency strength of the theory. The hierarchy of large cardinals is one of the frontiers of modern set theory.

Authoritative sources

Example problem

State precisely what it means for CH to be independent of ZFC, and name the two models that establish it.

Solution

CH is independent of ZFC if, assuming ZFC is consistent, there exists a model of ZFC in which CH is true and another model of ZFC in which CH is false. Gödel’s constructible universe L is a model where CH holds; Cohen’s forcing extensions are models where CH fails.

Interactive: Cantor’s diagonal argument

The simulation below lets you build the diagonal real s yourself: flip the highlighted diagonal digits and watch the new real differ from every row of the list.

How it relates to the other classes

Set theory is the default substrate: Analysis builds the reals and measure theory on it, Algebraic and discrete mathematics codes its structures as sets of sets, and Probability and statistics defines events as measurable sets — see Measure theory, which is built directly on the cardinality and set-algebra ideas above. Category theory offers an alternative, structural language for the same content, and Type theory a third.

Quizz

Test yourself

Problem. A student claims: “The set of all even natural numbers is smaller than the set of all natural numbers, because it is a proper subset.” Using the definition of cardinality, explain why this claim is wrong, and then state the theorem that does guarantee a strictly larger set than ℕ.

Solution

Cardinality is defined by the existence of a bijection, not by subset inclusion. The map n ↦ 2n is a bijection from ℕ onto the evens, so the two sets have the same cardinality ℵ₀ — a proper subset can be the same size as its superset, which is exactly what distinguishes infinite from finite sets. The theorem that guarantees a strictly larger set is Cantor’s theorem: for any set A, |A| < |𝒫(A)|; applied to A = ℕ it gives ℵ₀ < 2^ℵ₀.