Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 37 Β· Formal Systems and Completeness

ZFC Axioms and Russell's Paradox

See why naive set theory breaks with Russell's paradox and how the Zermelo-Fraenkel axioms with choice repair it, with Python models of sets built from nothing.

In the earlier lessons we treated sets informally: any collection you can describe is a set. This naive set theory is fine for everyday use but is inconsistent. Around 1901 Bertrand Russell showed that unrestricted set formation leads to a contradiction, and mathematicians responded by writing down careful axioms saying exactly which sets exist. The standard result is ZFC: Zermelo–Fraenkel set theory with the axiom of choice.

Russell's paradox

Naive comprehension says: for any property P, {x : P(x)} is a set. Take P(x) = "x βˆ‰ x" and let R = {x : x βˆ‰ x}, the set of all sets that are not members of themselves. Ask: is R ∈ R?

  • If R ∈ R, then R satisfies the defining property, so R βˆ‰ R.
  • If R βˆ‰ R, then R satisfies the property, so R ∈ R.

Either way, a contradiction. The structure is the same as Cantor's diagonal argument; in fact the paradox is Cantor's theorem applied to the "set of all sets". A popular version: a barber shaves exactly those who do not shave themselves. Who shaves the barber?

Python The barber, as a program that cannot exist

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ZFC axioms in plain words

ZFC repairs naive comprehension: you can only separate a subset out of a set you already have, never form a set from a property alone. The axioms, informally:

  1. Extensionality: sets with the same elements are equal.
  2. Empty set / Pairing: βˆ… exists; for any a, b the set {a, b} exists.
  3. Union: for a set of sets, its union exists.
  4. Power set: P(A) exists for every A.
  5. Infinity: an infinite set (such as β„•) exists.
  6. Separation: from a set A and a property P, {x ∈ A : P(x)} is a set.
  7. Replacement: the image of a set under a definable function is a set.
  8. Foundation (Regularity): every nonempty set has an element disjoint from it; no set contains itself.
  9. Choice: every family of nonempty sets has a choice function.

Separation blocks Russell's argument: {x ∈ A : x βˆ‰ x} exists, but it is a subset of A and cannot be a member of itself in the paradoxical way. The conclusion is only that no set contains all sets: there is no universal set. Collections that are too big, like "all sets", are called proper classes.

From paradox to axioms

Naive comprehension Any property forms a set
Russell's paradox The set of non-self-members
Careful axioms Only build from given sets
ZFC The standard foundation

Separation lets you filter a set, never conjure one.

1 / 2

Building mathematics from nothing

Everything in ZFC is a set; numbers, pairs and functions are built from βˆ…. The von Neumann naturals are 0 = βˆ…, n + 1 = n βˆͺ {n}. Kuratowski defines the ordered pair (a, b) = {{a}, {a, b}}, which satisfies the one property you need: (a, b) = (c, d) iff a = c and b = d. A function is then a set of pairs, as in functions.

Python Kuratowski pairs and a function as a set of pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Foundation: no set is a member of itself

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Consistency and independence

If ZFC were inconsistent, every statement would be provable. Nobody has found a contradiction in decades, but, as we see in GΓΆdel's incompleteness theorems, ZFC cannot prove its own consistency (if it is consistent). Statements independent of ZFC include the continuum hypothesis. Alternatives exist: NBG and Morse–Kelley add classes explicitly; type theory (used in Lean and Coq) avoids the paradox differently by stratifying objects into levels.

Day to day, mathematicians rarely use the axioms directly. They matter because they tell you precisely what you are allowed to assume, so a proof can be mechanically checked and paradoxes cannot sneak in.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What does Russell's paradox show?

    The set of all sets that are not members of themselves cannot consistently exist, so not every property defines a set.
  2. 2. Which ZFC axiom prevents Russell's construction?

    Separation only allows you to filter elements out of an existing set, not to collect everything with a property.
  3. 3. How does Kuratowski define the ordered pair (a, b)?

    The set {{a}, {a, b}} records which element is first, which is what makes (a, b) β‰  (b, a).
  4. 4. What is a proper class?

    Collections like all sets or all ordinals are proper classes: treating them as sets would lead to paradox.

Summary

  • Naive set theory is inconsistent: Russell's set {x : x βˆ‰ x} cannot exist.
  • ZFC restricts set formation with axioms: extensionality, pairing, union, power set, infinity, separation, replacement, foundation and choice.
  • All of mathematics can be encoded in sets: von Neumann naturals, Kuratowski pairs and functions as sets of pairs.
  • There is no universal set; ZFC cannot prove its own consistency, and some statements like CH are independent.

Next: Formal Systems and Proof Calculi