3 Die natürlichen Zahlen

Von Kronecker stammt folgendes Zitat

Die natürlichen Zahlen sind vom lieben Gott geschaffen, alles andere in der Mathematik ist nur Menschenwerk.

und von Dedekind 1897

Die natürlichen Zahlen sind freie Schöpfungen des menschlichen Geistes.

3.1 Konstruktion von $\mathbb{N}$.
Die Elemente $0,1,2,3,\dots\in\mathbb{R}$ heißen natürlichen Zahlen. Wie können wir dabei die Punkte ``...'' präzise machen? Diese sollen offensichtlich bedeuten, daß mit jeder natürlichen Zahl $n$ auch (der Nachfolger) $n+1$ eine natürliche Zahl sein soll. Die Abbildung $n\mapsto n+1$ sollte also nicht aus der Menge $\mathbb{N}$ der natürlichen Zahlen herausführen. Dadurch ist aber $\mathbb{N}$ noch nicht eindeutig beschrieben, denn z.B. auch die Teilmengen $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$ haben diese Eigenschaft. Die Menge $\mathbb{N}$ sollte wohl eine möglichst kleine Teilmenge mit dieser Eigenschaft sein. Allerdings sind auch $\emptyset$, $\{1,2,3,\dots\}$, $\{2,3,4,\dots\}$ solche Mengen. Wenn wir aber zusätzlich $0\in\mathbb{N}$ verlangen, dann paßt alles. Es ist also $\mathbb{N}$ die kleinste Teilmenge von $\mathbb{R}$, die 0 enthält und unter dem Zählen $n\mapsto n+1$ abgeschlossen ist, d.h.

$$\mathbb{N}=\bigcap\bigl\{N\subseteq \mathbb{R}:0\in N,(n\in N\Rightarrow n+1\in N)\bigr\}.$$

Da wir uns von der Existenz von $\mathbb{R}$ und der Addition aber noch nicht überzeugt haben und gerade $\mathbb{N}$ als ersten Schritt zur Konstruktion von $\mathbb{R}$ verwenden wollen, können wir $\mathbb{N}$ so nicht definieren.

Die einzelnen natürlichen Zahlen sollten wie alle mathematischen Objekte selbst Mengen sein, und zwar $n$ gerade eine Mengen mit $n$ Elementen. Wir können die einzelnen natürlichen Zahlen $0,1,2,3,\dots$ also rekursiv durch

$$:=\emptyset,$$ 0

$$1 :=\{0\},$$

$$2 :=\{0,1\}=1\cup\{1\}=\{\emptyset,\{\emptyset\}\},$$

$$3 :=\{0,1,2\}=2\cup\{2\}=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\},$$

$$\;\vdots$$

$$n+1 :=n^+:=\{0,1,2,3,\dots,n\}=n\cup\{n\},$$

$$\;\vdots$$

definieren. Die Menge $\mathbb{N}:=\{0,1,2,3,\dots\}$ aller natürlichen Zahlen soll dann die kleinste Menge $N$ sein, die 0 enthält und unter der Nachfolger-Abbildung $x\mapsto x^+:=x\cup\{x\}$ abgeschlossen ist, d.h. mit $x\in N$ ist auch $x^+$ in $N$. Vergleiche diese Operation mit $x++$ bzw. $++x$ in der Informatik, wo der Befehl $x++$ bedeutet, daß $x$ durch $x+1$ zu ersetzen ist. Mathematische Notation ist da eher statisch, denn Variablen sollten in einer Rechnung nicht ihren Wert ändern, d.h. $x=x+1$ ist in der Mathematik schlichtweg falsch, in der Informatik (C, Java, etc. ) hingegen bedeutet es, daß der Speicherinhalt von $x$ um eins erhöht wird. Wenn wir nun eine Menge $N$ mit obigen beiden Eigenschaften induktiv nennen, so ist die Menge der natürlichen Zahlen:

$$\mathbb{N}:=\bigcap\bigl\{N:N$$ ist induktiv$$\bigr\}.$$

Damit dies als Menge wirklich existiert, muß man die Existenz einer induktiven Menge oder von $\mathbb{N}$ als Menge voraussetzen. Dies ist das Unendlichkeitsaxiom der Mengenlehre.

3.2 Induktionsprinzip.
Es sei $N\subseteq \mathbb{N}$ eine induktive Teilmenge. Dann ist $\mathbb{N}=N$.

Beweis. Die ist offensichtlich, da $\mathbb{N}$ nach Konstruktion die kleinste induktive Teilmenge ist.     []

Dies ist die wichtigste Beweismethode für Aussagen über natürliche Zahlen, die sogenannte vollständige Induktion: Um also zu zeigen, daß eine Aussage $\mathcal{N}$ auf alle natürlichen Zahlen zutrifft, zeigt man zuerst, daß sie für 0 erfüllt ist (dies nennt man den Induktionsanfang) und dann, daß für jede natürliche Zahl gilt, wenn sie für diese erfüllt ist (die Induktionsannahme) so auch für deren Nachfolger (dies nennt man denn Induktionsschritt). Das Induktionsprinzip besagt dann, daß die induktive Menge $N:=\{n\in\mathbb{N}:\mathcal{N}$ trifft für $n$ zu$\}$ mit $\mathbb{N}$ übereinstimmt, die Aussage $\mathcal{N}$ also auf alle natürlichen Zahlen zutrifft.

Zur Erläuterung einige

3.3 Beispiele.

1. Für alle $n\in\mathbb{N}$ ist $0+1+\dots+n=\frac{n(n+1)}2$.
   Beweis. Beweis mittels Induktion nach $n$:
   Der Induktionsanfang $n=0$ ist offensichtlich erfüllt, denn $0+\dots+0=0=\frac{0(0+1)}2$.
   Den Induktionsschritt von $n$ auf $n+1$ zeigen wir nun wie folgt. Nach Induktionsannahme ist die Aussage für $n$ richtig, also $0+1+\dots+n=\frac{n(n+1)}2$. Nun zeigen wir die Aussage für $n+1$ an Stelle von $n$:

   $$0+1+\dots+n+(n+1) = (0+1+\dots+n)+(n+1)$$

   $$=\frac{n(n+1)}2+(n+1) =\frac{(n+1)(n+2)}2$$

   $$=\frac{(n+1)((n+1)+1)}2.$$

   
   
       []

2. Für alle $n\geq 4$ ist $2^n\geq n^2$.
   Beweis. Wieder verwenden wir Induktion nach $n$. Zwar ist $2^0=1>0=0^2$ und $2^1=2\geq 1=1^2$ aber $2^3=8<9=3^2$. Also verwenden wir als Induktionsanfang $(n=4)$ und erhalten $2^4=16=4^2$.
   Nun den Induktionsschritt von $n$ auf $n+1$. Unter Verwendung der Induktionsvoraussetzung $2^n\geq n^2$ erhalten wir

   $$2^{n+1} =2\cdot 2^n\geq 2\,n^2\geq (n+1)^2=n^2+2\,n+1,$$

   $$n^2-2\,n+1 =(n-1)^2\geq 2^2>1+1=2,$$

   
   
   sofern $n-1\geq 2$, also $n\geq 3$ ist.     []

