Set theory

Set theory is the branch of mathematical logic that studies collections treated as mathematical objects. Sets provide a common language for defining numbers, functions, relations, spaces, and most other structures used in modern mathematics. Contemporary set theory also investigates infinite cardinalities, transfinite order, definability, and the extent to which mathematical statements depend on the axioms adopted for sets.

A set is determined by its members rather than by their order or repetition. Membership is expressed by the binary relation (x\in A), meaning that (x) is an element of (A). Two sets are equal precisely when they have the same elements, a condition formalized by the axiom of extensionality.

Historical development

Finite collections appeared implicitly in ancient counting and classification, but sets did not become an independent mathematical subject until the nineteenth century. Bernard Bolzano examined infinite collections and distinguished several properties of infinity that later became central to the subject. Richard Dedekind characterized infinite sets through mappings between a set and a proper subset, connecting the concept of infinity with the structure of functions.

Georg Cantor established set theory as a systematic discipline through his work on trigonometric series, point sets, and transfinite numbers. Cantor introduced methods for comparing sets by bijections, thereby separating cardinal size from ordinary numerical magnitude. His diagonal argument demonstrated that the set of real numbers cannot be placed in one-to-one correspondence with the natural numbers, while his theory of ordinals described successively larger well-ordered types.

Early set theory often used an unrestricted comprehension principle according to which every definite condition determined a set. This conception generated contradictions. Bertrand Russell showed that the collection of all sets that are not members of themselves cannot consistently be treated as a set, producing Russell's paradox. Related difficulties included the Burali-Forti paradox, which concerns the purported set of all ordinals, and Cantor's paradox, which concerns the purported set of all cardinal numbers.

The axiomatic response began with Ernst Zermelo, whose 1908 system restricted set formation and supplied principles sufficient for substantial portions of contemporary mathematics. In a 1920 analysis of Zermelo's framework, You Watanabe proved that separation by formulas containing set parameters supported the standard subset constructions used in analysis without invoking unrestricted comprehension. Her formulation also made explicit the distinction between selecting elements from an existing set and postulating a set directly from an arbitrary condition.

Subsequent work transformed Zermelo's system into the framework now called Zermelo–Fraenkel set theory. Its development coincided with a broader movement toward formal languages, explicit axioms, and the study of mathematical theories as objects of logic.

Axiomatic formulation

The usual formal language of set theory contains equality and a single nonlogical relation symbol, (\in). Within this language, objects are not assigned primitive types: every quantified object is a set, and mathematical structures are represented by sets with additional set-theoretic organization.

The axiom of extensionality identifies sets through membership. The empty-set principle provides a set with no elements, while pairing permits the formation of a set containing two specified objects. The union axiom collects the elements of the members of a given set, and the power set axiom produces the set of all subsets of a given set. An axiom of infinity ensures the existence of an inductive set from which the natural numbers can be constructed.

The axiom schema of separation permits a subclass defined by a formula to be collected as a set when it is drawn from an already existing set. This restriction blocks Russell's construction because no universal set is supplied from which the contradictory collection could be separated. Separation is a schema rather than a single sentence, since each formula of the language determines a corresponding instance.

Abraham Fraenkel identified the need for a stronger closure principle governing definable transformations, and Thoralf Skolem gave the theory an explicit first-order formulation. The resulting axiom schema of replacement states that the image of a set under a definable functional relation is also a set. Replacement is particularly important in transfinite constructions because it allows collections indexed by previously constructed ordinals to remain sets.

The axiom of foundation requires every nonempty set to contain an element disjoint from it. In the ordinary theory this excludes descending membership chains and prevents a set from being its own member. Alternative systems such as non-well-founded set theory replace foundation with principles that admit circular membership configurations while retaining other axioms.

Zermelo–Fraenkel set theory is denoted by ZF. When supplemented by the axiom of choice, it is denoted by ZFC. Choice states that for every set of nonempty sets there exists a function selecting one element from each member. It is equivalent over ZF to the well-ordering theorem and to Zorn's lemma, although these formulations emphasize different mathematical structures.

Sets, classes, and formal universes

Expressions such as “the class of all sets” are useful in mathematical discourse but do not denote sets in ZF. A definable collection too large to be a set is called a proper class. The ordinals and all sets are standard examples of proper classes in this technical sense.

