Orderly couple

An ordered pair , also 2-tuples called, is in the mathematics an important way in which two mathematical objects together into one unit. The two objects do not necessarily have to be different from one another and their order plays a role. Ordered pairs are at the center of the mathematical world of terms and are the basic building blocks of many more complex mathematical objects.

notation

An ordered pair is a combination of two mathematical objects and a unit. The ordered pair of and is mostly with the help of parentheses by ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle (a,b)}$

written down. In this case is the left first or front component of the couple and the right, rear or second component of the pair. Occasionally, other types of brackets, such as square brackets , and other separators, such as semicolons or vertical bars , are used in the notation . The sequence of the elements is essential in pair formation, that is, and should represent different pairs if and are different. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (a,b)}$ ${\displaystyle (b,a)}$ ${\displaystyle a}$ ${\displaystyle b}$

Equality of ordered pairs

The concept of the ordered pair is characterized by Peano's pair axiom :

Two ordered pairs are considered equal if and only if both their first and second components are equal.

As a formula, the pair axiom can be expressed as follows:

${\displaystyle (a,b)=(c,d)\iff a=c~{\text{und}}~b=d}$.

Representation of ordered pairs

In the literature, the following representations can be found for the ordered pair as sets or classes: ${\displaystyle (a,b)}$

Pair representations for sets and primitive elements

• ${\displaystyle (a,b)_{\mathrm {K} }:=\{\{a\},\{a,b\}\}}$, most popular representation after Kazimierz Kuratowski (1921). A variant gives the definition ${\displaystyle (a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\}}$

- possible in a type theory according to Bertrand Russell with the same type of a and b.

- not possible if a or b is a real class.

• ${\displaystyle (a,b)_{\text{short}}:=\{a,\{a,b\}\}}$, so-called short presentation

- not allowed in a type theory according to Bertrand Russell.

• ${\displaystyle (a,b)_{\text{EM}}:=\{\{\emptyset ,\{a\}\},\{b\}\}}$, representation that can be generalized to the tuple term
• ${\displaystyle (a,b)_{\text{W}}:=\{\{\emptyset ,\{a\}\},\{\{b\}\}\}}$, after Norbert Wiener (1914)

- possible in a type theory according to Bertrand Russell with the same type of a and b, if that of the next higher type level is chosen as the empty set.

• ${\displaystyle (a,b)_{\text{H}}:=\{\{a,{\boldsymbol {1}}\},\{b,{\boldsymbol {2}}\}\}}$, whereby and are different objects from each other, both also different from and , according to Felix Hausdorff (1914) ${\displaystyle {\boldsymbol {1}}}$ ${\displaystyle {\boldsymbol {2}}}$ ${\displaystyle a}$ ${\displaystyle b}$

Class pairs according to Schmidt

${\displaystyle (a,b):=\{\{\{x\}\}\,{\boldsymbol {\mid }}\,x\in a\}\;{\boldsymbol {\cup }}\;\{\{\emptyset ,\{x\}\}\,{\boldsymbol {\mid }}\,x\in b\}}$, after Jürgen Schmidt (1966) based on Quine . A variant based on the representation by Wiener gives the definition ${\displaystyle (a,b):=\{\{\emptyset ,\{x\}\}\,{\boldsymbol {\mid }}\,x\in a\}\;{\boldsymbol {\cup }}\;\{\{\{x\}\}\,{\boldsymbol {\mid }}\,x\in b\}}$

- can also be real classes here , but not 'real' primitive elements (i.e. primitive elements different from ∅). ${\displaystyle a,b}$

The comparison of the representation by Wiener with the variant according to Schmidt shows how a pair representation for sets and ('real') primitive elements can be generated from a pair representation for sets and real classes: ${\displaystyle (a,b)}$ ${\displaystyle (a,b)_{\text{Schmidt}}}$

${\displaystyle (a,b)_{\text{Schmidt}}:=\bigcup _{x\in a}\bigcup _{y\in b}(x,y)}$

If a and b are sets (not real classes), the above expression can also be represented as follows:

${\displaystyle (a,b)_{\text{Schmidt}}=\bigcup \{(x,y)|x\in a\land y\in b\}=\bigcup \;(a\times b)}$ 

The method described can also be used on one side only on the left or only on the right. Another pair representation like that of Kuratowski could just as well be used as a basis.

Pair representation after Quine-Rosser

