Editing Ordered pair (section)

==Defining the ordered pair using set theory==

If one agrees that [[set theory]] is an appealing [[foundations of mathematics|foundation of mathematics]], then all mathematical objects must be defined as [[Set (mathematics)|sets]] of some sort. Hence if the ordered pair is not taken as primitive, it must be defined as a set.<ref>[[Willard van Orman Quine|Quine]] has argued that the set-theoretical implementations of the concept of the ordered pair   is a paradigm for the clarification of philosophical  ideas (see  "[[Word and Object]]", section 53).
The general notion of such definitions or implementations  are discussed in Thomas Forster "Reasoning about theoretical entities".
</ref> Several set-theoretic definitions of the ordered pair are given below (see also Diepert).<ref>{{Citation | jstor=40231262 | url= | author=Randall R. Dipert | title=Set-Theoretical Representations of Ordered Pairs and Their Adequacy for the Logic of Relations | journal=Canadian Journal of Philosophy | volume=12 | number=2 | pages=353&ndash;374 | date=Jun 1982 | doi= 10.1080/00455091.1982.10715803}}</ref>

===Wiener's definition===
[[Norbert Wiener]] proposed the first set theoretical definition of the ordered pair in 1914:<ref>Wiener's paper "A Simplification of the logic of relations" is reprinted, together with a valuable commentary on pages 224ff in van Heijenoort, Jean (1967), ''From Frege to Gödel: A Source Book in Mathematical Logic, 1979–1931'', Harvard University Press, Cambridge MA, {{isbn|0-674-32449-8}} (pbk.). van Heijenoort states the simplification this way: "By giving a definition of the ordered pair of two elements in terms of class operations, the note reduced the theory of relations to that of classes".</ref>
<math display="block">\left( a, b \right) := 
\left\{\left\{ \left\{a\right\},\, \emptyset \right\},\,  \left\{\left\{b\right\}\right\}\right\}.</math>
He observed that this definition made it possible to define the [[type theory|types]] of ''[[Principia Mathematica]]'' as sets. ''Principia Mathematica'' had taken types, and hence [[relation (mathematics)|relations]] of all arities, as [[primitive notion|primitive]].

Wiener used <nowiki>{{</nowiki>''b''}} 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 <math>\{\{a\}, \emptyset\}</math>'s.

===Hausdorff's definition===
About the same time as Wiener (1914), [[Felix Hausdorff]] proposed his definition:
<math display="block">(a, b) := \left\{ \{a, 1\}, \{b, 2\} \right\}</math>
"where 1 and 2 are two distinct objects different from a and b."<ref>cf introduction to Wiener's paper in van Heijenoort 1967:224</ref>

===Kuratowski's definition===
In 1921 [[Kazimierz Kuratowski]] offered the now-accepted definition<ref>cf introduction to Wiener's paper in van Heijenoort 1967:224. van Heijenoort observes that the resulting set that represents the ordered pair "has a type higher by 2 than the elements (when they are of the same type)"; he offers references that show how, under certain circumstances, the type can be reduced to 1 or 0.</ref><ref>{{cite journal | title=Sur la notion de l'ordre dans la Théorie des Ensembles | first=Casimir|last=Kuratowski| author-link=Kazimierz Kuratowski| year=1921| journal=[[Fundamenta Mathematicae]] | pages=161–171| volume=2 | number=1 | doi=10.4064/fm-2-1-161-171|doi-access = free}}</ref>
of the ordered pair (''a'', ''b''):
<math display="block">(a, \ b)_K \; := \  \{ \{ a \}, \ \{ a, \ b \} \}.</math>
When the first and the second coordinates are identical, the definition obtains:
<math display="block">(x,\ x)_K = \{\{x\},\{x, \ x\}\} = \{\{x\},\ \{x\}\} = \{\{x\}\}</math>

Given some ordered pair ''p'', the property "''x'' is the first coordinate of ''p''" can be formulated as:
<math display="block">\forall Y\in p:x\in Y.</math>
The property "''x'' is the second coordinate of ''p''" can be formulated as:
<math display="block">(\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).</math>
In the case that the left and right coordinates are identical, the right [[Logical conjunction|conjunct]] <math>(\forall Y_1,Y_2\in p: (x \in Y_1 \land x \in Y_2) \rarr Y_1 = Y_2)</math> is trivially true, since <math>Y_1 = Y_2</math> is the case.

If <math>p=(x,y)=\{\{x\},\{x,y\}\}</math> then:
: <math>\bigcap p = \bigcap \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cap \{x, y\} = \{x\},</math>
: <math>\bigcup p = \bigcup \bigg\{\{x\}, \{x, y\}\bigg\} = \{x\} \cup \{x, y\} = \{x, y\}.</math>