3. Rekursive Definition der Entlohnung für Schacherfindung als Beispiel: Bekanntlich hatte der Erfinder des Schachspiels vom König folgende Entlohnung gefordert. Man möge auf das erste Feld des Schachbretts 1 Korn Getreide lege, auf das zweite das doppelte also 2 Körner, auf das dritte das doppelte des zweiten, also vier Körner und so weiter bis zum letzten den $8*8=64$-ten. Die Anzahl $a_n$ der Körner auf Feld $n$ ist also rekursiv durch $a_1:=1$ und $a_{n+1}=2\,a_n$ gegeben. Explizit prüft man mittels Induktion leicht nach, daß $a_n=2^{n-1}$ ist und $S_n:=a_1+a_2+\dots+a_n=1+2+\dots+2^{n-1}=2^n-1$ ist. Das sind also insgesamt $S_{64}=2^{64}-1=18446744073709551615\sim 0.18*10^{20}$ viele Körner. Wenn wir ein Korn mit $50$mm$^3=5*10^{-8}\,$m$^3\sim 3*10^{-5}\,$kg abschätzen, dann wiegt $S_{64}$ circa $0.18*10^{20}*3*10^{-5}\sim 5*10^{14}\,$kg also $500$ Milliarden Tonnen - eine nicht zu erfüllende Forderung.
4. Zinseszinsrechnung als Beispiel: Ein Betrag $b$ werde mit jährlichen Zinsen von $p$ Prozent verzinst, d.h. nach einem Jahr sind die Zinsen $b\cdot \frac{p}{100}$ und der Endbetrag somit $b_1:=b+b\frac{p}{100}$. Nach 2 Jahren fallen nicht nur ein weiteres Mal die Zinsen $b\cdot \frac{p}{100}$ von $b$ sondern auch die Zinsen $b\cdot \frac{p}{100}\cdot \frac{p}{100}$ der Zinsen $b\cdot \frac{p}{100}$ des ersten Jahres an, d.h. der Endbetrag ist nun
   $$b_2 := b + b\frac{p}{100} + b\cdot \frac{p}{100} + b\cdot \frac{p}{100}\cdot \frac{p}{100} = b(1+\frac{p}{100})^2,$$
   und nach $n$ Jahren folgt mittels Rekursion, daß der Endbetrag
   $$b_n= b\left(1+\frac{p}{100}\right)^n$$
   ist.

3.5 Definition.
Man nennt Abbildungen $a:\mathbb{N}\to X$ auch Folgen in $X$ und schreibt gerne $a_n$ anstelle von $a(n)$, wie wir in Beispiel (3.3) bereits getan haben.

Man kann Induktion auch dazu verwenden die Sinnhaftigkeit rekursive Definitionen zu zeigen, d.h. anstelle explizit anzugeben wie gewisse Objekte $a_n$ für $n\in\mathbb{N}$ definiert sind, beschreibt man einerseits $a_0$ und andererseits wie man $a_{n+1}$ aus $a_n$ für jedes $n\in\mathbb{N}$ berechnen kann, d.h. man gibt eine Rekursionsvorschrift $R$ an, s.d. $a_{n+1}=R(a_n)$ ist.

3.4 Proposition. Rekursion.
Es sei $X$ eine Menge, $a_0\in X$ und $R:X\to X$ eine Abbildung. Dann existiert eine eindeutige Abbildung $a:\mathbb{N}\to X$ mit $a(0)=a_0$ und $a(n+1)=R(a(n))$ für alle $n\in\mathbb{N}$. Man sagt $a$ ist durch die Rekursion $R$ definiert.

Beweis. Abbildungen $a:\mathbb{N}\to X$ sind ja Teilmengen $a\subseteq \mathbb{N}\times X$. Folglich betrachten wir die kleinste Teilmenge $a\subseteq \mathbb{N}\times X$, die $(0,a_0)$ enthält und mit $(n,x)$ auch $(n+1,R(x))$ enthält, d.h.

$$a=\bigcap\Bigl\{A\subseteq \mathbb{N}\times X:(0,a_0)\in A,\Bigl((n,x)\in A \Rightarrow (n+1,R(x))\in A\Bigr)\Bigr\}.$$

Da $A=\mathbb{N}\times X$ eine Teilmenge $A$ mit obigen Eigenschaften ist, existiert $a$, und wir müssen nur noch zeigen, daß $a$ eine Funktion $\mathbb{N}\to X$ beschreibt. Sei dazu $N:=\{n\in\mathbb{N}:\exists x\in X:(n,x)\in A\}$. Offensichtlich ist $N$ eine induktive Teilmenge von $\mathbb{N}$ und wegen dem Induktionsprinzip (3.2) somit $N=\mathbb{N}$.

