Transfinite arithmetic

The transfinite arithmetic is the arithmetic of the ordinal numbers . The arithmetic operations between ordinal numbers can be introduced by means of transfinite recursion as a continuous continuation of the finite arithmetic operations or by suitable set compositions , so that their restriction to the finite ordinal numbers corresponds to the usual arithmetic for natural numbers. The addition and multiplication of ordinal numbers was introduced by Cantor (1897) through composition, whereas exponentiation was introduced functionally by means of border crossing . The first detailed and systematic study on transfinite arithmetic comes from Ernst Jacobsthal (" On the structure of transfinite arithmetic ", Math. Ann., 1909). It shows that both methods - the functional and the composition method - lead to the same arithmetic operations.

addition

If one of two ordinal numbers is the empty set, then their sum is equal to the other ordinal number. To define the sum of two non-empty ordinal numbers and , proceed as follows: Rename the elements of so that and the renamed set are disjoint , and “write to the left of ”, i.e. H. one unites with and defines the order in such a way that within and the previous order applies and each element of is smaller than each element of . In this way the new set is well ordered and is order isomorphic to a uniquely determined ordinal number, which is denoted by. This addition is associative and generalizes the addition of natural numbers. ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$ ${\displaystyle \tau ^{(0)}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau ^{(0)}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau ^{(0)}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau ^{(0)}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau ^{(0)}}$ ${\displaystyle \sigma +\tau }$

The first transfinite ordinal number is the ordered set of all natural numbers, it is called . Let's visualize the sum : We write the second copy as , then we have ${\displaystyle \omega }$ ${\displaystyle \omega +\omega }$ ${\displaystyle \{0_{(0)}<1_{(0)}<2_{(0)}<\dotsb \}}$

${\displaystyle \omega +\omega ={\textrm {ord}}(\{0<1<2<3<\dotsb <0_{(0)}<1_{(0)}<2_{(0)}<3_{(0)}<\dotsb \})}$

This set is not , because in is the only number without an immediate predecessor and has two elements without an immediate predecessor ( and ). The crowd looks like this: ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle 0}$ ${\displaystyle \omega +\omega }$ ${\displaystyle 0}$ ${\displaystyle 0_{(0)}}$ ${\displaystyle 3+\omega }$

${\displaystyle {\textrm {ord}}(\{0<1<2<0_{(0)}<1_{(0)}<2_{(0)}<3_{(0)}<\dotsb \})=\omega }$

So we have . Against it ${\displaystyle 3+\omega =\omega }$

${\displaystyle \omega +3={\textrm {ord}}(\{0<1<2<3<\dotsb <0_{(0)}<1_{(0)}<2_{(0)}\})}$

unequal , because is the largest element of , but does not have a largest element . So the addition is not commutative . One can define the sum of two ordinal numbers and functionally as follows, where both definitions in ZF are equivalent: ${\displaystyle \omega }$ ${\displaystyle 2_{(0)}}$ ${\displaystyle \omega +3}$ ${\displaystyle \omega }$ ${\displaystyle \xi +\eta }$ ${\displaystyle \xi }$ ${\displaystyle \eta }$

• if , then be , ${\displaystyle \eta =0}$ ${\displaystyle \xi +\eta =\xi }$
• if is isolated and the predecessor of , then is , ${\displaystyle \eta }$ ${\displaystyle \eta ^{-}}$ ${\displaystyle \eta }$ ${\displaystyle \xi +\eta =s(\xi +\eta ^{-})}$
• if is a limit , then let . ${\displaystyle \eta }$ ${\displaystyle \xi +\eta ={\textrm {sup}}\{\xi +\beta |\beta <\eta \}}$

