Ordered pair

From Example Problems
Jump to navigation Jump to search

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

(The notation (a, b) is also used to denote an open interval on the real number line; context should make it clear which meaning is meant. To distinguish the two meanings, the ordered pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a,b)} is sometimes written as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle a,b\rangle} .)

Two 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 X and Y, and written X × Y. Subsets of X × Y are binary 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 axiomatic set theory, where all mathematical objects are given set-theoretic definitions, the ordered pair (a, b) is usually defined as the Kuratowski pair (a, b)K := {{a}, {a,b}}. The statement that x is the first element of an ordered pair p can then be formulated as

Yp : xY

and that x is the second element of p as

(∃ Yp : xY) ∧ (∀ Y1p, ∀ Y2p : Y1Y2 → (xY1xY2)).

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 (∀ Y1p, ∀ Y2p : Y1Y2 → (xY1xY2)) is trivially true, since it is never the case that Y1Y2.

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 a pair, 2 = (0,0)short.

For a more general treatment, see Product (category theory). Category theory tells us that although many objects may play the role of pairs, they are all equivalent in the sense of being categorically isomorphic.

Rosser definition

In Logic (1953), Rosser uses a different definition, one which requires that a definition of the natural numbers be in place. Let Nn be the set of natural numbers, and define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(x) = \{ z : \exists y\in x : (y\in Nn \wedge z = y + 1) \vee (y \not\in Nn \wedge z = y) \}}

That is, φ(x) contains the successor of every natural number in x, together with all the non-numbers from x. In particular, it does not contain the number 0, so that for any sets A and B, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(A) \not= \{0\} \cup \phi(B)} .

Then the ordered pair (A,B) may be defined by adjoining 0 to each element of φ(B), and uniting the result with φ(A):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A,B) = \phi(A) \cup \{x : \exists y \in\phi(B) : x = y\cup\{0\} \}}

The component A may be recovered from the pair by extracting all the elements of the pair that do not contain 0, and vice-versa for B.

de:Geordnetes Paar et:Järjestatud paar es:Par ordenado fr:Couple (mathématiques) ko:순서쌍 hu:Rendezett pár pl:Para uporządkowana pt:Par ordenado sl:Urejen par sv:Ordnat par zh:有序对