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 \bgroup\color{demo}$ 0,1,2,3,\dots\in\mathbb{R}$\egroup 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 \bgroup\color{demo}$ n$\egroup auch (der Nachfolger) \bgroup\color{demo}$ n+1$\egroup eine natürliche Zahl sein soll. Die Abbildung \bgroup\color{demo}$ n\mapsto n+1$\egroup sollte also nicht aus der Menge \bgroup\color{demo}$ \mathbb{N}$\egroup der natürlichen Zahlen herausführen. Dadurch ist aber \bgroup\color{demo}$ \mathbb{N}$\egroup noch nicht eindeutig beschrieben, denn z.B. auch die Teilmengen \bgroup\color{demo}$ \mathbb{Z}$\egroup, \bgroup\color{demo}$ \mathbb{Q}$\egroup, \bgroup\color{demo}$ \mathbb{R}$\egroup haben diese Eigenschaft. Die Menge \bgroup\color{demo}$ \mathbb{N}$\egroup sollte wohl eine möglichst kleine Teilmenge mit dieser Eigenschaft sein. Allerdings sind auch \bgroup\color{demo}$ \emptyset$\egroup, \bgroup\color{demo}$ \{1,2,3,\dots\}$\egroup, \bgroup\color{demo}$ \{2,3,4,\dots\}$\egroup solche Mengen. Wenn wir aber zusätzlich \bgroup\color{demo}$ 0\in\mathbb{N}$\egroup verlangen, dann paßt alles. Es ist also \bgroup\color{demo}$ \mathbb{N}$\egroup die kleinste Teilmenge von \bgroup\color{demo}$ \mathbb{R}$\egroup, die 0 enthält und unter dem Zählen \bgroup\color{demo}$ n\mapsto n+1$\egroup abgeschlossen ist, d.h.

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

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

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

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

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

\bgroup\color{demo}$\displaystyle \mathbb{N}:=\bigcap\bigl\{N:N$\egroup ist induktiv\bgroup\color{demo}$\displaystyle \bigr\}.
$\egroup

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




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

