Kurs:Mathematik für Anwender (Osnabrück 2023-2024)/Teil I/Vorlesung 2/latex
\setcounter{section}{2}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller32.jpg} }
\end{center}
\bildtext {Vorli begleitet dich bei den Vorlesungen. Das hilft sehr, denn Vorli sorgt für eine gute Balance aus Energie und Entspannung.} }
\bildlizenz { Waeller32.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Quantoren}
Betrachten wir nochmal die beiden Beispielaussagen
\einrueckung{Marsmenschen sind grün} und \einrueckung{Ich fresse einen Besen,}
und schauen uns die innere Struktur genauer an. In der ersten Aussage wird einer gewissen Art von Lebewesen eine Eigenschaft zugesprochen, so wie wenn man sagt, dass Geparden schnell sind oder dass Faultiere faul sind. Damit kann man meinen, dass Marsmenschen \anfuehrung{im Normalfall}{} oder \anfuehrung{fast immer}{} grün sind, oder aber im strengeren Sinn, dass wirklich alle Marsmenschen grün sind. In der Mathematik interessiert man sich für Aussagen, die ohne Ausnahmen gelten
\zusatzklammer {wobei man allerdings in einer mathematischen Aussage die Ausnahmen auch explizit machen kann} {} {,}
sodass wir die Aussage im strengen Sinn verstehen wollen. Es handelt sich um eine sogenannte \stichwort {Allaussage} {.} In ihr kommen zwei \stichwort {Prädikate} {}
\zusatzklammer {Eigenschaften, Attribute} {} {}
vor, nämlich einerseits, ein Marsmensch zu sein, andererseits, grün zu sein. Ein Prädikat $P$ ist etwas, was einem Objekt
\zusatzklammer {grammatisch spricht man von einem Subjekt} {} {,}
einem Gegenstand, einem Element zukommen oder nicht zukommen kann. Ein Prädikat ist für sich genommen keine Aussage; aus einem Prädikat kann man aber grundsätzlich auf zwei verschiedene Arten eine Aussage machen, indem man nämlich einerseits
\zusatzklammer {durch \stichwort {einsetzen} {}} {} {}
für ein konkretes Objekt $a$ die Aussage
\mathdisp {P(a)} { }
bildet, die bedeutet, dass das Objekt $a$ die Eigenschaft $P$ besitzt, was wahr sein kann oder eben auch nicht. Andererseits kann man aus $P$ durch \stichwort {Quantifizierung} {} eine Aussage gewinnen. So kann man die Aussage bilden, dass alle\zusatzfussnote {Andere Formulierungen sind: jedes, ein beliebiges, irgendein Objekt/Element aus der Grundmenge. Wenn die Grundmenge räumlich ist, so spricht man auch von überall, wenn sie zeitlich ist, so spricht man von immer, stets, ...} {.} {} Objekte
\zusatzklammer {typischerweise aus einer bestimmten Grundmenge} {} {}
die Eigenschaft $P$ haben, was wiederum wahr oder falsch sein kann. Das drückt man formallogisch durch
\mathdisp {\forall x P(x)} { }
aus. Das Symbol
\mathdisp {\forall} { }
ist eine abkürzende Schreibweise für \anfuehrung{für alle}{\zusatzfussnote {Man kann mit einiger Berechtigung sagen, dass die Vokabeln \anfuehrung{für alle}{} und \anfuehrung{es gibt}{} die wichtigsten Formulierungen der Mathematik sind} {.} {},} oder \anfuehrung{für jedes}{} und besitzt ansonsten keine tiefere Bedeutung. Es wird \stichwort {Allquantor} {} genannt. Die obige Marsmenschenaussage kann man als
\mathdisp {\forall x (M(x) \rightarrow G(x))} { }
schreiben. Das bedeutet, dass für alle Objekte ohne weitere Einschränkung gilt: wenn es sich um einen Marsmenschen handelt
\zusatzklammer {wenn also $M$ zutrifft} {} {,}
dann ist er auch grün. Für jedes $x$ steht in der großen Klammer eine Aussage in der Form einer Implikation, die eben besagt, dass wenn der Vordersatz wahr ist, dann auch der Nachsatz wahr sein muss.
Die zweite Beispielaussage kann bedeuten, dass ich genau einen Besen fresse oder aber mindestens einen Besen. Die Wortbedeutung des unbestimmten Artikels ist nicht eindeutig, in einer Aussage wie \anfuehrung{eine Pflanze braucht Wasser}{} bedeutet \anfuehrung{eine}{} sogar \anfuehrung{alle}{.} In der Mathematik bedeutet es fast immer \anfuehrung{mindestens einen}{.} Die Besenaussage kann man also paraphrasieren als
\einrueckung{Es gibt einen Besen, den ich fresse.}
Dies ist eine \stichwort {Existenzaussage} {\zusatzfussnote {Neben \anfuehrung{es gibt}{} trifft man auf Formulierungen wie \anfuehrung{es existiert}{,} \anfuehrung{man findet}{,} \anfuehrung{man kann finden}{.} Wenn die Existenz eines Objektes bekannt ist, so wird in einer mathematischen Argumentation häufig ein solches Element \anfuehrung{hergenommen}{,} irgendwie bezeichnet und dann weiterverarbeitet} {.} {.}}
Eine formallogische Repräsentierung ist
\mathdisp {\exists x (B(x) \wedge F(x))} { , }
wobei
\mathl{B(x)}{} bedeutet, dass das Objekt $x$ ein Besen ist und wobei
\mathl{F(x)}{} bedeutet, dass ich dieses $x$ fresse. Man könnte genauso gut
\mathdisp {\exists x (F(x) \wedge B(x))} { }
schreiben. Das Zeichen
\mathdisp {\exists} { }
wird \anfuehrung{es gibt}{} oder \anfuehrung{es existiert}{} gesprochen und wird der \stichwort {Existenzquantor} {}
\zusatzklammer {oder \stichwort {Existenzoperator} {}} {} {}
genannt.
Eine Allaussage behauptet, dass ein gewisses Prädikat allen Objekten
\zusatzklammer {aus einer gewissen Grundmenge} {} {}
zukommt. Wie alle Aussagen kann dies wahr oder falsch sein. Eine Allaussage ist genau dann falsch, wenn es mindestens ein Objekt
\zusatzklammer {aus der Grundmenge} {} {}
gibt, dem das Prädikat nicht zukommt. Daher sind die beiden Quantoren, also der Allquantor und der Existenzquantor, über die Negation eng miteinander verknüpft und lassen sich gegenseitig ersetzen, und zwar gelten die Regeln
\mathdisp {\neg ( \forall x P(x)) \text{ ist gleichbedeutend mit } \exists x ( \neg P(x))} { , }
\mathdisp {\neg ( \exists x P(x)) \text{ ist gleichbedeutend mit } \forall x ( \neg P(x))} { , }
\mathdisp {\forall x P(x) \text{ ist gleichbedeutend mit } \neg ( \exists x ( \neg P(x)))} { }
und
\mathdisp {\exists x P(x) \text{ ist gleichbedeutend mit } \neg ( \forall x ( \neg P(x)))} { . }
Neben einstelligen Prädikaten wie
\mathl{P(x)}{} gibt es auch mehrstellige Prädikate der Form
\mathdisp {P(x,y) \text{ oder } Q(x,y,z) \text{ etc. }} { , }
die eine Beziehung zwischen mehreren Objekten ausdrücken, wie z.B. \anfuehrung{ist verwandt mit}{,} \anfuehrung{ist größer als}{,} \anfuehrung{sind Eltern von}{} u.s.w. Entsprechend kann dann über die verschiedenen Variablen quantifiziert werden, d.h. man hat mit Ausdrücken der Form
\mathdisp {\forall x (\exists y P(x,y)),\, \exists x (\forall y P(x,y)) ,\, \forall x (\exists y (\forall z Q(x,y,z))) \text{ usw. }} { }
zu tun.
Die Variablenbezeichnung in einer quantifizierten Aussage ist grundsätzlich unwichtig, d.h. es ist egal, ob man
\mathl{\forall a P(a)}{} oder
\mathl{\forall t P(t)}{} schreibt. Man darf dabei aber nur Variablennamen
\zusatzklammer {also Buchstaben} {} {}
verwenden, die im gegenwärtigen Kontext nicht schon anderweitig verwendet sind.
Die Logik, die sich mit quantifizierten Aussagen auseinandersetzt, heißt \stichwort {Prädikatenlogik} {} oder \stichwort {Quantorenlogik} {.} Wir werden sie nicht systematisch entwickeln, da sie in der Mathematik als Mengentheorie auftritt. Statt
\mathl{P(x)}{,} dass also ein Prädikat einem Objekt zukommt, schreiben wir
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ P
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei dann $P$ die Menge aller Objekte bezeichnet, die diese Eigenschaft haben. Mehrstellige Prädikate treten in der Mathematik als Relationen auf.
\zwischenueberschrift{Zahlen}
Ohne weitere Begründung können wir sagen, dass sich die Mathematik auch mit Zahlen beschäftigt. Wir arbeiten mit den folgenden Mengen, deren Kenntnis wir voraussetzen.
\mavergleichskettedisp
{\vergleichskette
{\N
}
{ =} { \{0,1,2, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die Menge der \stichwort {natürlichen Zahlen} {}
\zusatzklammer {mit der $0$} {} {.}
\mavergleichskettedisp
{\vergleichskette
{ \Z
}
{ =} {\{\ldots, -2,-1, 0,1,2, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die Menge der \stichwort {ganzen Zahlen} {,}
\mavergleichskettedisp
{\vergleichskette
{\Q
}
{ =} {{ \left\{ a/b \mid a \in \Z , \, b \in \Z \setminus \{0\} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die Menge der \stichwort {rationalen Zahlen} {} und die Menge der \stichwort {reellen Zahlen} {} $\R$.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Real_number_line.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Real number line.svg } {} {Phrood} {Commons} {PD} {}
Diese Mengen sind mit den natürlichen Operationen wie Addition und Multiplikation versehen, an deren Eigenschaften wir bald erinnern werden. Die reellen Zahlen stellen wir uns als die Punkte einer Geraden vor, auf der sich auch die zuvor genannten Zahlenmengen befinden. Zugleich kann man $\R$ als die Menge aller \zusatzklammer {vor dem Komma endlichen, nach dem Komma eventuell unendlichen} {} {} Ziffernfolgen im Dezimalsystem auffassen. Wir werden im Laufe der Vorlesung alle entscheidenden Eigenschaften der reellen Zahlen kennenlernen \zusatzklammer {die sogenannten \stichwort {Axiome} {} der reellen Zahlen} {} {,} aus denen man alle anderen Eigenschaften logisch herleiten kann und dann auch diese vorläufigen Sichtweisen präzisieren.
\zwischenueberschrift{Induktion}
Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man jede natürliche Zahl ausgehend von der $0$ durch den Zählprozess \zusatzklammer {das sukzessive Nachfolgernehmen} {} {} erreichen kann. Daher können mathematische Aussagen, die von natürlichen Zahlen abhängen, mit dem Beweisprinzip der \stichwort {vollständigen Induktion} {} bewiesen werden. Das folgende Beispiel soll an dieses Argumentationsschema heranführen.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {4Geraden6Schnittpunkte.png} }
\end{center}
\bildtext {} }
\bildlizenz { 4Geraden6Schnittpunkte.png } {} {Mgausmann} {CC-by-sa 4.0} {} {}
Wir betrachten in der Ebene $E$ eine Konfiguration von $n$ Geraden und fragen uns, was die maximale Anzahl an Schnittpunkten ist, die eine solche Konfiguration haben kann. Dabei ist es egal, ob wir uns die Ebene als einen $\R^2$
\zusatzklammer {eine kartesische Ebene mit Koordinaten} {} {}
oder einfach elementargeometrisch vorstellen, wichtig ist im Moment allein, dass sich zwei Geraden in genau einem Punkt schneiden können oder aber parallel sein können. Wenn $n$ klein ist, so findet man relativ schnell die Antwort.
\wertetabellesiebenausteilzeilen { $n$ }
{\mazeileundfuenf {0} {1} {2} {3} {4} }
{\mazeileundzwei {5} {n} }
{ $S(n)$ }
{\mazeileundfuenf {0} {0} {1} {3} {6} }
{\mazeileundzwei {?} {?} }
Doch schon bei etwas größerem $n$
\zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{n
}
{ = }{5,10, \ldots
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {?} {}
kann man ins Grübeln kommen, da man sich die Situation irgendwann nicht mehr präzise vorstellen kann. Aus einer präzisen Vorstellung wird eine Vorstellung von vielen Geraden mit vielen Schnittpunkten, woraus man aber keine exakte Anzahl der Schnittpunkte ablesen kann. Ein sinnvoller Ansatz zum Verständnis des Problems ist es, sich zu fragen, was eigentlich passiert, wenn eine neue Gerade hinzukommt, wenn also aus $n$ Geraden $n+1$ Geraden werden. Angenommen, man weiß aus irgendeinem Grund, was die maximale Anzahl der Schnittpunkte bei $n$ Geraden ist, im besten Fall hat man dafür eine Formel. Wenn man dann versteht, wie viele neue Schnittpunkte maximal bei der Hinzunahme von einer neuen Geraden hinzukommen, so weiß man, wie die Anzahl der maximalen Schnittpunkte von
\mathl{n+1}{} Geraden lautet.
Dieser Übergang ist in der Tat einfach zu verstehen. Die neue Gerade kann höchstens jede der $n$ alten Geraden in genau einem Punkt schneiden, deshalb kommen höchstens $n$ neue Schnittpunkte hinzu. Wenn man die neue Gerade so wählt, dass sie zu keiner der gegebenen Geraden parallel ist
\zusatzklammer {was möglich ist, da es unendlich viele Richtungen gibt} {} {}
und ferner so wählt, dass die neuen Schnittpunkte von den schon gegebenen Schnittpunkten der Konfiguration verschieden sind
\zusatzklammer {was man erreichen kann, indem man die neue Gerade parallel verschiebt, um den alten Schnittpunkten auszuweichen} {} {,}
so erhält man genau $n$ neue Schnittpunkte. Von daher ergibt sich die
\zusatzklammer {vorläufige} {} {}
Formel
\mavergleichskettedisp
{\vergleichskette
{S(n+1)
}
{ =} { 1+2+3 + \cdots + n-2 + n-1 +n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
bzw.
\mavergleichskettedisp
{\vergleichskette
{S(n)
}
{ =} { 1+2+3 + \cdots + n-3 + n-2 + n-1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
also einfach die Summe der ersten $n-1$ natürlichen Zahlen.
}
Im vorstehenden Beispiel liegt eine Summe vor, wobei die Anzahl der Summanden selbst variieren kann. Für eine solche Situation ist das \stichwort {Summenzeichen} {} sinnvoll. Für gegebene reelle Zahlen
\mathl{a_1 , \ldots , a_n}{} bedeutet
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n a_k
}
{ \defeq} { a_1 + a_2 + \cdots + a_{n-1} + a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei hängen im Allgemeinen die $a_k$ in einer formelhaften Weise von $k$ ab, beispielsweise ist im Beispiel
\mavergleichskette
{\vergleichskette
{ a_k
}
{ = }{ k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
es könnte aber auch etwas wie
\mavergleichskette
{\vergleichskette
{ a_k
}
{ = }{ 2k+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{a_k
}
{ = }{ k^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorliegen. Der $k$-te Summand der Summe ist jedenfalls $a_k$, dabei nennt man $k$ den \stichwort {Index} {} des Summanden. Entsprechend ist das \stichwort {Produktzeichen} {} definiert, nämlich durch
\mavergleichskettedisp
{\vergleichskette
{ \prod_{k = 1}^n a_k
}
{ \defeq} { a_1 \cdot a_2 { \cdots } a_{n-1} \cdot a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\inputbeispiel{}
{
Wir möchten für die Summe der ersten $n$ Zahlen, die die maximale Anzahl der Schnittpunkte in einer Konfiguration aus $n+1$ Geraden angibt, eine einfachere Formel angeben. Und zwar behaupten wir, dass
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} { { \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für kleinere Zahlen $n$ stimmt dies aus dem einfachen Grund, dass links und rechts dasselbe herauskommt. Um die Gleichung allgemein zu beweisen, überlegen wir uns, was links und was rechts passiert, wenn wir das $n$ um $1$ erhöhen, so wie wir in
Beispiel 2.1
die Geradenkonfiguration um eine zusätzliche Gerade verkompliziert haben. Auf der linken Seite kommt einfach der zusätzliche Summand $n+1$ hinzu. Auf der rechten Seite haben wir den Übergang von
\mathl{{ \frac{ n(n+1) }{ 2 } }}{} nach
\mathl{{ \frac{ (n+1)(n+1+1) }{ 2 } }}{.} Wenn wir zeigen können, dass die Differenz zwischen diesen beiden Brüchen ebenfalls
\mathl{n+1}{} ist, so verhält sich die rechte Seite genauso wie die linke Seite. Dann kann man so schließen: die Gleichung gilt für die kleinen $n$, etwa für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Durch den Differenzenvergleich gilt es auch für das nächste $n$, also für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
durch den Differenzenvergleich gilt es für das nächste $n$, u.s.w. Da dieses Argument immer funktioniert, und da man jede natürliche Zahl irgendwann durch sukzessives Nachfolgernehmen erreicht, gilt die Formel für jede natürliche Zahl.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Domen-indukto.gif} }
\end{center}
\bildtext {Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.} }
\bildlizenz { Domen-indukto.gif } {Joachim Mohr} {} {Commons} {CC-by-sa 3.0} {}
Die folgende Aussage begründet das Prinzip der vollständigen Induktion.
\inputfaktbeweis
{Zahlentheorie/Beweisverfahren/Induktionsprinzip/Fakt}
{Satz}
{}
{
\faktsituation {Für jede
\definitionsverweis {natürliche Zahl}{}{}
$n$ sei eine Aussage
\mathl{A(n)}{} gegeben.}
\faktvoraussetzung {Es gelte
\aufzaehlungzwei {$A(0)$ ist wahr.
} { Für alle $n$ gilt: wenn
\mathl{A(n)}{} gilt, so ist auch
\mathl{A(n+1)}{} wahr.
}}
\faktfolgerung {Dann gilt
\mathl{A(n)}{} für alle $n$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wegen der ersten Voraussetzung gilt
\mathl{A(0)}{.} Wegen der zweiten Voraussetzung gilt auch
\mathl{A(1)}{.} Deshalb gilt auch
\mathl{A(2)}{.} Deshalb gilt auch
\mathl{A(3)}{.} Da man so beliebig weitergehen kann und dabei jede natürliche Zahl erhält, gilt die Aussage
\mathl{A(n)}{} für jede natürliche Zahl $n$.
Der Nachweis von
\mathl{A(0)}{} heißt dabei der \stichwort {Induktionsanfang} {} und der Schluss von
\mathl{A(n)}{} auf
\mathl{A(n+1)}{} heißt der \stichwort {Induktionsschritt} {.} Innerhalb des Induktionsschrittes nennt man die Gültigkeit von $A(n)$ die \stichwort {Induktionsvoraussetzung} {.} In manchen Situationen ist die Aussage
\mathl{A(n)}{} erst für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein gewisses $n_0$
\zusatzklammer {definiert oder} {} {}
wahr. Dann beweist man im Induktionsanfang die Aussage
\mathl{A(n_0)}{} und den Induktionsschluss führt man für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch.
Wir begründen nun die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} { { \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
mit dem Induktionsprinzip.
Beim Induktionsanfang ist
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
daher besteht die Summe links nur aus einem Summanden, nämlich der $1$, und daher ist die Summe $1$. Die rechte Seite ist
\mavergleichskette
{\vergleichskette
{ { \frac{ 1 \cdot 2 }{ 2 } }
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
sodass die Formel für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stimmt.
Für den Induktionsschritt setzen wir voraus, dass die Formel für ein
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, und müssen zeigen, dass sie dann auch für
\mathl{n+1}{} gilt. Dabei ist $n$ beliebig. Es ist
\mavergleichskettealign
{\vergleichskettealign
{ \sum_{k = 1}^{n+1} k
}
{ =} { { \left( \sum_{k = 1}^{n} k \right) } + n+1
}
{ =} { { \frac{ n(n+1) }{ 2 } } + n+1
}
{ =} { { \frac{ n(n+1) +2(n+1) }{ 2 } }
}
{ =} { { \frac{ (n+2)(n+1) }{ 2 } }
}
}
{}
{}{.}
Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für
\mathl{n+1}{,} also ist die Formel bewiesen.
\inputbemerkung
{}
{
Induktionsbeweise kommen ständig vor. Die Voraussetzung dafür, dass man diese Beweismethode anwenden kann, ist, dass ein Aussagenschema vorliegt, das von einer \zusatzklammer {variablen} {} {} natürlichen Zahl $n$ abhängt. Diese natürliche Zahl $n$ nennt man auch die \stichwort {Induktionsvariable} {,} über die Induktion geführt wird. In der Aussage können ansonsten beliebige andere mathematische Objekte vorkommen und die natürliche Zahl $n$ kann jeweils sehr unterschiedliche Bedeutungen haben. Sie kann für den Exponenten einer reellen Zahl \zusatzklammer {siehe beispielsweise Satz 4.11 oder Satz 5.11} {} {,} den Grad eines Polynoms \zusatzklammer {etwa Satz 6.3} {} {,} den Differenzierbarkeitsgrad \zusatzklammer {etwa Aufgabe 15.17} {} {} oder die Anzahl von Vektoren \zusatzklammer {etwa Lemma 27.14} {} {} stehen.
}
\zwischenueberschrift{Primfaktorzerlegung}
Als ein weiteres Beispiel für das Induktionsprinzip beweisen wir die Existenz einer Primfaktorzerlegung für natürliche Zahlen.
\inputdefinition
{}
{
Eine
\definitionsverweis {natürliche Zahl}{}{}
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt eine \definitionswort {Primzahl}{,} wenn die einzigen natürlichen
\definitionsverweis {Teiler}{}{}
von ihr $1$ und $n$ sind.
}
\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/Existenz/Fakt}
{Satz}
{}
{
Jede
\definitionsverweis {natürliche Zahl}{}{}
\mathbed {n \in \N} {}
{n \geq 2} {}
{} {} {} {,}
besitzt eine Zerlegung in Primfaktoren.
D.h. es gibt eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {p_1 \cdot p_2 { \cdots } p_r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Primzahlen}{}{}
$p_i$.
}
{
Wir beweisen die Existenz durch Induktion über $n$, und zwar betrachten wir die Aussage $A(n)$, die besagt, dass jede natürliche Zahl $m$ mit
\mavergleichskette
{\vergleichskette
{2
}
{ \leq }{m
}
{ \leq }{n
}
{ }{
}
{ }{
}
}
{}{}{}
eine Primfaktorzerlegung besitzt.
Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt eine Primzahl vor. Sei
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei, als Induktionsvoraussetzung, angenommen, dass jede Zahl
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Primfaktorzerlegung besitzt. Es ist zu zeigen, dass dann auch jede Zahl
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Primfaktorzerlegung besitzt. Die einzig neue zu betrachtende Zahl ist $n+1$. Es ist also zu zeigen, dass wenn jede Zahl echt kleiner als $n+1$ eine Primfaktorzerlegung besitzt, dass dann auch $n+1$ eine Primfaktorzerlegung besitzt.
Wir betrachten also $n+1$. Im Beweis dieses Induktionsschrittes kommt ein weiteres wichtiges Argumentationsschema zum Tragen, nämlich \stichwort {Beweis durch Fallunterscheidung} {.} Dabei argumentiert man abhängig davon, ob eine zusätzliche Eigenschaft vorliegt oder nicht, in beiden Fällen muss man jeweils das nachweisen, was man zeigen will.
Hier macht man die Fallunterscheidung, ob $n+1$ eine Primzahl ist oder nicht. Wenn $n+1$ eine Primzahl ist, so liegt unmittelbar die Primfaktorzerlegung vor, die aus der Zahl selbst besteht. In diesem Fall wird also auf die Induktionsvoraussetzung gar nicht Bezug genommen.
Somit betrachten wir den Fall, wo $n+1$ keine Primzahl ist. Dies bedeutet, dass es eine nichttriviale Zerlegung
\mavergleichskette
{\vergleichskette
{n+1
}
{ = }{ab
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit kleineren Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ < }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Für diese Zahlen
\mathkor {} {a} {und} {b} {}
gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für $n+1$ zusammen.
Es gilt auch, dass die Primfaktorzerlegung eindeutig ist, dies haben wir aber nicht bewiesen. Man nennt diese Aussage den Hauptsatz der elementaren Zahlentheorie.
\inputbemerkung
{}
{
Eng verwandt mit der vollständigen Induktion ist das Prinzip der \stichwort {rekursiven Definition} {.} Bei dieser möchte man für jede natürliche Zahl $n$ einen mathematischen Ausdruck festlegen. Dies macht man, indem man für $0$ einen Ausdruck explizit festlegt und beschreibt, wie der Ausdruck für $n+1$ aus dem Ausdruck für $n$ berechnet werden soll. Letzteres nennt man die Rekursionsvorschrift. Der induktive Aufbau der natürlichen Zahlen stellt dabei sicher, dass durch diese rekursiven Festlegungen für jede natürliche Zahl ein eindeutiger Ausdruck festgelegt wird. Beispielsweise kann man einen Ausdruck
\mathl{F(n)}{} durch den Rukursionsanfang
\mavergleichskettedisp
{\vergleichskette
{F(0)
}
{ \defeq} {7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und die Rekursionsvorschrift
\mavergleichskettedisp
{\vergleichskette
{F(n+1)
}
{ \defeq} { F(n) \cdot n -n^2+3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
festlegen.
}