Set Theory

Idea

Set theory is an approach to the foundations of mathematics in which the primitive notion is the membership relation $x\in y$. Informally, one studies sets and their elements, and formulates axioms governing how sets may be formed and how membership behaves.

However, Russell’s paradox showed that naive set theory is inconsistent. This led to axiomatic set theories which restrict comprehension. The most common modern foundation is ZF, or ZFC if the Axiom of Choice is included.

Zermelo-Fraenkel Set Theory

Axioms

Axioms of ZF include:

• Extensionality
• existence of an empty set
• pairing: $\{x,y\}$ is a set for any $x,y$.
• Union
• Power Set
• Comprehension (restricted comprehension)
• Axiom of infinity: $\mathbb{N}$ is a set.
• Replacement
• Foundation

If the Axiom of Choice is added, the resulting theory is called ZFC. ¹

Naive Set Theory

A naive approach is the unrestricted comprehension scheme, which says that for any predicate $P$, there is a set consisting of exactly those objects satisfying $P$. Re-expressed informally in type-theoretic syntax, this looks like: ²

$$\frac{P:\mathcal{U}\to \mathrm{Prop}}{\{x\mid P(x)\}\mathbf{set}}\frac{P:\mathcal{U}\to \mathrm{Prop}a\mathbf{set}P(a)}{a\in \{x\mid P(x)\}}\frac{P:\mathcal{U}\to \mathrm{Prop}a\mathbf{set}a\in \{x\mid P(x)\}}{P(a)}$$

However, unrestricted comprehension is inconsistent. If one defines the Russell set

$$R=\{x\mid x\notin x\},$$

then one obtains the contradiction

$$R\in R⟺R\notin R.$$

This is Russell’s Paradox. ³

Key Concepts

• Set Theory: The study of sets, membership, and axioms governing set formation
• Set: A collection of elements regarded as a single object
• Empty Set: The unique set with no elements
• Subset: A set all of whose elements lie in another set
• Union: The set of elements lying in at least one of a family of sets
• Power Set: The set of all subsets of a given set
• Extensionality: The principle that sets are equal exactly when they have the same elements
• Axiom of Foundation: The axiom ruling out infinitely descending membership chains
• Axiom of Infinity: The axiom asserting the existence of an inductive set
• Replacement (Set Theory): The axiom schema saying images of sets under definable functions are sets
• Axiom of Choice: The principle that arbitrary families of nonempty sets admit choice functions
• Russell’s Paradox: The contradiction arising from unrestricted comprehension
• Cardinal: The notion of size of a set up to bijection
• Cantor’s Theorem: The theorem that a set is strictly smaller than its power set
• Ordinal: A transitive well-ordered set representing order type
• Ordinal: The least ordinal of a given cardinality
• Cardinal: The finite stages of the aleph sequence of infinite cardinals
• Injection: A function that never identifies two distinct inputs
• Surjection: A function that hits every element of the codomain
• Bijection: A function that is both injective and surjective
• Schröder-Bernstein theorem: The theorem stating that mutual injections imply a bijection
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive
• Set-Theoretic Model: An interpretation of formal objects inside sets
• Comprehension: The principle forming a set from all objects satisfying a predicate
• Union: The axiom asserting that unions of sets of sets are sets
• Natural Number: The canonical inductive set, often constructed inside set theory
• Well-Ordering: A total order in which every nonempty subset has a least element
• Cardinal: An initial ordinal representing the size of a set
• Cartesian Product: The set of ordered pairs drawn from two sets
• Ordered Tuple: A pair encoding two components with order remembered
• Well-Founded Relation: A relation admitting no infinite descending chains
• Partition (Mathematics): A decomposition of a set into disjoint pieces whose union is the whole set
• Transitive Set: A set whose elements are all subsets of it

History

Set-theoretic ideas were developed in the late 19th century by mathematicians such as Georg Cantor and Richard Dedekind. Frege proposed a logical foundation for mathematics that later turned out to be inconsistent, as shown by Bertrand Russell’s paradox. In response, axiomatic systems such as ZF and later NBG were developed in order to avoid these contradictions.

Footnotes

1. Without choice, the theory is called ZF; with choice, it is called ZFC. ↩

2. This is only an informal rendering, assuming a suitable logical basis. ↩

3. Other paradoxes also arise in naive set theory, such as the Burali-Forti Paradox. ↩