Diskrete Mathematik/Natürliche Zahlen/Textabschnitt

Wir stellen hier einige Grundtatsachen über die natürlichen Zahlen zusammen, auf die immer wieder Bezug genommen wird. Diese Eigenschaften sind in höchstem Maße vertraut, es ist aber sinnvoll, sich einmal klar zu machen, wie die grundlegenden Strukturen auf den natürlichen Zahlen ausgehend von der Nachfolgerabbildung aufgebaut und ihre Eigenschaften nachgewiesen werden. Der induktive Aufbau der natürlichen Zahlen ist für viele Fragestellungen der diskreten Mathematik auch deshalb instruktiv, weil man diese häufig dadurch zu verstehen versucht, indem man sich überlegt, was passiert, wenn eine gewisse diskrete oder kombinatorische Situation ein bisschen (um ein zusätzliches Element, eine neue Kante, etc.) komplizierter wird.

Der induktive Aufbau der natürlichen Zahlen

Definition

Eine Menge ${}N$ mit einem ausgezeichneten Element ${}0\in N$ (die Null) und einer (Nachfolger)-Abbildung

$'\colon N\longrightarrow N,\,n\longmapsto n',$

heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

1. Das Element ${}0$ ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
2. Jedes ${}n\in N$ ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
3. Für jede Teilmenge ${}T\subseteq N$ gilt: Wenn die beiden Eigenschaften
   • ${}0\in T$,
   • mit jedem Element
   ${}n\in T$ ist auch ${}n'\in T$,

gelten, so ist ${}T=N$.

Satz

Es seien ${}(N_{1},0_{1},\prime )$ und ${}(N_{2},0_{2},\star )$ Modelle für die natürlichen Zahlen.

Dann gibt es genau eine (bijektive) Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2},$

die das Zählen (also die ${}0$ und die Nachfolgerabbildung) respektiert.

Beweis

Da die Abbildung ${}\varphi$ insbesondere die Null respektieren soll, muss

${}\varphi (0_{1})=0_{2}\,$

sein. Da die Abbildung die Nachfolgerabbildungen respektieren soll, gilt generell

${}\varphi (x^{\prime })=(\varphi (x))^{\star }\,$

für alle ${}x\in N_{1}$. Speziell gilt

${}\varphi (0_{1}^{\prime })={\left(\varphi (0_{1})\right)}^{\star }=0_{2}^{\star }\,.$

Aus dem gleichen Grund muss unter Verwendung des schon Bewiesenen

${}\varphi {\left(0_{1}^{\prime \prime }\right)}=\varphi {\left((0_{1}^{\prime })^{\prime }\right)}={\left(\varphi (0_{1}^{\prime })\right)}^{\star }={\left(0_{2}^{\star }\right)}^{\star }=0_{2}^{\star \star }\,.$

Ebenso muss

${}\varphi {\left(0_{1}^{\prime \prime \prime }\right)}=0_{2}^{\star \star \star }\,,$

${}\varphi {\left(0_{1}^{\prime \prime \prime \prime }\right)}=0_{2}^{\star \star \star \star }\,,$

u.s.w gelten. Hier hat man keine Wahlmöglichkeiten, alles ist durch die Nachfolgereigenschaft bestimmt. Da jedes Element ${}\neq 0_{1}$ aus ${}N_{1}$ von ${}0_{1}$ aus durch die Nachfolgerabbildung ${}\prime$ schließlich und genau einmal erreicht wird, ist dies eine wohldefinierte Abbildung von ${}N_{1}$ nach ${}N_{2}$.

Zum Nachweis der Surjektivität betrachten wir die Menge

${}T={\left\{y\in N_{2}\mid {\text{ Es gibt }}x\in N_{1}{\text{ mit }}y=\varphi (x)\right\}}\,.$

Wir müssen zeigen, dass

${}T=N_{2}\,$

ist. Dazu wenden wir das Induktionsaxiom für ${}N_{2}$ an. Wegen

${}\varphi (0_{1})=0_{2}\,$

gehört ${}0_{2}\in T$. Wenn ${}y\in T$ ist, so ist also

${}y=\varphi (x)\,$

für ein ${}x\in N_{1}$. Wegen der Verträglichkeit mit der Nachfolgerabbildung ist

${}y^{\star }=\varphi (x^{\prime })\,,$

