FACTOID # 28: Austin, Texas has more people than Alaska.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Ordered pair

In mathematics, an ordered pair is a collection of two not necessarily distinct objects, one of which is distinguished as the first coordinate (or first entry or left projection) and the other as the second coordinate (second entry, right projection). The common notation for an ordered pair with first coordinate a and second coordinate b is (a, b). (Warning: this notation (a, b) also denotes an open interval on the real number line. The variant notation $langle a,brangle$ for the ordered pair extinguishes this ambiguity.) For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... In elementary algebra, an interval is a set that contains every real number between two indicated numbers, and possibly the two numbers themselves. ... In mathematics, the real line is simply the set of real numbers. ...

Let (a1, b1) and (a2, b2) be two ordered pairs. Then the characteristic or defining property of ordered pairs is:

(a1, b1) = (a2, b2) ↔ (a1 = a2 & b1 = b2).

Ordered pairs can have other ordered pairs as projections. Hence the ordered pair enables 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) ), 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. AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ... In mathematics, a tuple is a finite sequence of objects (a list of a limited number of objects). ... Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...

The notion of ordered pair is crucial for the definition of Cartesian product and relation. In mathematics, the Cartesian product is a direct product of sets. ... In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...

## Set theoretic definitions of the ordered pair

The characteristic property of ordered pairs mentioned in the preceding section is all that is necessary to understand the way ordered pairs are used in the mathematical literature. However, for purposes of foundations of mathematics it has been considered desirable to express the definition of every type of mathematical object in terms of sets, and for ordered pairs this has been done in several ways. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...

### Wiener's definition

Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914: Norbert Wiener Norbert Wiener (November 26, 1894, Columbia, Missouri â€“ March 18, 1964, Stockholm Sweden) was an American theoretical and applied mathematician. ...

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

He observed that this definition would allow all the types of Principia Mathematica to be expressed using sets alone. (In Principia Mathematica, relations of all arities were primitive.) The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910-1913. ... In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...

### The standard Kuratowski definition

In axiomatic set theory, the ordered pair (a,b) is usually defined as the Kuratowski pair: This article or section is in need of attention from an expert on the subject. ... Kazimierz Kuratowski (born February 2, 1896, Warsaw, died June 18, 1980, Warsaw) was a Polish mathematician. ...

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

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

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

and that x is the second element of p 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}}))$.

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 $(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 it is never the case that Y1Y2.

### 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

1. (a,b)reverse:= { {b}, {a,b} }
2. (a,b)short:= { a, {a,b} }
3. (a, b)01:= { {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. The axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory. ...

### 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 ab, 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 ab. 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.

### 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. Let $N$ be the set of natural numbers, and define John Barkley Rosser Sr. ... For people named Quine, see Quine (surname). ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...

$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.

This definition of the ordered pair has a single 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 arguments. For an extensive discussion of ordered pairs in the context of Quinian set theories, see Holmes (1998). At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ... In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. ...

### 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 $(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 Rosser definition in the preceding section also admits proper classes as projections. Morse-Keylley set theory (MK) is another axiomatization of set theory. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ...

### 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. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...

## 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.

Results from FactBites:

 Ordered pair (362 words) 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. An ordered pair with first element a and second element b is usually written as (a, b). Ordered triples and n-tuples (ordered lists of n terms) are defined recursively from this definition: an ordered triple (a,b,c) can be defined as (a, (b,c)): two nested pairs.
 PlanetMath: ordered pair (91 words) The characterizing property of an ordered pair is: and the above construction of ordered pair, as weird as it seems, is actually the simplest possible formulation which achieves this property. This is version 4 of ordered pair, born on 2001-10-19, modified 2002-03-04.
More results at FactBites »

Share your thoughts, questions and commentary here