Ordered pair: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Updated live from Wikipedia, last check: June 02, 2012 21:40 UTC (38 seconds ago)

From Wikipedia, the free encyclopedia

In mathematics, an ordered pair is a collection of objects having two coordinates (or entries or projections), such that one can always uniquely determine the object, which is the first coordinate (or first entry or left projection) of the pair as well as the second coordinate (or second entry or 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 binary 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)\quad\text{if and only if}\quad a_1 = a_2\text{ 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 by nesting cons cells. 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 the $\ (a,b)$ notation for a different purpose (such as denoting open intervals 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. This was the approach taken by the N. Bourbaki group in its Theory of Sets, published in 1954, long after Kuratowski discovered his reduction (below). The Kuratowski definition was added in the second edition of Theory of Sets, published in 1970.

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.

Wiener's definition

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

$\left( a, b \right) := \left\{\left\{ \left\{a\right\},\, \emptyset \right\},\, \left\{\left\{b\right\}\right\}\right\}.$

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.

Hausdorff's definition

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

(a, b) := { {a, 1}, {b, 2} }

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

Kuratowski definition

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

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

Note that this definition remains valid when the first and the second coordinate are identical, so that p = (x, x) = {{x}, {x, x}} = {{x}, {x}} = {{x}}.

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

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

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

$(\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}})).$

In the case that the left and right coordinates are identical, 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.

One may easily extract the first coordinate of a pair:

$\pi_1(p) = \bigcup\bigcap p$

The second coordinate is harder to extract:

$\pi_2(p) = \bigcup\bigcap p \quad\text{if}\quad \bigcap p = \bigcup p$

$\pi_2(p) = \bigcup\left(\bigcup p \setminus \bigcap p\right) \quad\text{if}\quad \bigcap p \not= \bigcup p$

Variants

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 \and b=y$ . There are other definitions, of similar or lesser complexity, that are equally adequate:

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

reverse is merely a trivial variant of the Kuratowski definition, and as such is of no further interest. short is so-called because it requires two rather than three pairs of braces. Proving that short satisfies the characteristic property requires the ZFC axiom of regularity^[5] Moreover, if one accepts the standard 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.

Proving that definitions satisfy the characteristic property

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

Kuratowski:
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 a ≠ b.

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 a ≠ b, 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 a ≠ b.

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

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.

Reverse:
(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:^[6]

If: Obvious.

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)^[7] 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 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).^[8]

Morse definition

Morse-Kelley set theory (Morse 1965)^[9] 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

A category-theoretic product A x 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.

References

^ 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".
^ 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".
^ cf introduction to Wiener's paper in van Heijenoort 1967:224
^ 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.
^ Tourlakis, George (2003) Lectures in Logic and Set Theory. Vol. 2: Set Theory. Cambridge Univ. Press. Proposition III.10.1.
^ For a formal Metamath proof of the adequacy of short, see here (opthreg). Also see Tourlakis (2003), Proposition III.10.1.
^ J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.
^ 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

Simple English

Introduction

In mathematics, an ordered pair is a collection of two objects, where one of the objects is first (the first coordinate or left projection), and the other is second (the second coordinate or right projection). An ordered pair where the first coordinate is $a$ and the second coordinate is $b$ is usually written $(a,b)$ (sometimes it is written $\langle a,b\rangle$ ). If $a$ is different from $b$ , then the ordered pair $(a,b)$ is different from the ordered pair $(b,a)$ - this is why it is called ordered.

Properties

If $(a_1,b_1)$ and $(a_2,b_2)$ are two ordered pairs, then the characteristic or defining property of ordered pairs is:

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

This means that two ordered pairs are equal if and only if: the first coordinates of the pairs are equal, and also the second coordinates of the pairs are equal.

Definition

There are many mathematical definitions of ordered pair which have this property. The definition given here is the most common one:

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

Kazimierz Kuratowski was the first person to make this definition.

Retrieved from "http://yak.rapint.com/wiki/Ordered_pair"

Category: Mathematics

The Full Wiki

Search:

More info on Ordered pair

Related topics