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 (a_{1}, b_{1}) and (a_{2}, b_{2}) are equal if and only if a_{1} = a_{2} and b_{1} = b_{2}.
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 ntuples (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
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 Y_{1} in p, for all Y_{2} in p : if Y_{1} ≠ Y_{2} then (x not in Y_{1} or x not in Y_{2})) is trivially true, since it is never the case that Y_{1} ≠ Y_{2}.
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 x ≠ z. Then we have that
although we want (x,x) ≠ (z,z).
Search Encyclopedia

Featured Article