d.h. auch ${}y^{\star }\in T$. Daher ist ${}T$ unter dem Nachfolger abgeschlossen und nach dem Induktionsaxiom ist also ${}T=N_{2}$. Zum Nachweis der Injektivität seien ${}x,{\tilde {x}}\in N_{1}$ verschieden. und zwar sei ${}{\tilde {x}}$ ein (direkter oder) höherer Nachfolger von ${}x$. Dann ist ${}\varphi ({\tilde {x}})$ der entsprechende Nachfolger von ${}\varphi (x)$ und insbesondere davon verschieden (siehe Aufgabe), da das Nachfolgernehmen in ${}N_{2}$ injektiv ist.

$\Box$

Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.

Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion. Wir schreiben ${}n+1$ für den Nachfolger.

Satz

Für jede natürliche Zahl ${}n$ sei eine Aussage ${}A(n)$ gegeben. Es gelte

1. ${}A(0)$ ist wahr.
2. Für alle ${}n$ gilt: wenn ${}A(n)$ gilt, so ist auch ${}A(n+1)$ wahr.

Dann gilt ${}A(n)$ für alle ${}n$.

Beweis

Es sei

${}M={\left\{n\in \mathbb {N} \mid A(n){\text{ ist wahr}}\right\}}\,.$

Wir wollen zeigen, dass ${}M=\mathbb {N}$ ist, denn genau dies bedeutet, dass die Aussage für alle ${}n$ gilt. Nach der ersten Bedingung ist

${}0\in M\,.$

Nach der zweiten Voraussetzung gilt für ${}M$, dass aus ${}n\in M$ stets ${}n+1\in M$ folgt. Damit erfüllt ${}M$ beide Voraussetzungen im Induktionsprinzip für Mengen, so dass ${}M=\mathbb {N}$ gilt.

$\Box$

Der Nachweis von (der Gültigkeit von) ${}A(0)$ heißt dabei der Induktionsanfang und der Schluss von ${}A(n)$ auf ${}A(n+1)$ heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von ${}A(n)$ auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage ${}A(n)$ erst für ${}n\geq n_{0}$ für ein gewisses ${}n_{0}$ (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage ${}A(n_{0})$ und den Induktionsschritt führt man für alle ${}n\geq n_{0}$ durch.

Die Addition

Die Addition auf den natürlichen Zahlen ist eine vertraute Operation und es gibt viele Möglichkeiten, sie einzuführen. Je nach Kontext und Absicht sind unterschiedliche Ansätze besser geeignet. Zur rechnerischen Definition der Addition ist etwa das schriftliche Addieren im Dezimalsystem besonders effektiv, während zum Nachweis der Assoziativität die inhaltliche Interpretation als disjunkte Vereinigung von Mengen sinnvoll ist. Um ein klares Fundament zu haben, muss man sich bei einem systematisches Aufbau der Mathematik dafür entscheiden, was man als Definition nimmt, und dann beweisen, dass der gewählte Zugang auch andere Charakterisierungen erlaubt und somit mit anderen Zugängen übereinstimmt.

Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar allein unter Bezug auf das Nachfolgernehmen, das das Zählen charakterisiert. Das Nachfolgernehmen ist ein Prozess, den man iterieren kann. Sowohl der Startwert des Nachfolgernehmens als auch die Anzahl, wie oft ein Nachfolger genommen werden soll, wird durch natürliche Zahlen beschrieben. Die ${}k$-fache Durchführung eines Prozesses bedeutet, dass er so oft durchgeführt wird, wie es die Menge ${}\{1,\ldots ,k\}$ vorgibt.

Definition

Die Summe ${}n+k$ zweier natürlicher Zahlen ${}n$ und ${}k$ ist diejenige natürliche Zahl, die man erhält, wenn man von ${}n$ ausgehend ${}k$-fach den Nachfolger nimmt.

Die Operation heißt die Addition und die beteiligten Zahlen nennt man die Summanden. Nach dieser Definition wird also ausgehend von ${}n$ der Nachfolgerprozess ${}k$-fach durchgeführt. Bei ${}k=0$ ist dies als der nullte Nachfolger, also als ${}n$ selbst, zu verstehen. Bei ${}k=1$ ist dies der erste Nachfolger, ${}n+1$ ist also die erste Zahl ${}n^{\prime }$ nach ${}n$. Die Summe ${}n+k$ ist also ${}n^{\prime \prime \ldots \prime }$ mit ${}k$ Nachfolgerstrichen. Wenn umgekehrt

${}n=0\,$

ist, so ist der ${}k$-te Nachfolger der ${}0$ gleich ${}k$. Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist, das wird sich aber gleich ergeben.

Das kleine Einsundeins. Das Umlegungsprinzip schlägt sich in der Additionstabelle darin nieder, dass in den Linksunten nach Rechtsoben-Diagonalen konstante Werte stehen.

Lemma

Für die Addition der natürlichen Zahlen (mit der in Definition festgelegten Addition) gelten die folgenden Aussagen.

1. ${}n+0=n=0+n\,$

   für alle ${}n$, d.h. ${}0$ ist das neutrale Element der Addition.

2. ${}n+k'=(n+k)'=n'+k\,$

   für alle ${}n,k\in \mathbb {N}$ (Umlegungsregel).

3. Die Addition ist kommutativ.
4. Die Addition ist assoziativ.
5. Aus einer Gleichung ${}n+k=m+k$ folgt

   ${}n=m\,$

   (Abziehregel).

Beweis

1. Die Gleichungen links und rechts sind unmittelbar klar, da der ${}n$-te Nachfolger der ${}0$ gleich ${}n$ ist.
2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl ${}n$ aus und nimmt einmal öfters als ${}k$-mal den Nachfolger. In der Mitte bestimmt man ${}k$-fach den Nachfolger von ${}n$ und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von ${}n$ den Nachfolger und davon dann ${}k$-fach den Nachfolger.
3. Es ist

   ${}n+k=k+n\,$

   für alle ${}k,n$ zu zeigen. Diese Gleichungen zeigen wir durch Induktion über ${}k$ für alle ${}n$. Bei ${}k=0$ steht beidseitig ${}n$ nach Teil (1). Es sei die Gleichheit nun für ein ${}k$ (und alle ${}n$) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)

   ${}n+k^{\prime }=(n+k)^{\prime }=(k+n)^{\prime }=k^{\prime }+n\,,$

   die Gleichung gilt also auch für ${}k^{\prime }$.

