Ordered pair

Last updated

In mathematics, an ordered pair (a, b) is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (a, b) is different from the ordered pair (b, a) unless a = b. (In contrast, the unordered pair {a, b} equals the unordered pair {b, a}.)


Ordered pairs are also called 2-tuples, or sequences (sometimes, lists in a computer science context) of length 2. Ordered pairs of scalars are sometimes called 2-dimensional vectors. (Technically, this is an abuse of terminology since an ordered pair need not be an element of a vector space.) The entries of an ordered pair can be other ordered pairs, enabling the recursive definition of ordered n-tuples (ordered lists of n objects). For example, the ordered triple (a,b,c) can be defined as (a, (b,c)), i.e., as one pair nested in another.

In the ordered pair (a, b), the object a is called the first entry, and the object b the second entry of the pair. Alternatively, the objects are called the first and second components, the first and second coordinates, or the left and right projections of the ordered pair.

Cartesian products and binary relations (and hence functions) are defined in terms of ordered pairs.


Let and be ordered pairs. Then the characteristic (or defining) property of the ordered pair is:

The set of all ordered pairs whose first entry is in some set A and whose second entry is in some set B is called the Cartesian product of A and B, and written A × B. A binary relation between sets A and B is a subset of A × B.

The (a, b) notation may be used for other purposes, most notably as denoting open intervals on the real number line. In such situations, the context will usually make it clear which meaning is intended. [1] [2] For additional clarification, the ordered pair may be denoted by the variant notation , but this notation also has other uses.

The left and right projection of a pair p is usually denoted by π1(p) and π2(p), or by π(p) and πr(p), respectively. In contexts where arbitrary n-tuples are considered, πn
(t) is a common notation for the i-th component of an n-tuple t.

Informal and formal definitions

In some introductory mathematics textbooks an informal (or intuitive) definition of ordered pair is given, such as

For any two objects a and b, the ordered pair (a, b) is a notation specifying the two objects a and b, in that order. [3]

This is usually followed by a comparison to a set of two elements; pointing out that in a set a and b must be different, but in an ordered pair they may be equal and that while the order of listing the elements of a set doesn't matter, in an ordered pair changing the order of distinct entries changes the ordered pair.

This "definition" is unsatisfactory because it is only descriptive and is based on an intuitive understanding of order. However, as is sometimes pointed out, no harm will come from relying on this description and almost everyone thinks of ordered pairs in this manner. [4]

A more satisfactory approach is to observe that the characteristic property of ordered pairs given above is all that is required to understand the role of ordered pairs in mathematics. Hence the ordered pair can be taken as a primitive notion, whose associated axiom is the characteristic property. This was the approach taken by the N. Bourbaki group in its Theory of Sets, published in 1954. However, this approach also has its drawbacks as both the existence of ordered pairs and their characteristic property must be axiomatically assumed. [3]

Another way to rigorously deal with ordered pairs is to define them formally in the context of set theory. This can be done in several ways and has the advantage that existence and the characteristic property can be proven from the axioms that define the set theory. One of the most cited versions of this definition is due to Kuratowski (see below) and his definition was used in the second edition of Bourbaki's Theory of Sets, published in 1970. Even those mathematical textbooks that give an informal definition of ordered pairs will often mention the formal definition of Kuratowski in an exercise.

Defining the ordered pair using set theory

If one agrees that set theory is an appealing foundation of mathematics, then all mathematical objects must be defined as sets of some sort. Hence if the ordered pair is not taken as primitive, it must be defined as a set. [5] Several set-theoretic definitions of the ordered pair are given below( see also [6] ).

Wiener's definition

Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914: [7]

He observed that this definition made it possible to define the types of Principia Mathematica as sets. Principia Mathematica had taken types, and hence relations of all arities, as primitive.

Wiener used {{b}} instead of {b} to make the definition compatible with type theory where all elements in a class must be of the same "type". With b nested within an additional set, its type is equal to 's.

Hausdorff's definition

About the same time as Wiener (1914), Felix Hausdorff proposed his definition:

"where 1 and 2 are two distinct objects different from a and b." [8]

Kuratowski's definition