Beweis. Die ist offensichtlich, da \bgroup\color{demo}$ \mathbb{N}$\egroup 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 \bgroup\color{demo}$ \mathcal{N}$\egroup 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 \bgroup\color{demo}$ N:=\{n\in\mathbb{N}:\mathcal{N}$\egroup trifft für $n$ zu\bgroup\color{demo}$ \}$\egroup mit \bgroup\color{demo}$ \mathbb{N}$\egroup übereinstimmt, die Aussage \bgroup\color{demo}$ \mathcal{N}$\egroup 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 \bgroup\color{demo}$ n$\egroup:
    Der Induktionsanfang \bgroup\color{demo}$ n=0$\egroup ist offensichtlich erfüllt, denn \bgroup\color{demo}$ 0+\dots+0=0=\frac{0(0+1)}2$\egroup.
    Den Induktionsschritt von \bgroup\color{demo}$ n$\egroup auf \bgroup\color{demo}$ n+1$\egroup zeigen wir nun wie folgt. Nach Induktionsannahme ist die Aussage für \bgroup\color{demo}$ n$\egroup richtig, also \bgroup\color{demo}$ 0+1+\dots+n=\frac{n(n+1)}2$\egroup. Nun zeigen wir die Aussage für \bgroup\color{demo}$ n+1$\egroup an Stelle von \bgroup\color{demo}$ n$\egroup:

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

        []

  2. Für alle \bgroup\color{demo}$ n\geq 4$\egroup ist \bgroup\color{demo}$ 2^n\geq n^2$\egroup.

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

    $\displaystyle 2^{n+1}$ $\displaystyle =2\cdot 2^n\geq 2\,n^2\geq (n+1)^2=n^2+2\,n+1,$ denn    
    $\displaystyle n^2-2\,n+1$ $\displaystyle =(n-1)^2\geq 2^2>1+1=2,$    

    sofern \bgroup\color{demo}$ n-1\geq 2$\egroup, also \bgroup\color{demo}$ n\geq 3$\egroup 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 \bgroup\color{demo}$ 8*8=64$\egroup-ten. Die Anzahl \bgroup\color{demo}$ a_n$\egroup der Körner auf Feld \bgroup\color{demo}$ n$\egroup ist also rekursiv durch \bgroup\color{demo}$ a_1:=1$\egroup und \bgroup\color{demo}$ a_{n+1}=2\,a_n$\egroup gegeben. Explizit prüft man mittels Induktion leicht nach, daß \bgroup\color{demo}$ a_n=2^{n-1}$\egroup ist und \bgroup\color{demo}$ S_n:=a_1+a_2+\dots+a_n=1+2+\dots+2^{n-1}=2^n-1$\egroup ist. Das sind also insgesamt \bgroup\color{demo}$ S_{64}=2^{64}-1=18446744073709551615\sim 0.18*10^{20}$\egroup viele Körner. Wenn wir ein Korn mit \bgroup\color{demo}$ 50$\egroupmm\bgroup\color{demo}$ ^3=5*10^{-8}\,$\egroupm\bgroup\color{demo}$ ^3\sim 3*10^{-5}\,$\egroupkg abschätzen, dann wiegt \bgroup\color{demo}$ S_{64}$\egroup circa \bgroup\color{demo}$ 0.18*10^{20}*3*10^{-5}\sim 5*10^{14}\,$\egroupkg also \bgroup\color{demo}$ 500$\egroup Milliarden Tonnen - eine nicht zu erfüllende Forderung.
  4. Zinseszinsrechnung als Beispiel: Ein Betrag \bgroup\color{demo}$ b$\egroup werde mit jährlichen Zinsen von \bgroup\color{demo}$ p$\egroup Prozent verzinst, d.h. nach einem Jahr sind die Zinsen \bgroup\color{demo}$ b\cdot \frac{p}{100}$\egroup und der Endbetrag somit \bgroup\color{demo}$ b_1:=b+b\frac{p}{100}$\egroup. Nach 2 Jahren fallen nicht nur ein weiteres Mal die Zinsen \bgroup\color{demo}$ b\cdot \frac{p}{100}$\egroup von \bgroup\color{demo}$ b$\egroup sondern auch die Zinsen \bgroup\color{demo}$ b\cdot \frac{p}{100}\cdot \frac{p}{100}$\egroup der Zinsen \bgroup\color{demo}$ b\cdot \frac{p}{100}$\egroup des ersten Jahres an, d.h. der Endbetrag ist nun

    \bgroup\color{demo}$\displaystyle 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,
$\egroup

    und nach \bgroup\color{demo}$ n$\egroup Jahren folgt mittels Rekursion, daß der Endbetrag

    \bgroup\color{demo}$\displaystyle b_n= b\left(1+\frac{p}{100}\right)^n
$\egroup

    ist.


3.5 Definition.
Man nennt Abbildungen \bgroup\color{demo}$ a:\mathbb{N}\to X$\egroup auch Folgen in \bgroup\color{demo}$ X$\egroup und schreibt gerne \bgroup\color{demo}$ a_n$\egroup anstelle von \bgroup\color{demo}$ a(n)$\egroup, 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 \bgroup\color{demo}$ a_n$\egroup für \bgroup\color{demo}$ n\in\mathbb{N}$\egroup definiert sind, beschreibt man einerseits \bgroup\color{demo}$ a_0$\egroup und andererseits wie man \bgroup\color{demo}$ a_{n+1}$\egroup aus \bgroup\color{demo}$ a_n$\egroup für jedes \bgroup\color{demo}$ n\in\mathbb{N}$\egroup berechnen kann, d.h. man gibt eine Rekursionsvorschrift \bgroup\color{demo}$ R$\egroup an, s.d. \bgroup\color{demo}$ a_{n+1}=R(a_n)$\egroup ist.




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

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