4. Wir beweisen die Assoziativität, also die Gleichheit

   ${}(m+n)+k=m+(n+k)\,,$

   durch Induktion über ${}k$ (für alle ${}m,n$ gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt

   ${}(m+n)+k^{\prime }=(m+n)^{\prime }+k=(m+n^{\prime })+k=m+(n^{\prime }+k)=m+(n+k^{\prime })\,.$

5. Die Abziehregel beweisen wir ebenfalls durch Induktion über ${}k$. Der Fall

   ${}k=0\,$

   ist klar. Es sei also die Aussage für ein ${}k$ schon bewiesen und sei eine Gleichung der Form

   ${}m+k^{\prime }=n+k^{\prime }\,$

   gegeben. Dann ist nach der Umlegungsregel auch

   ${}m^{\prime }+k=n^{\prime }+k\,.$

   Nach der Induktionsvoraussetzung ist somit

   ${}m^{\prime }=n^{\prime }\,.$

   Da die Nachfolgerabbildung injektiv ist, ergibt sich

   ${}m=n\,.$

$\Box$

Für einige alternative Begründungen siehe die Aufgaben. Teil (2) kann man auch so verstehen, dass man eine Summe ${}n+k$ dadurch berechnen kann, dass man sukzessive den ersten Summanden um eins erhöht (also den Nachfolger nimmt) und den zweiten um eins vermindert (also den Vorgänger nimmt), falls ${}k\neq 0$ ist. Dies macht man so lange, bis der zweite Summand ${}0$ ist. Der dabei entstandene neue erste Summand ist die Summe. Statt Umlegungsregel sagt man auch Umlegungsprinzip oder man spricht von einer „gegensinnigen Veränderung“, was auch oft bei Rechnungen effektiv eingesetzt wird, wenn man etwa ${}19+41=20+40=60$ rechnet. Die folgende Aussage besagt, dass durch das Umlegungsprinzip die Addition bereits festgelegt ist.

Satz

Auf den natürlichen Zahlen

gibt es genau eine Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(x,y)\longmapsto x+y,$

mit

$x+0=x{\text{ für alle }}x\in \mathbb {N} \,\,{\text{ und }}\,\,x+y'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N} .$

Beweis

Die Addition erfüllt nach Fakt  (1, 2) diese Eigenschaften.

Es seien zwei Verknüpfungen ${}+$ und ${}*$ auf ${}\mathbb {N}$ gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit

${}x+y=x*y\,$

für alle ${}x,y\in \mathbb {N}$ beweisen. Dies machen wir durch Induktion über ${}y$ (für beliebige ${}x$). Bei

${}y=0\,$

ist wegen

${}x+0=x=x*0\,$

die Aussage richtig. Es sei die Aussage nun für ein bestimmtes ${}y$ schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung

${}x+y^{\prime }=(x+y)^{\prime }=(x*y)^{\prime }=x*y^{\prime }\,.$

$\Box$

Lemma

Es seien ${}x,y$ natürliche Zahlen. Dann ist

${}x+y=0\,$

nur bei ${}x=0$ und ${}y=0$ möglich.

Beweis

Wenn ${}y\neq 0$ wäre, so wäre ${}x+y$ ein Nachfolger einer natürlichen Zahl (nämlich der ${}y$-te Nachfolger von ${}x$), was für die ${}0$ ausgeschlossen ist. Also ist ${}y=0$. Wegen

${}0=x+y=x+0=x\,$

ist auch der erste Summand gleich ${}0$.

$\Box$

Lemma

Für die Addition der natürlichen Zahlen (mit der in Definition festgelegten Addition) gelten die folgenden Aussagen.

1. ${}n+0=n=0+n\,$

   für alle ${}n$, d.h. ${}0$ ist das neutrale Element der Addition.

2. ${}n+k'=(n+k)'=n'+k\,$

   für alle ${}n,k\in \mathbb {N}$ (Umlegungsregel).

3. Die Addition ist kommutativ.
4. Die Addition ist assoziativ.
5. Aus einer Gleichung ${}n+k=m+k$ folgt

   ${}n=m\,$

   (Abziehregel).

Beweis

1. Die Gleichungen links und rechts sind unmittelbar klar, da der ${}n$-te Nachfolger der ${}0$ gleich ${}n$ ist.
2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl ${}n$ aus und nimmt einmal öfters als ${}k$-mal den Nachfolger. In der Mitte bestimmt man ${}k$-fach den Nachfolger von ${}n$ und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von ${}n$ den Nachfolger und davon dann ${}k$-fach den Nachfolger.
3. Es ist

   ${}n+k=k+n\,$

   für alle ${}k,n$ zu zeigen. Diese Gleichungen zeigen wir durch Induktion über ${}k$ für alle ${}n$. Bei ${}k=0$ steht beidseitig ${}n$ nach Teil (1). Es sei die Gleichheit nun für ein ${}k$ (und alle ${}n$) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)

   ${}n+k^{\prime }=(n+k)^{\prime }=(k+n)^{\prime }=k^{\prime }+n\,,$

   die Gleichung gilt also auch für ${}k^{\prime }$.

