Aus Wikibooks

Inhaltsverzeichnis 1 Einleitung 2 Natürliche Zahlen 2.1 Axiomensystem von Peano 2.2 Vollständige Induktion 2.3 Addition und Multiplikation 2.3.1 Rechenregeln 2.4 Beispiel n-te Potenz 2.5 Ordnung 2.6 Primzahlen

[Bearbeiten] Einleitung

Jeder kommt bereits in frühester Kindheit mit Zahlen in Berührung und hat, zumindest von den natürlichen Zahlen, eine sehr genaue Vorstellung. Für mathematische Zwecke ist es aber erforderlich, die Struktur von Zahlenmengen eindeutig festzulegen. Dies beantwortet leider nicht die Frage was Zahlen sind, beschreibt aber ihre typischen Merkmale. Diese mathematischen Merkmale müssen natürlich in Übereinstimmung mit den intuitiven Vorstellungen sein. Andererseits muss die Beschreibung so genau sein, dass es eben nur eine Zahlenmenge mit genau diesen Eigenschaften gibt, d. h. die Charakterisierung muss in diesem Sinne vollständig sein.

[Bearbeiten] Natürliche Zahlen

Der italienische Mathematiker G. Peano hat eine solche formale Beschreibung für die natürlichen Zahlen aufgestellt, die sich an dem Vorgang des Zählens orientiert und davon ausgeht, dass es einen Zählanfang gibt und eine Vorschrift, die jeder natürlichen Zahl einen Nachfolger zuordnet und dass diese beiden Eigenschaften die natürlichen Zahlen vollständig beschreiben. Formal lässt sich das Axiomensystem wie folgt angeben:

[Bearbeiten] Axiomensystem von Peano

(N0)	ist eine Menge
(N1)
(N2)	Es gibt eine injektive Abbildung , für die gilt:
(N2)	(Induktionsaxiom) Gelten für eine Teilmenge die beiden Eigenschaften: 1 ∈ M und ∀ m ∈ M gilt: Aus m ∈ M folgt s(m) ∈ M     dann folgt

Die Abbildung s ordnet zwei verschiedenen natürlichen Zahlen auch zwei verschiedene Nachfolger (s ist injektiv) zu und diese Nachfolger können nicht die 1 sein.

Definition

(n + 1):= s(n) heißt der Nachfolger von n und n nennt man den Vorgänger von (n + 1)

Als ein Beispiel für die Anwendung des Induktionsaxioms soll nun folgender Satz gezeigt werden:

Satz

s(n) ≠ n für jedes

Beweis

Sei N := { n ∈ | s(n) ≠ n }. Dann gilt:

1 ∈ N	denn:	dann falls 1 ∉ N würde gelten s(1)=1 also , was ein Widerspruch wäre.
Aus n ∈ N folgt s(n) ∈ N	denn:	Falls für ein  n ∈ N   s(n) ∉ N  gelten würde, folgt s(s(n))=s(n), also wegen der Injektivität von s: s(n)=n, was aber nach Voraussetzung ein Widerspruch ist.

Aus dem Induktionsaxiom folgt und das beweist den Satz!

Schreibweisen

Für die Menge der natürlichen Zahlen sind folgende Schreibweisen üblich: .

Die Menge der natürlichen Zahlen ist hier ohne die NULL definiert worden und wird im Folgenden auch so verwendet.

Menge der natürlichen Zahlen einschließlich der "Null"

Die Menge der natürlichen Zahlen ist eine ideale Indexmenge und wird für Abzählbarkeitsaussagen (s. Mächtigkeit) verwendet.

[Bearbeiten] Vollständige Induktion

Satz

Sei eine Eigenschaft, die auf natürliche Zahlen zutrifft oder auch nicht, d. h es gilt "" oder "nicht " für alle .

Wenn

1. Induktionsanfang:  und
2. Induktionsschritt:  ,

so gilt für alle .

Beweis

Man wendet einfach das obige Induktionsaxiom auf die Menge M:= { n | n ∈ } an.

Beweise über Eigenschaften von natürlichen Zahlen erfolgen häufig mit Hilfe der gerade besprochenen vollständigen Induktion. Diese Beweisführung ist Ihnen wahrscheinlich bekannt. Sie erfolgt in zwei Schritten.

1. Induktionsanfang: Es wird gezeigt, dass die behauptete Eigenschaft für 1 ∈ gilt.
2. Induktionsschritt: Es wird die Gültigkeit der Eigenschaft für n ∈ vorausgesetzt. Mit Hilfe dieser Voraussetzung zeigt man, dass auch sie auch für s(n) gilt.

Der Satz über die vollständige Induktion sagt nun gerade, dass diese Eigenschaft dann für die Menge gilt.

[Bearbeiten] Addition und Multiplikation

Multiplikation und Addition werden nun als Abbildung von einer " Relation auf " nach rekursiv (oder durch vollständige Induktion) definiert. Es werden also Bedingungen definiert, wie man schrittweise die Summe oder das Produkt zu bilden hat.