In 1921 Kazimierz Kuratowski offered the now-accepted definition [9] [10] of the ordered pair (a, b):

Note that this definition is used even when the first and the second coordinates are identical:

Given some ordered pair p, the property "x is the first coordinate of p" can be formulated as:

The property "x is the second coordinate of p" can be formulated as:

In the case that the left and right coordinates are identical, the right conjunct is trivially true, since Y1Y2 is never the case.

This is how we can extract the first coordinate of a pair (using the notation for arbitrary intersection and arbitrary union):

This is how the second coordinate can be extracted:


The above Kuratowski definition of the ordered pair is "adequate" in that it satisfies the characteristic property that an ordered pair must satisfy, namely that . In particular, it adequately expresses 'order', in that is false unless . There are other definitions, of similar or lesser complexity, that are equally adequate:

  • [11]

The reverse definition is merely a trivial variant of the Kuratowski definition, and as such is of no independent interest. The definition short is so-called because it requires two rather than three pairs of braces. Proving that short satisfies the characteristic property requires the Zermelo–Fraenkel set theory axiom of regularity. [12] Moreover, if one uses von Neumann's set-theoretic construction of the natural numbers, then 2 is defined as the set {0, 1} = {0, {0}}, which is indistinguishable from the pair (0, 0)short. Yet another disadvantage of the short pair is the fact, that even if a and b are of the same type, the elements of the short pair are not. (However, if a = b then the short version keeps having cardinality 2, which is something one might expect of any "pair", including any "ordered pair". Also note that the short version is used in Tarski–Grothendieck set theory, upon which the Mizar system is founded.)

Proving that definitions satisfy the characteristic property

Prove: (a, b) = (c, d) if and only if a = c and b = d.

If. If a = c and b = d, then {{a}, {a, b}} = {{c}, {c, d}}. Thus (a, b)K = (c, d)K.

Only if. Two cases: a = b, and ab.

If a = b:

(a, b)K = {{a}, {a, b}} = {{a}, {a, a}} = {{a}}.
(c, d)K = {{c}, {c, d}} = {{a}}.
Thus {c} = {c, d} = {a}, which implies a = c and a = d. By hypothesis, a = b. Hence b = d.

If ab, then (a, b)K = (c, d)K implies {{a}, {a, b}} = {{c}, {c, d}}.

Suppose {c, d} = {a}. Then c = d = a, and so {{c}, {c, d}} = {{a}, {a, a}} = {{a}, {a}} = {{a}}. But then {{a}, {a, b}} would also equal {{a}}, so that b = a which contradicts ab.
Suppose {c} = {a, b}. Then a = b = c, which also contradicts ab.
Therefore {c} = {a}, so that c = a and {c, d} = {a, b}.
If d = a were true, then {c, d} = {a, a} = {a} ≠ {a, b}, a contradiction. Thus d = b is the case, so that a = c and b = d.

(a, b)reverse = {{b}, {a, b}} = {{b}, {b, a}} = (b, a)K.

If. If (a, b)reverse = (c, d)reverse, (b, a)K = (d, c)K. Therefore, b = d and a = c.

Only if. If a = c and b = d, then {{b}, {a, b}} = {{d}, {c, d}}. Thus (a, b)reverse = (c, d)reverse.

Short: [13]

If: If a = c and b = d, then {a, {a, b}} = {c, {c, d}}. Thus (a, b)short = (c, d)short.

Only if: Suppose {a, {a, b}} = {c, {c, d}}. Then a is in the left hand side, and thus in the right hand side. Because equal sets have equal elements, one of a = c or a = {c, d} must be the case.

If a = {c, d}, then by similar reasoning as above, {a, b} is in the right hand side, so {a, b} = c or {a, b} = {c, d}.
If {a, b} = c then c is in {c, d} = a and a is in c, and this combination contradicts the axiom of regularity, as {a, c} has no minimal element under the relation "element of."
If {a, b} = {c, d}, then a is an element of a, from a = {c, d} = {a, b}, again contradicting regularity.
Hence a = c must hold.

Again, we see that {a, b} = c or {a, b} = {c, d}.

