Fact-checked by Grok 2 weeks ago

Unordered pair

In set theory, an unordered pair is a set consisting of exactly two elements, denoted as {a, b}, where the order of a and b does not matter, so {a, b} = {b, a}.^[1] If a = b, then {a, b} reduces to the singleton set {a}.^[2] The existence of such pairs for any sets a and b is guaranteed by the Axiom of Pairing, a fundamental axiom in Zermelo-Fraenkel set theory (ZF), which states that if a and b are sets, there exists a set whose elements are precisely a and b.^[3] Unordered pairs form a basic building block for constructing more complex sets and structures in mathematics.^[4] They differ from ordered pairs (a, b), which distinguish between the positions of a and b, with (a, b) ≠ (b, a) unless a = b.^[5] To define ordered pairs within pure set theory, which lacks inherent order, mathematicians use constructions based on unordered pairs, such as Kuratowski's definition: (a, b) = \{\{a\}, \{a, b\}\}, where the singleton \{a\} and the pair \{a, b\} encode the order.^[6] This approach ensures that all mathematical objects can be represented as sets, maintaining the foundational purity of set theory.^[5] Beyond set theory, unordered pairs appear in various mathematical contexts, such as graph theory, where the edges of an undirected graph are modeled as unordered pairs of vertices, capturing connections without direction.^[7] They also underpin the definition of Cartesian products and relations in more advanced structures, though relations themselves are typically sets of ordered pairs. The concept's simplicity belies its importance, as it enables the aggregation of elements essential for nearly all mathematical reasoning.^[3]

Definition and Notation

Formal Definition

In set theory, an unordered pair is fundamentally a set consisting of exactly two elements, where the sequence in which the elements are listed has no significance. Formally, for any sets a and b, the unordered pair \{a, b\} is the set whose elements are precisely a and b, satisfying the condition that x \in \{a, b\} if and only if x = a or x = b. This construction presupposes the basic notion of a set as an unordered collection of distinct objects, where membership is the sole primitive relation and there are no duplicate elements or inherent ordering among members.^[8] When a = b, the unordered pair \{a, a\} collapses to the singleton set \{a\}, containing only one element, as sets inherently exclude multiplicity. However, the standard conception of an unordered pair assumes a \neq b to ensure exactly two distinct elements, though the definition accommodates the degenerate case without contradiction.^[8]^[9] The existence of such unordered pairs is guaranteed by the axiom of pairing within Zermelo-Fraenkel set theory (ZF), which asserts that for any sets a and b, there exists a set z such that a \in z and b \in z. Combined with the axiom schema of specification (comprehension), this yields the unique set \{a, b\} containing exactly those elements, independent of order.^[8]^[9]

Common Notations

The primary notation for an unordered pair consisting of distinct elements a and b is the set \{a, b\}, which inherently disregards order such that \{a, b\} = \{b, a\}.^[10] This set-theoretic representation assumes a \neq b, as standard sets eliminate duplicates; attempting \{a, a\} collapses to the singleton \{a\}.^[10] When duplicates are permitted, such as for pairs where the elements may coincide, multiset notation is employed, allowing repeated listings within curly braces, as in \{a, a\} to denote two instances of a.^[11] In combinatorial settings, unordered pairs are frequently contextualized through the binomial coefficient, where \binom{|X|}{2} gives the number of all distinct unordered pairs from a set X, underscoring selections without regard to order.^[12]

Properties

Basic Properties

An unordered pair, denoted as {a, b}, is characterized by its indifference to the order of elements, meaning that {a, b} = {b, a} for any sets a and b, which distinguishes it from ordered structures like sequences where position matters.^[13] This property arises from the foundational axioms of set theory, particularly the Axiom of Extensionality, which equates sets based solely on their membership rather than arrangement.^[3] A key attribute of unordered pairs is the absence of duplicates; if a = b, then {a, a} simplifies to the singleton set {a}, containing only one distinct element rather than a true pair.^[13] This reflects the fundamental principle of sets as collections without repetition, ensuring that multiplicity does not affect membership.^[3] As subsets of the universal set, unordered pairs are closed under basic set operations, including union and intersection; for instance, the union of {a, b} and another set yields a set containing all unique elements from both, guaranteed by the Union Axiom, while intersection retains only shared elements via Separation.^[14] This closure underscores their integration into broader set-theoretic constructions.