In Kuratowski's representation of pairs, the coordinates of the pairs are two levels below the pairs in the relation of membership ( ), in Wiener it is even three levels ( ). With Schmidt's method, this distance is only reduced by 1. ${\displaystyle a,b\in ^{2}(a,b)}$ ${\displaystyle a,b\in ^{3}(a,b)}$

In 1953 Rosser used a pair representation according to Quine, which requires a set- theoretical representation (or also an axiomatic definition ) of the natural numbers . Instead, the pairs are on the same level as their coordinates. To do this, we first need the following auxiliary definition: ${\displaystyle \mathbb {N} }$

${\displaystyle \sigma (x):=\left\{{\begin{matrix}x,&{\text{für }}x\not \in \mathbb {N} \\x+1,&{\text{für }}x\in \mathbb {N} .\end{matrix}}\right.}$

${\displaystyle \sigma }$increments the argument (by 1) if it is a natural number and leaves it as it is otherwise - the number 0 does not appear as a function value of . We also use: ${\displaystyle \sigma }$

${\displaystyle \varphi (x):=\sigma [x]=\{\sigma (\alpha )|\alpha \in x\}=(x\setminus \mathbb {N} )\cup \{n+1|n\in (x\cap \mathbb {N} )\}.}$

Here is the amount of elements that are not in . refers to the image of a crowd below the figure , and is sometimes also referred to as. Applying this function to a set increments all natural numbers it contains. In particular, it never contains the number 0, so it holds for any set ${\displaystyle x\setminus \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \varphi (x)}$ ${\displaystyle x}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma ''x}$ ${\displaystyle \varphi (x)}$ ${\displaystyle x,y}$

${\displaystyle \varphi (x)\not =\{0\}\cup \varphi (y).}$

Further is defined

${\displaystyle \psi (x):=\sigma [x]\cup \{0\}=\varphi (x)\cup \{0\}}$.

This always contains the number 0 as an element. ${\displaystyle \psi (x)}$

Finally, we define the ordered pair as the following disjoint union:

${\displaystyle (A,B)_{QR}:=\varphi [A]\cup \psi [B]=\{\varphi (a)|a\in A\}\cup \{\varphi (b)\cup \{0\}|b\in B\}.}$

(also in other notation ). ${\displaystyle \varphi ''A\cup \psi ''B}$

When extracting all elements of the so-defined pair that not the 0 included, and reverses, one obtains A . In the same way, B can be recovered from the elements of the pair which in turn contain the 0. ${\displaystyle \varphi }$

The definition assumes the countably infinite set of natural numbers. This is the case in ZF and NF , but not in NFU . J. Barkley Rosser was able to show that the existence of such ordered pairs on the same level as their coordinates presupposes the axiom of infinity . For a detailed discussion of ordered pairs in the context of Quine menegent theories, see Holmes (1998).

Use of ordered pairs

Ordered pairs are the elementary building blocks of many mathematical structures. For example be

• In set theory, Cartesian products , relations and functions are defined as sets of ordered pairs,
• In analysis, complex numbers as ordered pairs with real numbers as components, real numbers as sets ( equivalence classes ) of infinite sequences ( Cauchy sequences of rational numbers ), rational numbers as equivalence classes of ordered pairs whose components are whole numbers , whole numbers as equivalence classes of ordered pairs whose components are natural numbers ,
• in algebra the algebraic structures , for example groups , rings , bodies are essentially defined as functions ( binary links ).

literature

• Felix Hausdorff : Collected Works . Volume 2: Fundamentals of set theory . Springer, Berlin 2002, ISBN 3-540-42224-2 .
• Herbert B. Enderton: Elements of Set Theory. Academic Press, New York 1977, ISBN 0-12-238440-7 .
• Paul R. Halmos : Naive set theory. 5th edition. Vandenhoeck & Ruprecht, Göttingen 1994, ISBN 3-525-40527-8 .
• Heinz-Dieter Ebbinghaus : Introduction to set theory. 4th edition. Spectrum Academic Publishing House, Heidelberg / Berlin 2003, ISBN 3-8274-1411-3 .
• Oliver Deiser: Introduction to set theory. 2nd, improved and enlarged edition. Springer, Berlin a. a. 2004, ISBN 3-540-20401-6 .

Web links

Wikibooks: Math for Non-Freaks: Orderly Pair  - Learning and Teaching Materials