The addition is monotonous. That means: and . If so , then there is a definite ordinal number such that . They are known as: . Let and two ordinals. If the equation has a solution , then in the case it has infinitely many solutions and in the case exactly one. If you have any solutions at all, then you understand the smallest of them. In this sense, applies to any isolated number : . Each transfinite ordinal number can be represented in exactly one way as the sum of a limit number and a finite ordinal number . An ordinal number is called a remainder of if there is an ordinal number such that . Every ordinal number has finitely many residues. ${\displaystyle \xi <\eta \Rightarrow \beta +\xi <\beta +\eta }$ ${\displaystyle \xi \leq \eta \Rightarrow \xi +\beta \leq \eta +\beta }$ ${\displaystyle \xi \leq \eta }$ ${\displaystyle x}$ ${\displaystyle \eta =\xi +x}$ ${\displaystyle -\xi +\eta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle x+\alpha =\beta }$ ${\displaystyle x}$ ${\displaystyle \alpha \geq \omega }$ ${\displaystyle \alpha <\omega }$ ${\displaystyle x+\alpha =\beta }$ ${\displaystyle \beta -\alpha }$ ${\displaystyle \gamma }$ ${\displaystyle s(\gamma -1)=\gamma }$ ${\displaystyle \lambda +n}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle \delta }$ ${\displaystyle \xi }$ ${\displaystyle \eta }$ ${\displaystyle \xi =\eta +\delta }$

multiplication

To multiply two ordinals and , write down and replace each element of with a different copy of . The result is a well-ordered set that is isomorphic to exactly one ordinal number, which is denoted by. This connection is also associative and generalizes the multiplication of the natural numbers. ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma \tau }$

The ordinal number ω 2 looks like this:

${\displaystyle \{0_{(0)}<1_{(0)}<2_{(0)}<\dotsb <0_{(1)}<1_{(1)}<2_{(1)}<\dotsb \}}$

It can be seen that ω · 2 = ω + ω. In contrast, 2 ω looks like this:

${\displaystyle \{0_{(0)}<1_{(0)}<0_{(1)}<1_{(1)}<0_{(2)}<1_{(2)}<\dotsb \}}$

and after renaming we see that 2 · ω = ω. So the multiplication of ordinal numbers is not commutative either.

One of the distributive applies to ordinal numbers: . You can read that directly from the definitions. However, the other distributive law does not apply in general, because z. B. (1 + 1) ω = 2 ω = ω, but 1 ω + 1 ω = ω + ω. ${\displaystyle \rho (\sigma +\tau )=\rho \sigma +\rho \tau }$

The neutral element of addition is 0, the neutral element of multiplication is 1. No ordinal number except 0 has a negative (an additively inverse element ), so the ordinal numbers do not form a group with the addition, and certainly not a ring . The functional definition of multiplication is:

• if , then be , ${\displaystyle \eta =0}$ ${\displaystyle \xi \eta =\eta }$
• for each ordinal is , ${\displaystyle \eta }$ ${\displaystyle \xi (\eta +1)=\xi \eta +\xi }$
• if is a limit, then let . ${\displaystyle \eta }$ ${\displaystyle \xi \eta =\sup\{\xi \beta |\beta <\eta \}}$

The monotony laws apply:

• ${\displaystyle \xi <\eta \Rightarrow \forall \beta >0(\beta \xi <\beta \eta )}$
• ${\displaystyle \xi \leq \eta \Rightarrow \xi \beta \leq \eta \beta }$
• ${\displaystyle (\xi +\eta )\beta \leq \xi \beta +\eta \beta }$