Cardinality and Equality

The cardinality of an unordered pair \{a, b\} where a \neq b is exactly 2, as it consists of precisely two distinct elements, establishing it as a finite set of size 2 under the standard definition of cardinality via bijection to the natural number 2. If a = b, however, \{a, b\} reduces to the singleton \{a\} with cardinality 1, distinguishing it from the intended two-element structure. Equality of unordered pairs follows from the axiom of extensionality, which states that two sets are equal if and only if they have identical elements: thus, \{a, b\} = \{c, d\} if and only if {a, b} and {c, d} have exactly the same elements, regardless of order (e.g., \{a, b\} = \{b, a\}, but \{a, b\} \neq \{a, c\} if b \neq c). This extensional criterion ensures that unordered pairs are identified solely by their contents, without regard to arrangement. This cardinality contrasts with the empty set, which has cardinality 0, and singletons, which have cardinality 1, thereby underscoring the unordered pair's role as a minimal two-element collection in set constructions. As a result, any unordered pair \{a, [b](/page/List_of_French_composers)\} serves as a subset of a larger set S if and only if both a \in S and [b](/page/List_of_French_composers) \in S, facilitating its integration into broader set-theoretic structures.

Relation to Ordered Pairs

Kuratowski Encoding

In axiomatic set theory, ordered pairs are defined using unordered pairs to encode order without primitive ordered structures. Kazimierz Kuratowski introduced this construction in 1921, defining the ordered pair (a, b) as the set {{a}, {a, b}}. This uses the singleton {a} and the unordered pair {a, b} to distinguish the first and second elements: the unique singleton identifies the first, while the two-element set identifies the second.^[15] The rationale for this encoding is to construct all mathematical structures, such as Cartesian products and relations, using only sets and membership, aligning with the foundational goals of Zermelo-Fraenkel set theory (ZF) to minimize primitives. It relies on the Axiom of Pairing for unordered pairs and the Axiom of Union for singletons (derived from the empty set). This approach ensures expressive power while maintaining purity.^[15] To verify the encoding, note that it satisfies the key property of ordered pairs: (a, b) = (c, d) if and only if a = c and b = d. For distinct a and b, {{a}, {a, b}} ≠ {{b}, {b, a}}, since {a, b} = {b, a} but the singletons differ. If a = b, it reduces consistently to {{a}, {a}}. This prevents circularity, as unordered pairs are axiomatized directly.^[15]

Key Differences

The fundamental distinction between an unordered pair and an ordered pair lies in their treatment of element arrangement: an unordered pair {a, b} is symmetric, meaning {a, b} = {b, a} regardless of the elements' positions, whereas an ordered pair (a, b) distinguishes sequence, so (a, b) ≠ (b, a) unless a = b.^[16]^[13] This order insensitivity in unordered pairs stems from their definition as sets, which inherently disregard arrangement, while ordered pairs require a separate construction to encode sequence.^[17] In practical applications, unordered pairs are employed for collections where sequence is irrelevant, such as representing edges in undirected graphs, where {v, w} denotes a connection between vertices v and w without direction.^[18]^[19] Conversely, ordered pairs form the basis for functions and binary relations, where the distinction between input and output or source and target is essential, as a relation is defined as a set of such ordered pairs.^[20] Structurally, unordered pairs lack designated "first" or "second" elements, precluding the definition of projection functions that extract components by position, a feature inherent to ordered pairs.^[3] This absence reinforces their role as pure collections rather than sequenced tuples.^[17] Regarding interconversion, any unordered pair {a, b} with a ≠ b can be equivalently represented as the set of two ordered pairs {(a, b), (b, a)}, capturing both possible sequences, but deriving a single ordered pair from an unordered one requires selecting an order, which introduces arbitrariness absent in the reverse mapping.^[21]^[3]

Applications in Mathematics

In Set Theory

