Artikel über Folgerungsrichtg. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:56 Sa 27.04.2013 | | Autor: | Marcel |
| Aufgabe | Vorneweg: Diese Frage ist keine wirkliche Frage, sondern ein Artikel, der
erklären soll, wie eigentlich ein mathematischer Beweis einer Aussage [mm] $A\,$
[/mm]
funktioniert. Insbesondere schreibe ich diesen deshalb, weil oft gerade in
Induktionsbeweisen die "Beweisrichtung", die man eigentlich braucht,
immer mal wieder "verfälscht" oder sagen wir besser "unterschlagen" wird. |
Zunächst einmal erinnern wir daran, dass eine Aussage [mm] $A\,$ [/mm] die Eigenschaft
haben sollte, dass sie entweder wahr ist (in diesem Falle schreibt man
einfach [mm] $A\,$ [/mm] - im Sinne von [mm] "$A\,$ [/mm] gilt") oder falsch ist (man schreibt dann
[mm] $\neg [/mm] A$ im Sinne von [mm] "$A\,$ [/mm] ist nicht wahr" oder [mm] "$A\,$ [/mm] gilt nicht").
Im Folgenden seien [mm] $A,B\,$ [/mm] Aussagen:
Uns allen ist bewußt, dass $A [mm] \Longrightarrow [/mm] B$ per Definitionem nichts anderes als
[mm] $\neg [/mm] A [mm] \vee [/mm] B$ ist. D.h., wenn man bewiesen hat, dass $A [mm] \Longrightarrow [/mm] B$ gilt,
hat man gezeigt, dass [mm] $\neg [/mm] A [mm] \vee [/mm] B$ wahr ist, oder anders gesagt: Man hat bewiesen,
dass die Aussage, dass [mm] '$A\,$ [/mm] nicht gilt oder eben [mm] $B\,$ [/mm] gilt', wahr ist.
Rein logisch bedeutet das - was man sich auch an Wahrheitstafeln etwa
klar machen kann:
Es kann NICHT sein, dass $A$ und [mm] $\neg [/mm] B$ gilt, d.h., wenn [mm] $A\,$ [/mm] gilt, dann kann
es nicht sein, dass [mm] $B\,$ [/mm] nicht gilt. [mm] $A\,$ [/mm] ist also HINREICHEND für [mm] $B\,,$ [/mm] bzw.
[mm] $B\,$ [/mm] ist NOTWENDIG für [mm] $A\,.$
[/mm]
-----------------------------------------------
-----------------------------------------------
Wie funktioniert nun ein Beweis einer Aussage [mm] $B\,$?
[/mm]
(D.h., man hat eine Aussage [mm] $B\,$ [/mm] formuliert und will zeigen, dass [mm] $B\,$ [/mm]
eine wahre Aussage ist!)
Auch hier wird jeder sagen, dass uns das allen klar ist: Man geht aus von
einer "bekanntlich oder offensichtlich" WAHREN Aussage [mm] $A\,,$ [/mm] und mit
weiteren Aussagen [mm] $A_1,...,A_n$ [/mm] zeigt man etwa
[mm] $$(\*)\;\;\;\;\;A \Longrightarrow A_1 \Longrightarrow A_2 \Longrightarrow \ldots \Longrightarrow A_n \Longrightarrow B\,.$$ [/mm]
Was wird hier eigentlich gemacht?
Nunja, die Aussage [mm] $(\*)$ [/mm] besagt, dass die Folgerung $A [mm] \Longrightarrow [/mm] B$ wahr
ist, das heißt, es gilt [mm] $\neg [/mm] A [mm] \vee B\,.$ [/mm]
Damit alleine wäre aber noch lange nicht bewiesen, dass [mm] $B\,$ [/mm] auch wahr ist.
Da man aber zuvor bewiesen hat (oder benutzen darf), dass [mm] $A\,$ [/mm] gilt, weiß
man nun, dass [mm] $\neg [/mm] A$ eine falsche Aussage ist. Somit kann [mm] $\neg [/mm] A [mm] \vee [/mm] B$ nur noch
dann wahr sein, wenn [mm] $B\,$ [/mm] wahr ist!
Es gibt also eigentlich zwei Beweisteile:
1. $A [mm] \Longrightarrow [/mm] B$ ist zu beweisen!
2. [mm] $A\,$ [/mm] (d.h., [mm] $A\,$ [/mm] ist eine wahre Aussage) muss bekannt sein oder
bewiesen werden.
[mm] $(\*)$ [/mm] alleine bringt uns gar nichts, wir demonstrieren das an einem
Beispiel:
Die Aussage [mm] $-2=5\,$ [/mm] ist offensichtlich falsch (etwa in [mm] $\IR$). [/mm] Nichtsdestotrotz
ist die Folgerung
$$-2=5 [mm] \Longrightarrow [/mm] 4=4$$
richtig. Denn bzgl. der Aussagen
[mm] $$A:\;\;-2=5$$
[/mm]
und
[mm] $$B:\;\;4=4$$
[/mm]
ist [mm] $\neg [/mm] A$ und damit auch [mm] $\neg [/mm] A [mm] \vee [/mm] B$ wahr, also gilt $A [mm] \Longrightarrow B\,.$
[/mm]
Übrigens wäre auch mit [mm] $B:\;\;3=9$ [/mm] dann $A [mm] \Longrightarrow [/mm] B$ wahr, aus
dem gleichen Grund.
Allgemein gilt: Ist [mm] $\neg [/mm] A$ wahr, d.h., wenn [mm] $A\,$ [/mm] eine falsche Aussage ist, so
folgt für jede Aussage [mm] $B\,,$ [/mm] dass die Folgerung $A [mm] \Longrightarrow [/mm] B$ wahr ist.
Beweis: Weil [mm] $\neg [/mm] A$ wahr ist, ist [mm] $\neg [/mm] A [mm] \vee [/mm] B$ und damit $A [mm] \Longrightarrow [/mm] B$ wahr.
Diesen Sachverhalt meint man übrigens, wenn man sagt: "Aus FALSCHEM
folgt ALLES!"
-----------------------------------------------
-----------------------------------------------
Wozu dieses Vorgeplänkel und was soll eigentlich dieser Artikel?
Mir fällt (seit Jahren) immer wieder auf, das fast jeder Mathematiker, ob er
das nun "professionell" oder "hobbymäßig" betreibt, sich der obigen
Tatsachen stets bewußt ist - oder sagen wir besser: Er glaubt sich, dessen
stets bewußt zu sein. Und in den allerkompliziertesten Beweisen, oder
auch in "langen" Beweisen, wird auf obige Sachverhalte penibelst genau
geachtet. Verwunderlich ist es dann doch, dass man oft Induktionsbeweise
der folgenden Art immer mal wieder findet:
Für jedes $n [mm] \in \IN$ [/mm] sei eine Aussage [mm] $A(n)\,$ [/mm] gegeben. Und nun will man zeigen,
dass für jedes $n [mm] \in \IN$ [/mm] auch [mm] $A(n)\,$ [/mm] (im Sinne von [mm] "$A(n)\,$ [/mm] ist wahr").
(Bemerkung: "Sprachlich" besser wäre es, zu schreiben "... auch [mm] $A(n)\,$ [/mm] GILT".
Aber für eine Aussage [mm] $A\,$ [/mm] schreiben wir ja [mm] $A\,,$ [/mm] wenn [mm] $A\,$ [/mm] wahr ist, daran
wollte ich nochmal erinnern!)
Im Induktionsschritt wird dann folgendes gemacht:
Man weiß, dass [mm] $A(n)\,$ [/mm] (wahr ist). Man WILL NUN ZEIGEN, dass dann auch
[mm] $A(n+1)\,$ [/mm] (wahr ist).
Nun geht folgender Prozess vonstatten:
[mm] $$(\*\*)\;\;\;\;\;A(n+1) \iff A_1 \iff A_2 [/mm] ... [mm] \iff A_k \red{\;\Longrightarrow\;} A_{k+1} \iff...\iff A_m \iff A(n)\,.$$
[/mm]
Dabei kann es sein, dass [mm] $\red{\;\Longrightarrow\;}$ [/mm] auch (nur) direkt vor [mm] $A(n)\,$
[/mm]
steht.
Dann wird gesagt: "Weil [mm] $A(n)\,$ [/mm] gilt, haben wir nun gezeigt, dass [mm] $A(n+1)\,$
[/mm]
gilt!"
Leider ist das FALSCH. Wer einen Induktionsbeweis so führt, wird den
Induktionsschritt nicht mit der Methode - wie sie in [mm] $(\*\*)$ [/mm] angedeutet
wurde - bewiesen haben.
Im Induktionsschritt hat man ja die VORAUSSETZUNG, dass [mm] $A(n)\,$ [/mm] (wahr ist), und
will mithilfe von diesem Wissen zeigen, dass sich daraus ergibt, dass dann
auch [mm] $A(n+1)\,$ [/mm] (wahr ist).
Wenn man sich aber [mm] $(\*\*)$ [/mm] genau anguckt, so sieht man, dass man
zweifellos $A(n+1) [mm] \Longrightarrow A(n)\,$ [/mm] mithilfe dieser Methode
bewiesen hat. Und man weiß nun auch, dass [mm] $A(n)\,$ [/mm] gilt. Was bringt uns
das aber bzgl. des Induktionsschritts? (So gut wie) Nichts!!
Im Induktionsschritt will man TATSÄCHLICH nämlich folgendes machen:
Man will zeigen, dass [mm] $A(n+1)\,$ [/mm] (wahr ist).
Dies macht man, indem man
$$A(n) [mm] \Longrightarrow [/mm] A(n+1)$$
beweist (daraus folgt, wie im Vorgeplänkel nochmal erklärt, dass [mm] $\neg [/mm] A(n) [mm] \vee A(n+1)\,$ [/mm]
wahr ist), und wenn man jetzt benutzen darf, dass [mm] $A(n)\,$ [/mm] (wahr ist),
dann kann doch [mm] $\neg [/mm] A(n) [mm] \vee [/mm] A(n+1)$ nur noch dann wahr sein, wenn [mm] $A(n+1)\,$ [/mm] wahr ist!
-----------------------------------------------
-----------------------------------------------
Beispiel eines einfachen Beweises:
Wir wollen $n [mm] \le n^3$ [/mm] für alle $n [mm] \in \IN$ [/mm] beweisen.
Beweis:
Für $n [mm] \in \IN$ [/mm] beliebig gilt: Die Aussage $1 [mm] \le [/mm] n$ ist offenbar wahr. Ferner
gilt die Folgerung
$$1 [mm] \le [/mm] n [mm] \;\;\;\;\stackrel{\text{bea.: }n > 0}{\Longrightarrow}\;\;\;\; [/mm] n*1 [mm] \le [/mm] n*n [mm] \;\;\;\;\stackrel{\text{bea.: }n > 0}{\Longrightarrow}\;\;\;\; n*n*1=n^2 \le n*n*n=n^3\,.$$
[/mm]
Somit sind die Ungleichungen $n [mm] \le n^2$ [/mm] und [mm] $n^2 \le n^3$ [/mm] beide wahr. Wegen des
Transitivgesetzes folgt, dass dann auch $n [mm] \le n^3$ [/mm] wahr sein muss. [mm] $\Box$
[/mm]
Beobachtung: Bei diesem Beweis wurde insbesondere ausgenutzt, dass
$1 [mm] \le [/mm] n$ eine wahre Aussage ist!
-----------------------------------------------
-----------------------------------------------
Beispiel eines falschen Induktionsbeweises bzgl. der oben erwähnten
"falschen Folgerungsrichtung":
Wir beweisen, dass für alle $n [mm] \in \IN_0$ [/mm] gilt [mm] $-\,n=n\,.$
[/mm]
I.A.: Für [mm] $n=0\,$ [/mm] ist die Behauptung klar.
I.S.: Zu zeigen ist [mm] $-(n+1)=n+1\,.$
[/mm]
"Beweis": Es sei $n [mm] \in \IN_0$ [/mm] mit [mm] $-\,n=n\,.$ [/mm] Wir zeigen, dass dann auch $-(n+1)=n+1$
folgt: Es gilt
[mm] $$-\,(n+1)=n+1$$
[/mm]
[mm] $$\iff -1=1\,,$$
[/mm]
wegen $n+1 [mm] \not=0$ [/mm] - es ist ja $n [mm] \in \IN_0$ [/mm] und damit $n+1 [mm] \ge 1\,.$
[/mm]
Multiplizieren wir [mm] $-1=1\,$ [/mm] mit $n [mm] \in \IN_0\,,$ [/mm] so folgt [mm] $-\,n=n\,,$ [/mm] was nach
I.V. wahr ist. Also folgt die Behauptung! [mm] "$\Box$"
[/mm]
"Oha... gibt es also gar keine negativen ganzen Zahlen?"
Beweisanalyse: Natürlich ist der obige Beweis FALSCH. In der Tat ist aber
[mm] $$-\,(n+1)=n+1 \iff -\,1=1 \red{\;\Longrightarrow\;} -\,n=n$$
[/mm]
richtig - die Folgerung [mm] $\red{\;\Longrightarrow\;}$ [/mm] gilt auch für [mm] $n=0\,.$
[/mm]
Was ist das Problem? Das Problem ist, dass - für einen RICHTIGEN
Induktionsbeweis - wir an der Stelle [mm] $\red{\Longrightarrow}$ [/mm] eben [mm] $\Longleftarrow$ [/mm] bräuchten. Oben haben
wir im Induktions-"Beweis" (die Anführungszeichen deuten an, dass
dieser Beweis MISSLUNGEN ist, ebenso ist das Beweisbeendende Viereck
[mm] $\Box$ [/mm] deswegen auch in Anführungszeichen notiert!) nur gezeigt:
Es gibt ein $n [mm] \in \IN_0,$ [/mm] für das
[mm] $$A(n):\;\;-\,n=n$$
[/mm]
wahr ist.
Dann haben wir gesagt: Okay, sei $n [mm] \in \IN_0$ [/mm] mit [mm] $A(n)\,$ [/mm] (ist wahr).
Und dann haben wir gezeigt, dass $A(n+1) [mm] \red{\;\Longrightarrow\;} A(n)\,$ [/mm] wahr ist.
Wir hätten aber zeigen müssen, dass die Folgerung $A(n) [mm] \Longrightarrow [/mm] A(n+1)$ wahr ist.
Wäre das vielleicht doch gegangen? Nein!!
Warum denn nicht?
Nun ja: Wenn $n [mm] \in \IN_0$ [/mm] ist mit [mm] $A(n)\,,$ [/mm] d.h. hier, dass [mm] $-\,n=n\,$ [/mm] gilt,
dann würden wir doch gerne [mm] $-\,n=n$ [/mm] durch [mm] $n\,$ [/mm] dividieren, um daraus
[mm] $-\,1=1$ [/mm] zu erhalten. Dafür müssten wir aber den Fall [mm] $n=0\,$ [/mm] ausschließen,
was wir hier nicht können!
-----------------------------------------------
-----------------------------------------------
Helfen uns Umformungen dann bei Induktionsbeweisen nicht?
DOCH. Und am Besten ist es, wenn man erstmal soweit äquivalent
umformt, bis man "etwas bekanntes" sieht. Wichtig ist aber, dass man
sich klarmacht, "dass man so auch $A(n+1) [mm] \Longleftarrow [/mm] A(n)$" insgesamt schließen
kann. Wenn man also von der zu beweisenden Aussage [mm] $A(n+1)\,$ [/mm] ausgeht,
braucht man eigentlich immer nur die Folgerungsrichtungen [mm] $\Longleftarrow\,,$ [/mm] denn diese
sind die Folgerungen, die "zu der Wahrheit von [mm] $A(n+1)\,$" [/mm] führen (können).
Beispiel:
Zu zeigen ist [mm] $n^2 \le 2^n$ [/mm] für $n=0,1,2$ und alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge 4\,.$
[/mm]
Beweis:
Einfaches nachrechnen zeigt, dass die Ungleichung für $n=0,1,2,4$ gilt.
I.A. machen wir mit [mm] $n=4\,,$ [/mm] vorrechnen, dass der funktioniert: das tun wir
hier nicht.
I.S. $n [mm] \to [/mm] n+1$: Sei $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 4$ und [mm] $n^2 \le 2^n\,.$ [/mm] Zu zeigen ist
[mm] $$(n+1)^2 \le 2^{n+1}\,.$$
[/mm]
Es gilt
[mm] $$(n+1)^2 \le 2^{n+1}$$
[/mm]
[mm] $$\iff$$ [/mm]
[mm] $$(\*\*\*)\;\;\;\;\;n^2+2n+1 \le 2^n+2^n\,.$$
[/mm]
Nach Induktionsvoraussetzung gilt für unser natürliches [mm] $\blue{\;n \ge 4\;}$
[/mm]
[mm] $$n^2 \le 2^n\,.$$
[/mm]
Aus [mm] $n^2 \le 2^n$ [/mm] (für unser natürliches [mm] $\blue{\;n \ge 4\;}$) [/mm] folgt unmittelbar
[mm] $$(n+1)^2=n^2+2n+1 \le 2^n+(2n+1)\,.$$
[/mm]
Wir wollen ja nun [mm] $(\*\*\*)$ [/mm] beweisen (denn bei dem zuvorstehenden [mm] $\iff$
[/mm]
können wir dann insbesondere [mm] $\Longleftarrow$ [/mm] verwenden), und da wir bisher
wissen:
es gilt (für unser natürliches [mm] $\blue{\;n \ge 4\;}$)
[/mm]
[mm] $$n^2 \le 2^n \Longrightarrow (n+1)^2 \le 2^n+(2n+1)\,,$$
[/mm]
so wäre es, um [mm] $(\*\*\*)$ [/mm] einzusehen, HINREICHEND, nun zu beweisen,
dass (für unser natürliches [mm] $\blue{\;n \ge 4\;}$) [/mm] gilt
$$2n+1 [mm] \le 2^n\,.$$
[/mm]
Etwa eine einfache weitere Induktion zeigt, dass aber sogar
$$2n+1 [mm] \le 2^n$$
[/mm]
für alle natürlichen $n [mm] \ge [/mm] 3$ gilt - damit gilt diese Ungleichung natürlich
auch für unser natürliches [mm] $\blue{\;n \ge 4\;}\,.$
[/mm]
Nur zur Übersicht also nochmal ein
sortierter Zusammenschrieb der wesentlichen Schritte im
Induktionsschritt des letzten Induktionsbeweises:
Wir setzen voraus, dass wir ein natürliches $n [mm] \ge [/mm] 4$ mit [mm] $n^2 \le 2^n$ [/mm] haben.
Da die Ungleichung $2m+1 [mm] \le 2^m$ [/mm] für alle natürlichen $m [mm] \ge [/mm] 3$ gilt (dies
kann man etwa mittels eines weiteren Induktionsbeweises beweisen!),
gilt sie auch für unser $n [mm] \ge 4\,,$ [/mm] man setze einfach $m:=n [mm] \ge 4\,$ [/mm] ein!
Es folgt also
[mm] $$n^2 \le 2^n$$
[/mm]
[mm] $$\Longrightarrow\;\;\;(n+1)^2=n^2+2n+1 \le 2^n+2n+1$$
[/mm]
wegen der I.V. und weiter (mit der obigen Ungleichung mit [mm] $m:=n\ge 4\,$)
[/mm]
[mm] $$\Longrightarrow\;\;\;(n+1)^2 \le 2^n+2n+1 \le 2^n+2^n$$
[/mm]
[mm] $$\Longrightarrow\;\;\;(n+1)^2 \le 2*2^n=2^{n+1}\,.\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Box$$
[/mm]
Gruß,
Marcel
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:45 Sa 27.04.2013 | | Autor: | Marcel |
Hallo,
nur zur Ergänzung: Was in obigem Artikel vielleicht etwas verwirrend ist,
oder unschön rüberkommt, ist, dass dort nicht beschrieben wird, wie der
Beweis zu $A [mm] \Longrightarrow [/mm] B$ eigentlich abläuft:
Man setzt voraus, dass [mm] $A\,$ [/mm] gilt, und zeigt dann, das dann auch [mm] $B\,$ [/mm] gelten
muss. Warum zeigt das, dass $A [mm] \Longrightarrow [/mm] B$ gilt? Nunja:
$A [mm] \Longrightarrow [/mm] B$ ist per Definitionem nichts anderes als [mm] $\neg [/mm] A [mm] \vee B\,.$ [/mm]
Im Falle, dass [mm] $\neg [/mm] A$ gilt, ist [mm] $\neg [/mm] A [mm] \vee [/mm] B$ sicher immer wahr. Nur im Falle [mm] $A\,$ [/mm]
(d.h. [mm] $A\,$ [/mm] ist wahr) hat man also noch etwas zu tun, um die Wahrheit von [mm] $\neg [/mm] A [mm] \vee [/mm] B$
dann zu erkennen - und dann muss man, weil [mm] $\neg [/mm] A$ dann falsch ist, folglich zeigen,
dass [mm] $B\,$ [/mm] dann wahr sein muss!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:16 Sa 27.04.2013 | | Autor: | Marcel |
Hallo,
das Folgende habe ich aus einer anderen Antwort von mir nochmal rauskopiert:
Was ist denn Idee des Induktionsbeweises? Man hat Aussagen [mm] $A(n)\,$ [/mm] etwa für
jedes $n [mm] \in \IN_0\,.$
[/mm]
Nun will man zeigen: [mm] $A(n)\,$ [/mm] gilt für alle $n [mm] \in \IN_0$ [/mm] mit $n [mm] \ge n_0\,.$
[/mm]
Induktionsanfang: Man zeigt: [mm] $A(n_0)$ [/mm] ist wahr.
Der Induktionsschritt zeigt bzw. soll zeigen:
Wenn $n [mm] \in \IN_0$ [/mm] mit $n [mm] \ge n_0$ [/mm] so ist, dass [mm] $A(n)\,$ [/mm] gilt, so folgt, dass dann
auch $A(n+1)$ gilt.
D.h., was man dort insgesamt macht, ist (für alle natürliche $n [mm] \ge n_0$):
[/mm]
[mm] $A(n)\,$ [/mm] ist wahr und im Induktionsschritt wird bewiesen, dass die Folgerung
$A(n) [mm] \Longrightarrow [/mm] A(n+1)$ (jedenfalls für natürliche $n [mm] \ge n_0$) [/mm] wahr ist, so liefert
das zusammen, dass [mm] $A(n+1)\,$ [/mm] dann auch wahr ist.
Man kann sich das auch einfach mit Logik überlegen:
Wenn man $A(n) [mm] \Longrightarrow [/mm] A(n+1)$ bewiesen hat, so weiß man, dass
[mm] $\neg [/mm] A(n) [mm] \vee [/mm] A(n+1)$ wahr ist.
Wenn nun [mm] $A(n)\,$ [/mm] wahr ist - wir schreiben nun dafür nur [mm] $A(n)\,$ [/mm] (wir würden
[mm] $\neg [/mm] A(n)$ schreiben, wenn [mm] $A(n)\,$ [/mm] falsch wäre),
so bedeutet
$A(n)$ [mm] $\wedge$ [/mm] $(A(n) [mm] \Longrightarrow [/mm] A(n+1))$
doch nichts anderes als
($A(n)$ [mm] $\wedge$ $(\neg [/mm] A(n) [mm] \vee [/mm] A(n+1))$).
Die Aussage
($A(n)$ [mm] $\wedge$ $(\neg [/mm] A(n) [mm] \vee [/mm] A(n+1))$)
kann aber nur noch genau dann wahr sein, wenn [mm] $A(n+1)\,,$ [/mm] d.h. wenn [mm] $A(n+1)\,$ [/mm]
wahr ist, denn sie ist doch gleichbedeutend mit
[mm] ($\red{(}A(n) \wedge \neg A(n)\red{)}$ $\vee$ $\red{(}A(n)\wedge A(n+1)\red{)}$)
[/mm]
und damit zu
[mm] $A(n)\wedge A(n+1)\,,$
[/mm]
und [mm] $A(n)\,$ [/mm] ist hier ja schon als wahr erkannt (im Zeichen [mm] $A(n)\,$)!
[/mm]
Zusammenfassend: Im Induktionsanfang zeigt man, dass [mm] $A(n_0)$ [/mm] wahr ist.
Im Induktionsschritt zeigt man, dass die Folgerung $A(n) [mm] \Longrightarrow A(n+1)\,$ [/mm] wahr
ist (für alle $n [mm] \ge n_0$ [/mm] jedenfalls).
Nur BEIDES ZUSAMMEN liefert dann, dass [mm] $A(n)\,$ [/mm] für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge n_0$ [/mm]
wahr ist.
Denn dann kann man so schließen:
1.)
[mm] $A(n_0)$ [/mm] ist wahr. Weil die Folgerung [mm] $A(n_0) \Longrightarrow A(n_0+1)$ [/mm] gilt, liefert
[mm] $A(n_0) \wedge \red{(}A(n_0) \Longrightarrow A(n_0+1)\red{)}$
[/mm]
sofort, dass [mm] $A(n_0+1)$ [/mm] wahr sein muss.
2.) [mm] $A(n_0+1)$ [/mm] ist nun wahr (siehe 1.). Weil die Folgerung
[mm] $A(n_0+1) \Longrightarrow A((n_0+1)+1)=A(n_0+2)$ [/mm] gilt,
liefert
[mm] $A(n_0+1) \wedge \red{(}A(n_0+1) \Longrightarrow A(n_0+2)\red{)}$
[/mm]
sofort, dass [mm] $A(n_0+2)$ [/mm] wahr sein muss.
etc. pp.!
Daraus folgt dann, dass [mm] $A(n_0+k)$ [/mm] für alle $k [mm] \in \IN_0$ [/mm] wahr ist. Die Menge
[mm] $$\{n_0+k:\;\; k \in \IN_0\}$$
[/mm]
ist aber gerade
[mm] $$\{n \in \IN_0:\;\; n \ge n_0\}\,.$$
[/mm]
Also haben wir so [mm] $A(n)\,$ [/mm] für alle $n [mm] \ge n_0$ [/mm] bewiesen.
Gruß,
Marcel
|
|
|
|