The option {a, b} = c and a = c implies that c is an element of c, contradicting regularity.
So we have a = c and {a, b} = {c, d}, and so: {b} = {a, b} \ {a} = {c, d} \ {c} = {d}, so b = d.

Quine–Rosser definition

Rosser (1953) [14] employed a definition of the ordered pair due to Quine which requires a prior definition of the natural numbers. Let be the set of natural numbers and define first

The function increments its argument if it is a natural number and leaves it as is otherwise; the number 0 does not appear as functional value of . As is the set of the elements of not in go on with

This is the set image of a set under , sometimes denoted by as well. Applying function to a set x simply increments every natural number in it. In particular, does never contain the number 0, so that for any sets x and y,

Further, define

By this, does always contain the number 0.

Finally, define the ordered pair (A, B) as the disjoint union

(which is in alternate notation).

Extracting all the elements of the pair that do not contain 0 and undoing yields A. Likewise, B can be recovered from the elements of the pair that do contain 0. [15]

For example, the pair is encoded as provided .

In type theory and in outgrowths thereof such as the axiomatic set theory NF, the Quine–Rosser pair has the same type as its projections and hence is termed a "type-level" ordered pair. Hence this definition has the advantage of enabling a function, defined as a set of ordered pairs, to have a type only 1 higher than the type of its arguments. This definition works only if the set of natural numbers is infinite. This is the case in NF, but not in type theory or in NFU. J. Barkley Rosser showed that the existence of such a type-level ordered pair (or even a "type-raising by 1" ordered pair) implies the axiom of infinity. For an extensive discussion of the ordered pair in the context of Quinian set theories, see Holmes (1998). [16]

Cantor–Frege definition

Early in the development of the set theory, before paradoxes were discovered, Cantor followed Frege by defining the ordered pair of two sets as the class of all relations that hold between these sets, assuming that the notion of relation is primitive: [17]

This definition is inadmissible in most modern formalized set theories and is methodologically similar to defining the cardinal of a set as the class of all sets equipotent with the given set. [18]

Morse definition

Morse–Kelley set theory makes free use of proper classes. [19] Morse defined the ordered pair so that its projections could be proper classes as well as sets. (The Kuratowski definition does not allow this.) He first defined ordered pairs whose projections are sets in Kuratowski's manner. He then redefined the pair

where the component Cartesian products are Kuratowski pairs of sets and where

This renders possible pairs whose projections are proper classes. The Quine–Rosser definition above also admits proper classes as projections. Similarly the triple is defined as a 3-tuple as follows:

The use of the singleton set which has an inserted empty set allows tuples to have the uniqueness property that if a is an n-tuple and b is an m-tuple and a = b then n = m. Ordered triples which are defined as ordered pairs do not have this property with respect to ordered pairs.

Axiomatic definition

Ordered pairs can also be introduced in Zermelo–Fraenkel set theory(ZF) axiomatically by just adding to ZF a new function symbol of arity 2 (it is usually omitted) and a defining axiom for :

This definition is acceptable because this extension of ZF is a conservative extension.[ citation needed ]

The definition helps to avoid so called accidental theorems like (a,a) = {{a}}, {a} ∈ (a,b), if Kuratowski's definition (a,b) = {{a}, {a,b}} was used.

Category theory

Commutative diagram for the set product X1xX2. CategoricalProduct-03.svg
Commutative diagram for the set product X1×X2.

A category-theoretic product A × B in a category of sets represents the set of ordered pairs, with the first element coming from A and the second coming from B. In this context the characteristic property above is a consequence of the universal property of the product and the fact that elements of a set X can be identified with morphisms from 1 (a one element set) to X. While different objects may have the universal property, they are all naturally isomorphic.

Related Research Articles

Associative algebra Algebraic structure with (a + b)(c + d) = ac + ad + bc + bd and (a)(bc) = (ab)(c)

In mathematics, an associative algebra is an algebraic structure with compatible operations of addition, multiplication, and a scalar multiplication by elements in some field. The addition and multiplication operations together give A the structure of a ring; the addition and scalar multiplication operations together give A the structure of a vector space over K. In this article we will also use the term K-algebra to mean an associative algebra over the field K. A standard first example of a K-algebra is a ring of square matrices over a field K, with the usual matrix multiplication.