For every two ordinal numbers and applies . If , then is left divisor of and right divisor . It is also said that the right-hand multiple is of and the left-hand multiple of . The limit numbers are left-sided multiples of . Every ordinal number has finitely many right-hand divisors and only finitely many left-hand divisors if it is not a limit number. Sets of positive ordinals have a greatest common right divisor, a greatest common left divisor, and a smallest left common multiple. A right-sided common multiple is not always present. Counterexample is . For two ordinals and there are clearly definite ordinals and , so that . ${\displaystyle \xi >1}$ ${\displaystyle \eta >1}$ ${\displaystyle \xi +\eta \leq \xi \eta }$ ${\displaystyle \eta \gamma =\xi }$ ${\displaystyle \eta }$ ${\displaystyle \xi }$ ${\displaystyle \gamma }$ ${\displaystyle \xi }$ ${\displaystyle \gamma }$ ${\displaystyle \eta }$ ${\displaystyle \omega }$ ${\displaystyle \{\omega ,\omega +1\}}$ ${\displaystyle \xi }$ ${\displaystyle \eta >0}$ ${\displaystyle \beta }$ ${\displaystyle \rho <\eta }$ ${\displaystyle \xi =\eta \beta +\rho }$

General sum

Let be a network of ordinal numbers with the ordinal number as the index set. be the order relations of the copies for . The general sum of all is defined as follows: ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$ ${\displaystyle \xi }$ ${\displaystyle {\delta _{{S_{\gamma }}^{(\beta )}}}^{\!\!\!^{\!^{\color {white}.}}}}$ ${\displaystyle {S_{\gamma }}^{(\beta )}}$ ${\displaystyle \beta <\xi }$ ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$

${\displaystyle \sum \nolimits _{\gamma <\xi }S_{\gamma }=\operatorname {ord} \left(\bigcup \nolimits _{\gamma <\xi }{S_{\gamma }}^{(\gamma )},\bigcup \nolimits _{\gamma }\delta _{{S_{\gamma }}^{(\gamma )}}\cup \bigcup \nolimits _{\gamma <\eta <\xi }({S_{\gamma }}^{(\gamma )}\times {S_{\eta }}^{(\eta )})\right)}$

The multiplication is a special case of the general sum:

${\displaystyle \xi \beta =\sum \nolimits _{\gamma <\beta }\xi }$

There is exactly one function for each ordinal network : with the following three properties: ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$ ${\displaystyle F\colon \{\gamma |\gamma \leq \xi \}\rightarrow {\textrm {On}}}$

• ${\displaystyle F(0)=0}$
• ${\displaystyle F(s(\beta ))=F(\beta )+S_{\beta }}$ for each ordinal number ${\displaystyle \beta <\xi }$
• ${\displaystyle F(\beta )=\sup _{\eta <\beta }F(\gamma )}$ for each limit number ${\displaystyle \beta \leq \xi }$

The value corresponds exactly to the general sum of . ${\displaystyle F(\xi )}$ ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$

General product

For a network of ordinal numbers let ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$

${\displaystyle P=\left\{x\in {\underset {\beta <\xi }{\mathbf {\times } }}{S_{\beta }}{\Big |}\operatorname {card} (\{\zeta <\xi |0<\pi _{\zeta }(x)\})<\aleph _{0}\right\},}$

in which

${\displaystyle \pi _{\zeta }\colon {\underset {\beta <\xi }{\mathbf {\times } }}{S_{\beta }}\rightarrow {S_{\zeta }}}$

${\displaystyle (\dotsc ,a,\dotsc )\mapsto a}$

is the name for the canonical projection . Define in the relation: ${\displaystyle P}$ ${\displaystyle {\delta }_{P}^{*}=\left\{(x,y)\in P\times P{\Big |}\{\kappa <\xi |\pi _{\kappa }(x)<\pi _{\kappa }(y);\ \forall \eta (\kappa <\eta <\xi )(\pi _{\eta }(x)=\pi _{\eta }(y))\}\neq \emptyset \right\}}$

The general product of all the elements of is by ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$

${\displaystyle \prod _{\gamma <\xi }S_{\gamma }=\operatorname {ord} \left(P,\delta _{P}^{*}\cup \left\{(x,y)\in P\times P|x=y\right\}\right)}$

