Set-Theoretic Paradoxes and Type Theory

The set of all sets that do not contain themselves both does and does not contain itself — Russell's paradox toppled naive set theory and reshaped the foundations of logic.

Definition

The set-theoretic paradoxes are contradictions derivable in naive set theory from the unrestricted comprehension principle that every condition defines a set; type theory blocks them by ordering entities into a hierarchy of types and forbidding a set from belonging to itself.

Scope

This topic covers the logical and set-theoretic paradoxes and the foundational responses they provoked. It treats Russell's paradox of the set of all non-self-membered sets, the Burali-Forti paradox of the greatest ordinal, and Cantor's paradox of the universal set; Russell's diagnosis via the vicious-circle principle and the resulting ramified theory of types in Principia Mathematica; and the alternative response of axiomatic (Zermelo-Fraenkel) set theory that restricts comprehension to avoid the paradoxes.

Core questions

• What assumption in naive set theory generates Russell's paradox?
• Does avoiding the paradoxes require a vicious-circle principle and type restrictions?
• How do type theory and axiomatic set theory differ as responses?
• Are the logical paradoxes fundamentally the same as the semantic ones?

Key concepts

• unrestricted comprehension
• Russell's paradox
• Burali-Forti and Cantor's paradoxes
• vicious-circle principle
• theory of types
• axiom of separation

Key theories

Ramified type theory

Russell blocks the paradoxes with the vicious-circle principle and a hierarchy of types in which an entity can only be defined over entities lower in the hierarchy, preventing self-membership and self-applicable definitions.

Restricted comprehension

Axiomatic set theory (Zermelo-Fraenkel) abandons unrestricted comprehension for separation and replacement, so that no set of all non-self-membered sets can be formed, dissolving Russell's paradox without a type hierarchy.

History

Russell discovered his paradox in 1901 while studying Frege's logicism, undermining Frege's Basic Law V. Russell's 1908 type theory and the 1910 Principia Mathematica offered one cure; Zermelo's 1908 axiomatization, later extended by Fraenkel, offered another, and the two approaches anchor modern foundations and the simple type theory used in logic and computer science.

Debates

Types vs. axiomatic set theory

Whether the paradoxes are best avoided by a type hierarchy grounded in the vicious-circle principle or by restricting set-existence axioms, and what each approach implies about the nature of sets, classes, and predicative versus impredicative definitions.

Key figures

• Bertrand Russell
• Alfred North Whitehead
• Gottlob Frege
• Ernst Zermelo
• Cesare Burali-Forti

Seminal works

• russell1908
• whiteheadrussell1910

Frequently asked questions

What is Russell's paradox in plain terms?

Consider the set R of all sets that are not members of themselves. Ask whether R is a member of itself. If it is, then by its own definition it should not be; if it is not, then it qualifies and should be. Either answer contradicts the other, which shows that naive set theory's assumption that any property defines a set must be wrong.