In axiomatic set theory, particularly Zermelo–Fraenkel set theory with the axiom of choice (ZFC), the unordered pair \{a, b\} is foundational, guaranteed to exist by the axiom of pairing. This axiom states that for any sets a and b, there exists a set u such that every element z of u is either a or b, formally: \forall x \forall y \exists u \forall z (z \in u \leftrightarrow (z = x \lor z = y)). By the axiom of extensionality, this u is unique and denoted \{a, b\}, which equals \{b, a\} regardless of order. The axiom enables the construction of singletons \{a\} as \{a, a\} and, through iteration starting from the empty set \emptyset, allows the formation of all finite sets, such as \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, and beyond, serving as the basis for defining the natural numbers in von Neumann's ordinals.^[22]^[9] Unordered pairs play a crucial role in the von Neumann cumulative hierarchy, which organizes the universe of sets into levels V_\alpha indexed by ordinals. The hierarchy begins with V_0 = \emptyset, and successor levels are defined as V_{\alpha+1} = \mathcal{P}(V_\alpha), the power set of V_\alpha, while limit levels take unions of previous stages. The initial finite levels build upon unordered pairs: V_1 = \{\emptyset\}, V_2 = \{\emptyset, \{\emptyset\}\}, and higher V_n incorporate pairs like \{\emptyset, \{\emptyset\}\} to generate all hereditarily finite sets. The union V_\omega, comprising all such finite iterations, contains precisely the hereditarily finite sets, where unordered pairs form the elementary building blocks for these initial strata.^[23] Within ZFC, unordered pairs are essential for defining more complex structures, starting with ordered pairs via Kuratowski's encoding (a, b) = \{\{a\}, \{a, b\}\}, which preserves order distinctions using only set-theoretic operations. This construction relies on the pairing axiom to form the inner singletons and pairs, enabling the definition of Cartesian products A \times B = \{(a, b) \mid a \in A, b \in B\} as sets of ordered pairs. From there, functions and relations follow as particular subsets of products, underpinning the theory's ability to model mathematics rigorously.^[22] Philosophically, unordered pairs reinforce the axiom of extensionality, which asserts that sets are identical if and only if they have the same elements: \forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y). This principle ensures that the identity of \{a, b\} depends solely on its elements, independent of presentation or order, embodying set theory's extensional view where sets are defined purely by membership relations. Such extensionality avoids structural ambiguities and supports the consistency of foundational constructions in ZFC.^[9]

In Combinatorics and Graph Theory

In combinatorics, unordered pairs play a fundamental role in counting selections where the order of elements does not matter. The number of unordered pairs that can be formed from a set of n distinct elements is given by the binomial coefficient \binom{n}{2} = \frac{n(n-1)}{2}, which counts the ways to choose 2 elements without regard to order.^[12] This formula arises in problems such as determining the number of handshakes among n people or the number of possible edges in a complete undirected graph.^[24] In graph theory, unordered pairs are essential for modeling undirected graphs, where each edge is represented as an unordered pair \{u, v\} connecting two vertices u and v, with no distinction between the directions from u to v or v to u.^[25] This contrasts with directed graphs, where edges are ordered pairs or arcs. The use of unordered pairs ensures that the graph structure captures symmetric relationships, such as mutual connections in social networks or physical links in transportation systems.^[26] An extension to multisets allows unordered pairs to include repeated elements, such as \{a, a\}, which accommodates scenarios like self-loops in graphs or selections with repetition in advanced counting problems.^[27] In graph theory, such pairs model loops at a vertex, enabling representations of structures like pseudographs. In combinatorics, this supports combinations with repetition, where the formula adjusts to account for multiplicities.^[28] In algorithms, unordered pairs influence designs requiring symmetry, such as hashing for efficient storage and lookup in undirected graph representations. Custom hash functions for unordered pairs ensure that \{u, v\} and \{v, u\} map to the same value, avoiding duplicates in data structures like adjacency lists or edge sets.^[29] This approach is critical in graph algorithms for tasks like isomorphism testing or subgraph matching, where order invariance preserves computational efficiency.^[30]