Are defined. The general product thus consists of tuples of length that are ordered anti-lexicographically and only have a finite number of positive components. There is exactly one function for each ordinal network : with the following four properties: ${\displaystyle \xi }$ ${\displaystyle (S_{\gamma })_{\gamma \in \xi }}$ ${\displaystyle F\colon \{\gamma |\gamma \leq \xi \}\rightarrow {\textrm {On}}}$

• ${\displaystyle F(0)=1}$
• ${\displaystyle F(s(\beta ))=F(\beta )S_{\beta }}$ for each ordinal number ${\displaystyle \beta <\xi }$
• ${\displaystyle F(\beta )=\sup _{\eta <\beta }F(\gamma )}$for limit number , if ${\displaystyle \beta \leq \xi }$ ${\displaystyle \forall \eta <\beta (S_{\eta }>0)}$
• ${\displaystyle F(\beta )=0}$for limit number , if ${\displaystyle \beta \leq \xi }$ ${\displaystyle \exists \eta <\beta (S_{\eta }=0)}$

The value corresponds exactly to the general product of ${\displaystyle F(\xi )}$ ${\displaystyle (S_{\gamma })}$ _{${\displaystyle \gamma \in \xi }$}

The consequence

${\displaystyle \{(0,0,0,\dotsc )<(0,1,0,\dotsc )<(0,0,1,\dotsc )<(0,1,1,\dotsc )<(0,0,2,\dotsc )<(0,1,2,\dotsc )}$ ${\displaystyle <(0,0,0,1,\dotsc )<\dotsb <(0,1,2,3,0,\dotsc )<(0,0,0,0,1,\dotsc )<\dotsb <(0,1,2,\dotsc ,n,0,\dotsc )<(0,0,\dotsc ,0,1,0,\dotsc )<\dotsb \}}$

is an example of an anti-lexicographical order and, according to the definition, represents a set that is too isomorphic in order . So and ! which is not surprising because yes ! . ${\displaystyle \Pi _{\xi <\omega }\xi }$ ${\displaystyle \omega =\Pi _{\xi <\omega }\xi }$ ${\displaystyle \omega }$ ${\displaystyle =\omega \omega }$ ${\displaystyle \omega =\sup }$ _{${\displaystyle n}$} ${\displaystyle n}$

Potentiate

The potencies are special cases of general products:

${\displaystyle \beta ^{\xi }=\prod \nolimits _{\gamma <\xi }\beta \,}$

example

A set that is too order isomorphic can be constructed by considering (according to the product definition) sequences of natural numbers with a finite number of positive elements: ${\displaystyle \omega ^{\omega }}$

${\displaystyle ({\overbrace {{\underbrace {a_{0},\dotsc ,a_{n-1}} _{n\in \mathbb {N} }},\underbrace {0,\dotsc ,0,\dotsc } _{\overset {\shortparallel }{0}}} ^{\omega }})\in \omega \times \omega }$

and this antilexicographically arranges:

${\displaystyle (0,0,0,\dotsc )<(1,0,0,\dotsc )<\dotsb <(0,1,0,\dotsc )<(1,1,0,\dotsc )<\dotsb <(0,0,1,\dotsc )<(1,0,1,0,\dotsc )<\dotsb <(0,1,1,0,\dotsc )<(1,1,1,0,\dotsc )<(2,1,1,0,\dotsc )<\dotsb }$

properties

The following applies to ordinal numbers : ${\displaystyle \xi >0,\beta ,\eta }$

• ${\displaystyle \xi ^{\beta +\eta }=\xi ^{\beta }\xi ^{\eta }}$
• ${\displaystyle (\xi ^{\beta })^{\eta }=\xi ^{\beta \eta }}$
• ${\displaystyle \beta <\eta \Rightarrow \xi ^{\beta }<\xi ^{\eta }}$
• ${\displaystyle \beta \leq \xi ^{\beta }}$.