\bgroup\color{demo}$\displaystyle 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\}.
$\egroup

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

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


3.6 Die Grundrechnungsarten für natürliche Zahlen.
Die Addition \bgroup\color{demo}$ m\mapsto n+m$\egroup natürlicher Zahlen definiert man rekursiv durch

$\displaystyle n+0$ $\displaystyle :=n,$    
$\displaystyle n+m^+$ $\displaystyle :=(n+m)^+$    

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

Ebenso verfährt man mit der Multiplikation \bgroup\color{demo}$ m\mapsto n\cdot m$\egroup:

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

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

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

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

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

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

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 \bgroup\color{demo}$ n\cdot (m+k)=n\cdot m+n\cdot k$\egroup.


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

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

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

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




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

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

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




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

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

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

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




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

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

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




3.10 Folgerung. Primfaktorenzerlegung.
Jede natürliche Zahl \bgroup\color{demo}$ n>1$\egroup läßt sich in ein Produkt von Primzahlen zerlegen.

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


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




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

  $\displaystyle 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},$    
  $\displaystyle 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 \bgroup\color{demo}$ m$\egroup:
( \bgroup\color{demo}$ m=1$\egroup) \bgroup\color{demo}$ a^{n+1}=a^n\cdot a=a^{n}\cdot a^{1}$\egroup.
( \bgroup\color{demo}$ m+1$\egroup) \bgroup\color{demo}$ 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}$\egroup.

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

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

\bgroup\color{demo}$\displaystyle (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)}.
$\egroup

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

\bgroup\color{demo}$\displaystyle 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}.
$\egroup

Daraus folgt die fünfte durch Division.     []


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

\bgroup\color{demo}$\displaystyle a_0=c,\;a_1=c^2,\,a_2=(c^2)^2=c^4,\,a_3=(c^4)^2=c^8,\dots
$\egroup

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

\bgroup\color{demo}$\displaystyle a_0=2, a_1=4, a_2=16, a_2=256, a_3=65536, a_4=4294967296,\dots
$\egroup

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


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

$\displaystyle \sum_{i=1}^0 x_i$ $\displaystyle :=0$, oder wer lieber bei 1 beginnt $\displaystyle \sum_{i=1}^1 x_i:= x_1$    
$\displaystyle \sum_{i=1}^{n+1} x_i$ $\displaystyle := \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

\bgroup\color{demo}$\displaystyle \sum_{i=1}^n x_i=x_1+x_2+\dots+x_{n-1}+x_n
$\egroup

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

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

$\displaystyle \prod_{i=1}^0 x_i$ $\displaystyle :=1$, oder wer lieber bei 1 beginnt $\displaystyle \prod_{i=1}^1 x_i:=x_1$    
$\displaystyle \prod_{i=1}^{n+1} x_i$ $\displaystyle := \Bigl(\prod_{i=1}^n x_i\Bigr)\cdot x_{n+1}$    

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




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

$\displaystyle \sum_{i=1}^n a_i\pm\sum_{i=1}^n b_i$ $\displaystyle = \sum_{i=1}^n (a_i\pm b_i) \qquad$ $\displaystyle \qquad c\sum_{i=1}^n a_i$ $\displaystyle = \sum_{i=1}^n c\,a_i$    
$\displaystyle \sum_{i=1}^n a_i + \sum_{i=n+1}^{n+m} a_i$ $\displaystyle = \sum_{i=1}^{n+m} a_i \qquad$ $\displaystyle \qquad \sum_{i=1}^n a_i$ $\displaystyle = \sum_{i=1+m}^{n+m} a_{i-m}$    

Man veranschauliche sich diese Formeln durch Übersetzung in `` \bgroup\color{demo}$ \dots$\egroup''-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 \bgroup\color{demo}$ 0,1,2,3,\dots$\egroup nur für die ersten paar Zahlen zur Verfügung.