In mathematics, particularly linear algebra and functional analysis, a spectral theorem is a result about when a linear operator or matrix can be diagonalized. This is extremely useful because computations involving a diagonalizable matrix can often be reduced to much simpler computations involving the corresponding diagonal matrix. The concept of diagonalization is relatively straightforward for operators on finite-dimensional vector spaces but requires some modification for operators on infinite-dimensional spaces. In general, the spectral theorem identifies a class of linear operators that can be modeled by multiplication operators, which are as simple as one can hope to find. In more abstract language, the spectral theorem is a statement about commutative C*-algebras. See also spectral theory for a historical perspective.

Arithmetical hierarchy Hierarchy of complexity classes for formulas defining sets

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.

In mathematics, particularly in functional analysis, the spectrum of a bounded linear operator is a generalisation of the set of eigenvalues of a matrix. Specifically, a complex number λ is said to be in the spectrum of a bounded linear operator T if is not invertible, where I is the identity operator. The study of spectra and related properties is known as spectral theory, which has numerous applications, most notably the mathematical formulation of quantum mechanics.

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:

Foliation In mathematics, a type of equivalence relation on an n-manifold

In mathematics, a foliation is an equivalence relation on an n-manifold, the equivalence classes being connected, injectively immersed submanifolds, all of the same dimension p, modeled on the decomposition of the real coordinate space Rn into the cosets x + Rp of the standardly embedded subspace Rp. The equivalence classes are called the leaves of the foliation. If the manifold and/or the submanifolds are required to have a piecewise-linear, differentiable, or analytic structure then one defines piecewise-linear, differentiable, or analytic foliations, respectively. In the most important case of differentiable foliation of class Cr it is usually understood that r ≥ 1. The number p is called the dimension of the foliation and q = np is called its codimension.

In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.

Reproducing kernel Hilbert space

In functional analysis, a reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which point evaluation is a continuous linear functional. Roughly speaking, this means that if two functions and in the RKHS are close in norm, i.e., is small, then and are also pointwise close, i.e., is small for all . The reverse does not need to be true.

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

In mathematics, a sesquilinear form is a generalization of a bilinear form that, in turn, is a generalization of the concept of the dot product of Euclidean space. A bilinear form is linear in each of its arguments, but a sesquilinear form allows one of the arguments to be "twisted" in a semilinear manner, thus the name; which originates from the Latin numerical prefix sesqui- meaning "one and a half". The basic concept of the dot product – producing a scalar from a pair of vectors – can be generalized by allowing a broader range of scalar values and, perhaps simultaneously, by widening the definition of a vector.

In abstract algebra, Hilbert's Theorem 90 is an important result on cyclic extensions of fields that leads to Kummer theory. In its most basic form, it states that if L/K is an extension of fields with cyclic Galois group G = Gal(L/K) generated by an element and if is an element of L of relative norm 1, that is

A locally compact quantum group is a relatively new C*-algebraic approach toward quantum groups that generalizes the Kac algebra, compact-quantum-group and Hopf-algebra approaches. Earlier attempts at a unifying definition of quantum groups using, for example, multiplicative unitaries have enjoyed some success but have also encountered several technical problems.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic. For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and , and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix , which expresses that depends on , and depends on , but does not depend on .

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In functional analysis, the dual norm is a measure of size for a continuous linear function defined on a normed vector space.

In computability theory, index sets describe classes of computable functions; specifically, they give all indices of functions in a certain class, according to a fixed Gödel numbering of partial computable functions.

Cartesian product

In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B. In terms of set-builder notation, that is

In mathematics, lifting theory was first introduced by John von Neumann in a pioneering paper from 1931, in which he answered a question raised by Alfréd Haar. The theory was further developed by Dorothy Maharam (1958) and by Alexandra Ionescu Tulcea and Cassius Ionescu Tulcea (1961). Lifting theory was motivated to a large extent by its striking applications. Its development up to 1969 was described in a monograph of the Ionescu Tulceas. Lifting theory continued to develop since then, yielding new results and applications.