For two ordinal numbers and applies . From follows . For two ordinal numbers and there are clearly definite ordinal numbers: - called logarithm from to base , positive and so that ( logarithm set ). The power rule from finite arithmetic cannot be transferred to infinity: ${\displaystyle \xi >1}$ ${\displaystyle \eta >1}$ ${\displaystyle \xi \eta \leq \xi ^{\eta }}$ ${\displaystyle \eta \leq \zeta }$ ${\displaystyle \eta ^{\beta }\leq \zeta ^{\beta }}$ ${\displaystyle \xi >0}$ ${\displaystyle \beta >1}$ ${\displaystyle \lambda }$ ${\displaystyle \xi }$ ${\displaystyle \beta }$ ${\displaystyle \delta <\beta }$ ${\displaystyle \rho <\beta ^{\lambda }}$ ${\displaystyle \xi =\beta ^{\lambda }\delta +\rho }$ ${\displaystyle (\alpha \beta )^{\gamma }=\alpha ^{\gamma }\beta ^{\gamma }}$

${\displaystyle (2\cdot 2)^{\omega }<2^{\omega }2^{\omega }}$

${\displaystyle (2(\omega +1))^{2}>2^{2}(\omega +1)^{2}}$

Cantor's normal form

→ Main article : Cantor's normal form

For two ordinal numbers and there exist finitely many uniquely determined and such that ${\displaystyle \beta >1}$ ${\displaystyle \xi <\beta ^{\lambda }}$ ${\displaystyle \lambda _{0}<\dotsb <\lambda _{n}<\lambda }$ ${\displaystyle \{\kappa _{0},\dotsc ,\kappa _{n}\}\subset \beta }$

${\displaystyle \xi =\beta ^{\lambda _{n}}\kappa _{n}+\dotsb +\beta ^{\lambda _{0}}\kappa _{0}}$.