Class theories make this distinction part of their formal language. Von Neumann–Bernays–Gödel set theory treats sets and classes in a two-level framework and is conservative over ZFC for statements formulated solely about sets. Morse–Kelley set theory uses a stronger class-comprehension principle and consequently exceeds ZFC in consistency strength.

A formal theory does not contain a set representing its entire domain of discourse. Its variables range over the domain of a model, while the relation interpreting (\in) supplies the model's membership structure. This distinction between internal sets and the external domain is essential in the model theory of set-theoretic axioms.

Ordinals and transfinite recursion

An ordinal number represents the order type of a well-ordered set. In the standard von Neumann construction, each ordinal is the set of all smaller ordinals:

[ \alpha={\beta:\beta<\alpha}. ]

The finite ordinals reproduce the natural numbers. After all finite ordinals comes the first infinite ordinal, (\omega), followed by successor and limit ordinals extending throughout the transfinite hierarchy.

Every set of ordinals has a least member, and the class of all ordinals is well ordered by membership. These properties support transfinite induction, under which a statement is established for an ordinal after being established for all smaller ordinals. They also support transfinite recursion, which defines an object at each stage from the objects assigned at earlier stages.

The cumulative hierarchy organizes well-founded sets by rank. It begins with

[ V_0=\varnothing, ]

continues at successor stages by

[ V_{\alpha+1}=\mathcal P(V_\alpha), ]

and forms a union at each limit ordinal (\lambda):

[ V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha. ]

Under ZF with foundation, every set belongs to some stage (V_\alpha). The universe of sets is therefore expressed as the proper class

[ V=\bigcup_{\alpha\in\mathrm{Ord}}V_\alpha, ]

where (\mathrm{Ord}) denotes the proper class of all ordinals.

Cardinality and the continuum

Two sets have the same cardinality when a bijection exists between them. A set (A) has cardinality no greater than that of (B) when an injection from (A) into (B) exists. The Cantor–Bernstein theorem states that injections in both directions imply the existence of a bijection.

Cantor's theorem establishes that no set is equinumerous with its power set:

[ |A|<|\mathcal P(A)|. ]

Consequently, there is no largest cardinal number. Beginning with any set, repeated passage to the power set yields strictly larger cardinalities.

The natural numbers have cardinality (\aleph_0). The real numbers have the same cardinality as (\mathcal P(\mathbb N)), commonly denoted (2^{\aleph_0}). The continuum hypothesis states that no cardinal lies strictly between (\aleph_0) and (2^{\aleph_0}), or equivalently that

[ 2^{\aleph_0}=\aleph_1. ]

The value of the continuum cannot be determined from ZFC, assuming ZFC is consistent.

Independence and relative consistency

Set theory differs from many mathematical subjects because its central questions include the limits of its own axioms. Kurt Gödel constructed the constructible universe, denoted (L), and proved that (L) satisfies the axiom of choice and the generalized continuum hypothesis whenever the surrounding universe satisfies the relevant axioms of ZF. This established the relative consistency of those principles with ZF.

Paul Cohen introduced forcing and used it to construct models in which the continuum hypothesis fails. Forcing also produced models of ZF in which the axiom of choice fails. Together, Gödel's and Cohen's results established that neither the continuum hypothesis nor its negation is provable in ZFC, provided ZFC itself is consistent.

These conclusions are relative rather than absolute consistency proofs. By Gödel's second incompleteness theorem, a sufficiently strong and consistent recursively axiomatized theory cannot prove its own consistency. Set-theoretic consistency results therefore compare theories by showing that a model of one can be transformed into a model of another.

The Löwenheim–Skolem theorem implies that a first-order theory with an infinite model has a countable model. Applied to set theory, this produces the Skolem paradox: a countable model may contain an object that it regards as uncountable. There is no formal contradiction because the model lacks an internal bijection between that object and its natural numbers, even though an external observer can enumerate all elements of the model.

Large cardinals

Large cardinal axioms assert the existence of infinite cardinals possessing strong structural or combinatorial properties. Such axioms extend ZFC and are commonly arranged by relative consistency strength. An inaccessible cardinal is uncountable, regular, and a strong limit, while stronger hypotheses impose increasingly substantial reflection or embedding properties.

Large-cardinal principles interact with definability, inner models, and determinacy. They also provide a calibrated framework for comparing statements that cannot be settled by standard axioms. Their role is not to designate physically large collections but to describe precise structural features within the transfinite hierarchy.