Historical Context

Origins in Set Theory

In the 17th century, Gottfried Wilhelm Leibniz developed the concept of aggregates as collections of distinct entities unified solely through extrinsic relations, such as spatial proximity or conceptual association, rather than any intrinsic order or structure. These aggregates, exemplified by a flock of sheep perceived as a unity only in the mind of an observer, lacked inherent unity and were mind-dependent, foreshadowing the idea of unordered collections in modern set theory by emphasizing relational grouping without sequential arrangement.^[31] The foundational conceptualization of unordered pairs emerged in the late 19th century through Georg Cantor's work on infinite point sets, where sets were introduced as arbitrary, unordered collections of elements during his investigations into the continuum in the 1870s. Cantor's 1872 paper on point sets implicitly treated pairs as basic components of these collections, viewing them as extensional entities determined solely by their members, without regard to order. This approach, elaborated in his Grundlagen einer allgemeinen Mannigfaltigkeitslehre (1883), established sets as unitary objects comprising infinite multiplicities, with pairs serving as implicit building blocks in analyses of real number points.^[32] Cantor's development was motivated by the need to resolve paradoxes arising from infinite sets, such as the apparent equipollence of intervals of different lengths, by prioritizing extensional equality—where two sets are identical if they share the same elements—over intuitive notions of size or order. This emphasis on extensionality helped address inconsistencies in transfinite arithmetic, ensuring that infinite collections could be rigorously compared without leading to contradictions like the uncountability of the reals conflicting with naive infinity assumptions.^[32] The explicit formalization of unordered pairs occurred in Ernst Zermelo's 1908 axiomatization of set theory, where the axiom of pairing asserts that for any sets A and B, there exists a set C such that x \in C if and only if x = A or x = B, denoted \{A, B\}. This axiom directly enables the construction of unordered pairs, confirming their uniqueness via the axiom of extensionality and distinguishing them from ordered structures, thus providing a foundational tool for building complex sets from simpler ones.^[33]

Evolution and Usage

In 1921, Kazimierz Kuratowski advanced the formal treatment of pairs in set theory by defining ordered pairs in terms of unordered pairs, using the construction (a, b) = \{\{a\}, \{a, b\}\}. This approach resolved ambiguities in earlier definitions, such as Norbert Wiener's 1914 proposal, and facilitated precise constructions in pure set theory without primitive ordered pairs.^[34]^[35] Post-World War II developments saw the integration of unordered pairs into category theory and model theory as foundational elements. In category theory, initiated by Samuel Eilenberg and Saunders Mac Lane in the 1940s, unordered pairs relate to symmetric constructions like the coequalizer of the projections from the product object, serving as building blocks for morphisms and diagrams in abstract algebraic structures.^[36] Similarly, in model theory, which gained prominence through Alfred Tarski's work in the 1950s, unordered pairs underpin the interpretation of basic relations and the cardinality of structures in non-standard models of set theory. These integrations highlighted the versatility of unordered pairs beyond pure set theory, influencing applications in topology and logic. In contemporary computer science, unordered pairs have found widespread adoption in data structures designed for efficient handling of unique, order-independent elements. For example, Python's frozenset class implements immutable unordered collections, enabling the representation of an unordered pair \{a, b\} as \text{frozenset}(\{a, b\}), which supports hashing and set operations crucial for algorithms in databases and graph processing. This practical usage underscores the transition from theoretical constructs to computational tools, with similar implementations in languages like C++ via unordered_set for pair keys.^[37] Debates persist on the role of unordered pairs in constructivism versus classical set theory, particularly regarding their existential assumptions. In classical Zermelo-Fraenkel set theory, the pair axiom unconditionally guarantees the existence of \{a, b\} for any sets a and b, supporting impredicative definitions. In contrast, constructive set theories like IZF retain the pair axiom but emphasize that proofs involving pairs must provide explicit constructions, avoiding reliance on the law of excluded middle, which can limit certain non-constructive applications in intuitionistic frameworks.^[38]

References

