If one agrees that
set theory is an appealing
foundation of mathematics, then all mathematical objects must be defined as
sets of some sort. Hence if the ordered pair is not taken as primitive, it must be defined as a set. Several set-theoretic definitions of the ordered pair are given below (see also Diepert).
Wiener's definition Norbert Wiener proposed the first set theoretical definition of the ordered pair in 1914: \left( a, b \right) := \left\{\left\{ \left\{a\right\},\, \emptyset \right\},\, \left\{\left\{b\right\}\right\}\right\}. He observed that this definition made it possible to define the
types of
Principia Mathematica as sets.
Principia Mathematica had taken types, and hence
relations of all
arities, as
primitive. Wiener used instead of {
b} to make the definition compatible with
type theory where all elements in a class must be of the same "type". With
b nested within an additional set, its type is equal to \{\{a\}, \emptyset\}'s.
Hausdorff's definition About the same time as Wiener (1914),
Felix Hausdorff proposed his definition: (a, b) := \left\{ \{a, 1\}, \{b, 2\} \right\} "where 1 and 2 are two distinct objects different from a and b."
Kuratowski's definition In 1921
Kazimierz Kuratowski offered the now-accepted definition of the ordered pair (
a,
b): (a, \ b)_K \; := \ \{ \{ a \}, \ \{ a, \ b \} \}. When the first and the second coordinates are identical, the definition obtains: (x,\ x)_K = \{\{x\},\{x, \ x\}\} = \{\{x\},\ \{x\}\} = \{\{x\}\} Given some ordered pair
p, the property "
x is the first coordinate of
p" can be formulated as: \forall Y\in p:x\in Y. The property "
x is the second coordinate of
p" can be formulated as: (\exist Y\in p:x\in Y) \land(\forall Y_1,Y_2\in p: (x \in Y_1 \land x \in Y_2) \rarr Y_1 = Y_2). In the case that the left and right coordinates are identical, the right
conjunct (\forall Y_1,Y_2\in p: (x \in Y_1 \land x \in Y_2) \rarr Y_1 = Y_2) is trivially true, since Y_1 = Y_2 is the case. If p=(x,y)=\{\{x\},\{x,y\}\} then: : \bigcap p = \bigcap \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cap \{x, y\} = \{x\}, : \bigcup p = \bigcup \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cup \{x, y\} = \{x, y\}. This is how we can extract the first coordinate of a pair (using the
iterated-operation notation for
arbitrary intersection and
arbitrary union): \pi_1(p) = \bigcup\bigcap p = \bigcup \{x\} = x. This is how the second coordinate can be extracted: \pi_2(p) = \bigcup\left\{\left. a \in \bigcup p\,\right|\,\bigcup p \neq \bigcap p \rarr a \notin \bigcap p \right\} = \bigcup\left\{\left. a \in \{x,y\}\,\right|\,\{x,y\} \neq \{x\} \rarr a \notin \{x\} \right\} = \bigcup \{y\} = y. (if x \neq y, then the set \{y\} could be obtained more simply: \{y\}=\{\left. a \in \{x,y\}\,\right|\, a \notin \{x\} \}, but the previous formula also takes into account the case when x=y.) Note that \pi_1 and \pi_2 are
generalized functions, in the sense that their domains and codomains are
proper classes.
Variants The above Kuratowski definition of the ordered pair is "adequate" in that it satisfies the characteristic property that an ordered pair must satisfy, namely that (a,b) = (x,y) \leftrightarrow (a=x) \land (b=y). In particular, it adequately expresses 'order', in that (a,b) = (b,a) is false unless b = a. There are other definitions, of similar or lesser complexity, that are equally adequate: • ( a, b )_{\text{reverse}} := \{ \{ b \}, \{a, b\}\}; • ( a, b )_{\text{short}} := \{ a, \{a, b\}\}; • ( a, b )_{\text{01}} := \{\{0, a \}, \{1, b \}\}. The
reverse definition is merely a trivial variant of the Kuratowski definition, and as such is of no independent interest. The definition
short is so-called because it requires two rather than three pairs of
braces. Proving that
short satisfies the characteristic property requires the
Zermelo–Fraenkel set theory axiom of regularity. Moreover, if one uses
von Neumann's set-theoretic construction of the natural numbers, then 2 is defined as the set {0, 1} = {0, {0}}, which is indistinguishable from the pair (0, 0)short. Yet another disadvantage of the
short pair is the fact that, even if
a and
b are of the same type, the elements of the
short pair are not. (However, if
a =
b then the
short version keeps having cardinality 2, which is something one might expect of any "pair", including any "ordered pair".)
Proving that definitions satisfy the characteristic property Prove: (
a,
b) = (
c,
d)
if and only if a =
c and
b =
d.
Kuratowski:
If. If
a =
c and
b =
d, then {{
a}, {
a,
b}} = {{
c}, {
c,
d}}. Thus (
a, b)K = (
c,
d)K.
Only if. Two cases:
a =
b, and
a ≠
b. If
a =
b: :(
a, b)K = {{
a}, {
a,
b}} = {{
a}, {
a,
a}} = . :{{
c}, {
c,
d}} = (
c,
d)K = (
a,
b)K = . :Thus {
c} = {
c,
d} = {
a}, which implies
a =
c and
a =
d. By hypothesis,
a =
b. Hence
b =
d. If
a ≠
b, then (
a,
b)K = (
c,
d)K implies {{
a}, {
a,
b}} = {{
c}, {
c,
d}}. :Suppose {
c,
d} = {
a}. Then
c =
d =
a, and so {{
c}, {
c,
d}} = {{
a}, {
a,
a}} = {{
a}, {
a}} = . But then {{
a}, {
a, b}} would also equal , so that
b =
a which contradicts
a ≠
b. :Suppose {
c} = {
a,
b}. Then
a =
b =
c, which also contradicts
a ≠
b. :Therefore {
c} = {
a}, so that
c = a and {
c,
d} = {
a,
b}. :If
d =
a were true, then {
c,
d} = {
a,
a} = {
a} ≠ {
a,
b}, a contradiction. Thus
d =
b is the case, so that
a =
c and
b =
d.
Reverse: (
a, b)reverse = {{
b}, {
a, b}} = {{
b}, {
b, a}} = (
b, a)K.
If. If (
a, b)reverse = (
c, d)reverse, (
b, a)K = (
d, c)K. Therefore,
b = d and
a = c.
Only if. If
a = c and
b = d, then {{
b}, {
a, b}} = {{
d}, {
c, d}}. Thus (
a, b)reverse = (
c, d)reverse.
Short: If: If
a = c and
b = d, then {
a, {
a, b}} = {
c, {
c, d}}. Thus (
a, b)short = (
c, d)short.
Only if: Suppose {
a, {
a, b}} = {
c, {
c, d}}. Then
a is in the left hand side, and thus in the right hand side. Because equal sets have equal elements, one of
a = c or
a = {
c, d} must be the case. :If
a = {
c, d}, then by similar reasoning as above, {
a, b} is in the right hand side, so {
a, b} =
c or {
a, b} = {
c, d}. ::If {
a, b} =
c then
c is in {
c, d} =
a and
a is in
c, and this combination contradicts the axiom of regularity, as {
a, c} has no minimal element under the relation "element of." ::If {
a, b} = {
c, d}, then
a is an element of
a, from
a = {
c, d} = {
a, b}, again contradicting regularity. :Hence
a = c must hold. Again, we see that {
a, b} =
c or {
a, b} = {
c, d}. :The option {
a, b} =
c and
a = c implies that
c is an element of
c, contradicting regularity. :So we have
a = c and {
a, b} = {
c, d}, and so: {
b} = {
a, b} \ {
a} = {
c, d} \ {
c} = {
d}, so
b =
d.
Quine–Rosser definition Rosser (1953) employed a definition of the ordered pair due to
Quine which requires a prior definition of the
natural numbers. Let \N be the set of natural numbers and define first \sigma(x) := \begin{cases} x, & \text{if }x \notin \N, \\ x+1, & \text{if }x \in \N. \end{cases} The function \sigma increments its argument if it is a natural number and leaves it as is otherwise; the number 0 does not appear in the range of \sigma. As x \setminus \N is the set of the elements of x not in \N go on with \varphi(x) := \sigma[x] = \{\sigma(\alpha)\mid\alpha \in x\} = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}. This is the
set image of a set x under \sigma,
sometimes denoted by \sigma
x as well. Applying function \varphi to a set x
simply increments every natural number in it. In particular, \varphi(x) never contains the number 0, so that for any sets x
and y'', \varphi(x) \neq \{0\} \cup \varphi(y). Further, define \psi(x) := \sigma[x] \cup \{0\} = \varphi(x) \cup \{0\}. By this, \psi(x) does always contain the number 0. Finally, define the ordered pair (
A,
B) as the disjoint union (A, B) := \varphi[A] \cup \psi[B] = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}. (which is \varphi
A \cup \psiB in alternate notation). 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. For example, the pair ( \{\{a,0\},\{b,c,1\}\} , \{\{d,2\},\{e,f,3\}\} ) is encoded as \{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\} provided a,b,c,d,e,f\notin \N. In
type theory and in outgrowths thereof such as the axiomatic set theory
NF, the Quine–Rosser pair has the same type as its projections and hence is termed a "type-level" ordered pair. Hence this definition has the advantage of enabling a
function, defined as a set of ordered pairs, to have a type only 1 higher than the type of its arguments. This definition works only if the set of natural numbers is infinite. This is the case in
NF, but not in
type theory or in
NFU.
J. Barkley Rosser showed that the existence of such a type-level ordered pair (or even a "type-raising by 1" ordered pair) implies the
axiom of infinity. For an extensive discussion of the ordered pair in the context of Quinian set theories, see Holmes (1998).
Cantor–Frege definition Early in the development of the set theory, before paradoxes were discovered, Cantor followed Frege by defining the ordered pair of two sets as the class of all relations that hold between these sets, assuming that the notion of relation is primitive: (x, y) = \{R : x R y \}. This definition is inadmissible in most modern formalized set theories and is methodologically similar to defining the
cardinal of a set as the class of all sets equipotent with the given set.
Morse definition Morse–Kelley set theory makes free use of
proper classes.
Morse defined the ordered pair so that its projections could 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) = (\{0\} \times s(x)) \cup (\{1\} \times s(y)) where the component Cartesian products are Kuratowski pairs of sets and where s(x) = \{\emptyset \} \cup \{\{t\} \mid t \in x\} This renders possible pairs whose projections are proper classes. The Quine–Rosser definition above also admits
proper classes as projections. Similarly the triple is defined as a 3-tuple as follows: (x, y, z) = (\{0\} \times s(x)) \cup (\{1\} \times s(y)) \cup (\{2\} \times s(z)) The use of the singleton set s(x) which has an inserted empty set allows tuples to have the uniqueness property that if
a is an
n-tuple and b is an
m-tuple and
a =
b then
n =
m. Ordered triples which are defined as ordered pairs do not have this property with respect to ordered pairs. ==Category theory==