Um nicht in römischer Manier laufend neue Symbole wie \bgroup\color{demo}$ I,V,X,L,C,\dots$\egroup 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 \bgroup\color{demo}$ 0,1,2,3,4,5,6,7,8,9$\egroup) und interpretiert ein Folge \bgroup\color{demo}$ a_0,a_1,\dots,a_{n-1},a_n$\egroup solcher Ziffern als als die natürliche Zahl \bgroup\color{demo}$ a_0+a_1\,b+a_2\,b^2+\dots+a_{n-1}\,b^{n-1}+a_n\,b^n$\egroup, wobei \bgroup\color{demo}$ b$\egroup 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. \bgroup\color{demo}$ 123=1\cdot b^2+2\cdot b+3$\egroup. Das sich wirklich jede natürliche Zahl so darstellen läßt besagt folgendes




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

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

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

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

Ein andere (vielleicht einsichtigere) Möglichkeit die Ziffern einer Zahl \bgroup\color{demo}$ x$\egroup zu bestimmen ist sich zuerst einen Vorrat an Potenzen \bgroup\color{demo}$ b^1,b^2,b^3,\dots$\egroup aufzuschreiben. Die kleinste solche Potenz \bgroup\color{demo}$ b^{n+1}>x$\egroup zu suchen und dann \bgroup\color{demo}$ x$\egroup durch \bgroup\color{demo}$ b^n$\egroup ganzzahlig zu dividieren, d.h. \bgroup\color{demo}$ x=x_n\,b^n+x'$\egroup nach \bgroup\color{demo}$ x_n,x'$\egroup mit \bgroup\color{demo}$ x'<b$\egroup zu lösen. Dann ist \bgroup\color{demo}$ x_n$\egroup die höchste Stelle, und man fährt nun mit \bgroup\color{demo}$ x'$\egroup anstelle von \bgroup\color{demo}$ x$\egroup 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 \bgroup\color{demo}$ 1$\egroup auftreten kann. Nachteil ist allerdings, daß man genügend viele Zweierpotenzen \bgroup\color{demo}$ 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,\dots$\egroup bei der Hand haben muß.


3.17 Beispiel.
Wir betrachten die Dezimalzahlen \bgroup\color{demo}$ 123$\egroup und \bgroup\color{demo}$ 321$\egroup und bestimmen ihre Binärdarstellungen \bgroup\color{demo}$ 1111011$\egroup und \bgroup\color{demo}$ 101000001$\egroup:

$\displaystyle 123$ $\displaystyle = 61\cdot 2+1$ $\displaystyle 321$ $\displaystyle = 160\cdot 2+1$    
$\displaystyle 61$ $\displaystyle = 30\cdot 2+1$ $\displaystyle 160$ $\displaystyle = 80\cdot 2+0$    
$\displaystyle 30$ $\displaystyle = 15\cdot 2+0$ $\displaystyle 80$ $\displaystyle = 40\cdot 2+0$    
$\displaystyle 15$ $\displaystyle = 7\cdot 2+1$ $\displaystyle 40$ $\displaystyle = 20\cdot 2+0$    
$\displaystyle 7$ $\displaystyle = 3\cdot 2+1$ $\displaystyle 20$ $\displaystyle = 10\cdot 2+0$    
$\displaystyle 3$ $\displaystyle = 1\cdot 2+1$ $\displaystyle 10$ $\displaystyle = 5\cdot 2+0$    
$\displaystyle 1$ $\displaystyle = 0\cdot 2+1$ $\displaystyle 5$ $\displaystyle = 2\cdot 2+1$    
    $\displaystyle 2$ $\displaystyle = 1\cdot 2+0$    
    $\displaystyle 1$ $\displaystyle = 0\cdot 2+1$    