This representation is known by the name of Cantor's polynomial representation (or - adic normal form ). It is called for Cantor 's normal representation (or Cantor's normal form ). One can use Cantor's normal representation recursively and represent the ordinal numbers exactly as in their normal form. If this process ends after a finite number of steps in finite ordinal numbers, one obtains an elementary expression for , which consists of natural numbers and symbols for arithmetic operations. However, this is not possible for every ordinal number. Even more general: with a finite number of characters, only a countable number of ordinal numbers can be represented - so only a "vanishingly small" part of the entire class . There are ordinal numbers for which is the same in their Cantor normal representation . In this case, the normal representation does not lead to any simplification. The smallest such number is called . The natural operations of Hessenberg are defined with the help of Cantor's normal representation . ${\displaystyle \beta }$ ${\displaystyle \beta =\omega }$ ${\displaystyle \lambda _{0},\dotsc ,\lambda _{n}}$ ${\displaystyle \xi }$ ${\displaystyle \xi }$ ${\displaystyle \omega }$ ${\displaystyle {\textrm {On}}}$ ${\displaystyle \xi }$ ${\displaystyle \lambda _{n}}$ ${\displaystyle \xi }$ ${\displaystyle \varepsilon _{0}}$

literature

• Heinz Bachmann: Transfinite numbers. Springer, 1967.
• Ernst Jacobsthal : About the structure of transfinite arithmetic. In: Mathematical Annals. 66, 1909, pp. 145-194.
• Dieter Klaua : Cardinal and Ordinal Numbers. Part 2. Vieweg, Braunschweig 1974, ISBN 3-528-06141-3
• Dieter Klaua: General set theory. A foundation of mathematics. Akademie-Verlag, Berlin 1964.
• Peter Komjath, Vilmos Totik: Problems and Theorems in Classical Set Theory. Springer, 2006, ISBN 978-0387302935 .
• Wacław Sierpiński : Cardinal and ordinal numbers. 1965, ISBN 978-0900318023 .
• Kazimierz Kuratowski , Andrzej Mostowski : Set theory. North-Holland, 1968, ISBN 978-0720404708 .
• Felix Hausdorff : Fundamentals of set theory. 1914. Chelsea Publishing Company, New York, 1949.
• Herbert Enderton : Elements of Set Theory. Academic Press, New York 1977, ISBN 978-0122384400 .
• Oliver Deiser: Introduction to set theory. Springer, 2004, ISBN 978-3540204015 .

See also

• Cardinal number arithmetic

Remarks

1. ^ Cantor G .: Contributions to the foundation of the transfinite set theory. (Second article) , Mathematische Annalen, 1897, 49, pp. 207–246
2. ↑ At this point it is appropriate to explain what is meant by renaming the elements of an ordinal number and how this renaming is justified. Be a non-empty ordinal number. For any element of and any ordinal number , the set is designated. It is important here that the Kuratowski definition of an ordered pair is used. This guarantees that none of the sets is an ordinal number. The set is known as the renamed ordinal or copy . The well-being in is determined by. Ordinal numbers are order isomorphic to their copies. No copy is an ordinal number and no ordinal number is an element or subset of a copy. All copies of an ordinal number and the ordinal number itself are pairwise disjoint from one another. ${\displaystyle X}$ ${\displaystyle \xi }$ ${\displaystyle X}$ ${\displaystyle a}$ ${\displaystyle \xi _{(a)}}$ ${\displaystyle (a,\xi )=\{\{a\},\{a,\xi \}\}}$ ${\displaystyle \xi _{(a)}}$ ${\displaystyle X^{(a)}=\{\xi _{(a)}\}_{\xi \in X}}$ ${\displaystyle X^{(a)}}$ ${\displaystyle \eta _{(a)}\leq \xi _{(a)}\Leftrightarrow \eta \leq \xi }$
3. ↑ It is true , where the order relation denotes the well-ordered set . ${\displaystyle \delta _{\sigma \cup \tau ^{(0)}}}$ ${\displaystyle =(\sigma \times \tau ^{(0)})\cup \delta _{\sigma }\cup \delta _{\tau ^{(0)}}}$ ${\displaystyle \delta _{X}}$ ${\displaystyle (X,\leq _{X})}$
4. ↑ It is even the case that (see Komjath, 2006, 8.17). ${\displaystyle \forall \xi \exists \eta \leq \xi }$ ${\displaystyle ((\eta +\xi =\xi +\eta )\Rightarrow (\xi =0))}$
5. ↑ In some sources the designation is used that probably goes back to Cantor (see Sierpinski, 1965, XIV., §4, Th. 2 and Kuratowski, Mostowski, 1968, VII., §5). We stick to the designation given by Jacobsthal, 1909, p. 166 and Hausdorff, 1914, chap. V., § 2. and Bachmann, § 17.2. ${\displaystyle \eta -\xi }$ ${\displaystyle -\xi +\eta }$
6. ↑ s. Sierpinski, 1965, XIV., § 5.
7. ↑ Each element is replaced by by . ${\displaystyle \alpha }$ ${\displaystyle \tau }$ ${\displaystyle \sigma ^{(\alpha )}}$
8. ↑ So in our names there is with and . Such an order in a Cartesian product is called anti-lexicographical . ${\displaystyle \sigma \tau =ord(\sigma \times \tau ,R_{1}\cup R_{2})}$ ${\displaystyle R_{1}=\bigcup \{\delta _{\sigma ^{(\beta )}}|\beta <\tau \}}$ ${\displaystyle R_{2}=\bigcup \{\sigma ^{(\xi )}\times \sigma ^{(\eta )}|\xi <\eta <\tau \}}$ ${\displaystyle \sigma \times \tau }$
9. ↑ ^{a b} s. Bachmann, § 10.
10. ↑ ^{a b c d} s. Bachmann, § 17.3, § 18. and Sierpinski, 1965, XIV., § 11-12. and Komjath, Totik, 2006, 9.2, 9.8-9 and Jacobsthal, 1909, pp. 176-188
11. ↑ s. also: King's Paradox
12. ↑ This book is based on a special system of axioms.