This is how we can extract the first coordinate of a pair (using the [[Iterated binary operation#Notation|iterated-operation notation]] for [[Intersection (set theory)#Arbitrary intersections|arbitrary intersection]] and [[Union (set theory)#Arbitrary unions|arbitrary union]]):
<math display="block">\pi_1(p) = \bigcup\bigcap p = \bigcup \{x\} = x.</math>

This is how the second coordinate can be extracted:
<math display="block">\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.</math>

(if <math>x \neq y</math>, then the set <math>\{y\}</math> could be obtained more simply: <math>\{y\}=\{\left. a \in \{x,y\}\,\right|\, a \notin \{x\}  \}</math>, but the previous formula also takes into account the case when <math>x=y</math>.)

Note that <math>\pi_1</math> and <math>\pi_2</math> are [[Function (mathematics)#In the foundations of mathematics|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 <math>(a,b) = (x,y) \leftrightarrow (a=x) \land (b=y)</math>. In particular, it adequately expresses 'order', in that <math>(a,b) = (b,a)</math> is false unless <math>b = a</math>. There are other definitions, of similar or lesser complexity, that are equally  adequate:
* <math>( a, b )_{\text{reverse}} :=  \{ \{ b \}, \{a, b\}\};</math>
* <math>( a, b )_{\text{short}} :=  \{ a, \{a, b\}\};</math>
* <math>( a, b )_{\text{01}} := \{\{0, a \}, \{1, b \}\}.</math><ref>This differs from Hausdorff's definition in not requiring the two elements 0 and 1 to be distinct from ''a'' and ''b''.</ref>
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 (punctuation)|braces]]. Proving that '''short''' satisfies the characteristic property requires the [[Zermelo–Fraenkel set theory]] [[axiom of regularity]].<ref>Tourlakis, George (2003) ''Lectures in Logic and Set Theory. Vol. 2: Set Theory''. Cambridge Univ. Press. Proposition III.10.1.</ref> Moreover, if one uses [[Set-theoretic definition of natural numbers#Definition as von Neumann ordinals|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)<sub>short</sub>. 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''&nbsp;=&nbsp;''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''':<br>
''If''. If ''a'' = ''c'' and ''b'' = ''d'', then {{''a''}, {''a'', ''b''}} = {{''c''}, {''c'', ''d''}}. Thus (''a, b'')<sub>K</sub> = (''c'', ''d'')<sub>K</sub>.

''Only if''. Two cases: ''a'' = ''b'', and ''a'' ≠ ''b''.

If ''a'' = ''b'':
:(''a, b'')<sub>K</sub> = {{''a''}, {''a'', ''b''}}  = {{''a''}, {''a'', ''a''}} = <nowiki>{{</nowiki>''a''}}.
:{{''c''}, {''c'', ''d''}} = (''c'', ''d'')<sub>K</sub> = (''a'', ''b'')<sub>K</sub> = <nowiki>{{</nowiki>''a''}}.
: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'')<sub>K</sub> = (''c'', ''d'')<sub>K</sub> 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''}} = <nowiki>{{</nowiki>''a''}}. But then {{''a''}, {''a, b''}} would also equal <nowiki>{{</nowiki>''a''}}, 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''':<br>
(''a, b'')<sub>reverse</sub> = {{''b''}, {''a, b''}} = {{''b''}, {''b, a''}} = (''b, a'')<sub>K</sub>.

''If''. If (''a, b'')<sub>reverse</sub> = (''c, d'')<sub>reverse</sub>,
(''b, a'')<sub>K</sub> = (''d, c'')<sub>K</sub>. Therefore, ''b = d'' and ''a = c''.

''Only if''. If ''a = c'' and ''b = d'', then {{''b''}, {''a, b''}} = {{''d''}, {''c, d''}}.
Thus (''a, b'')<sub>reverse</sub> = (''c, d'')<sub>reverse</sub>.

'''Short:'''<ref>For a formal [[Metamath]] proof of the adequacy of '''short''', see [http://us.metamath.org/mpegif/opthreg.html here (opthreg).] Also see Tourlakis (2003), Proposition III.10.1.</ref>

''If'': If ''a = c'' and ''b = d'', then {''a'', {''a, b''}} = {''c'', {''c, d''}}. Thus (''a, b'')<sub>short</sub> = (''c, d'')<sub>short</sub>.

''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===
[[J. Barkley Rosser|Rosser]] (1953)<ref>[[J. Barkley Rosser]], 1953. ''Logic for Mathematicians''. McGraw–Hill.</ref> employed a definition of the ordered pair due to [[Willard van Orman Quine|Quine]] which requires a prior definition of the [[natural number]]s. Let <math>\N</math> be the set of natural numbers and define first
<math display="block">\sigma(x) := \begin{cases}
      x, & \text{if }x \notin \N, \\
      x+1, & \text{if }x \in \N.
    \end{cases}</math>
The function <math>\sigma</math> 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 <math>\sigma</math>.
As <math>x \setminus \N</math> is the set of the elements of <math>x</math> not in <math>\N</math> go on with
<math display="block">\varphi(x) := \sigma[x] = \{\sigma(\alpha)\mid\alpha \in x\} = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}.</math>
This is the [[Image (mathematics)#Image of a subset|set image]] of a set <math>x</math> under <math>\sigma</math>, [[Image (mathematics)#Other terminology|sometimes denoted]] by <math>\sigma''x</math> as well. Applying function <math>\varphi</math> to a set ''x'' simply increments every natural number in it. In particular, <math>\varphi(x)</math> never contains contain the number 0, so that for any sets ''x'' and ''y'',
<math display="block">\varphi(x) \neq \{0\} \cup \varphi(y).</math>
Further, define
<math display="block">\psi(x) := \sigma[x] \cup \{0\} = \varphi(x) \cup \{0\}.</math>
By this, <math>\psi(x)</math> does always contain the number 0.

Finally, define the ordered pair (''A'', ''B'') as the disjoint union
<math display="block">(A, B) := \varphi[A] \cup \psi[B] = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}.</math>
(which is <math>\varphi''A \cup \psi''B</math> in alternate notation).

Extracting all the elements of the pair that do not contain 0 and undoing <math>\varphi</math> yields ''A''. Likewise, ''B'' can be recovered from the elements of the pair that do contain 0.<ref>[https://randall-holmes.github.io/ Holmes, M. Randall]: ''[https://web.archive.org/web/20180416202817/http://math.boisestate.edu/~best/best18/Talks/holmes_best18.pdf On Ordered Pairs]'', on: Boise State, March 29, 2009. The author uses <math>\sigma_1</math> for <math>\varphi</math> and <math>\sigma_2</math> for <math>\psi</math>.</ref>

For example, the pair <math>( \{\{a,0\},\{b,c,1\}\} , \{\{d,2\},\{e,f,3\}\} ) </math> is encoded as <math>\{\{a,1\},\{b,c,2\},\{d,3,0\},\{e,f,4,0\}\}</math> provided <math>a,b,c,d,e,f\notin \N</math>.

In [[type theory]] and in outgrowths thereof such as the axiomatic set theory [[New Foundations|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 (mathematics)|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 [[New Foundations|NF]], but not in [[type theory]] or in [[New Foundations|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).<ref>Holmes, M. Randall (1998) ''[http://math.boisestate.edu/~holmes/holmes/head.pdf  Elementary Set Theory with a Universal Set] {{Webarchive|url=https://web.archive.org/web/20110411041046/http://math.boisestate.edu/%7Eholmes/holmes/head.pdf |date=2011-04-11 }}''. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web.</ref>

===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:<ref>{{cite book |last=Frege |first=Gottlob |year=1893 |title=Grundgesetze der Arithmetik |url=https://korpora.zim.uni-duisburg-essen.de/Frege/PDF/gga1_o_corr.pdf |location=Jena |publisher=Verlag Hermann Pohle | section = 144}}</ref>
<math display="block">(x, y) = \{R : x R y \}.</math>

This definition is inadmissible in most modern formalized set theories and is methodologically similar to defining the [[Cardinality|cardinal]] of a set as the class of all sets equipotent with the given set.<ref>{{cite book |last=Kanamori |first=Akihiro |year=2007 |title=Set Theory From Cantor to Cohen |url=http://math.bu.edu/people/aki/16.pdf |publisher=Elsevier BV }} p. 22, footnote 59</ref>

===Morse definition===
[[Morse–Kelley set theory]] makes free use of [[proper class]]es.<ref>{{cite book |last=Morse |first=Anthony P. |year=1965 |title=A Theory of Sets |url=https://archive.org/details/theoryofsets0000mors |url-access=registration |publisher=Academic Press }}</ref> [[Anthony Morse|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
<math display="block"> (x, y) = (\{0\} \times s(x)) \cup (\{1\} \times s(y))</math>
where the component Cartesian products are Kuratowski pairs of sets and where
<math display="block"> s(x) = \{\emptyset \} \cup \{\{t\} \mid t \in x\} </math>

This renders possible pairs whose projections are proper classes. The Quine–Rosser definition above  also admits [[proper class]]es as projections. Similarly the triple is defined as a 3-tuple as follows:
<math display="block"> (x, y, z) = (\{0\} \times s(x)) \cup (\{1\} \times s(y)) \cup (\{2\} \times s(z))</math>

The use of the singleton set <math> s(x) </math> 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.