Set Theory

The axiom of choice (AC) states that given any collection of nonempty sets, it is possible to choose exactly one element from each set simultaneously, even if the collection is infinite and there is no explicit rule for the choices. For finite collections this is provable from more basic axioms, but for infinite collections it is a genuinely independent assumption. First isolated by Ernst Zermelo in 1904 to prove the well-ordering theorem, AC is now a standard part of ZFC set theory (Zermelo–Fraenkel plus Choice), though it remains philosophically notable because it guarantees the existence of a choice function without ever constructing one, and it implies some famously counterintuitive results such as the Banach–Tarski paradox.

Zermelo–Fraenkel (ZF) set theory is the standard axiomatic foundation for modern mathematics, a list of axioms describing precisely what sets exist and how they may be formed, expressed entirely in first-order logic with a single primitive relation, membership (∈). Developed by Ernst Zermelo in 1908 and refined by Abraham Fraenkel and Thoraf Skolem in the 1920s, ZF was designed specifically to avoid the paradoxes (like Russell's paradox) that plagued earlier, unrestricted 'naive' set theory, by carefully restricting which collections are allowed to count as sets. When the axiom of choice is included, the system is called ZFC, and essentially all of ordinary mathematics can be formally developed within it.

The Cartesian product of two sets A and B, written A × B, is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B. Order matters — (a,b) is generally different from (b,a) — which distinguishes it from an unordered pairing. For finite sets, |A × B| = |A| · |B|, and the construction extends to any finite (or infinite) list of sets, producing ordered n-tuples. The Cartesian product is the basic building block for coordinates, relations, and functions: the plane ℝ² is R × R, and any binary relation or function is simply a specially chosen subset of a Cartesian product.

The power set of a set A, written P(A) or 2^A, is the set of all subsets of A, including the empty set and A itself. If A has n elements, P(A) has exactly 2^n elements, since each element independently is either included or excluded from a given subset. The power set is itself a set — its elements are sets — which makes it a natural way to build richer structures (topologies, sigma-algebras, Boolean algebras) on top of a base set.

A Venn diagram is a picture that shows how sets relate to one another, using overlapping circles inside a rectangle representing the universal set. Every region formed by the overlaps corresponds to exactly one logical combination of membership (in A only, in both A and B, in neither, etc.), making abstract set operations like union, intersection, and complement immediately visible.

A set is countable if it is finite or can be put in a bijection with the natural numbers ℕ (i.e., its elements can be listed in an infinite sequence x₁, x₂, x₃, ...); such infinite countable sets are called countably infinite and have cardinality ℵ₀. A set that cannot be so listed is uncountable. The integers ℤ and the rationals ℚ are both countably infinite despite seeming 'denser' than ℕ, while the real numbers ℝ are uncountable, as Cantor proved with his diagonal argument — establishing that infinite sets come in genuinely different sizes.

An equivalence relation on a set is a binary relation that is reflexive, symmetric, and transitive — capturing the everyday notion of 'being essentially the same' with respect to some criterion. Classic examples include equality itself, congruence modulo n on the integers, and 'has the same shape as' among triangles. The defining feature of an equivalence relation is that it partitions its underlying set into disjoint equivalence classes, and conversely every partition of a set arises from some equivalence relation — the two notions are exactly interchangeable.

Set identities are the algebraic laws that govern union, intersection, and complement, mirroring the laws of ordinary arithmetic (and Boolean algebra) with ∪ playing the role of + and ∩ the role of ×. They include commutativity, associativity, distributivity, idempotence, and De Morgan's laws, and they hold for every choice of sets drawn from a common universe. Because these identities can be proved once and reused everywhere, they let mathematicians manipulate complicated set expressions symbolically instead of re-checking membership by hand each time.

Set-theoretic paradoxes are contradictions that arise from allowing sets to be formed too freely — specifically, from 'naive' (unrestricted) comprehension, the assumption that any well-formed property φ(x) defines a set {x : φ(x)}. The most famous is Russell's paradox, discovered by Bertrand Russell in 1901, which considers the set of all sets that do not contain themselves and derives a direct contradiction. These paradoxes were not flaws in logic itself but in the naive assumption that arbitrary properties always define sets; they directly motivated the development of axiomatic set theory (ZF), which restricts set formation precisely enough to block every known paradox of this kind.

A set is a collection of distinct objects, called its elements or members. The objects can be anything — numbers, points, letters, even other sets. Sets are the foundational language of modern mathematics: nearly every mathematical object is ultimately built from sets. What matters about a set is only which elements it contains, not their order or repetition, so {1, 2, 3} and {3, 2, 1, 1} denote the same set.

A binary relation associates some elements of one set, called the domain, with some elements of another set, called the codomain. Precisely, a binary relation over sets X and Y is a set R of ordered pairs (x, y), where x is an element of X and y is an element of Y. It encodes the common concept of relation: an element x is related to an element y — written xRy — if and only if the pair (x, y) belongs to R. Familiar examples include 'is less than' on numbers, 'is a subset of' on sets, and 'is the parent of' on people — each is fully captured by the set of ordered pairs for which the relation holds.

A function f: X → Y can be defined set-theoretically as nothing more than a special binary relation on X × Y: a set of ordered pairs (x, y) that satisfies two extra constraints beyond being a relation. First, it must be total — every x in the domain X appears as a first coordinate in some pair. Second, it must be functional (single-valued) — no x appears as the first coordinate of two different pairs. Together these say that each input is assigned exactly one output, which is the everyday meaning of 'function' recast entirely in the language of sets. This viewpoint unifies functions and relations under one framework: every function IS a relation, but most relations are not functions, since a general relation can leave inputs unassigned or assign several outputs to the same input.

A partial order is a relation on a set that captures the idea of 'ranking' or 'precedence' without forcing every pair of elements to be comparable. Formally, it is a relation that is reflexive, antisymmetric, and transitive — the same three properties possessed by 'is a subset of' on a collection of sets, or 'divides' on the positive integers. What makes it only PARTIAL is that some pairs of elements need not be related in either direction: {1,2} and {3,4} are both subsets of {1,2,3,4}, but neither is a subset of the other. A total order (or linear order) is a partial order with the extra requirement that every pair of elements IS comparable, like ≤ on the real numbers. Every total order is a partial order, but not conversely — the divisibility relation on the integers is a partial order that is not total, since e.g. 2 and 3 are incomparable (neither divides the other).

Cardinality is an inherent property of sets, roughly meaning the number of individual objects they contain, which may be infinite. The concept is understood through one-to-one correspondences (bijections) between sets: two sets have the same cardinality if their objects can be paired such that each object has a pair, and no object is paired more than once. For finite sets, cardinality is just the familiar count of elements. For infinite sets, this pairing idea leads to a genuine hierarchy of infinities — some infinite sets (like the integers) are 'countable,' while others (like the real numbers) are strictly 'larger,' a result first proved rigorously by Georg Cantor.

The Continuum Hypothesis (CH), first proposed by Georg Cantor in 1878, asserts that there is no set whose cardinality is strictly between that of the natural numbers ℕ and the real numbers ℝ (the 'continuum'). Cantor had already shown |ℝ| = 2^{ℵ₀} is strictly greater than |ℕ| = ℵ₀; CH says that 2^{ℵ₀} is the very NEXT infinite cardinal after ℵ₀, i.e. 2^{ℵ₀} = ℵ₁. What makes CH famous beyond its content is its fate: it was David Hilbert's first problem on his celebrated 1900 list, yet it turned out to be neither provable nor disprovable from the standard axioms of set theory (ZFC). Kurt Gödel showed in 1940 that CH cannot be disproved from ZFC (it is consistent to assume it), and Paul Cohen showed in 1963 that CH also cannot be proved from ZFC (it is consistent to assume its negation) — together establishing that CH is independent of ZFC, one of the most striking limitative results in the foundations of mathematics.

Cardinal arithmetic defines addition, multiplication, and exponentiation on cardinal numbers — the sizes of sets, including infinite ones — via operations on disjoint unions, Cartesian products, and function sets. For finite cardinals these operations reduce to ordinary arithmetic, but for infinite cardinals the rules become strikingly different: adding or multiplying two infinite cardinals (assuming choice) simply returns the LARGER of the two, so ℵ₀+ℵ₀ = ℵ₀ and ℵ₀·ℵ₀ = ℵ₀, collapsing operations that would blow up in the finite world. Exponentiation is the one operation that still grows: Cantor's theorem guarantees 2^κ > κ for every cardinal κ, which is exactly why the reals (of cardinality 2^{ℵ₀}) form a strictly larger infinity than the naturals. This 'flattening' of addition/multiplication alongside genuine growth under exponentiation is the central, counterintuitive fact that makes infinite cardinal arithmetic behave so differently from arithmetic on finite numbers.

The Schröder–Bernstein theorem (also called the Cantor–Schröder–Bernstein theorem) says that if there is an injection from set A into set B, and also an injection from B into A, then there must exist a bijection between A and B — that is, |A| ≤ |B| and |B| ≤ |A| together force |A| = |B|. This is exactly the property that makes cardinality behave like an ordering in the familiar sense (antisymmetry), and it is what justifies writing '≤' for cardinal comparison at all: without it, having injections both ways wouldn't guarantee the sets are truly the 'same size.' Remarkably, the theorem's proof needs no explicit description of either injection's inverse and does not require the Axiom of Choice — it works by a clever chain-tracing construction that stitches the two given injections together into one true bijection.

An indexed family of sets is a collection of sets labeled by an index set I, written {A_i}_{i∈I}, which is formally just a function A that assigns a set A_i to each index i ∈ I. This is a small but powerful generalization of an ordinary list or sequence of sets: when I = {1,2,3} you recover an ordinary finite list A_1, A_2, A_3, and when I = ℕ you recover an infinite sequence of sets — but I can just as well be uncountable, letting you talk about 'a set for every real number' or 'a set for every point in the plane.' Indexed families let set operations like union and intersection generalize cleanly beyond two sets, or even beyond countably many sets, to ANY collection, however large, via the indexed union ⋃_{i∈I} A_i and indexed intersection ⋂_{i∈I} A_i.

Transfinite induction extends ordinary mathematical induction from the natural numbers to any well-ordered set, in particular to the ordinal numbers, which continue counting past every finite number (0, 1, 2, ..., then ω, ω+1, ω+2, ..., then ω·2, and on transfinitely). Ordinary induction has two cases — a base case and a successor step — but because ordinals include 'limit' ordinals like ω that are not the successor of any single previous ordinal, transfinite induction needs a THIRD case handling limits, where the property must be shown to hold by combining its truth at all smaller ordinals at once. This extra case is the only real novelty: once you can prove a property holds at 0, passes from any ordinal to its successor, and passes to any limit ordinal from all its predecessors, transfinite induction concludes the property holds for every ordinal whatsoever, or every element of any well-ordered set.

Ordinal numbers extend the natural numbers 0, 1, 2, 3, ... past every finite number, giving a precise way to describe the 'position' of an element in a well-ordered set rather than just how many elements there are. After all the finite ordinals comes ω, the first infinite ordinal (the order type of the naturals themselves), then ω+1, ω+2, ..., then ω·2, ω·3, ..., then ω², and onward without end. In the von Neumann construction, each ordinal IS the set of all ordinals strictly less than it — so 0 = ∅, 1 = {0}, 2 = {0,1}, and ω = {0,1,2,...} — which makes '<' between ordinals literally the same as '∈'. Every ordinal is either 0, a successor (α+1 for some ordinal α), or a limit ordinal (one with no immediate predecessor, like ω); this trichotomy is exactly what licenses transfinite induction and recursion.

Union (A ∪ B), intersection (A ∩ B), and complement (Aᶜ) are the three basic operations for combining and modifying sets, and De Morgan's laws describe exactly how complement interacts with union and intersection: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. These two identities are not just a curiosity — they are the set-theoretic mirror of the logical De Morgan's laws relating 'and,' 'or,' and 'not' (since x ∈ A∪B means 'x∈A or x∈B,' and negating an 'or' statement turns it into an 'and' of negations). Because every set-builder condition can be rephrased as a logical statement, De Morgan's laws let you systematically rewrite complicated combinations of unions, intersections, and complements into an equivalent but often simpler or more convenient form.

An urelement (from German Ur-, 'original' or 'primordial') is an object that is a member of sets but is not itself a set and has no members of its own — a foundational 'atom' from which sets are built, distinct from the empty set (which has zero members but IS a set). Ernst Zermelo's original 1908 axiomatization of set theory allowed urelements, since he wanted to build sets out of pre-existing mathematical or physical objects (like points or numbers treated as primitive). Modern axiomatic set theory (ZF or ZFC), however, is usually formulated as a 'pure' theory with NO urelements: every object in the universe of ZFC is itself a set, all the way down to the empty set ∅, and familiar mathematical objects (numbers, ordered pairs, functions) are instead simulated as specific sets (e.g. the von Neumann construction of the natural numbers). This pure approach is not strictly necessary — set theory with urelements (ZFA) is equiconsistent with ZF — but it is preferred for its economy: a single primitive notion (set membership) suffices to build the entire mathematical universe.