Ordered_pair

Ordered pair

In mathematics, an ordered pair is a collection of two distinguishable objects, one being the first coordinate (or the first entry or left projection), and the other being the second coordinate (second entry, right projection). If the first coordinate is a and the second is b, the usual notation for an ordered pair is (a, b). The pair is "ordered" in that (a, b) differs from (b, a) unless a = b.

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

1 Generalities
2 Defining the ordered pair using set theory
3 Category theory
4 References

Generalities

Let $(a 1, b 1)$ and $(a 2, b 2)$ be two ordered pairs. Then the characteristic (or defining) property of the ordered pair is:

$(a_1, b_1) = (a_2, b_2) \leftrightarrow (a_1 = a_2 \and b_1 = b_2)$ .

The entries of an ordered pair can be other ordered pairs, enabling the recursive definition of ordered n-tuples (ordered lists of n terms). For example, the ordered triple (a,b,c) can be defined as (a, (b,c)), i.e., as one pair nested in another. This approach is mirrored in computer programming languages that enable constructing a list of elements from nested ordered pairs. For example, the list (1 2 3 4 5) becomes (1, (2, (3, (4, (5, {} ))))). The Lisp programming language employs such lists as its primary data structure.

The set of all ordered pairs whose first element is in some set X and whose second element is in some set Y is called the Cartesian product of X and Y, and written X×Y. A binary relation over the field X∪Y is a subset of X×Y.

If one wishes to employ $\ (a,b)$ to denote the open interval on the real number line, the ordered pair may be denoted by the variant notation $\left \langle a,b\right \rangle.$

Defining the ordered pair using set theory

The above characteristic property of ordered pairs 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.

If one agrees that set theory is an appealing foundations 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. Several set-theoretic definitions of the ordered pair are given below.

Wiener's definition

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

(a, b) := {{{a},{}}, { {b} }}.

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.

Kuratowski definition

The standard Kuratowski definition of the ordered pair (a, b) is:

(a, b)_K := { {a}, {a,b} }.

Given some ordered pair p, that x is its first element can be formulated as:

$\forall{Y}{\in}{p}:{x}{\in}{Y}.$

If x is the second element of p, then:

$(\exist{Y}{\in}{p}:{x}{\in}{Y})\and(\forall{Y_{1},Y_{2}}{\in}{p}:Y_{1}\ne Y_{2}\rarr ({x}{\notin}{Y_{1}}\or{x}{\notin}{Y_{2}})).$

Note that this definition remains valid when the first and second elements are identical, so that p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }. In this case, the right conjunct $(\forall{Y_{1},Y_{2}}{\in}{p}:Y_{1}\ne Y_{2}\rarr ({x}{\notin}{Y_{1}}\or{x}{\notin}{Y_{2}}))$ is trivially true, since Y₁ ≠ Y₂ is never the case.

Variants

The above Kuratowski definition of the ordered pair is "adequate" in the sense that it satisfies the characteristic property that an ordered pair must satisfy, namely that $(a,b) = (x,y) \leftrightarrow a=x \and b=y$ . This definition is also arbitrary, as there are other adequate definitions of similar or lesser complexity, such as:

(a,b)_reverse := { {b}, {a,b} };
(a,b)_short := { a, {a,b} };
(a, b)₀₁ := { {0,a}, {1,b} }.

The "reverse" pair is of little interest, as it has no obvious advantage (nor disadvantage) over the Kuratowski pair. The "short" pair is so-called because it requires two rather than three pairs of curly braces. A drawback is that proving that it satisfies the characteristic property requires the ZFC axiom of regularity. Moreover, if one accepts the standard construction of the natural numbers, then 2 is the set { 0, 1 } = { {}, {{}} }, which is indistinguishable from the pair (0,0)_short.

Proving the characteristic property

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

Kuratowski:

If a=b:

(a,b)_K = {{a}, {a,b}} = {{a}, {a,a}} = { {a} },

and (c,d)_K = {{c},{c,d}} = { {a} }.

Thus {c} = {c,d} = {a}, and c=d=a=b.

If a≠b, then {{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 b=a, which contradicts a≠b.

Suppose {c} = {a,b}. Then a=b=c, which contradicts a≠b.

Therefore {c} = {a}, or c=a, and {c,d} = {a,b}.

If it were true that d=a, then {c,d} = {a,a} = {a} ≠ {a,b}, a contradiction. So d=b. Thus a=c and b=d.

Conversely, if a=c and b=d, then {{a},{a,b} = {{c},{c,d}}. Thus (a,b)_K = (c,d)_K.

Reverse: (a,b)_reverse = {{b},{a,b}} = {{b},{b,a}} = (b,a)_K.

If (a,b)_reverse = (c,d)_reverse, (b,a)_K = (d,c)_K. Therefore b=d and a=c.

Conversely, if a=c and b=d, then {{b},{a,b}} = {{d},{c,d}}. Thus (a,b)_reverse = (c,d)_reverse.

Short: For a formal Metamath proof of the adequacy of the short pair, see the proofs of theorems 4618-21. Metamath's axiom of regularity is #4608.

Quine-Rosser definition

Rosser (1953) employed a definition of the ordered pair, due to Quine and requiring a prior definition of the natural numbers. Let $\N$ be the set of natural numbers, and define

$\varphi(x) = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}.$

Applying this function simply increments every natural number in x. In particular, $\varphi(x)$ does not contain the number 0, so that for any sets x and y,

$\varphi(x) \not= \{0\} \cup \varphi(y).$

Define the ordered pair (A,B) as

$(A,B) = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}.$

Extracting all the elements of the pair that do not contain 0 and undoing $\varphi$ yields A. Likewise, B can be recovered from the elements of the pair that do contain 0.

In type theory, and in set theories such as New Foundations that are outgrowths of type theory, 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. For an extensive discussion of the ordered pair in the context of Quinian set theories, see Holmes (1998).

Morse definition

Morse-Kelley set theory (Morse 1965) makes free use of proper classes. 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 (x,y) as $(x \times \{0\}) \cup (y \times \{1\})$ , where the component Cartesian products are Kuratowski pairs on sets. This second step renders possible pairs whose projections are proper classes. The Quine-Rosser definition above also admits proper classes as projections.

Category theory

Product is the category theoretic notion most similar to that of ordered pair. While various objects may play the role of pairs, they are all equivalent in the sense of being categorically isomorphic.

References

Holmes, Randall, 1998. Elementary Set Theory with a Universal Set. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.
Morse, Anthony P., 1965. A Theory of Sets. Academic Press
J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.

Contents