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 equals the unordered pair .)
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, cf. picture.
Let
(a1,b1)
(a2,b2)
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 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. For additional clarification, the ordered pair may be denoted by the variant notation , but this notation also has other uses.
The left and right 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, (t) is a common notation for the i-th component of an n-tuple t.
In some introductory mathematics textbooks an informal (or intuitive) definition of ordered pair is given, such as
For any two objects and, the ordered pair is a notation specifying the two objects and, in that order.This is usually followed by a comparison to a set of two elements; pointing out that in a set and 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.
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.
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.
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.[1] Several set-theoretic definitions of the ordered pair are given below(see also [2]).
Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914:[3] 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 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
\{\{a\},\emptyset\}
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."[4]
In 1921 Kazimierz Kuratowski offered the now-accepted definition[5] [6] of the ordered pair (a, b):When the first and the second coordinates are identical, the definition obtains:
(\forallY1,Y2\inp:Y1\neY2\rarr(x\notinY1\lorx\notinY2))
If
p=(x,y)=\{\{x\},\{x,y\}\}
capp=cap\{\{x\},\{x,y\}\}=\{x\}\cap\{x,y\}=\{x\},
cupp=cup\{\{x\},\{x,y\}\}=\{x\}\cup\{x,y\}=\{x,y\}.
This is how we can extract the first coordinate of a pair (using the iterated-operation notation for arbitrary intersection and arbitrary union):
This is how the second coordinate can be extracted:
(if
x ≠ y
\{y\}=\{\left.a\in\{x,y\}\right|a\notin\{x\}\}
Note that
\pi1
\pi2
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
(a,b)=(x,y)\leftrightarrow(a=x)\land(b=y)
(a,b)=(b,a)
b=a
(a,b)reverse:=\{\{b\},\{a,b\}\};
(a,b)short:=\{a,\{a,b\}\};
(a,b)01:=\{\{0,a\},\{1,b\}\}.
Prove: (a, b) = (c, d) if and only if a = c and b = d.
Kuratowski:
If. If a = c and b = d, then = . Thus (a, b)K = (c, d)K.
Only if. Two cases: a = b, and a ≠ b.
If a = b:
(a, b)K = = = {{a}}.
= (c, d)K = (a, b)K = {{a}}.
Thus = =, which implies a = c and a = d. By hypothesis, a = b. Hence b = d.
If a ≠ b, then (a, b)K = (c, d)K implies = .
Suppose = . Then c = d = a, and so = = = {{a}}. But then would also equal {{a}}, so that b = a which contradicts a ≠ b.
Suppose = . Then a = b = c, which also contradicts a ≠ b.
Therefore =, so that c = a and = .
If d = a were true, then = = ≠, a contradiction. Thus d = b is the case, so that a = c and b = d.
Reverse:
(a, b)reverse = = = (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 = .Thus (a, b)reverse = (c, d)reverse.
Short:[9]
If: If a = c and b = d, then = . Thus (a, b)short = (c, d)short.
Only if: Suppose = .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 = must be the case.
If a =, then by similar reasoning as above, is in the right hand side, so = c or = .
If = c then c is in = a and a is in c, and this combination contradicts the axiom of regularity, as has no minimal element under the relation "element of."
If =, then a is an element of a, from a = =, again contradicting regularity.
Hence a = c must hold.
Again, we see that = c or = .
The option = c and a = c implies that c is an element of c, contradicting regularity.
So we have a = c and =, and so: = \ = \ =, so b = d.
Rosser (1953)[10] employed a definition of the ordered pair due to Quine which requires a prior definition of the natural numbers. Let
\N
\sigma
\sigma
x\setminus\N
x
\N
x
\sigma
\sigma''x
\varphi
\varphi(x)
\psi(x)
Finally, define the ordered pair (A, B) as the disjoint union(which is
\varphi''A\cup\psi''B
Extracting all the elements of the pair that do not contain 0 and undoing
\varphi
For example, the pair
(\{\{a,0\},\{b,c,1\}\},\{\{d,2\},\{e,f,3\}\})
\{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}
a,b,c,d,e,f\notin\N
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).[12]
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:[13]
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.[14]
Morse–Kelley set theory makes free use of proper classes.[15] 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 pairwhere 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
s(x)
Ordered pairs can also be introduced in Zermelo–Fraenkel set theory (ZF) axiomatically by just adding to ZF a new function symbol
f
f
The definition helps to avoid so called accidental theorems like (a,a) = {{a}}, and ∈ (a,b), if Kuratowski's definition (a,b) = {{a}, {a,b}} was used.
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.