Axiom of extensionality
The axiom of extensionality is a foundational axiom in axiomatic set theory, asserting that two sets are equal precisely when they have exactly the same elements, thereby defining sets by their membership relations alone.[1] Formally, it can be stated as: for all sets x and y, if for every z, z \in x if and only if z \in y, then x = y.[1] This principle ensures the uniqueness of sets based on their contents, preventing distinct sets from being indistinguishable by their elements.[2] Introduced by Ernst Zermelo in his 1908 axiomatization of set theory, which addressed foundational issues arising from paradoxes like Russell's paradox, the axiom establishes a clear criterion for set identity.[3] In Zermelo's original formulation, it was phrased as: if M \subset N and N \subset M, then M = N, emphasizing extensional equality through mutual subset relations.[3] This axiom forms the first principle in Zermelo's system and remains the initial axiom in the modern Zermelo-Fraenkel set theory (ZF), where it underpins the development of all subsequent axioms.[1] The axiom's implications extend to proving key properties, such as the uniqueness of the empty set, as any two sets with no elements must be identical under extensionality (with existence provided by other axioms).[2] It also reinforces the idea that sets lack inherent "labels" or internal structure beyond membership, distinguishing set theory from other mathematical structures like multisets or tagged collections.[4] In the full Zermelo-Fraenkel-Choice (ZFC) system, extensionality interacts with axioms like separation and replacement to enable rigorous constructions of mathematical objects, from natural numbers to uncountable infinities.[1]Introduction
Formal Definition
The axiom of extensionality asserts that sets are equal if and only if they have precisely the same elements, embodying the principle of extensional equality whereby the identity of a set is determined solely by its membership rather than by any intensional description or mode of presentation.[5][6] This captures the intuitive notion that sets are collections defined purely by what belongs to them, without regard to order, repetition, or external labels.[7] In first-order logic, the axiom is formally stated as \forall x \forall y \left( \forall z (z \in x \leftrightarrow z \in y) \to x = y \right), where the universal quantifiers range over all sets, the biconditional \leftrightarrow specifies that every element of x is an element of y and vice versa, and the implication \to concludes that x equals y under this condition.[5][6][8] In pure set theory, this is a single axiom rather than an infinite schema, as it applies uniformly to all sets without requiring separate instances for different predicates.[7][5] For example, the sets \{1, 2\} and \{2, 1\} are equal because they share exactly the same elements, regardless of the order in which they are listed.[6] This principle distinguishes sets from multisets, where order or multiplicity might affect equality.[8]Basic Implications
The axiom of extensionality ensures that sets are uniquely determined by their elements, implying that for any given collection of elements, there is at most one set that contains precisely those elements and no others. This uniqueness follows directly from the axiom's statement, as any two sets sharing identical membership relations must be identical.[2] Consequently, this principle eliminates the possibility of distinct sets that are indistinguishable based on contents, providing a foundational criterion for set equality in extensional set theories.[9] Under the axiom, sets serve as pure containers defined solely by membership, devoid of any additional inherent properties or identities beyond what their elements confer. This extensional view treats sets as abstractions where identity is exhausted by extension, reinforcing the idea that sets lack "internal structure" independent of their constituents.[2] Such a conceptualization supports extensional reasoning across mathematical foundations, ensuring consistency in how collections are identified and manipulated. The axiom is typically stated as \forall x \forall y \left( \forall z (z \in x \leftrightarrow z \in y) \to x = y \right), capturing one direction of the biconditional for set equality. The converse, \forall x \forall y \left( x = y \to \forall z (z \in x \leftrightarrow z \in y) \right), derives as a theorem from the standard properties of equality in first-order logic, particularly the substitution rule. To sketch the proof: assume x = y; then for arbitrary z, if z \in x, substitution yields z \in y (since membership is an atomic predicate), and symmetrically if z \in y then z \in x; thus the membership biconditional holds universally. This logical derivation complements the axiom, yielding the full equivalence that sets are equal if and only if they have the same elements.[1] A concrete illustration of uniqueness arises with the empty set, denoted \emptyset, which contains no elements at all. Suppose another collection Y also has no elements; then for every z, z \notin \emptyset and z \notin Y, so \forall z (z \in \emptyset \leftrightarrow z \in Y), implying \emptyset = Y by extensionality. Thus, the empty set is singular, with no alternative empty collections possible to distinguish it.[10]Historical Development
Etymology
The concept of "extensionality" in logic originates from the distinction between the "extension" of a concept—the full set of objects to which it applies—and its "intension," the inherent qualities or properties that define it.[11] This opposition, rooted in 19th-century logical analysis, underscores how entities like sets or classes are identified solely by their members rather than their descriptive attributes.[12] Gottlob Frege employed the term in this sense in his 1893 work Grundgesetze der Arithmetik, where he defined the equality of concepts through their shared extensions, laying foundational groundwork for treating logical objects extensionally.[11] Ernst Zermelo, in his 1908 axiomatization of set theory, referred to the corresponding principle as the "Axiom der Bestimmtheit" (axiom of definiteness), emphasizing the unique determination of sets by their elements.[13] The English term "extensionality" gained traction in mathematical and logical discourse during the 1920s and 1930s, as formal axiomatic systems proliferated in works by David Hilbert and Paul Bernays, who adopted "Extensionalitätsaxiom" in their Grundlagen der Mathematik.[14] By the mid-20th century, through translations and standardizations in texts like Jean van Heijenoort's anthology, "Axiom of Extensionality" emerged as the conventional designation in English-language set theory. This shift marked a broader assimilation of German logical terminology into international mathematical practice, contrasting with intensional approaches that prioritize meaning over mere membership.[15]Origins and Early Formulations
The roots of the axiom of extensionality trace back to the late 19th century, embedded in the foundational concepts of set theory developed by Georg Cantor. In his seminal 1895 paper Beiträge zur Begründung der transfiniten Mengenlehre, Cantor defined a set as "any collection M into a whole of definite and separate objects m of our intuition or our thought."[16] This characterization implicitly embodies extensionality by treating sets as indistinguishable if they share the same elements, disregarding order or multiplicity, as membership equality determines the collection's identity. Building on such ideas, Gottlob Frege advanced a more formal version in his 1893 work Grundgesetze der Arithmetik. There, Basic Law V equates the extensions of two functions f and g precisely when they agree on all arguments: the course-of-values of f equals that of g if and only if f(x) = g(x) for every x.[17] This principle of extensionality for concept extensions served as a cornerstone for deriving arithmetic from logic but ultimately contributed to Bertrand Russell's 1901 paradox, exposing inconsistencies in unrestricted comprehension.[11] Ernst Zermelo explicitly formulated the axiom in 1908 to establish a paradox-free axiomatic foundation for set theory. In his paper Untersuchungen über die Grundlagen der Mengenlehre I, the axiom appears as the first postulate, known as the Axiom der Bestimmtheit (Axiom of Definiteness): if every element of set M belongs to N and every element of N belongs to M, then M = N.[18] Zermelo's inclusion resolved ambiguities in set equality arising from the paradoxes, using the term Bestimmtheit to denote this determinacy by membership.[13] In the ensuing decades, the axiom gained widespread acceptance and refinement in emerging systems. By the 1920s, John von Neumann integrated an extensionality axiom for sets and classes into his 1925 axiomatization, emphasizing equality via identical elements.[19] This approach was expanded in the von Neumann–Bernays–Gödel (NBG) framework through collaborations in the 1930s and 1940s, where extensionality extended to classes, reinforcing its status as a core principle in axiomatic set theory.Role in Zermelo-Fraenkel Set Theory
Statement in ZF
In Zermelo-Fraenkel set theory (ZF), the axiom of extensionality is the first axiom in the standard list and is formally stated as \forall x \forall y \, [\forall z (z \in x \leftrightarrow z \in y) \rightarrow x = y]. This asserts that two sets are equal if and only if they have precisely the same elements, with the converse direction following from the definition of equality in first-order logic.[20] Within ZF, which is a theory of pure sets without urelements, the axiom ensures that every set is fully determined by its elements, preventing distinctions or accidental equalities based on different constructions or notations.[20] This extensional characterization underpins the uniqueness of set constructions throughout the theory. The axiom is compatible with other ZF axioms, such as the axiom of the empty set, which posits the existence of a set with no elements (\exists x \, \neg \exists y (y \in x)); combined with extensionality, it guarantees that there is a unique empty set \varnothing.[20] Similarly, the axiom of pairing (\forall x \forall y \exists z \forall w (w \in z \leftrightarrow (w = x \lor w = y))) ensures the existence of a set containing exactly x and y, and extensionality makes this pair set \{x, y\} unique regardless of how it is formed.[20] For instance, consider the power set axiom (\forall x \exists y \forall z (z \in y \leftrightarrow z \subseteq x)), which asserts the existence of a set containing all subsets of x; extensionality proves the uniqueness of this power set \mathscr{P}(x), as any two such collections must have identical elements and thus be equal.[20]Relation to Other Axioms
The axiom of extensionality in Zermelo-Fraenkel set theory (ZF) relies on the underlying first-order logic's properties of equality for its converse implication, which states that equal sets have the same elements; this follows from the substitution property of equality, allowing the extensionality axiom to focus solely on the direction that sets with identical elements are equal.[21] Without this logical foundation, the axiom would require a biconditional formulation, but in standard ZF, it integrates seamlessly with equality to define set identity purely in terms of membership.[22] In interaction with the axiom schema of separation (the restricted comprehension in ZF), extensionality ensures the uniqueness of sets defined by properties. ZF's restricted comprehension limits definitions to subsets of existing sets, preventing the formation of paradoxical entities that arise in unrestricted comprehension schemes of naive set theory, while extensionality guarantees that such subsets are distinct only if their elements differ.[21] For instance, the empty set, obtained via separation as the subset with no elements, is unique due to extensionality, avoiding multiple indistinguishable empties that could undermine set construction.[22] Extensionality works with the axiom schema of separation to derive unique subsets from given sets based on formulas, ensuring that the resulting collection is a set identical to any other with the same elements, which is essential for iterative definitions in the cumulative hierarchy.[21] Similarly, in conjunction with the axiom schema of replacement, it guarantees that the image of a set under a definable function is a unique set, as extensionality identifies any two such images with matching elements; this interplay supports the transfinite recursion needed to build higher ranks in the von Neumann hierarchy.[22] The axiom of extensionality is independent of the remaining ZF axioms, as demonstrated by models where the other axioms hold but extensionality fails, such as partial models with multiple empty sets; this independence, established through consistency proofs, underscores extensionality's primitive status in ZF, though it is often assumed as foundational for practical set-theoretic reasoning.Formulations in Alternative Set Theories
In New Foundations (NF)
In Quine's New Foundations (NF) set theory, the axiom of extensionality is explicitly stated as a core postulate, formulated as \forall x \forall y \, (x = y \leftrightarrow \forall z (z \in x \leftrightarrow z \in y)), which asserts that two sets are identical if and only if they have precisely the same members.[23] This formulation, introduced by Willard Van Orman Quine in his 1937 paper "New Foundations for Mathematical Logic," serves as one of only two fundamental principles in NF, alongside the axiom schema of stratified comprehension. Unlike in Zermelo-Fraenkel set theory (ZF), where extensionality is paired with multiple other axioms to enforce well-foundedness, in NF it is integrated directly with stratified comprehension, which restricts set formation to formulas that respect a type-like stratification to avoid paradoxes like Russell's.[23] A key difference from ZF arises in NF's treatment of equality and membership, where extensionality applies universally within a single, stratified universe that includes a total set V comprising all sets. This allows the membership relation \in to define equality extensionally across the entire system, enabling the construction of sets that would be "proper classes" in ZF, such as the Russell class \{x \mid x \nsubseteq x\}, without leading to contradiction due to the stratification constraint.[23] Quine's 1937 framework thus positions extensionality as the foundational assumption for identifying sets solely by their elements, providing an alternative logical basis for mathematics that avoids the iterative hierarchy of ZF while maintaining extensional uniqueness. The implications of extensionality in NF extend to supporting non-well-founded structures, such as hypersets—sets that can contain themselves indirectly through infinite descending membership chains—and circular sets, which permit cyclic memberships like x \in y \in x.[23] This contrasts sharply with ZF's axiom of regularity, which enforces well-foundedness and prohibits such constructions; in NF, extensionality's integration with stratification allows these features without paradox, opening avenues for modeling recursive or self-referential entities in set theory.[23]In Zermelo Set Theory with Urelements (ZU)
In Zermelo Set Theory with Urelements (ZU), the axiom of extensionality is a primitive axiom, typically formulated to apply only to sets: \forall x \forall y \, (\mathrm{Set}(x) \land \mathrm{Set}(y) \land \forall z (z \in x \leftrightarrow z \in y) \to x = y), where \mathrm{Set} distinguishes sets from urelements.[13] Zermelo's original 1908 axiomatization incorporated the possibility of urelements—non-set atoms—as part of the domain, alongside axioms enabling the formation of sets via separation (Aussonderung), which extracts subsets defined by definite properties, and collection (implicit in union and power set operations), which ensures the existence of sets whose elements satisfy given definite conditions. These mechanisms, together with extensionality, guarantee that any two sets built iteratively from urelements, sharing identical membership, must coincide, as their construction uniquely determines their identity based on elements.[13] Urelements play a crucial role by serving as foundational atoms that are neither sets nor composed of elements, distinguished formally by the property that no object belongs to them (\forall u (U(u) \to \neg \exists v (v \in u)), where U denotes urelements). Extensionality thus applies post-construction: while urelements themselves may be indistinguishable except by primitive identity, any sets formed from them via separation and collection inherit uniqueness from their elements, preventing duplicate representations in the hierarchy. This distinction maintains the purity of set formation atop an atomic base.[13] In his 1908 paper, Zermelo introduced extensionality as the first axiom, stating that two sets are equal if they have the same elements, while accommodating urelements optionally to resolve foundational paradoxes.[13] Later developments have explored set theories with urelements in various non-standard contexts, such as anti-foundational approaches, while retaining extensionality as a primitive postulate.[13]Extensions and Modifications
With Urelements
In set theories incorporating urelements, also known as atoms, the axiom of extensionality requires modification to accommodate these primitive objects, which lack elements and internal set structure. The standard formulation of extensionality would equate all urelements to the empty set, as they share the property of having no members, thereby collapsing distinct urelements into a single entity. To preserve the distinctness of urelements while maintaining extensionality for constructed sets, the axiom is restricted to apply only to sets (excluding urelements).[24] The modified axiom states:\forall x \forall y \bigl( \mathrm{set}(x) \land \mathrm{set}(y) \land \forall z (z \in x \leftrightarrow z \in y) \to x = y \bigr),
where \mathrm{set}(x) indicates that x is a set, not a urelement. This ensures that any two sets with identical members are equal, while allowing multiple urelements to coexist as distinct non-set objects separate from the unique empty set \emptyset. In this setup, urelements serve as foundational building blocks without violating the identity principle for sets formed via the other axioms. The empty set remains the unique set with no elements, as the axiom applies to it.[24] The rationale for this adjustment stems from the nature of urelements, which are intended to model indivisible entities without membership relations, such as points in geometry or individuals in permutation models. Applying full extensionality over all objects would undermine their utility by forcing all such objects to be indistinguishable and equivalent to \emptyset, rendering them ineffective for applications like independence proofs. By restricting to sets, the axiom upholds the extensional characterization of sets built from urelements, ensuring uniqueness based on membership while permitting a potentially infinite or class-sized collection of distinct urelements.[25] In theories such as ZFA (Zermelo-Fraenkel set theory with atoms), this modified extensionality allows for the construction of unique sets containing urelements. For instance, given distinct urelements a and b, the sets \{a\} and \{b\} are distinct because their sole members differ, and \{a, b\} is uniquely determined by its contents. This framework supports the formation of hereditarily symmetric sets over urelements, where higher-rank sets inherit uniqueness from their elements via the modified axiom.[24] Historically, this adaptation emerged in the 1920s to facilitate permutation models for investigating the independence of the axiom of choice. Abraham Fraenkel introduced urelements in 1922 to construct models where choice fails, using permutations of the urelements to define symmetric subsets, with extensionality adjusted to preserve atomic distinctness.[25] In the 1930s, Andrzej Mostowski refined these models, solidifying the role of restricted extensionality in handling atoms.[26] Forcing techniques, developed by Paul Cohen in the 1960s for ZFC, were later extended to ZFA contexts, enabling broader independence results by incorporating urelements into generic extensions while maintaining the modified extensionality.[27]