Encyclopedia > Ordered pair

  Article Content

Ordered pair

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). Two such ordered pairs (a1, b1) and (a2, b2) are equal if and only if a1 = a2 and b1 = b2.

The set of all ordered pairs whose first element is in some set X and second element in some set Y is called the Cartesian product of said sets. Subsets thereof are mathematical relations.

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. This approach is mirrored in programming languages: It is possible to represent a list of elements as a construction of 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.

In pure set theory, where there are only sets, ordered pairs (a, b) can be defined as the set { {a}, {a, b} }. The statement that x is the first element of an ordered pair p can then be formulated as

for all Y in p : x in Y
and that x is the second element of p as
(exist Y in p : x in Y) and (for all Y1 in p, for all Y2 in p : if Y1Y2 then (x not in Y1 or x not in Y2)).

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 (for all Y1 in p, for all Y2 in p : if Y1Y2 then (x not in Y1 or x not in Y2)) is trivially true, since it is never the case that Y1Y2.

In the usual ZF formulation of set theory including the axiom of regularity, ordered pairs (a, b) can also be defined as the set {a, {a, b}}. However, the axiom of regularity is required, since without it, it is possible to consider sets x and z such that x = {z}, z = {x}, and xz. Then we have that

(x, x) = {x, {x, x}} = {x,{x}} = {x, z} = {z, x} = {z, {z}} = {z, {z, z}} = (z, z)

although we want (x,x) ≠ (z,z).

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Lake Ronkonkoma, New York

... are non-families. 20.3% of all households are made up of individuals and 9.7% have someone living alone who is 65 years of age or older. The average household size is ...

This page was created in 22.5 ms