Wegen \bgroup\color{demo}$ 2^3=8$\egroup und \bgroup\color{demo}$ 2^4=16$\egroup 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 \bgroup\color{demo}$ 173$\egroup und \bgroup\color{demo}$ 501$\egroup und Hexadezimal \bgroup\color{demo}$ 7D$\egroup und \bgroup\color{demo}$ 141$\egroup.

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

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


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ß \bgroup\color{demo}$ 1+1=10$\egroup und \bgroup\color{demo}$ 1+1+1=11$\egroup 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 \bgroup\color{demo}$ 9+19+29+39+49+59+69+79+89+99+109+119$\egroup erhalten wir \bgroup\color{demo}$ 9+\dots+9=12*9=108$\egroup und somit \bgroup\color{demo}$ 8$\egroup und ein Übertrag von \bgroup\color{demo}$ 10$\egroup)

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 \bgroup\color{demo}$ (123)_2=1111011$\egroup und \bgroup\color{demo}$ (321)_2=101000001$\egroup und \bgroup\color{demo}$ 123\cdot 321=39483$\egroup hat als Binärzahl die Darstellung \bgroup\color{demo}$ 1001101000111011$\egroup, denn

\bgroup\color{demo}$\displaystyle \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}$\egroup

Kombinatorik

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


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




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

Man setzt auch \bgroup\color{demo}$ 0!=1$\egroup, 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 \bgroup\color{demo}$ n$\egroup-elementige Menge auf \bgroup\color{demo}$ n!$\egroup-viele Möglichkeiten anordnen. Um auch das \bgroup\color{demo}$ n+1$\egroup-te nun neu hinzugekommene Element zu positionieren haben wir \bgroup\color{demo}$ n+1$\egroup viele Möglichkeiten, nämlich entweder vor allen anderen, oder zwischen 1-ten und 2-ten, oder 2-ten und 3-ten, ..., oder \bgroup\color{demo}$ n-1$\egroup-ten und \bgroup\color{demo}$ n$\egroup-ten, oder nach allen anderen. Zu jeder der \bgroup\color{demo}$ n!$\egroup vielen Möglichkeiten alle bis auf ein Element anzuordnen gibt es also jeweils \bgroup\color{demo}$ n+1$\egroup viele Möglichkeiten auch dieses noch einzuordnen, also insgesamt \bgroup\color{demo}$ n!\cdot(n+1)=(n+1)!$\egroup. Hier haben wir \bgroup\color{demo}$ \vert A\times B\vert=\vert A\vert\times \vert B\vert$\egroup verwendet.
    []


3.20 Definition.
Unter einer Variation ohne Wiederholung von \bgroup\color{demo}$ k$\egroup vielen Objekten aus \bgroup\color{demo}$ n$\egroup vielen, versteht man eine Auswahl von \bgroup\color{demo}$ k$\egroup-verschiedenen Elementen aus einer Grundmenge von \bgroup\color{demo}$ n$\egroup 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 \bgroup\color{demo}$ k$\egroup vielen Objekten aus \bgroup\color{demo}$ n$\egroup vielen ist \bgroup\color{demo}$ (n)_k:=n\cdot(n-1)\cdot \ldots\cdot (n-k+2)\cdot (n-k+1)$\egroup.

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

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


3.22 Definition.
Unter einer Variation mit Wiederholung von \bgroup\color{demo}$ k$\egroup vielen Objekten aus \bgroup\color{demo}$ n$\egroup vielen, versteht man eine Auswahl von \bgroup\color{demo}$ k$\egroup Elementen aus einer Grundmenge von \bgroup\color{demo}$ n$\egroup 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 \bgroup\color{demo}$ k$\egroup vielen Objekten aus \bgroup\color{demo}$ n$\egroup vielen ist \bgroup\color{demo}$ n^k:=n\cdot\dots\cdot n$\egroup.

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


3.25 Beispiel.
Wir wollen die Anzahl aller möglichen Bytes (d.h. Folgen von 8 Ziffern in \bgroup\color{demo}$ \{0,1\}$\egroup) bestimmen. Wir müssen also für jede der 8 Stellen eine Ziffer aus \bgroup\color{demo}$ \{0,1\}$\egroup 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 \bgroup\color{demo}$ 8$\egroup aus \bgroup\color{demo}$ 2$\egroup ist somit \bgroup\color{demo}$ 2^8=256$\egroup.