In representation theory of mathematics, the Waldspurger formula relates the special values of two L-functions of two related admissible irreducible representations. Let k be the base field, f be an automorphic form over k, π be the representation associated via the Jacquet–Langlands correspondence with f. Goro Shimura (1976) proved this formula, when and f is a cusp form; Günter Harder made the same discovery at the same time in an unpublished paper. Marie-France Vignéras (1980) proved this formula, when { and f is a newform. Jean-Loup Waldspurger, for whom the formula is named, reproved and generalized the result of Vignéras in 1985 via a totally different method which was widely used thereafter by mathematicians to prove similar formulas.

In first-order arithmetic, the induction principles, bounding principles, and least number principles are three related families of first-order principles, which may or may not hold in nonstandard models of arithmetic. These principles are often used in reverse mathematics to calibrate the axiomatic strength of theorems.


  1. Lay, Steven R. (2005), Analysis / With an Introduction to Proof (4th ed.), Pearson / Prentice Hall, p. 50, ISBN   978-0-13-148101-5
  2. Devlin, Keith (2004), Sets, Functions and Logic / An Introduction to Abstract Mathematics (3rd ed.), Chapman & Hall / CRC, p. 79, ISBN   978-1-58488-449-1
  3. 1 2 Wolf, Robert S. (1998), Proof, Logic, and Conjecture / The Mathematician's Toolbox, W. H. Freeman and Co., p. 164, ISBN   978-0-7167-3050-7
  4. Fletcher, Peter; Patty, C. Wayne (1988), Foundations of Higher Mathematics, PWS-Kent, p. 80, ISBN   0-87150-164-3
  5. Quine has argued that the set-theoretical implementations of the concept of the ordered pair is a paradigm for the clarification of philosophical ideas (see "Word and Object", section 53). The general notion of such definitions or implementations are discussed in Thomas Forster "Reasoning about theoretical entities".
  6. Dipert, Randall. "Set-Theoretical Representations of Ordered Pairs and Their Adequacy for the Logic of Relations".
  7. Wiener's paper "A Simplification of the logic of relations" is reprinted, together with a valuable commentary on pages 224ff in van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1979–1931, Harvard University Press, Cambridge MA, ISBN   0-674-32449-8 (pbk.). van Heijenoort states the simplification this way: "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes".
  8. cf introduction to Wiener's paper in van Heijenoort 1967:224
  9. cf introduction to Wiener's paper in van Heijenoort 1967:224. van Heijenoort observes that the resulting set that represents the ordered pair "has a type higher by 2 than the elements (when they are of the same type)"; he offers references that show how, under certain circumstances, the type can be reduced to 1 or 0.
  10. Kuratowski, Casimir (1921). "Sur la notion de l'ordre dans la Théorie des Ensembles" (PDF). Fundamenta Mathematicae . 2 (1): 161–171. doi: 10.4064/fm-2-1-161-171 . Archived from the original (PDF) on 2019-04-29. Retrieved 2013-05-29.
  11. This differs from Hausdorff's definition in not requiring the two elements 0 and 1 to be distinct from a and b.
  12. Tourlakis, George (2003) Lectures in Logic and Set Theory. Vol. 2: Set Theory. Cambridge Univ. Press. Proposition III.10.1.
  13. For a formal Metamath proof of the adequacy of short, see here (opthreg). Also see Tourlakis (2003), Proposition III.10.1.
  14. J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw–Hill.
  15. Holmes, M. Randall: On Ordered Pairs , on: Boise State, March 29, 2009. The author uses for and for .
  16. Holmes, M. Randall (1998) Elementary Set Theory with a Universal Set Archived 2011-04-11 at the Wayback Machine . Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web.
  17. Frege, Gottlob (1893). Grundgesetze der Arithmetik (PDF). Jena: Verlag Hermann Pohle. §144
  18. Kanamori, Akihiro (2007). Set Theory From Cantor to Cohen (PDF). Elsevier BV. p. 22, footnote 59
  19. Morse, Anthony P. (1965). A Theory of Sets . Academic Press.