Individual evidence

1. ^ Giuseppe Peano: Logique Mathématique . 1897, Formula 71. In: Opere scelte. II 224, verbalized above
2. ^ Kazimierz Kuratowski: Sur la notion de l'ordre dans la Théorie des Ensembles. In: Fundamenta Mathematica. II (1921), p. 171.
3. ↑ If they differ, the object with the lower type level could be raised to the level of the other by iterated quantity formation . A suitable modification of the representation must ensure that it is always transparent which was the output stage. Because of the pairing axiom, it must always be recognizable whether each of the coordinates is a or . Therefore, one cannot simply raise the level of one of the coordinates by iterated solving in the form . ${\displaystyle x\mapsto \{x,\dots \}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \{x\}}$ ${\displaystyle x\mapsto \{\cdots \{x\}\cdots \}}$
4. ↑ tuple . In: Encyclopaedia of Mathematics
5. ^ Jean van Heijenoort: From Frege to Gödel. Harvard University Press, Cambridge / London 2002, ISBN 0-674-32449-8 , pp. 224ff.
6. ↑ Akihiro Kanamori: The Empty Set, The Singleton, And The Ordered Pair. In: The Bulletin of Symbolic Logic. Vol. 9, No. 3, September 2003, p. 290.
7. ↑ Felix Hausdorff: Fundamentals of set theory. Veit & Comp., Leipzig 1914, pp. 32-33.
8. ↑ Jürgen Schmidt: Set theory. Volume 1: Basic Concepts . BI university pocket books, p. 95 f.
9. ↑ A generally valid pair representation can be formed based on Schmidt's method as follows: The definition valid for sets

   ${\displaystyle a^{+}:=a\cup \{a\}}$
   (Peter Aczel, Michael Rathjen: Notes on Constructive Set Theory , PDF Book draft of August 19, 2010, p. 32, Definition 4.2.1 Part 4; older Notes on Constructive Set Theory , in: Report No. 40, 2000/2001 , Institut Mittag-Leffler of the Royal Swedish Academy of Sciences, ISSN  1103-467X , p. 3-1, definition part 4; also M. Randall Holmes: Elementary Set Theory with a Universal Set , Cahiers du Center de logique, Vol. 10 , p are 79. Other notations , see also axiom of infinity , inductive set ) ${\displaystyle a'}$ ${\displaystyle S(a)}$

   is continued in a natural way for real primordial elements (not equal to the empty set)

   ${\displaystyle a^{+}:=\{a\}}$

   and for actual classes

   ${\displaystyle a^{+}:=a}$.

   A pair representation valid for all of these three cases is then

   ${\displaystyle (a,b)_{\text{all}}:=(a^{+},b^{+})_{\text{Schmidt}}}$.

   In the case of real primordial elements, the original pair representation on which Schmidt is based (e.g. according to Kuratowski) is reproduced:

   ${\displaystyle (a,b)_{\text{all}}=(\{a\},\{b\})_{\text{Schmidt}}=\bigcup _{x\in \{a\}}\bigcup _{x\in \{b\}}(x,y)=(a,b)}$;

   in the case of actual classes, by definition, the Schmidtsche itself:

   ${\displaystyle (a,b)_{\text{all}}=(a,b)_{\text{Schmidt}}}$;

   for sets it is assumed that what is true for many set theories ( ZFU , ZFCU, Quine atoms, Peter Aczel's Hyperset Theory, ...) applies. ${\displaystyle a,b}$ ${\displaystyle a^{+}=b^{+}\Leftrightarrow a=b}$
10. ^ J. Barkley Rosser , 1953. Logic for Mathematicians . McGraw-Hill.
11. ↑ Note that we are only talking about sets (possibly classes), not 'real' primitive elements. If necessary, the Quine atoms take their place , circular sets that satisfy x = {x}. In contrast, this pair representation is also suitable for real classes.
12. ^ M. Randall Holmes: On Ordered Pairs . on: Boise State, March 29, 2009, p. 10. The author uses the terms for and for . ${\displaystyle \sigma _{1}}$ ${\displaystyle \varphi }$ ${\displaystyle \sigma _{2}}$ ${\displaystyle \psi }$
13. ↑ M. Randall Holmes: Elementary Set Theory with a Universal Set . Academia-Bruylant, 1998. The publisher has graciously consented to permit diffusion of this monograph via the web.