Ein Computer der als Adressen binäre Worte von 16bit Länge verwendet, kann also \bgroup\color{demo}$ 2^{16}=65536=64k$\egroup Speicherpositionen adressieren, wobei \bgroup\color{demo}$ 1k=2^{10}=1024\sim 10^3$\egroup 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 \bgroup\color{demo}$ 2^{32}=4294967296=4G$\egroup Speicherpositionen adressieren, wobei \bgroup\color{demo}$ 1G=2^{30}=1024^3\sim 10^9$\egroup 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 \bgroup\color{demo}$ n:=\{0,\dots,n-1\}$\egroup oder auch \bgroup\color{demo}$ \{1,\dots,n\}$\egroup dafür verwenden. Eine Permutation dieser Menge wird also durch eine bijektive Abbildung \bgroup\color{demo}$ \pi:n\to n$\egroup beschrieben, die jeden Element \bgroup\color{demo}$ i\in\{0,1,\dots,n-1\}$\egroup einen eindeutig bestimmten Platz \bgroup\color{demo}$ \pi(i)\in\{0,\dots,n-1\}$\egroup zuordnet. Natürlich können wir auch genausogut die Umkehrfunktion \bgroup\color{demo}$ \pi^{-1}:n\to n$\egroup verwenden, die für jeden Platz \bgroup\color{demo}$ k$\egroup angibt, welches Element \bgroup\color{demo}$ i$\egroup auf diesen gesetzt wird, d.h. \bgroup\color{demo}$ \pi(i)=k$\egroup oder \bgroup\color{demo}$ i=\pi^{-1}(k)$\egroup.

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

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

\bgroup\color{demo}$\displaystyle \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}$\egroup

Z.B.:

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

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

\bgroup\color{demo}$\displaystyle \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]
}$\egroup

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

Allgemein erhält man dadurch eine weitere Darstellung nämlich durch Zyklen, d.h. man zerlegt \bgroup\color{demo}$ \{0,1,\dots,n\}$\egroup in kleinstmögliche, unter \bgroup\color{demo}$ \pi$\egroup invariante nicht-leere Teilmengen \bgroup\color{demo}$ A$\egroup, d.h. \bgroup\color{demo}$ \pi(A)\subseteq A$\egroup. Solche erhält man, indem man mit einem Element aus \bgroup\color{demo}$ i\in\{0,\dots,n-1\}$\egroup startet und sooft \bgroup\color{demo}$ \pi$\egroup darauf anwendet, bis man wieder \bgroup\color{demo}$ i$\egroup erhält, d.h. \bgroup\color{demo}$ i$\egroup, \bgroup\color{demo}$ \pi(i)$\egroup, \bgroup\color{demo}$ \pi^2(i):=\pi(\pi(i))$\egroup,..., \bgroup\color{demo}$ \pi^d(i)=i$\egroup betrachtet. Dies passiert wirklich für hinreichend großes \bgroup\color{demo}$ d$\egroup, denn die \bgroup\color{demo}$ \pi^j(i)\in\{0,\dots,n-1\}$\egroup können nicht für alle \bgroup\color{demo}$ j$\egroup verschieden sein, und wenn \bgroup\color{demo}$ \pi^{j}(i)=\pi^{j'}(i)$\egroup für \bgroup\color{demo}$ j<j'$\egroup ist, so ist \bgroup\color{demo}$ \pi^{j'-j}(i)=((\pi^{j})^{-1}\o\pi^{j'})(i)=i$\egroup. Die Menge \bgroup\color{demo}$ A:=\{i=\pi^0(i),\pi(i),\dots,\pi^{d-1}(i)\}$\egroup ist dann eine minimale invariante nicht-leere Menge. Und \bgroup\color{demo}$ \pi$\egroup kann darauf durch die Folge \bgroup\color{demo}$ (i,\pi(i),\dots,\pi^{d-1}(i))$\egroup 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 \bgroup\color{demo}$ (1,2)$\egroup und \bgroup\color{demo}$ (2,1)$\egroup verschieden, aber die zyklischen Permutationen \bgroup\color{demo}$ (1,2)$\egroup und \bgroup\color{demo}$ (2,1)$\egroup ident. Auf ganz \bgroup\color{demo}$ \{0,\dots,n-1\}$\egroup kann somit \bgroup\color{demo}$ \pi$\egroup als Zusammensetzung der Element-fremden Zyklen, die zu der Zerlegung in invariante Teilmengen gehören, beschrieben werden. Das Inverse zu einen Zyklus \bgroup\color{demo}$ (a_1,a_2,\dots,a_n)$\egroup in \bgroup\color{demo}$ \mathcal{S}_n$\egroup ist offensichtlich durch den umgekehrt durchlaufenen Zyklus \bgroup\color{demo}$ (a_n,a_{n-1},\dots,a_2,a_1)$\egroup gegeben.