Genau genommen ist es nicht nur eine Definition sondern ein Satz, denn die Existenz dieser Abbildungen kann nicht einfach vorausgesetzt werden, sondern ist nachzuweisen. In einem zweiten Schritt ist dann noch zu zeigen, dass es, wie allgemein im Alltagsleben unterstellt, jeweils nur genau eine Abbildung für Addition und Multiplikation gibt.

Definition und Satz

Sei +: und für alle m,n ∈ gelte:

(m,n) → +(m,n) =: m+n mit

1. m+1 = s(m) und
2. m+s(n) = s(m+n)

und sei · : und für alle m,n ∈ gelte:

(m,n) → · (m,n) =: mn mit

1. m1 = m und
2. ms(n) = (mn)+m

Es gibt genau eine Abbildung + (genannt Addition) und genau eine Abbildung · (genannt Multiplikation) mit diesen Eigenschaften.

Beweis

Der Beweis dieses "selbstverständlichen" Satzes ist nicht besonders trival. Er wird hier beispielhaft für die Addition gezeigt. Der Beweis für die Multiplikation verläuft genauso und wird dem Leser zur Übung empfohlen.

Es sind zwei Dinge zu zeigen: die Existenz der Addition und die Eindeutigkeit. Die Eindeutigkeitsaussage wird für den Beweis der Existenz benötigt und daher zuerst gezeigt.

 

1. Eindeutigkeit der Addition

Hilfssatz

Zu einem z ∈ gibt es höchstens eine Abbildung f für die gilt:

mit   f(1) = z und f _° s = s _° f

 

Der Beweis dieses Hilfssatzes erfolgt über das Induktionsaxiom:

Sei eine Abbildung für die gilt: g(1) = z und g _° s = s _° g.

Zu beweisen ist, dass f = g gilt.

Definition- und Bildbereich von f und g sind gleich.

Sei N := { n ∈ | f(n) = g(n) }.

Dann gilt:

f(1) = z = g(1) also 1∈N

Sei n∈N. Dann gilt f(n) = g(n) und es folgt:

f(s(n)) = (f _° s)(n) = (s _° f) (n) = s(f(n)) = s(g(n)) = (s _° g)(n) = (g _° s)(n) = g(s(n)), also gilt auch s(n)∈N.

Mit dem Induktionsaxiom gilt N = , d. h. f(n) = g(n) für alle n∈, daraus folgt f=g, was die Eindeutigkeit zeigt.

 

Mit diesem Hilfssatz ist es einfach zu zeigen, dass es höchstens eine Möglichkeit gibt die Addition wie oben zu definieren. Sei also die oben definierte Addition gegeben und sei n∈ eine beliebige Zahl. Dann definiert

mit f_n (x) := n+x

eine Abbildung für die gilt:

f_n (1) = n+1 = s(n) und f_n (s(x)) = n+s(x)=s(n+x)= s(f_n(x)).

Mit dem Hilfssatz folgt, dass es für jedes n∈ höchstens eine solche Abbildung f_n gibt. Und dies zeigt, dass die oben definierte Addition eindeutig ist, wenn es sie geben sollte.

 

2. Existenz der Addition

Zunächst zeigt man mit Hilfe des Induktionsaxioms, dass für jedes n∈ genau eine Abbildung mit:

mit

f_n (1) = s(n) und f_{n °} s = s _°f_n existiert.

Mit den Funktionen f_n lässt sich die Addition wie folgt definieren:

n+m := f_n (m) für alle n,m∈, denn für alle n,m∈ gilt: n+1 = s(n) = f_n (1) und n+s(m) = f_n (s(m)) = s(n+m).

 

Hilfssatz

Für jedes n∈ gibt es genau eine Abbildung mit

mit f_n (1) = s(n) und f_{n °} s = s _°f_n

 

Der Beweis erfolgt wieder mit Hilfe des Induktionsaxioms:

 

Für n=1 definiert man   mit f₁ = s.

Dann gilt: f₁(1)=s(1) und f_1° s = s_°s =s _°f₁

Diese Abbildung f₁ existiert und erfüllt die o. g.Bedingungen. Der Hilfssatz bei der Eindeutigkeitsaussage zeigt weiter, dass es höchstens eine solche Abbildung gibt (mit s(1)=z).

 

Sei also ein n∈ vorgegeben für das gilt: f_n (1) = s(n) und f_{n °} s = s _°f_n.

Für eine Funktion f_s(n) := s _° f_n gilt:

f_s(n) (1) = s _° f_n (1) = s(f_n(1)) = s (s(n))   (da nach Voraussetzung f_n (1) = s(n) gilt) und

f_{s(n) °} s = (s _° f_n)_° s = s _° (f_{n °} s) = s _° (s _° f_n))= s _° f_s(n)