Bleibt zu zeigen, daß auch die Menge $M:=\{n\in\mathbb{N}:$ es gibt höchstens ein $x\in X$ mit $(n,x)\in a\}$ mit $\mathbb{N}$ übereinstimmt. Offensichtlich ist $0\in M$, denn gäbe es ein $x\ne a_0$ mit $(0,a_0)\in a$, so könnten wir $(0,x)$ ungestraft aus $a$ entfernen und würden eine kleinere Menge $A$ mit obiger Eigenschaft erhalten. Sei nun $n\in M$, also existiert ein eindeutiges $x\in X$ mit $(n,x)\in a$ und damit auch $(n+1,R(x))\in a$. Wäre $n+1\notin M$, dann gäbe es ein $x'\in X$ mit $R(x)\ne x'$ und $(n+1,x')\in a$. Die Menge $A:=a\setminus\{(n+1,x')\}$ hätte dann obige Eigenschaft, also $a\subseteq A$ und somit wäre $(n+1,x')\notin a$.     []

3.6 Die Grundrechnungsarten für natürliche Zahlen.
Die Addition $m\mapsto n+m$ natürlicher Zahlen definiert man rekursiv durch

$$n+0 :=n,$$

$$n+m^+ :=(n+m)^+$$

D.h. für fixes $n\in\mathbb{N}$ ist die Rekursionsvorschrift $R:\mathbb{N}\to\mathbb{N}$ durch $R(x):=x^+=x+1$ gegeben. Beachte, daß dies nur die mathematische Formulierung der Methode ist VolksschülerInnen, die bereits zählen können, die Addition zu erklären: $x+2=(x+1)+1$, $x+3=(x+2)+1=((x+1)+1)+1$, ....

Ebenso verfährt man mit der Multiplikation $m\mapsto n\cdot m$:

$$n\cdot 0 :=0,$$

$$n\cdot m^+ :=n\cdot m + n,$$

und hat nun für fixes $n\in\mathbb{N}$ als Rekursionsvorschrift $R:\mathbb{N}\to\mathbb{N}$, $R(x):=x+n$. Beachte, daß auch dies nur die mathematische Formulierung der Methode ist VolksschülerInnen, die bereits addieren können, die Multiplikation zu erklären: $x\cdot 1=x$, $x\cdot 2=x\cdot 1+x=x+x$, $x\cdot 3=x \cdot 2+x=(x+x)+x$, ....

Es ist 0 nach Definition ein links-neutrales Element bzgl. Addition, d.h. $n+0=n$ für alle $n\in\mathbb{N}$.

Wir zeigen nun mittels Induktion, daß auch $0+n=n$ gilt:
Induktionsanfang: $0+0=0$ nach Definition.
Induktionsschritt: $0+n=n$ $\Rightarrow$ $0+n^+=(0+n)^+=n^+$.
Nach Induktion gilt somit $\{n\in\mathbb{N}:0+n=n\}=\mathbb{N}$, d.h. $\forall n\in\mathbb{N}$: $0+n=n$.

Weiters zeigen wir mittels Induktion, daß ebenso $n^++m=(n+m)^+$ für alle $n,m\in\mathbb{N}$ gilt.
Dazu betrachten wir die Menge $N:=\{m\in\mathbb{N}:\forall n\in\mathbb{N}:n^++m=(n+m)^+\}$.
Induktionsanfang: $0\in N$, denn $n^++0=n^+=(n+0)^+$.
Induktionsschritt: $m\in\mathbb{N}$ $\Rightarrow$ $m^+\in\mathbb{N}$, denn für alle $n\in\mathbb{N}$ gilt: $n^++m^+=(n^++m)^+=((n+m)^+)^+=(m+m^+)^+$.
Nach Induktion gilt somit $N=\mathbb{N}$.

Diese beiden Resultate sind Spezialfälle des kommutativ-Gesetzes der Addition, welches wir mit deren Hilfe und Induktion nun zeigen: Sei dazu $N:=\{n\in\mathbb{N}:\forall m\in\mathbb{N}:n+m=m+n\}$.
Induktionsanfang: $0\in N$, da nach obigen $0+n=n$ und nach Definition $n+0=n$ ist.
Induktionsschritt: $n\in N$ $\Rightarrow$ $n^+\in N$, da $n^++m= (n+m)^+=n+m^+$ für jedes $m\in\mathbb{N}$ gilt.
Nach Induktion ist somit $N=\mathbb{N}$, d.h. $\forall n,m\in\mathbb{N}$: $n+m=m+n$.

Auf ähnliche Weise zeigt man auch das assoziativ-Gesetz für die Addition, daß 1 ein neutrales Element für die Multiplikation ist, das kommutativ-Gesetz und das assoziativ-Gesetz für die Multiplikation, sowie schließlich das distributiv-Gesetz $n\cdot (m+k)=n\cdot m+n\cdot k$.

3.7 Die Ordnung der natürlichen Zahlen.
Man kann die Ordnung $\leq$ auf $\mathbb{N}$ durch $n\leq m$ $:\Leftrightarrow$ $n\subseteq m$ für $n,m\in\mathbb{N}$ definieren. Es ist $n<m$, d.h. $n\leq m$ und $n\ne m$, genau dann, wenn $n\in m$ gilt. Offensichtlich ist dies eine partielle Ordnung auf $\mathbb{N}$, denn für $\subseteq$ gilt das.

Es läßt sich zeigen, daß dies sogar eine lineare Ordnung ist und $n\leq m$ genau dann gilt, wenn $\exists k\in\mathbb{N}:m=n+k$.

Für $n\in\mathbb{N}$ gilt $\bigcup n\subseteq n$ (d.h. $\in$ ist auf $n$ transitiv), denn $\bigcup 0 =\bigcup\emptyset=\emptyset$ und aus $\bigcup n\subseteq n$ folgt $\bigcup n^+=\bigcup (n\cup\{n\})=(\bigcup n)\cup n=n\subseteq n^+$.

Weiters gilt die Kürzungsregel: Aus $n+k=m+k$ folgt $n=m$.
Für $k=0$ ist dies trivial. Für $k=1$ folgt es aus $\bigcup n^+=n$, und allgemein mittels Induktion $(n+k)+1=n+(k+1)=m+(k+1)=(m+k)+1$, also $n+k=m+k$ und damit $n=m$.
Beachte, daß wir beim Beweis nicht $-k\notin\mathbb{N}$ verwenden können.

3.33 Folgerung. Ganzzahlige Division mit Rest.
Es sei $1\leq m\in\mathbb{N}$. Dann läßt sich jede natürliche Zahl $n$ eindeutig als $n=q\,m+r$ mit $q,r\in\mathbb{N}$ und $r<m$ schreiben.

Beweis. Existenzbeweis mittels Induktion nach $n$:
Für $n=0$ erhalten wir die Darstellung $0=0\,m+0$. Nun der Induktionsschritt von $n$ auf $n+1$. Nach Induktionsannahme ist $n=q\,m+r$ mit $r<m$. Damit ist $n+1=q\,m+r+1$. Falls $r+1\geq m$, also $m-1\leq r<m$ ist und somit die natürliche Zahl $r=m-1$ ist, so ist $n+1=q\,m+m=(q+1)\,m+0$. In jeden Fall erhalten wir also eine Darstellung $n=q'\,m+r'$ mit $r'<m$.

Die Eindeutigkeit sieht man nun wie folgt: Angenommen $q\,m+r=q'\,m+r'$ mit $r,r'<m$ und ohne Beschränkung der Allgemeinheit (kurz: o.B.d.A.) $q\geq q'$. Wäre $q>q'$, also $q\geq q'+1$ so wäre $n=q\,m+r\geq (q'+1)\,m+r=q'\,m+(m+r)> q'\,m+r'=n$, ein Widerspruch. Also ist $q=q'$ und wegen $(q-q')m=r'-r$ auch $r=r'$.     []

3.9 Folgerung. Wohlordnung von $\mathbb{N}$.
$\mathbb{N}$ ist wohlgeordnet, d.h. jede nicht-leere Teilmenge $N\subseteq \mathbb{N}$ besitzt ein kleinstes Element $\min(N)$, das sogenannte Minimum von $N$.

Beachte, daß dies für unendliche Teilmengen $N$ nicht trivial ist, z.B. besitzt die unendliche Teilmenge $N:=\{\frac11,\frac12,\frac13,\dots\}\subseteq \mathbb{R}$ kein kleinstes Element.

Beweis. Indirekt, angenommen $N\subseteq \mathbb{N}$ sei nicht-leer und ohne kleinstes Element. Sei $S$ die Menge der unteren Schranken aus $\mathbb{N}$ von $N$ (d.h. jener natürlichen Zahlen, die $\leq$ allen Elementen aus $N$ sind). Wir zeigen mittels Induktion, daß $S=\mathbb{N}$ ist:
Offensichtlich ist $0\in S$. Sei nun $a\in S$, also eine untere Schranke von $N$. Dann ist auch $a+1$ eine untere Schranke, den andernfalls gäbe es ein $n\in N$ mit $a+1>n$ und somit wäre $n\leq a\leq n'$ für alle $n'\in\mathbb{N}$, also $n$ ein minimales Element von $N$, ein Widerspruch zur Annahme.

Da aber $S\cap N=\emptyset$ (ein Element des Durchschnitts wäre ein Minimum von $N$) und $S=\mathbb{N}\supseteq N$ gilt, ist $N=\emptyset$, ebenfalls ein Widerspruch zur Annahme.     []

3.8 Folgerung. Ordnungsinduktion.
Es sei $N\subseteq \mathbb{N}$ und für alle $n\in\mathbb{N}$ mit $\{k\in\mathbb{N}:k< n\}\subseteq N$ gelte $n\in N$. Dann ist $N=\mathbb{N}$.

Dies ist ein stärkeres Beweismittels als die vollständige Induktion, denn nun dürfen wir beim Induktionsschritt auf $n+1$ die Induktionsannahme nicht nur für den unmittelbaren Vorgänger $n$ verwenden, sondern für alle $k\leq n$.

Beweis. Indirekt: Angenommen es ist $N\ne\mathbb{N}$. Nach (3.9) existiert das Minimum der Menge $N^c=\mathbb{N}\setminus N$. Sei $n\in N^c\subseteq \mathbb{N}$ dieses Minimum. Für alle $k\in\mathbb{N}$ mit $k<n$ ist also $k\notin N^c$, d.h. $k\in N$. Nach Voraussetzung an $N$ ist damit auch $n\in N$, ein Widerspruch zu $n\in N^c$.     []

3.10 Folgerung. Primfaktorenzerlegung.
Jede natürliche Zahl $n>1$ läßt sich in ein Produkt von Primzahlen zerlegen.

Beweis. Wir machen eine Ordnungsinduktion nach $n$. Entweder $n$ ist selbst eine Primzahl (und wir sind fertig) oder $n$ besitzt einen echten Teiler $m$, d.h. $1<m\in\mathbb{N}$ und $1<k:=\frac{n}{m}\in\mathbb{N}$. Da somit sowohl $m<n$ als auch $k<n$ ist, besitzen diese beiden Faktoren nach Induktionsvoraussetzung Zerlegungen in Primzahlen $m=p_1\cdot\dots\cdot p_i$ und $k=q_1\cdot\dots\cdot q_j$ und somit auch $n=m\cdot k=p_1\cdot\dots\cdot p_i\cdot q_1\cdot\dots\cdot q_j$.     []

3.11 Rekursive Definition der Potenzen..
Es ist $a^n$ für $n\in\mathbb{N}$ wie folgt rekursiv definiert. $a^1:=a$, $a^{n+1}:=a^n\cdot a$. Die Idee dabei ist natürlich, daß $a^n=a\cdot\ldots\cdot a$ ist. Mittels Induktion zeigt man dann $a^n\cdot a^m=a^{n+m}$ für $n,m\geq 1$. Setzt man $n=0$ so ergäbe sich $a^0\cdot a^m=a^m$, also $a^0=1$. Darum definiert man $a^0:=1$ für alle $a$.

3.12 Proposition. Rechnen mit Potenzen.
Es gelten folgende Rechenregeln (für Elemente $a,b$ einer Halbgruppe und natürlicher Zahlen $n,m$, wobei in den Formeln mit Bruchstrich die Invertierbarkeit von $b$ vorausgesetzt ist):

$$a^n\cdot a^m = a^{n+m},\quad \frac{a^n}{a^m}=a^{n-m},\quad (a^n)^m = a^{n\cdot m},$$

$$a^n\cdot b^n = (a\cdot b)^n,\quad \frac{a^n}{b^n} = \left(\frac{a}b\right)^n$$

Beweis. Beweis durch Induktion nach $m$:
( $m=1$) $a^{n+1}=a^n\cdot a=a^{n}\cdot a^{1}$.
( $m+1$) $a^{n+(m+1)}=a^{(n+m)+1}=a^{n+m}\cdot a=(a^n\cdot a^m)\cdot a=a^n\cdot (a^m\cdot a)=a^n\cdot a^{m+1}$.

Die zweite Gleichung folgt aus $a^n=a^m\cdot a^{n-m}$ durch Division mit $a^{n-m}$.

Die dritte Gleichung folgt wieder mit vollständiger Induktion, denn

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

Die vierte Gleichung folgt ebenfalls mittels vollständiger Induktion, denn

$$a^{n+1}\cdot b^{n+1} =(a^n\cdot a)\cdot (b^n\c... ...t b^n)\cdot (a\cdot b) =(a\cdot b)^n\cdot (a\cdot b) =(a\cdot b)^{n+1}.$$

Daraus folgt die fünfte durch Division.     []

3.13 Beispiel. Quadrieren als Rekursionsvorschrift.
Es sei $a_0:=c$ und $a_{n+1}:=(a_n)^2$, also

$$a_0=c,\;a_1=c^2,\,a_2=(c^2)^2=c^4,\,a_3=(c^4)^2=c^8,\dots$$

Wir vermuten $a_n=c^{2^n}:=c^{(2^n)}$ und können dies auch leicht mittels vollständiger Induktion zeigen. Insbesonders für $c=2$ erhalten wir

$$a_0=2, a_1=4, a_2=16, a_2=256, a_3=65536, a_4=4294967296,\dots$$

allesamt wichtige Zahlen in der Informatik, siehe (3.25).

3.14 Rekursive Definition von endlichen Summen und Produkten.
Man definiert die Summe $\sum_{i=1}^n x_i$ rekursiv durch

$$\sum_{i=1}^0 x_i :=0 \sum_{i=1}^1 x_i:= x_1$$

$$\sum_{i=1}^{n+1} x_i := \Bigl(\sum_{i=1}^n x_i\Bigr)+x_{n+1}$$

Die Idee dabei ist natürlich eine unzweideutige Formulierung für die Punkte in

$$\sum_{i=1}^n x_i=x_1+x_2+\dots+x_{n-1}+x_n$$

zu geben. Vergleiche diese Schreibweise mit $\bigcup_{i=1}^n A_i$ und $\bigcap_{i=1}^n A_i$.
Für $a_k+a_{k+1}+\dots+a_{k+n-1}+a_{k+n}$ schreibt man entsprechend $\sum_{i=k}^{k+n} a_i$ und definiert diese auf gleiche Weise rekursiv.

Ebenso definiert man das Produkt $\prod_{i=1}^n x_i$ als präzise Formulierung für $x_1\cdot\ldots\cdot x_n$ rekursiv durch

$$\prod_{i=1}^0 x_i :=1 \prod_{i=1}^1 x_i:=x_1$$

$$\prod_{i=1}^{n+1} x_i := \Bigl(\prod_{i=1}^n x_i\Bigr)\cdot x_{n+1}$$

Z.B. ist $a^n:=\prod_{i=1}^n a$ und $n!:=\prod_{i=1}^n i$.

3.15 Lemma. Rechenregeln für Summation.
Für $n,m\in\mathbb{N}$ und beliebige $c,a_1,b_1,a_2,b_2,\dots$ gilt:

$$\sum_{i=1}^n a_i\pm\sum_{i=1}^n b_i = \sum_{i=1}^n (a_i\pm b_i) \qquad \qquad c\sum_{i=1}^n a_i = \sum_{i=1}^n c\,a_i$$

$$\sum_{i=1}^n a_i + \sum_{i=n+1}^{n+m} a_i = \sum_{i=1}^{n+m} a_i \qquad \qquad \sum_{i=1}^n a_i = \sum_{i=1+m}^{n+m} a_{i-m}$$

Man veranschauliche sich diese Formeln durch Übersetzung in `` $\dots$''-Schreibweise.

Beweis. Zeigt man leicht mittels vollständiger Induktion.     []

3.16 Zifferndarstellung.
Wir können nun zwar mit beliebigen natürlichen Zahlen herumrechnen, haben aber kurze Namen $0,1,2,3,\dots$ nur für die ersten paar Zahlen zur Verfügung.

Um nicht in römischer Manier laufend neue Symbole wie $I,V,X,L,C,\dots$ für größere Zahlen einführen zu müssen wurde die Ziffernschreibweise erfunden. Man führt dabei nur für die ersten paar (sagen wir zehn) Zahlen Symbole (die Ziffern) ein (üblicherweise $0,1,2,3,4,5,6,7,8,9$) und interpretiert ein Folge $a_0,a_1,\dots,a_{n-1},a_n$ solcher Ziffern als als die natürliche Zahl $a_0+a_1\,b+a_2\,b^2+\dots+a_{n-1}\,b^{n-1}+a_n\,b^n$, wobei $b$ die Anzahl der zur Verfügung stehenden Ziffern (üblicherweise also zehn) ist, und schreibt diese Ziffern als Wort mit den Stellen in umgekehrter Reihenfolge, z.B. $123=1\cdot b^2+2\cdot b+3$. Das sich wirklich jede natürliche Zahl so darstellen läßt besagt folgendes

Lemma.
Es sei $2\le b\in\mathbb{N}$. Dann existiert für jede natürliche Zahl $z$ eine eindeutige Darstellung (die Zifferndarstellung von $z$ zur Basis $b$)

$$z=\sum_{k=0}^n z_k\,b^k$$ mit $$z_k\in\{0,1,\dots,b-1\}.$$

Bislang war (von den Babyloniern abgesehen) vor allem die Basis $b=10$ üblich (man spricht dann von der Dezimaldarstellung). In der Informatik spielen aber vor allem die Basen $2$ (Binärdarstellung), $8$ (Oktaldarstellung) und $16$ (Hexadezimaldarstellung) eine wichtige Rolle. Bei der Hexadezimaldarstellung wird üblicherweise $A,B,C,D,E$ und $F$ für die Ziffern mit Dezimalzahldarstellung $10,11,12,13,14,15$ geschrieben.

Beweis. Die Ziffern $z_0,\dots,z_k$ einer Zahl $z$ erhält man als Reste bei wiederholter Division mit Rest beginnend bei $z$ durch die Basis $b$, d.h. $z=z'\cdot b+z_0$, $z'=z''\cdot b+x_1$, ..., $z^{(k)}=z^{(k)}\cdot b+x_k$, bis $z^{(k)}=0$ ist.     []

Ein andere (vielleicht einsichtigere) Möglichkeit die Ziffern einer Zahl $x$ zu bestimmen ist sich zuerst einen Vorrat an Potenzen $b^1,b^2,b^3,\dots$ aufzuschreiben. Die kleinste solche Potenz $b^{n+1}>x$ zu suchen und dann $x$ durch $b^n$ ganzzahlig zu dividieren, d.h. $x=x_n\,b^n+x'$ nach $x_n,x'$ mit $x'<b$ zu lösen. Dann ist $x_n$ die höchste Stelle, und man fährt nun mit $x'$ anstelle von $x$ mit dem gleichen Verfahren fort und erhält so auch die weiteren Ziffern. Für die Binärdarstellung ist diese Methode natürlich besonders einfach, da als Ziffer nur 0 oder $1$ auftreten kann. Nachteil ist allerdings, daß man genügend viele Zweierpotenzen $2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,\dots$ bei der Hand haben muß.

3.17 Beispiel.
Wir betrachten die Dezimalzahlen $123$ und $321$ und bestimmen ihre Binärdarstellungen $1111011$ und $101000001$:

$$123 = 61\cdot 2+1 321 = 160\cdot 2+1$$

$$61 = 30\cdot 2+1 160 = 80\cdot 2+0$$

$$30 = 15\cdot 2+0 80 = 40\cdot 2+0$$

$$15 = 7\cdot 2+1 40 = 20\cdot 2+0$$

$$7 = 3\cdot 2+1 20 = 10\cdot 2+0$$

$$3 = 1\cdot 2+1 10 = 5\cdot 2+0$$

$$1 = 0\cdot 2+1 5 = 2\cdot 2+1$$

$$2 = 1\cdot 2+0$$

$$1 = 0\cdot 2+1$$

Wegen $2^3=8$ und $2^4=16$ erhält man daraus die Darstellungen als Oktalzahlen bzw. Hexadezimalzahlen durch Zusammenfassen jeweils 3 bzw. 4 Ziffern der Binärzahldarstellung, also in unserem Beispiel Oktal $173$ und $501$ und Hexadezimal $7D$ und $141$.

$$\begin{array}{r\vert\vert c\vert c\vert c\vert... ...när} & 1 & 10 & 11 & 100 & 101 & 110 & 111 & 1000 \\ \hline \end{array}$$

$$\begin{array}{r\vert\vert c\vert c\vert c\vert... ...& 1010 & 1011 & 1100 & 1101 & 1110 & 1111 & 10000 \\ \hline \end{array}$$

Addition und Multiplikation der Zifferndarstellungen.
Genauso wie wir es schon von Dezimalzahlen kennen, können wir Zahlen auch mittels Darstellung bezüglich anderer Basen addieren und multiplizieren. Für die Addition von zwei Binärzahlen brauchen wir dazu nur, daß $1+1=10$ und $1+1+1=11$ um Überträge zu berücksichtigen. Bei der Addition mehrerer Zahlen auf einmal müssen wir wie bei Dezimalzahlen auch Überträge auf mehrere Stellen auf einmal berücksichtigen (also z.B. bei Berechnung der 1-er Stelle der Summe $9+19+29+39+49+59+69+79+89+99+109+119$ erhalten wir $9+\dots+9=12*9=108$ und somit $8$ und ein Übertrag von $10$)

Bei der Multiplikation von Binärzahlen in Ziffernschreibweise, brauchen wir nur mit 0 und 1 multiplizieren, also Weglassen oder Kopieren. Eine Multiplikation ist somit nichts anderes als eine mehrfache Addition. Z.B. ist $(123)_2=1111011$ und $(321)_2=101000001$ und $123\cdot 321=39483$ hat als Binärzahl die Darstellung $1001101000111011$, denn

$$\begin{array}{ccccccccccccccccccc} &1&1&1&1&0&... ... &1&1&1&1&0&1&1& \\ \hline 1&0&0&1&1&0&1&0&0&0&1&1&1&0&1&1& \end{array}$$

Kombinatorik

In der Kombinatorik geht es darum Anzahlen von jeweils endlich vielen Möglichkeiten zu bestimmen.

3.18 Definition.
Unter einer Permutation einer $n$-elementigen Mengen versteht man eine lineare Anordnung dieser Menge, das läuft darauf hinaus die Elemente der $n$-elementigen Menge auf die Plätze $1,2,\dots,n$ zu positionieren. Wir wollen nun die Anzahl der möglichen Permutationen bestimmen.

3.19 Lemma.
Die Anzahl der möglichen Permutationen einer $n$-elementigen Menge ist $n!=1\cdot 2\cdot\ldots\cdot (n-1)\cdot n$ (sprich: $n$-faktorielle).

Man setzt auch $0!=1$, als Anzahl der Permutationen der leeren Menge.

Beweis. Mittels Induktion:
(n=1) Hier gibt es nur eine Möglichkeit das einzige Element auf den einzigen Platz zu setzen.
(n+1) Nach Induktionsannahme können wir eine $n$-elementige Menge auf $n!$-viele Möglichkeiten anordnen. Um auch das $n+1$-te nun neu hinzugekommene Element zu positionieren haben wir $n+1$ viele Möglichkeiten, nämlich entweder vor allen anderen, oder zwischen 1-ten und 2-ten, oder 2-ten und 3-ten, ..., oder $n-1$-ten und $n$-ten, oder nach allen anderen. Zu jeder der $n!$ vielen Möglichkeiten alle bis auf ein Element anzuordnen gibt es also jeweils $n+1$ viele Möglichkeiten auch dieses noch einzuordnen, also insgesamt $n!\cdot(n+1)=(n+1)!$. Hier haben wir $\vert A\times B\vert=\vert A\vert\times \vert B\vert$ verwendet.     []

3.20 Definition.
Unter einer Variation ohne Wiederholung von $k$ vielen Objekten aus $n$ vielen, versteht man eine Auswahl von $k$-verschiedenen Elementen aus einer Grundmenge von $n$ vielen, wobei es auf die Reihenfolge der Auswahl ankommen soll. Also wenn z.B. der Vorstand bestehend aus Obmann, Schriftführer und Kassier eines Vereins mit 100 Mitgliedern gewählt werden soll ohne daß Ämterkummulierung zulässig ist, so ist eine Variation ohne Wiederholungen von 3 aus 100 zu bestimmen.

3.21 Lemma.
Die Anzahl der möglichen Variationen ohne Wiederholung von $k$ vielen Objekten aus $n$ vielen ist $(n)_k:=n\cdot(n-1)\cdot \ldots\cdot (n-k+2)\cdot (n-k+1)$.

Beweis. Wie in (3.19) verwenden wir Induktion nun nach $k$:
(k=1) Wir haben genau $n=(n)_1$ Möglichkeiten ein Element aus $n$ auszuwählen.
(k+1) Für die ersten $k$-Wahlen haben wir nach Induktionsannahme $(n)_k$ viele Möglichkeiten. Für die $k+1$-te Wahl sind nur noch $n-k$ viele Elemente übrig, da wir ja nicht gleiche Elemente wiederholt wählen dürfen. Insgesamt gibt es also $(n)_k\cdot (n-k)=(n)_{k+1}$ viele Möglichkeiten.     []

Wie ändert sich dies nun, wenn wir Wiederholungen doch zulassen.

3.22 Definition.
Unter einer Variation mit Wiederholung von $k$ vielen Objekten aus $n$ vielen, versteht man eine Auswahl von $k$ Elementen aus einer Grundmenge von $n$ vielen, wobei es auf die Reihenfolge der Auswahl ankommen soll und gleiche Elemente auch mehrfach gewählt werden dürfen. Also wenn z.B. der Vorstand bestehend aus Obmann, Schriftführer und Kassier eines Vereins mit 100 Mitgliedern gewählt werden soll, wobei Personen auch mehrerer Positionen innehaben dürfen, so ist eine Variation mit Wiederholungen von 3 aus 100 zu bestimmen.

3.23 Lemma.
Die Anzahl der Variationen mit Wiederholung von $k$ vielen Objekten aus $n$ vielen ist $n^k:=n\cdot\dots\cdot n$.

Beweis. Der Beweis geht wie in (3.21), wobei nun die für die Wahl des $(k+1)$-ten Elements verbleibende Anzahl noch immer alle, also $n$ ist,     []

3.25 Beispiel.
Wir wollen die Anzahl aller möglichen Bytes (d.h. Folgen von 8 Ziffern in $\{0,1\}$) bestimmen. Wir müssen also für jede der 8 Stellen eine Ziffer aus $\{0,1\}$ wählen, wobei es auf die Reihenfolge der Ziffern natürlich ankommt und gleiche Ziffern vorkommen können (ja sogar müssen). Die Anzahl dieser Variationen mit Wiederholung von $8$ aus $2$ ist somit $2^8=256$.

Ein Computer der als Adressen binäre Worte von 16bit Länge verwendet, kann also $2^{16}=65536=64k$ Speicherpositionen adressieren, wobei $1k=2^{10}=1024\sim 10^3$ ist, also gerade die Anzahl der mit zehn bits (engl.: digits = Finger, Stellen) darstellbaren Zahlen.

Verwendet er hingegen doppelt so lange Worte von 32bit Länge, dann kann er $2^{32}=4294967296=4G$ Speicherpositionen adressieren, wobei $1G=2^{30}=1024^3\sim 10^9$ ist.

3.24 Zyklen und Transpositionen.
Für die rechnerische Behandlung von Permutationen ist nicht wirklich wichtig, wie die Elemente der endlichen Menge heißen, wir können genausogut die Menge $n:=\{0,\dots,n-1\}$ oder auch $\{1,\dots,n\}$ dafür verwenden. Eine Permutation dieser Menge wird also durch eine bijektive Abbildung $\pi:n\to n$ beschrieben, die jeden Element $i\in\{0,1,\dots,n-1\}$ einen eindeutig bestimmten Platz $\pi(i)\in\{0,\dots,n-1\}$ zuordnet. Natürlich können wir auch genausogut die Umkehrfunktion $\pi^{-1}:n\to n$ verwenden, die für jeden Platz $k$ angibt, welches Element $i$ auf diesen gesetzt wird, d.h. $\pi(i)=k$ oder $i=\pi^{-1}(k)$.

Die Menge aller Permutationen $\pi$ auf $n$ bilden offensichtlich bzgl. der Zusammensetzung eine Gruppe, die sogenannte symmetrische Gruppe $\mathcal{S}_n$ der Ordnung $n$.

Solche Bijektionen können wir auf verschiedene Weisen veranschaulichen bzw. festlegen. Einerseits durch Angabe der Funktionswerte am besten in Form einer Tabelle:

$$\begin{array}{\vert c\vert\vert c\vert c\vert ... ...line \pi(i)&\pi(0)&\pi(1)&\dots&\pi(n-2)&\pi(n-1) \\ \hline \end{array}$$

Z.B.:

$$\begin{array}{\vert c\vert\vert c\vert c\vert ... ... & 6 \\ \hline \pi(i)& 0 & 2 & 1 & 4 & 5 & 6 & 3 \\ \hline \end{array}$$

Oder aber als Graph, wobei die Punkte $0,1,\dots,n-1$ so durch Pfeile verbunden werden, wie sie aufeinander abgebildet werden. In unseren Beispiel ist das:

$$\xymatrix{ 0 \ar@(r,d)[] & 1 \ar@/^/[0,1] & 2 ... ...,-1]& 3 \ar@{->}[1,-2] \\ & 4 \ar[0,1]& 5 \ar[0,1]& 6 \ar@{->}[-1,0] }$$

Die Elemente der Menge $\{0,1,\dots,6\}$ zerfallen offensichtlich in Klassen $\{0\}$, $\{1,2\}$ und $\{3,4,5,6\}$, aus welchen $\pi$ nicht herausführt, und deren Elemente durch $\pi$ durchgemischt werden.

Allgemein erhält man dadurch eine weitere Darstellung nämlich durch Zyklen, d.h. man zerlegt $\{0,1,\dots,n\}$ in kleinstmögliche, unter $\pi$ invariante nicht-leere Teilmengen $A$, d.h. $\pi(A)\subseteq A$. Solche erhält man, indem man mit einem Element aus $i\in\{0,\dots,n-1\}$ startet und sooft $\pi$ darauf anwendet, bis man wieder $i$ erhält, d.h. $i$, $\pi(i)$, $\pi^2(i):=\pi(\pi(i))$,..., $\pi^d(i)=i$ betrachtet. Dies passiert wirklich für hinreichend großes $d$, denn die $\pi^j(i)\in\{0,\dots,n-1\}$ können nicht für alle $j$ verschieden sein, und wenn $\pi^{j}(i)=\pi^{j'}(i)$ für $j<j'$ ist, so ist $\pi^{j'-j}(i)=((\pi^{j})^{-1}\o\pi^{j'})(i)=i$. Die Menge $A:=\{i=\pi^0(i),\pi(i),\dots,\pi^{d-1}(i)\}$ ist dann eine minimale invariante nicht-leere Menge. Und $\pi$ kann darauf durch die Folge $(i,\pi(i),\dots,\pi^{d-1}(i))$ beschrieben werden (man nennt dies einen Zyklus). Man beachte jedoch, daß verschiedene Tupel (die Verallgemeinerung von Paar, Tripel, Quadrupel, Quintupel, ...) die gleiche zyklische Permutation beschreiben, z.B. sind die Paare $(1,2)$ und $(2,1)$ verschieden, aber die zyklischen Permutationen $(1,2)$ und $(2,1)$ ident. Auf ganz $\{0,\dots,n-1\}$ kann somit $\pi$ als Zusammensetzung der Element-fremden Zyklen, die zu der Zerlegung in invariante Teilmengen gehören, beschrieben werden. Das Inverse zu einen Zyklus $(a_1,a_2,\dots,a_n)$ in $\mathcal{S}_n$ ist offensichtlich durch den umgekehrt durchlaufenen Zyklus $(a_n,a_{n-1},\dots,a_2,a_1)$ gegeben.

Besonders einfach Zyklen sind jene der Länge 2, d.h. der Form $(j,j')$, wo also $\pi$ nur die Position der beiden Elemente $j$ und $j'$ vertauscht. Diese heißen Transpositionen. Und am einfachsten ist, wenn dies benachbarte Elemente sind, also $j'=j+1$ ist.

Unser Ziel ist nun zu zeigen, daß sich jede Anordnung (d.h. Permutation) dadurch erreichen läßt, das man hintereinander gewisse Transpositionen (benachbarter Elemente) ausführt.

3.26 Proposition. Zerlegung in Transpositionen.
Jede Permutation läßt sich als Zusammensetzung endlich vieler elementfremder Zyklen schreiben und jeder Zyklus läßt sich als Zusammensetzung endlich vieler Transpositionen aufeinanderfolgender Elemente schreiben.

Beweis. Daß sich Permutationen in elementfremde Zyklen zerlegen lassen, haben wir oben bereits gezeigt.

Ein Zyklus der Form $(1,2,3,\dots,n)$ läßt sich wie folgt in ein Produkt von Transpositionen zerlegen:

$$(1,2,3,\dots,n-2,n-1,n)=(1,2)\o (2,3)\o\dots\o (n-2,n-1)\o (n-1,n).$$

oder allgemeiner

$$(a_1,a_2,a_3,\dots,a_{n-2},a_{n-1},a_n) =(a_1,a_2)\o (a_2,a_3)\o\dots\o (a_{n-2},a_{n-1})\o (a_{n-1},a_n).$$

Idee dabei ist, daß um ein Element vom letzten Platz $n$ an den ersten Platz $1$ zu bekommen (und alle anderen um einen Platz nach hinten rücken zu lassen) man zuerst das Element auf Platz $n$ und $n-1$ Platz tauschen läßt, danach jene nunmehr auf Platz $n-1$ und $n-2$ liegenden, u.s.w. bis schließlich noch die dann auf Platz 1 und 2 liegenden Plätze tauschen. Der Ablauf sieht also folgendermaßen aus:

Am Anfang	1	2	...	n-2	n-1
nach 1. Schritt	1	2	...	n-2		n-1
nach 2. Schritt	1	2	...		n-2	n-1
&vellip#vdots;
nach (n-2). Schritt	1	2		...	n-2	n-1
nach (n-1). Schritt	1		2	...	n-2	n-1
nach n. Schritt		1	2	...	n-2	n-1

Eine beliebige Transposition $(k,j)=(j,k)$ mit o.B.d.A. $k<j$ läßt sich als Produkt von Zyklen der zuletzt behandelten Form schreiben:

$$(k,j) = (j,j-1,\dots,k+3,k+2,k+1)\o (k,k+1,k+2,k+3,\dots,j-1,j).$$

In der Tat ist nach obigen

$$(k+1,k+2,\dots,j-1,j) =(k+1,k+2)\o\dots\o (j-1,j)$$

$$(k+1,k+2,\dots,j-1,j,k) =(k+1,k+2)\o\dots\o (j-1,j)\o (j,k)$$

und damit

$$(k,j) =(j,k)$$

$$= (k+1,k+2,k+3,\dots,j-1,j)^{-1}\o (k+1,k+2,k+3,\dots,j-1,j,k)$$

$$= (j,j-1,\dots,k+3,k+2,k+1)\o (k,k+1,k+2,k+3,\dots,j-1,j)$$

Mittels Graphen sieht man das wie folgt ein:

Somit läßt sich jeder allgemeine Zyklus als Zusammensetzung von Transpositionen schreiben, die sich seinerseits jeweils als Zusammensetzung zweier Zyklen mit aufeinanderfolgenden Elementen schreiben lassen und somit ihrerseits Zusammensetzungen von Transpositionen aufeinanderfolgender Elemente sind.     []

Beispiel.
Wir berechnen $(1,3)$ und $(1,4)$ nach obiger Formel, $(1,3)=(3,2)\o (1,2,3)=(3,2)\o (1,2)\o (2,3)$ und $(1,4)=(4,3,2)\o (1,2,3,4)=(4,3)\o (3,2)\o (1,2)\o (2,3)\o (3,4)$. Permutionen können somit verschiedene Zerlegungen in Produkte aus Transpositionen haben.

Wir wollen als nächstes zeigen, daß die Anzahl der Transpositionen in die man eine fixe Permutation zerlegen kann aber immer gerade oder immer ungerade ist und man somit von geraden und ungeraden Permutationen sprechen kann.

3.27 Definition.
Unter einer Inversion einer Permutation $\pi$ versteht man ein Paar $(i,j)$ mit $i<j$ aber $\pi(i)>\pi(j)$. Eine Permutation $\pi$ heißt gerade und man schreibt $\operatorname{sgn}(\pi)=+1$, wenn die Anzahl all ihrer Inversionen gerade ist. Andernfalls heißt sie ungerade und man schreibt $\operatorname{sgn}(\pi)=-1$.

3.28 Beispiel.
Die Inversionen der Permutation

$$\pi = \begin{pmatrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 2 & 1 & 4 & 5 & 6 & 3 \end{pmatrix}$$

sind die mit `+' gekennzeichneten Punkte in der folgenden Tabelle

$$\begin{array}{c\vert c\vert c\vert c\vert c\ve... ...& - & + \\ 5 & & & & & & & + \\ 6 & & & & & & & \\ \hline \end{array}$$

Die Anzahl der Inversionen ist somit 4 und $\pi$ ist gerade.

3.29 Lemma.
Es sei $\pi$ eine Permutation und $\sigma$ eine Transposition.

Dann ist $\operatorname{sgn}(\sigma \o\pi)=-\operatorname{sgn}(\pi)$.

Beweis. Es sei $\sigma =(a,b)$ mit $a<b$. Dann unterscheiden sich die Werte von $\pi$ und $\sigma \o\pi$ nur an den Stellen $\pi^{-1}(a)$ und $\pi^{-1}(b)$, und diese werden ausgetauscht. Es ändert sich die Eigenschaft Inversion zu sein also höchstens für solche Paare die $a$ oder $b$ im Bild haben. Das Paar $(\pi^{-1}(a),\pi^{-1}(b))$ ändert sicher seine Eigenschaft Inversion zu sein. Und die übrigen dieser Paare ändern ihre Eigenschaft Inversion zu sein genau dann, wenn der andere Bildpunkt $a<\pi(i)<b$ erfüllt. Es seien nun $p$ viele der $i$ mit $a<\pi(i)<b$ Inversionen mit zweiten Punkt $a$, d.h. $i<a$ und $q$ viele mit zweiten Punkt $b$, d.h. $i>b$. Da es insgesamt $b-a-1$ viele $i$ in $\pi^{-1}(\{a+1,\dots,b-1\})$ gibt, sind nach Vertauschen von $a$ mit $b$ gerade $b-a-1-p$ viele Inversionen mit zweiten Punkt $\sigma (a)=b$ und $b-a-1-q$ viele Inversionen mit anderen Punkt $\sigma (b)=a$. Insgesamt hat sich also die Anzahl der relevanten Inversionen von $p+q$ auf $\pm 1+(b-a-1-p)+(b-a-1-q)$ geändert, also um eine ungerade Anzahl $\pm 1+2(b-a-1-p-q)$. Somit ist $\operatorname{sgn}(\sigma \o\pi)=-\operatorname{sgn}(\pi)$.     []

3.30 Folgerung. Vorzeichen einer Permutation.
Eine Permutation ist genau dann gerade, wenn sie sich in eine gerade Anzahl von Transpositionen zerlegen läßt. Das Vorzeichen einer zyklischen Permutation $(a_0,a_2,\dots,a_{k-1},a_k)$ ist $(-1)^k$. Insbesonders ist $\operatorname{sgn}(\pi\o\sigma )=\operatorname{sgn}(\pi)\cdot\operatorname{sgn}(\sigma )$ für alle Permutationen $\sigma$ und $\pi$. Und die Menge $\mathcal{A}_n$ der geraden Permutationen der Ordnung $n$ bildet eine Untergruppe von $\mathcal{S}_n$, d.h. eine Teilmenge die bezüglich der Operation der Obermenge selbst eine Gruppe ist.

Beweis. Mittels Induktion folgt aus (3.29), daß eine Komposition von Transpositionen genau dann gerade ist, wenn die Anzahl der Faktoren gerade ist. Dies zeigt die erste Aussage.

Da eine zyklische Permutation $(a_0,a_2,\dots,a_{k-1},a_k)$ in $(a_0,a_1)\o\cdots\o (a_{k-1},a_k)$ zerlegt werden kann, also in $k$ viele Transpositionen, folgt auch die zweite.

Mittels Induktion folgt aus (3.29) und der Zerlegung von $\sigma$ in Transpositionen, daß die behauptete Formel für das Vorzeichen einer Zusammensetzung gilt.

Und, da $(+1)\cdot(+1)=+1$ und $1/(+1)=+1$ ist, folgt, daß $\mathcal{A}_n:=\{\pi\in\mathcal{S}_n:\operatorname{sgn}(\pi)=+1\}$ eine Untergruppe ist.     []

3.31 Definition.
Eine Abbildung $f:X^n:=X\times \dots\times X\to \mathbb{R}$ in $n$ vielen Variablen heißt symmetrisch, wenn

$$f(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)})$$

für alle Permutationen $\pi\in\mathcal{S}_n$ und alle $x_1,\dots,x_n\in X$ gilt, d.h. man die Variablen $x_1,\dots,x_n$ beliebig vertauschen darf ohne den Funktionswert $f(x_1,\dots,x_n)$ zu ändern. Z.B. sind $f(x_1,x_2):=x_1+x_2$ und $f(x_1,x_2):= x_1\cdot x_2$ symmetrisch (Man braucht nur mit der Permutation $\pi=(1,2)$ zu testen). Allgemeiner ist $f(x_1,x_2,x_3):=x_1+x_2+x_3$ und $f(x_1,x_2,x_3):=x_1\cdot x_2\cdot x_3$ symmetrisch, aber auch $f(x_1,x_2,x_3):=x_1\,x_2+x_2\,x_3+x_3\,x_1$ (Hier müssen wir bereits mit den Transpositionen $(1,2)$, $(2,3)$ und $(3,1)$ testen). Noch allgemeiner ist $f(x_1,\dots x_n):=\sum_{j=1}^n x_j^p$ sowie die Elementarsymmetrischen Funktionen

$$\sigma _k(x_1,\dots,x_n):=\sum_{1\leq j_1<\dot... ...{\substack{J\subseteq \{1,\dots,n\}\\ Vert J\vert=k}} \prod_{j\in J}x_j$$

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

Eine Abbildung $f:X^n:=X\times \dots\times X\to \mathbb{R}$ heißt alternierend, wenn

$$\operatorname{sgn}(\pi)\,f(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)})$$

für alle Permutationen $\pi\in\mathcal{S}_n$ und alle $x_1,\dots,x_n\in X$ gilt, d.h. sich der Funktionswert nur um ein Vorzeichen (nämlich jenes der Permutation) ändert, wenn man die Variablen vertauscht. Z.B. ist $f(x_1,x_2):=x_1-x_2$ alternierend, denn für $\pi=(1,2)$ ist $f(x_{\pi(1)},x_{\pi(2)})=f(x_2,x_1)=x_2-x_1=-(x_1-x_2)=\operatorname{sgn}(\pi)\, f(x_1,x_2)$. Allgemeiner ist $f(x_1,x_2,x_3):=(x_1-x_2)\,(x_2-x_3)\,(x_1-x_3)$ alternierend, denn z.B. für $\pi=(1,2)$ erhalten wir

$$\begin{multline*} f(x_{\pi(1)},x_{\pi(2)},x_{\pi(3)})=f(x_2,x_1,x_3) =(x_2-x_1... ...,(x_2-x_3)\,(x_1-x_3) =\operatorname{sgn}(\pi)\,f(x_1,x_2,x_3), \end{multline*}$$

oder noch allgemeiner ist $f:(x_1,\dots,x_n)\mapsto\prod_{i<j}(x_i-x_j)$ alternierend.