Ordered pair

From Wikipedia, the free encyclopedia

In mathematics, an ordered pair is a collection of two objects such that one can be distinguished as the first element and the other as the second element (the first and second elements are also known as left and right projections). A pair with no such first or second elements is sometimes referred to as an unordered pair. An ordered pair with first element a and second element b is often written as (a, b).

The notation (a, b) also denotes an open interval on the real number line; which meaning of "(" and ")" is intended should be clear from the context. The variant notation <math>\langle a,b\rangle</math> extinguishes this ambiguity.

1 Generalities
2 Set theoretic definitions of the ordered pair
3 References

[edit] Generalities

Let (a₁, b₁) and (a₂, b₂) be two ordered pairs. Then the characteristic or defining property of ordered pairs is:

(a₁, b₁) = (a₂, b₂) ↔ (a₁ = a₂ ∧ b₁ = b₂).

Ordered pairs can have other ordered pairs as projections. Hence the ordered pair enables the recursive definition of ordered [[n-tuple]]s (ordered lists of n terms). For example, the ordered triple (a,b,c) can be defined as (a, (b,c) ), as one pair nested in another. This approach is mirrored in computer programming languages, where it is possible to construct 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 uses such lists as its primary data structure.

The notion of ordered pair is crucial for the definition of Cartesian product and relation.

[edit] Set theoretic definitions of the ordered pair

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

(x,y) := {{{x},∅}, { {y} }}.

He observed that this definition would allow all the types of Principia Mathematica to be expressed using sets alone. (In PM, relations of all arities were primitive.)

[edit] The standard Kuratowski definition

In axiomatic set theory, the ordered pair (a,b) is usually defined as the Kuratowski pair:

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

The statement that x is the first element of an ordered pair p can then be formulated as

∀ Y ∈ p : x ∈Y

and that x is the second element of p as

(∃ Y ∈ p : x ∈ Y) ∧ (∀ Y₁ ∈ p, ∀ Y₂ ∈ p : Y₁ ≠ Y₂ → (x ∉ Y₁ ∨ x ∉ Y₂)).

Note that this definition is still valid for the ordered pair p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }; in this case the statement (∀ Y₁ ∈ p, ∀ Y₂ ∈ p : Y₁ ≠ Y₂ → (x ∉ Y₁ ∨ x ∉ Y₂)) is trivially true, since it is never the case that Y₁ ≠ Y₂.

[edit] Variant definitions

The above definition of an ordered pair is "adequate", in the sense that it satisfies the characteristic property that an ordered pair must have (namely: if (a,b)=(x,y), then a=x and b=y), but also arbitrary, as there are many other definitions which are no more complicated and would also be adequate. Examples for other possible definitions include

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

The "reverse" pair is almost never used, as it has no obvious advantages (nor disadvantages) over the usual Kuratowski pair. The "short" pair has the disadvantage that the proof of the characteristic pair property (see above) is more complicated than for the Kuratowski pair (the axiom of regularity has to be used); moreover, as the number 2 is in set theory sometimes defined as the set { 0, 1 } = { {}, {0} }, this would mean that 2 is the pair (0,0)_short.

[edit] Proving the characteristic property of ordered pairs

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

If a=b: (a,b)_K = {{a}, {a,a}} = { {a} }, and (c,d)_K = {{c},{c,d}} = { {a} }. Thus {c} = {a} = {c,d}, or c=d=a=b.

If a≠b, then {{a}, {a,b}} = {{c},{c,d}}. If {c,d} = {a}, then c=d=a or {{c},{c,d}} = {{a}, {a,a}} = {{a}, {a}} = { {a} }.

If {c} = {a,b}, then a=b=c, which contradicts a≠b. Therefore {c} = {a}, or c=a, and {c,d} = {a,b}.

And if d=a, then {c,d} = {a,a} = {a}≠{a,b}. 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.

[edit] Quine-Rosser definition

Rosser (1953) made extensive use of a definition of the ordered pair due to Willard van Orman Quine. The Quine-Rosser definition requires a prior definition of the natural numbers; the following one will do. Let Nn be the set of natural numbers, and define

<math>\phi(x) = \{ z : \exists y\in x : (y\in Nn \wedge z = y + 1) \vee (y \not\in Nn \wedge z = y) \}.</math>

φ(x) contains the successor of every natural number in x, together with all the non-numbers from x. In particular, φ(x) does not contain the number 0, so that for any sets A and B, <math>\phi(A) \not= \{0\} \cup \phi(B)</math>.

Define the ordered pair (A,B) by adjoining 0 to each element of φ(B), then forming the union of the result with φ(A):

<math>(A,B) = \phi(A) \cup \{x : \exists y \in\phi(B) : x = y\cup\{0\} \}</math>

Extracting all the elements of the pair that do not contain 0 yields A. Likewise, B can be recovered by extracting all elements of the pair that do contain 0.

This definition of the ordered pair has a signal advantage. In type theory, and in set theories such as New Foundations that are outgrowths of type theory, this pair is of the same type as its projections (and hence is termed a "type-level" ordered pair). Hence a function, defined as a set of ordered pairs, has a type only 1 higher than the type of its projections. For an extensive discussion of ordered pairs in the context of Quinian set theories, see Holmes (1998).

[edit] Morse definition

Morse-Kelley set theory, set out in Morse (1965), makes free use of proper classes. Morse defined the ordered pair so as to allow its projections to 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 <math>(x \times \{0\}) \cup (y \times \{1\})</math>, where the component Cartesian products are Kuratowski pairs on sets. This second step renders possible pairs whose projections are proper classes. The Rosser definition in the preceding section also admits proper classes as projections.

[edit] Category theory

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

[edit] 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.ar:أزواج مرتبة

ca:Parell ordenat de:Geordnetes Paar et:Järjestatud paar es:Par ordenado fr:Couple (mathématiques) ko:순서쌍 it:Coppia (matematica) he:זוג סדור hu:Rendezett pár nl:Geordend paar (Nl) / Koppel (Be) pl:Para uporządkowana pt:Par ordenado sk:Usporiadaná dvojica sl:Urejen par sv:Ordnat par zh:有序对