[1]
Basic Set Theory - Stanford Encyclopedia of Philosophy
We begin by introducing the notion of the ordered pair. If a and b are sets, then the unordered pair {a, b} is a set whose elements are exactly a and b. The “ ...
[2]
[PDF] Section 3. Unordered Pairs
Jan 3, 2023 · Unordered Pairs. Note. In this section, we axiomatically hypothesize that a set exists and that, for given sets a and b, the set {a, b} exists.
[3]
[PDF] A Sketch of the Rudiments of Set Theory
Axiom 3 (Axiom of Pairing). If a and b are sets, then there exists a set whose elements are exactly a and b. This set is called the unordered pair of a and b, ...
[4]
[PDF] Elements of Set Theory by Sidney Felder - Rutgers Philosophy
In thinking about anything, we mentally aggregate and separate things in all kinds of combinations. In any such case, we are forming sets.
[5]
Notes on Set Theory - Northwestern University
A × B := {(a, b) | a ∈ A and b ∈ B}. To be precise, we should give a definition for the term “ordered pair”. ... ordered pair (a, b) as the set. {{a},{a, b}} ...<|control11|><|separator|>
[6]
No Title - Stony Brook Computer Science
Surprisingly, (ordered) pairs can be defined in terms of (unordered) sets. In set theory, an ordered pair (x,y) is taken as an abbreviation for the set ...
[7]
Unordered Pair - an overview | ScienceDirect Topics
Unordered pairs refer to sets of two elements where the order does not matter, commonly represented as pairs consisting of a vertex from one set and a vertex ...
[8]
[PDF] a brief introduction to zfc
Sep 26, 2016 · Abstract. We present a basic axiomatic development of Zermelo-Fraenkel and Choice set theory, commonly abbreviated ZFC.
[9]
[PDF] Set Theory (MATH 6730)
For any sets x and y we define the ordered pair (x, y) to be the set {{x},{x, y}}. By the pairing axiom (applied three times), {{x},{x, y}} is indeed a set. The ...
[10]
unordered pair in nLab
### Summary of Notation for Unordered Pairs
[11]
3.5 Counting Multisets - Discrete Mathematics
Multisets are written using the same notation as sets: a comma-separated list in braces, such as .
[12]
Binomial Coefficient -- from Wolfram MathWorld
The binomial coefficient (n; k) is the number of ways of picking k unordered outcomes from n possibilities, also known as a combination or combinatorial number.
[13]
SetTheory - Department of Computer Science
Two sets A and B that have no elements in common are said to be disjoint; in set-theoretic notation, this means A∩B = ∅. In this case we have |A∪B| = |A|+|B|.
[14]
[PDF] The Axioms of Set Theory.
(4) (Pairing) Given sets A and B, there is a set whose only elements are A and B. (I.e., the unordered pair {A, B} is a set.) (5) (Union) Given a set A, the ...
[15]
Set Theory - Stanford Encyclopedia of Philosophy
Oct 8, 2014 · The Axiom of Choice is equivalent, modulo ZF, to the Well-ordering Principle, which asserts that every set can be well-ordered, i.e., it can be ...
[16]
[PDF] CS 19: Discrete Mathematics
Set versus Ordered Pair. Important! A set is inherently unordered. Therefore, {a, b} = {b, a}. However, for an ordered pair, the order matters. Therefore, (a ...<|control11|><|separator|>
[17]
[PDF] Graphs and Relations
Jan 22, 2019 · Ordered and Unordered Pairs. ○ An unordered pair is a set {a, b} of two elements. (remember that sets are unordered). ○. {0, 1} = {1, 0}.
[18]
[PDF] Introduction to Graph Theory - FSU Mathematics
Since the edges of a simple graph are undirected, they are represented by unordered pairs of vertices rather than ordered pairs. For example, if V = {a, b ...
[19]
[PDF] Def. A simple graph G = (V,E) consists of a nonempty Set of vertices ...
A simple graph G = (V,E) consists of a nonempty set of vertices, V, and a distinct set of unordered pairs of vertices called edges, E.
[20]
Basic Set Theory - Stanford Encyclopedia of Philosophy
A binary relation is determined by specifying all ordered pairs of objects in that relation; it does not matter by what property the set of these ordered pairs ...
[21]
[PDF] ∑ ∑ U - cs.Princeton
Each unordered pair is listed twice on a list of the ordered pairs, but we consider the ordered pairs to be the same. 31. Ordered Versus Unordered. • From a ...
[22]
[PDF] The Axioms of Set Theory ZFC
However, with the Axiom of Pairing we can easily define ordered pairs, denoted hx, yi, as follows: hx, yi := {x}, {x, y} . It is not hard to show that hx, yi = ...
[23]
[PDF] Set Theory and the Foundation of Mathematics - KWARC
Jun 19, 2018 · For any set x, we call the degree of x (deg(x)) the smallest α ∈ On with x ∈ Vα (definable). Page 12. The Von Neumann Hierarchy. 12. Page 13 ...<|separator|>
[24]
2.4: Combinations and the Binomial Theorem
Aug 16, 2021 · The binomial coefficient ( n k ) represents the number of combinations of n objects taken k at a time, and is read “ n choose k . ” We would now ...
[25]
[PDF] Graph theory terminology – Undirected graphs
An edge is an unordered pair of vertices. Two vertices joined by an edge are said to be adjacent. Two vertices are neighbors if they are adjacent.
[26]
[PDF] Chapter 2 Mathematical Preliminaries
) is a set of edges. In an undirected graph, each edge is an unordered pair e = {u, v} (or equivalently {v, u}). By this definition an undirected graph ...
[27]
Multiset Theory - Project Euclid
A multiset is a collection of elements where elements can repeat, and the number of times an element occurs is its multiplicity. A set is a multiset where ...
[28]
Combinations - StatLect
Like sets, multisets are unordered collections of objects, i.e. the order in which the elements of a multiset are listed does not matter. Let a_1 , a_2 ,..., ...<|separator|>
[29]
How to create an unordered_map of pairs in C++? - GeeksforGeeks
Jul 11, 2025 · To create an unordered_map of pairs in C++, you need a custom hash function, as unordered_map doesn't have a default one for pairs. Example: ` ...
[30]
(PDF) General Graph Identification With Hashing - ResearchGate
A method for identifying graphs using MD5 hashing is presented. This allows fast graph equality comparisons and can also be used to facilitate graph isomorphism ...
[31]
[PDF] Leibniz's Notion of an Aggregate
Leibniz notes that, while our ideas of aggregates have a unity that is 'very genuine', the aggregates or collections themselves are uni ed by nothing more than ...
[32]
[PDF] SET THEORY FROM CANTOR TO COHEN
Working out of this tradition Georg Cantor1(1845–1918) in 1870 established a basic ... dering relations as collections of ordered pairs.63 Hausdorff thus made ...
[33]
[PDF] fundamentals of zermelo-fraenkel set theory
Aug 23, 2011 · Ernst Zermelo proposed the first axiomatic set theory in 1908 ... Axiom of Pair. For any A and B, there exists C such that x ∈ C if ...
[34]
unordered pair in nLab
Dec 12, 2022 · An unordered pair is just an element of said quotient set. In material set theory without ordered pairing structure, an unordered pair is ...Idea · Definition · In type theory
[35]
Reconsidering Ordered Pairs - jstor
Abstract. The well known Wiener-Kuratowski explicit definition of the ordered pair, which sets (x,y) = {{x}, {x, y}}, works well in many set theories but fails ...Missing: title | Show results with:title
[36]
Category Theory - Stanford Encyclopedia of Philosophy
Dec 6, 1996 · Category theory reveals how different kinds of structures are related to one another. For instance, in algebraic topology, topological spaces ...
[37]
unordered set of Pairs in C++ with Examples - GeeksforGeeks
Jul 23, 2025 · An unordered set of pairs is an unordered set in which each element is a pair itself. By default, C++ doesn't allow us to create an unordered set of pairs ...
[38]
Constructive Set Theory - jstor
Given any two objects, a and b, there exists their unordered pair. D4 (3X)(Vx)(x c X x = a V x = b); this is called {a, b}. (The ordered pair (a, b) is that ...