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 (a₁, b₁) and (a₂, b₂) are equal if and only if a₁ = a₂ and b₁ = b₂.

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

∀ 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₂.

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

(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).