Dedekind's isomorphism theorem

The isomorphism of Dedekind , named after Richard Dedekind , is a mathematical theorem, the uniqueness statement about the natural numbers, as represented by the Peano axioms meet are defined. This statement can be found in Dedekind's classic book " What are and what should the numbers? " From 1888 as sentence 132 in the following formulation:

• All simply infinite systems are of the series N and consequently are similar to each other.

Today we call simply infinite systems Peano systems , instead of similar we say isomorphic . The following illustration uses these more modern terms and adds some logical aspects of this theorem.

introduction

The properties of natural numbers have been characterized axiomatically by Giuseppe Peano using the following so-called Peano axioms. A Peano system is a set with the following properties ${\displaystyle N}$

1. There is an element (this element plays the role of 0) ${\displaystyle 0\in N}$
2. There is a picture (successor picture ) ${\displaystyle \sigma \colon N\rightarrow N}$
3. ${\displaystyle \forall n\in N:\sigma (n)\not =0}$ (0 is not a successor)
4. ${\displaystyle \sigma }$is injective (different elements have different successors)
5. If a subset with and , it follows ( complete induction ) ${\displaystyle X\subseteq N}$ ${\displaystyle 0\in X}$ ${\displaystyle \forall n\in N\colon (n\in X\rightarrow \sigma (n)\in X)}$ ${\displaystyle X=N}$

More precisely, this Peano system is called . The meaning of the axioms is given in brackets. ${\displaystyle (N,0,\sigma )}$

The entire theory of natural numbers can be built from this. Hence the question of the uniqueness of the Peano systems. This question is answered positively by Dedekind's isomorphism theorem to be discussed here. Of course, one can get several Peano systems by changing names, but these turn out to be essentially the same. To make this kind of uniqueness more precise, it is necessary to determine when one wishes to regard two Peano systems as essentially the same, and this is done using the concept of isomorphism, which is now to be clarified.

To symbolize the above axioms, a constant symbol 0 and a function symbol - were used, a Peano system is therefore a structure with the above properties. An isomorphism between Peano systems is therefore understood to be a bijective mapping that contains these structural elements, more precisely: ${\displaystyle \sigma }$ ${\displaystyle \{0,\sigma \}}$

An isomorphism between two Peano systems and is a bijective mapping with the following two properties: ${\displaystyle (N,0,\sigma )}$ ${\displaystyle ({\tilde {N}},{\tilde {0}},{\tilde {\sigma }})}$ ${\displaystyle f\colon N\rightarrow {\tilde {N}}}$

• ${\displaystyle f(0)={\tilde {0}}}$
• ${\displaystyle \forall n\in N\colon f(\sigma (n))={\tilde {\sigma }}(f(n))}$.

It is easy to show that the reverse mapping has the same properties. Two Peano systems are called isomorphic if there is an isomorphism between them.

A concrete Peano system can be constructed as follows. Defining , for a lot of the so-called successor amount and the average of all amounts with 0 each also contain, as is a Peano system is briefly referred to. This is the usual construction of natural numbers in set theory . ${\displaystyle 0=\emptyset }$ ${\displaystyle a}$ ${\displaystyle s(a):=a\cup \{a\}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle a}$ ${\displaystyle s(a)}$ ${\displaystyle (\mathbb {N} ,0,s|_{\mathbb {N} })}$ ${\displaystyle \mathbb {N} }$

Formulations of the sentence

• Every two Peano systems are isomorphic.

Since we have specified a concrete Peano system with, we can rephrase the equivalent: ${\displaystyle \mathbb {N} }$

• Every Peano system is isomorphic to . ${\displaystyle \mathbb {N} }$

Remarks

The definition given above uses second order predicate logic because the formal rendering of the induction axiom reads

${\displaystyle \forall X\,((0\in X\land \forall n\,(Xn\rightarrow X\sigma (n)))\rightarrow \forall n\,Xn)}$.

The notation means in every interpretation that is included in the subset . ${\displaystyle Xn}$ ${\displaystyle n}$ ${\displaystyle X}$

So here the single-digit relation is used to quantify, and this is not possible in the first-level predicate logic . In fact, there are structures that are too elementary equivalent but not isomorphic, that is, they fulfill the same statements that can be formulated in the first order predicate logic, but are still not isomorphic. Such structures are called non-standard models . According to Skolem's theorem, there are even countable non-standard models. ${\displaystyle X}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

If one replaces the induction axiom 5 by the infinitely many axioms

${\displaystyle (\varphi (0)\land \forall n\,(\varphi (n)\rightarrow \varphi (\sigma (n)))\rightarrow \forall n\,\varphi (n)}$,

That means for every formula of the first order predicate logic with a free variable one has an axiom, one gets the so-called Peano arithmetic . The existence of countable non-standard models thus shows that Dedekind's theorem cannot be transferred to Peano arithmetic. This historically surprising result becomes plausible when one considers that there are only countably many formulas and therefore one only has a countable number of induction axioms in Peano arithmetic. The induction axiom 5 makes a statement about all subsets of a Peano system, and that is an uncountable number, so it is formally stronger. ${\displaystyle \{0,\sigma \}}$ ${\displaystyle \varphi }$ ${\displaystyle \{0,\sigma \}}$

As mentioned above, one can construct the natural numbers in set theory, that is, one can define them with the symbol in the language of first-order predicate logic, and Dedekind's theorem can also be proven. This does not contradict the above statements on Skolem's theorem. The latter relates to Peano systems in the first-level predicate logic, in which one can only quantify via the elements of the basic class and the subsets of the basic class do not belong there. In set theory, however, the basic class is the entire universe of sets, i.e. the induction axiom can be described by means of quantification using the elements of the basic class: ${\displaystyle \in }$

${\displaystyle \forall x\,((\emptyset \in x\land \forall y\,(y\in x\rightarrow y\cup \{y\}\in x))\rightarrow \mathbb {N} \subset x)}$

Please note that the symbols can be defined using , so these could in principle be dispensed with at the expense of easier readability, so that it is actually a statement. The proof of Dedekind's theorem can thus be transferred. ${\displaystyle \emptyset ,\cup ,\{y\},\mathbb {N} ,\subset }$ ${\displaystyle \in }$ ${\displaystyle \in }$

Individual evidence

1. ↑ R. Dedekind: What are and what are the numbers? , 1st edition, Vieweg, Braunschweig 1888, sentence 132
2. ↑ G. Peano: Opere scelte III, p. 216, original with operator n + instead of σ (n)
3. ↑ H.-D. Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic , spectrum Akademischer Verlag, ISBN 3-8274-0130-5 , III, sentence 7.4
4. ↑ Dirk W. Hoffmann: Die Gödel'schen incompleteness sentences: A guided journey through Kurt Gödels historical proof , Springer-Verlag (2013), ISBN 3-827-43000-3 , sentence 2.3: Isomorphiesatz von Dedekind
5. ↑ H.-D. Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic , spectrum Akademischer Verlag, ISBN 3-8274-0130-5 , VI, sentence 4.6
6. ↑ H.-D. Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic , spectrum Akademischer Verlag, ISBN 3-8274-0130-5 , Chapter VII: On the scope of the first stage
7. ↑ Dirk Siefkes : Formalize and Prove: Logic for Computer Scientists , Springer-Verlag (2013), ISBN 3-322-85621-6 , explanations from page 218.