Besonders einfach Zyklen sind jene der Länge 2, d.h. der Form \bgroup\color{demo}$ (j,j')$\egroup, wo also \bgroup\color{demo}$ \pi$\egroup nur die Position der beiden Elemente \bgroup\color{demo}$ j$\egroup und \bgroup\color{demo}$ j'$\egroup vertauscht. Diese heißen Transpositionen. Und am einfachsten ist, wenn dies benachbarte Elemente sind, also \bgroup\color{demo}$ j'=j+1$\egroup 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 \bgroup\color{demo}$ (1,2,3,\dots,n)$\egroup läßt sich wie folgt in ein Produkt von Transpositionen zerlegen:

\bgroup\color{demo}$\displaystyle (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).
$\egroup

oder allgemeiner

\bgroup\color{demo}$\displaystyle (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).
$\egroup

Idee dabei ist, daß um ein Element vom letzten Platz \bgroup\color{demo}$ n$\egroup an den ersten Platz \bgroup\color{demo}$ 1$\egroup zu bekommen (und alle anderen um einen Platz nach hinten rücken zu lassen) man zuerst das Element auf Platz \bgroup\color{demo}$ n$\egroup und \bgroup\color{demo}$ n-1$\egroup Platz tauschen läßt, danach jene nunmehr auf Platz \bgroup\color{demo}$ n-1$\egroup und \bgroup\color{demo}$ n-2$\egroup 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 \boxed{n}
nach 1. Schritt 1 2 ... n-2 \boxed{n} n-1
nach 2. Schritt 1 2 ... \boxed{n} n-2 n-1
&vellip#vdots;
nach (n-2). Schritt 1 2 \boxed{n} ... n-2 n-1
nach (n-1). Schritt 1 \boxed{n} 2 ... n-2 n-1
nach n. Schritt \boxed{n} 1 2 ... n-2 n-1

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

\bgroup\color{demo}$\displaystyle (k,j)
= (j,j-1,\dots,k+3,k+2,k+1)\o (k,k+1,k+2,k+3,\dots,j-1,j).
$\egroup

In der Tat ist nach obigen

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

und damit

$\displaystyle (k,j)$ $\displaystyle =(j,k)$    
  $\displaystyle = (k+1,k+2,k+3,\dots,j-1,j)^{-1}\o (k+1,k+2,k+3,\dots,j-1,j,k)$    
  $\displaystyle = (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:

\includegraphics[scale=0.6]{pic-1034}

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 \bgroup\color{demo}$ (1,3)$\egroup und \bgroup\color{demo}$ (1,4)$\egroup nach obiger Formel, \bgroup\color{demo}$ (1,3)=(3,2)\o (1,2,3)=(3,2)\o (1,2)\o (2,3)$\egroup und \bgroup\color{demo}$ (1,4)=(4,3,2)\o (1,2,3,4)=(4,3)\o (3,2)\o (1,2)\o (2,3)\o (3,4)$\egroup. 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 \bgroup\color{demo}$ \pi$\egroup versteht man ein Paar \bgroup\color{demo}$ (i,j)$\egroup mit \bgroup\color{demo}$ i<j$\egroup aber \bgroup\color{demo}$ \pi(i)>\pi(j)$\egroup. Eine Permutation \bgroup\color{demo}$ \pi$\egroup heißt gerade und man schreibt \bgroup\color{demo}$ \operatorname{sgn}(\pi)=+1$\egroup, wenn die Anzahl all ihrer Inversionen gerade ist. Andernfalls heißt sie ungerade und man schreibt \bgroup\color{demo}$ \operatorname{sgn}(\pi)=-1$\egroup.


3.28 Beispiel.
Die Inversionen der Permutation

\bgroup\color{demo}$\displaystyle \pi = \begin{pmatrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & 2 & 1 & 4 & 5 & 6 & 3 \end{pmatrix}$\egroup

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

\bgroup\color{demo}$\displaystyle \begin{array}{c\vert c\vert c\vert c\vert c\ve...
...& - & + \\
5 & & & & & & & + \\
6 & & & & & & & \\
\hline
\end{array}$\egroup

Die Anzahl der Inversionen ist somit 4 und \bgroup\color{demo}$ \pi$\egroup ist gerade.




3.29 Lemma.
Es sei \bgroup\color{demo}$ \pi$\egroup eine Permutation und \bgroup\color{demo}$ \sigma $\egroup eine Transposition.

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

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




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 \bgroup\color{demo}$ (a_0,a_2,\dots,a_{k-1},a_k)$\egroup ist \bgroup\color{demo}$ (-1)^k$\egroup. Insbesonders ist \bgroup\color{demo}$ \operatorname{sgn}(\pi\o\sigma )=\operatorname{sgn}(\pi)\cdot\operatorname{sgn}(\sigma )$\egroup für alle Permutationen \bgroup\color{demo}$ \sigma $\egroup und \bgroup\color{demo}$ \pi$\egroup. Und die Menge \bgroup\color{demo}$ \mathcal{A}_n$\egroup der geraden Permutationen der Ordnung \bgroup\color{demo}$ n$\egroup bildet eine Untergruppe von \bgroup\color{demo}$ \mathcal{S}_n$\egroup, 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 \bgroup\color{demo}$ (a_0,a_2,\dots,a_{k-1},a_k)$\egroup in \bgroup\color{demo}$ (a_0,a_1)\o\cdots\o (a_{k-1},a_k)$\egroup zerlegt werden kann, also in \bgroup\color{demo}$ k$\egroup viele Transpositionen, folgt auch die zweite.

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

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


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

\bgroup\color{demo}$\displaystyle f(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)})
$\egroup

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

\bgroup\color{demo}$\displaystyle \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
$\egroup

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

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

\bgroup\color{demo}$\displaystyle \operatorname{sgn}(\pi)\,f(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)})
$\egroup

für alle Permutationen \bgroup\color{demo}$ \pi\in\mathcal{S}_n$\egroup und alle \bgroup\color{demo}$ x_1,\dots,x_n\in X$\egroup gilt, d.h. sich der Funktionswert nur um ein Vorzeichen (nämlich jenes der Permutation) ändert, wenn man die Variablen vertauscht. Z.B. ist \bgroup\color{demo}$ f(x_1,x_2):=x_1-x_2$\egroup alternierend, denn für \bgroup\color{demo}$ \pi=(1,2)$\egroup ist \bgroup\color{demo}$ 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)$\egroup. Allgemeiner ist \bgroup\color{demo}$ f(x_1,x_2,x_3):=(x_1-x_2)\,(x_2-x_3)\,(x_1-x_3)$\egroup alternierend, denn z.B. für \bgroup\color{demo}$ \pi=(1,2)$\egroup 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 \bgroup\color{demo}$ f:(x_1,\dots,x_n)\mapsto\prod_{i<j}(x_i-x_j)$\egroup alternierend.

Andreas Kriegl 2002-02-01