4. Wir beweisen die Assoziativität, also die Gleichheit

   ${}(m+n)+k=m+(n+k)\,,$

   durch Induktion über ${}k$ (für alle ${}m,n$ gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt

   ${}(m+n)+k^{\prime }=(m+n)^{\prime }+k=(m+n^{\prime })+k=m+(n^{\prime }+k)=m+(n+k^{\prime })\,.$

5. Die Abziehregel beweisen wir ebenfalls durch Induktion über ${}k$. Der Fall

   ${}k=0\,$

   ist klar. Es sei also die Aussage für ein ${}k$ schon bewiesen und sei eine Gleichung der Form

   ${}m+k^{\prime }=n+k^{\prime }\,$

   gegeben. Dann ist nach der Umlegungsregel auch

   ${}m^{\prime }+k=n^{\prime }+k\,.$

   Nach der Induktionsvoraussetzung ist somit

   ${}m^{\prime }=n^{\prime }\,.$

   Da die Nachfolgerabbildung injektiv ist, ergibt sich

   ${}m=n\,.$

$\Box$

Lemma

Für die Multiplikation der natürlichen Zahlen (mit der in der Definition festgelegten Multiplikation)

gelten folgende Aussagen.

1. Es gilt

   ${}0\cdot n=0=n\cdot 0\,$

   für alle ${}n$.

2. Es gilt

   ${}1\cdot n=n=n\cdot 1\,$

   für alle ${}n$, d.h. ${}1=0^{\prime }$ ist das neutrale Element für die Multiplikation.

3. Es ist

   ${}k'\cdot n=k\cdot n+n\,$

   und

   ${}n\cdot k'=n\cdot k+n\,$

   für alle ${}n,k\in \mathbb {N}$.

4. Die Multiplikation ist kommutativ.
5. Für beliebige ${}k,m,n\in \mathbb {N}$ gilt

   ${}k\cdot (m+n)=k\cdot m+k\cdot n\,$

   (Distributivgesetz).

6. Die Multiplikation ist assoziativ.

Beweis

1. Die zweite Gleichung ist klar, da unabhängig davon, wie oft die ${}0$ mit sich selbst addiert wird, stets ${}0$ herauskommt. Die erste Gleichung kann man als eine Konvention oder auch als Teil der Definition ansehen: Eine Summe, in der überhaupt keine Zahl vorkommt (die leere Summe), ist als ${}0$ zu interpretieren.
2. Die erste Gleichung ist klar, der Ausdruck ${}1\cdot n$ besagt einfach, dass die Zahl ${}n$ einmal dasteht. Die zweite Gleichung bedeutet, dass die ${}n$-fache Addition der ${}1$ mit sich selbst gleich ${}n$ ist. Dies zeigen wir durch Induktion nach ${}n$, wobei der Induktionsanfang (für ${}n=0,1$) klar ist. Es sei die Aussage also schon für ${}n$ bewiesen. Der Unterschied zwischen ${}n\cdot 1$ und ${}n^{\prime }\cdot 1$ besteht darin, dass im zweiten Fall einmal mehr ${}+1$ dasteht. Somit ist

   ${}n^{\prime }\cdot 1=n\cdot 1+1=n+1=n^{\prime }\,.$

3. Die linke Gleichung ergibt sich unmittelbar aus der Definition. Die rechte Gleichung ergibt sich aus

   ${}{\begin{aligned}n\cdot k^{\prime }&=\underbrace {k^{\prime }+\cdots +k^{\prime }} _{n{\text{-mal}}}\\&=\underbrace {(k+1)+\cdots +(k+1)} _{n{\text{-mal}}}\\&=\underbrace {k+\cdots +k} _{n{\text{-mal}}}+\underbrace {1+\cdots +1} _{n{\text{-mal}}}\\&=n\cdot k+n.\end{aligned}}$

4. Die Kommutativität beweisen wir durch Induktion nach ${}k$, und zwar beweisen wir die Behauptung

   ${}n\cdot k=k\cdot n\,$

   für alle ${}n$. Der Fall ${}k=0$ ist klar, da dann beidseitig ${}0$ steht. Es sei die Gesamtaussage also für ein bestimmtes ${}k$ und beliebiges ${}n$ bereits bewiesen. Dann ist unter Verwendung von (3) und der Induktionsvoraussetzung

   ${}n\cdot k^{\prime }=n\cdot k+n=k\cdot n+n=k^{\prime }\cdot n\,.$

5. Das Distributivgesetz

   ${}k\cdot (m+n)=k\cdot m+k\cdot n\,$

   beweisen wir durch Induktion nach ${}k$ für beliebige ${}m,n$. Der Fall ${}k=0$ ist klar, da beidseitig ${}0$ rauskommt. Unter Verwendung der Induktionsvoraussetzung und Teil (3) ergibt sich

   ${}{\begin{aligned}k^{\prime }\cdot (m+n)&=k\cdot (m+n)+m+n\\&=k\cdot m+k\cdot n+m+n\\&=k\cdot m+m+k\cdot n+n\\&=k^{\prime }\cdot m+k^{\prime }\cdot n.\end{aligned}}$

6. Das Assoziativitätsgesetz beweisen wir durch Induktion nach dem ersten Faktor (wobei der Induktionsanfang wieder klar ist) unter Verwendung des Distributivgesetzes und Teil (3).

   ${}{\begin{aligned}k^{\prime }\cdot (m\cdot n)&=k\cdot (m\cdot n)+m\cdot n\\&=(k\cdot m)\cdot n+m\cdot n\\&=(k\cdot m+m)\cdot n\\&=(k^{\prime }\cdot m)\cdot n.\end{aligned}}$

$\Box$

Lemma

Für das Potenzieren gelten die folgenden Eigenschaften, wobei ${}a,b\in \mathbb {N} _{+}$ und ${}m,n\in \mathbb {N}$ seien.

1. ${}a^{m+n}=a^{m}\cdot a^{n}\,.$

2. ${}(a^{m})^{n}=a^{mn}\,.$

3. ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,.$

Beweis

Siehe Aufgabe.

$\Box$