Nach dem Hilfssatz beim Beweis der Eindeutigkeit (z=s(n)) gibt es höchstens eine Abbildung f_s(n) und da nach Voraussetzung f_n existiert, also genau eine Abbildung. Damit ist die Existenz und Eindeutigkeit der Abbildung auch für n+1 bewiesen und nach dem Induktionsaxiom für alle n∈.

[Bearbeiten] Rechenregeln

Satz

Für alle x, y, z ∈ gilt:

1. (x + y) + z = x + (y + z)	(Assoziativität)
2. x + y = y + x	(Kommutativität)
3. (xy) z = x (yz)	(Assoziativität)
4. x (y + z) = (xy) + (xz)	(Distributivität)

Beweis

Die Beweise lassen sich mit Hilfe des Induktionsaxioms führen.

[Bearbeiten] Beispiel n-te Potenz

Durch vollständige Induktion lässt sich folgender Satz leicht zeigen:

Satz

Sei R eine Menge, f: → R eine Abbildung und y ein Element von R. Dann gibt es genau eine Abbildung g : → R mit

1. g(1) = y und
2. g(n+1) = f ( g(n), n ) für alle n ∈

Mit diesem Satz lassen sich nun einfach die Existenz und Eindeutigkeit der n-ten Potenz nachweisen:

Setzt man ( ist die Menge der reellen Zahlen)

und für

die Abbildung

    für ein,

so liefert obiger Satz eine Abbildung g mit

1. g:
2. g(n) := yⁿ
3. g(1) = y = y¹
4. g(n+1) = f ( g(n) , n ) = g(n) y = yⁿy = yⁿ⁺¹ für alle n.

[Bearbeiten] Ordnung

Mit Hilfe der Addition lässt sich nun sehr einfach eine weitere Struktur auf den natürlichen Zahlen nachweisen:

Definition - "natürliche" Ordnung

Für alle x,y ∈ definiert man:

1. x < y (lies: x kleiner y) oder
   y > x (lies: y größer x)
   wenn es ein z ∈ gibt mit x + z = y
    
2. x ≤ y (lies: x kleiner-gleich y) oder
   y ≥ x (lies: y größer-gleich x)
   wenn x=y oder x < y.

Satz

1. Die Relation ≤ , d. h. {(x,y) ∈ | x ≤ y} ist eine Ordnungsrelation auf
2. (, ≤ ) ist linear geordnet
3. Für alle x.y,z ∈ git:
   x ≤ y   ⇒   x + z  ≤  y + z und
   x ≤ y   ⇒   xz  ≤  yz.
   Die Ordnungsrelation ist also verträglich mit der Addition und Multiplikation.

Hinweise zum Beweis

Reflexivität und Antisymmetrie sind durch Rechnungen einfach nachzuweisen.

Die übrigen Beweise verwenden wieder das Induktionsaxiom. Beispielsweise kann man für den Beweis der linearen Ordnung (zu 2.) für ein vorgegebenes x eine Menge
M_x := { n ∈ | x ≤ n oder n ≤ x ] definieren und zeigen, dass M_x = gilt. Beim Nachweis der Antisymmetrie unterstützt folgender Hilfssatz: ∀ x,y ∈  : x ≤ y   ⇒   x ≠ y" , der ebenfalls über das Induktionsaxiom bewiesen werden kann. Die Ausführung der Beweise ist Ihnen zur Übung überlassen.

Wohlordnungssatz

ist mit der natürlichen Ordnung wohlgeordnet.

Dieser Satz besagt, dass jede nichtleere Teilmenge M von ein kleinstes Element, min M, enthält. Dieser Satz mag Ihnen reichlich überflüssig vorkommen. Bedenken Sie aber, dass für allgemeine Mengen die Aussagen Zornsches Lemma, Wohlordnungssatz und Auswahlaxiom äquivalent und von großer Tragweite sind.

Hinweise zum Beweis

Wieder wird das Induktionsaxiom verwendet, diesmal wird aber folgende Eigenschaft induktiv nachgewiesen:
"Jede Teilmenge M_n von , die die Zahl n enthält, besitzt ein kleinstes Element".

Für M₁ ist die Behauptung sicher richtig, da 1 ∈M₁.

Die Behauptung gelte nun für ein n ∈ .

Zu zeigen ist, dass "jede Teilmenge M_n+1 von , kleinstes Element besitzt". Man unterscheidet zwei Fälle:

1. Fall: Für alle x ∈ M_n+1 gilt n+1 ≤ x und

2. Fall: Es gibt ein x ∈ M_n+1 mit x < n+1.

Der erste Fall ist klar, für den Beweis des zweiten Falls verwendet man die Injektivität von s und die Induktionsvoraussetzung.

Da jede nichtleere Teilmenge von ein n∈ enthält ist der Satz bewiesen.

[Bearbeiten] Primzahlen

Eine wichtige Teilmenge der Natürlichen Zahlen sind die Primzahlen. Primzahlen sind alle natürliche Zahlen mit genau zwei Teilern.

►___weiter: Ganze Zahlen ▲___zum Inhaltsverzeichnis ◄___zurück: Relationen