Induktion

21.05.2011, 15:55

marie123

Induktion

Meine Frage:
Also ich weis bei dieser aufgabe nichts so richtig, was ich da beweisen soll.....

Meine Ideen:
für mich ist es logisch.. das n nicht n´ ist... wird ja im peano axiom 2 so definiert, das n` der nachfolger ist von n ...... was soll man nu noch beweisen..

22.05.2011, 10:31

carlf

Auf diesen Beitrag antworten »

RE: Induktion
Hallo marie,

anschaulich klar ist die Aussage, ja. Aber das hindert dich ja nicht daran (und nimmt es dir auch nicht ab),
einen formalen Beweis zu führen.

Der angegebene Hinweis sollte dir dabei schon weiterhelfen können.
Was sagt denn das Induktionsaxiom aus und an welcher Stelle (auf welche Menge) lässt es sich hier anwenden?
Welche zwei Aussagen musst du über diese Menge also zeigen?

22.05.2011, 19:03

marie123

Auf diesen Beitrag antworten »

ich denke mal das die menge A alle reellen zahlen sind außer 1 ? kann das sein?

22.05.2011, 19:44

carlf

Auf diesen Beitrag antworten »

Nein, leider nicht.
Mit den reellen Zahlen funktioniert auch das Induktionsaxiom nicht so super...

Der Hinweis lautet ja, dass du die Menge A mit
$\begin{eqnarray*} A := \{n \in \mathbb{N} ~|~ n \neq n'\} \end{eqnarray*}$
betrachten sollst.

Nach Definition sind in dieser Menge nun alle natürlichen Zahlen (alle $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ ), die von ihrem
Nachfolger (zu gegebenem n ist der hier mit n' bezeichnet) verschieden sind.

Wie lässt sich darauf jetzt das Induktionsaxiom anwenden? Und welche Aussage folgt dann damit, die dir wie weiterhilft?

22.05.2011, 19:47

marie123

Auf diesen Beitrag antworten »

kann leider die felder nicht lesen die du geschrieben hast.. hmmm..

22.05.2011, 19:52

carlf

Auf diesen Beitrag antworten »

Auch gerade gesehen, sorry.
Ist jetzt korrigiert.

22.05.2011, 19:59

marie123

Auf diesen Beitrag antworten »

Also ich versuche jetzt zu verstehen ....

Wir haben die Menge N und eine menge A

für die das Selbe gilt. nun dann müssen sie gleich sein, da sie ja gleich definiert sind.

ich glaub ich bin zu blöd dafür.. ich mag ja sonst mathe.. aber nicht das thema.. wobei ich induktion mit zahlen und so noch hinbekommen habe.. aber das ist mir jetzt zu hoch.. unglücklich

22.05.2011, 20:03

carlf

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \mathbb N \end{eqnarray*}$ ist die Menge der natürlichen Zahlen.
A ist erstmal als Teilmenge von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ definiert, nämlich soll A genau die natürlichen Zahlen enthalten, die sich von ihrem Nachfolger unterscheiden, also die nicht gleich ihrem Nachfolger sind.

Wie lautet denn das Induktionsaxiom ganz formal, erstmal?

22.05.2011, 20:11

marie123

Auf diesen Beitrag antworten »

hmmm ein feld ist wieder nicht zu lesen ;-)

aber davon ab... ich verstehe es einfach nicht.. weis auch nicht warum....

wenn n eine zahl ist... und n´ deren nachfolger... dann ist es ja durch n ungleich n´ in der definition festgelegt das die ungleich sind...
ich hoffe du verstehst mein problem... ich weis nicht was ich wooomit beweisen soll .. es ist doch definiert.....

ich frag mich obs einfach zu einfach ist oder einfach zu schwer

sorry das ich aufm schlauch stehe.. mathe is eher was für männer scheint mir Big Laugh

22.05.2011, 20:30

carlf

Auf diesen Beitrag antworten »

Zitat:

Original von marie123
hmmm ein feld ist wieder nicht zu lesen ;-)

Schon korrigiert.

Schreib doch bitte mal das Induktionsaxiom hin, damit wir damit arbeiten können.
Und vielleicht schreibst du auch mal hin, wie ihr Nachfolger definiert habt usw.

Zitat:

sorry das ich aufm schlauch stehe.. mathe is eher was für männer scheint mir Big Laugh

So ein Quatsch!

22.05.2011, 20:33

marie123

Auf diesen Beitrag antworten »

so also das ist das womit ich arbeiten soll... und mit zahlen versteh ich das auch,, also wenn man für n = 1 einsetzt und dann im IS auf n+1 geht... aber ich weis hier so garnicht was die wollen... wir sollen in der menge N etwas beweisen... wo zum teufel kommt die Menge A plötzlich her...

22.05.2011, 20:50

carlf

Auf diesen Beitrag antworten »

Okay, danke. Das hilft smile

Dass n vom Nachfolger n' verschieden ist, steht in den Axiomen nirgends!
Also musst du diese Aussage formal beweisen.

Die Menge A ist hier eine Hilfsmenge, die man sich eben definiert, um zu zeigen, dass $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ für alle
$\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt.
Das tut man, indem man eben A als Menge derjenigen natürlichen Zahlen definiert, die $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ erfüllen -- und dann zeigt, dass A bereits alle natürlichen Zahlen enthält.

Was muss man jetzt alles für die Menge A zeigen, um zu beweisen, dass A eine vollständige Menge natürlicher Zahlen (also schon $\begin{eqnarray*} = \mathbb N \end{eqnarray*}$ ) ist?

22.05.2011, 20:54

marie123

Auf diesen Beitrag antworten »

Also in P2 ist doch definiert, das n´ der nachfolger von n ist... also ist doch definiert das n nicht gleich n´ sein kann ... oder sehe ich das falsch

22.05.2011, 21:16

carlf

Auf diesen Beitrag antworten »

Ja, siehst du.
Da steht nur, dass zu jeder natürlichen Zahl n ein Nachfolger $\begin{eqnarray*} n' \end{eqnarray*}$ _existiert_.
Der muss nach dieser Formulierung nicht unbedingt von n verschieden sein.

Beantworte doch bitte mal meine Frage: Wie kannst du zeigen, dass A schon die Menge aller natürlichen Zahlen ist?

22.05.2011, 21:31

marie123

Auf diesen Beitrag antworten »

hm.. also ich vermute mal durch P5, denn dort wird ja ebenfalls eine Menge zusammengebaut, die B lautet und gleich der Menge n ist

22.05.2011, 21:48

carlf

Auf diesen Beitrag antworten »

Genau.
(P5) heißt auch Induktionsaxiom und die erste Aussage ( $\begin{eqnarray*} 1 \in B \end{eqnarray*}$ ) ist der sog. Induktionsanfang, die zweite ( $\begin{eqnarray*} n \in B \Longrightarrow n' \in B \end{eqnarray*}$ ) der sog. Induktionsschluss.

Die Voraussetzung $\begin{eqnarray*} A \subset \mathbb N \end{eqnarray*}$ ist ja erfüllt, A war schließlich genau als Teilmenge der natürlichen Zahlen definiert.
Jetzt muss du noch Induktionsanfang und -schluss zeigen.

22.05.2011, 21:54

marie123

Auf diesen Beitrag antworten »

ok hab ich verstanden glaub ich.... ich versuch mal den Induktions anfang...

für n= 1 ist laut P3 n ungleich n´ , da ja die 1 für kein n der nachfolger sein darf... ist das richtig?

22.05.2011, 22:09

carlf

Auf diesen Beitrag antworten »

Genauso! Für jedes $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ ist $\begin{eqnarray*} n' \neq 1 \end{eqnarray*}$ , also gilt für n = 1 auch $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ , d.h. nach Definition von A gilt $\begin{eqnarray*} 1 \in A \end{eqnarray*}$ .
Der Induktionsanfang ist damit erfüllt.

Jetzt der Induktionsschluss.

22.05.2011, 22:12

marie123

Auf diesen Beitrag antworten »

nu muss ja n+1 = n´ sein.. nur welches axiom sagt mir das?

Also beim Schluss weis ich nich wie ich das machen soll...

22.05.2011, 22:14

carlf

Auf diesen Beitrag antworten »

Du musst dafür zeigen, dass für ein beliebiges $\begin{eqnarray*} n \in A \end{eqnarray*}$ auch n' ein Element von A ist.
Dazu musst du natürlich die Definition der Menge A anwenden, also dir überlegen, was es heißt dass n ein Element von A ist.
Und wie du mit dieser Voraussetzung und den Peano-Axiomen dann zeigst, dass auch n' in A liegt (was bedeutet das, wieder nach Definition?).

22.05.2011, 22:20

marie123

Auf diesen Beitrag antworten »

Ich weis nicht wie ich das Zeige...

als erstes hab ich noch eine Unklarheit... die Menge A ist gleichzusetzen mit unserer menge B wie sie im Skript als P5 definiert ist?

Also meine Idee wäre eigentlich jetz das zum Beispiel n+1 = m ist

und Laut P4 äääähm... ne blödsinn... ne hier häng ich fest.. weil ich nicht weis was du immer damit genau meinst das ich schauen soll, wie menge A definiert ist... denn A ist ja noch nicht definiert.. denn das wollen wir ja gerade tub... ich glaub ich dreh mich im Kreis traurig

22.05.2011, 22:44

carlf

Auf diesen Beitrag antworten »

Nein, A ist schon definiert, und zwar durch
$\begin{eqnarray*} A := \{n \in \mathbb N ~|~ n \neq n'\} \end{eqnarray*}$ .

Eine natürliche Zahl n ist also genau dann Element von A, wenn der Nachfolger n' von n verschieden ist.
Wir müssen jetzt _zeigen_, dass das für jedes Element der natürlichen Zahlen gilt.
Den ersten Schritt (Induktionsanfang) hast du schon geschafft.

Wenn du jetzt noch zeigst, dass falls n in A liegt auch n' in A liegen muss, dann heißt das eben nach (P5), dass
A bereits alle natürlichen Zahlen enthält.
Also dass jede natürliche Zahl von ihrem Nachfolger verschieden ist. Und das ist ja gerade, was gezeigt werden soll.

Und ja, als Menge B in (P5) betrachten wir hier die Menge A.

Was heißt es, dass n in A liegt (habe ich oben schon hingeschrieben, vielleicht formulierst du es mal als Gleichung) und was heißt es, dass n' in A liegt?

22.05.2011, 22:49

marie123

Auf diesen Beitrag antworten »

Als gleichung formulieren? Jetz schalt ich glaub ich ab.....

Also das n in A liegt haben wir ja schon gezeigt... durch den IA ..dachte ich

Alles was ich verstehe ist das ziehl... was wir zeigen müssen... aber wieso müssen wir etwas zeigen...

ich soll zeigen n liegt in A.. und n´ auch... aber das ist doch in A schon definiert.... also ist es doch gezeigt... durch den IA und der definition... ..

langsam komm ich mir echt blöd vor

22.05.2011, 23:01

carlf

Auf diesen Beitrag antworten »

Zitat:

Original von marie123
Als gleichung formulieren? Jetz schalt ich glaub ich ab.....

Die Bedingung, dass eine natürliche Zahl n in A liegt ist doch, dass sie von ihrem Nachfolger n' verschieden ist.
Drück diese Bedingung doch mal in einer Ungleichung (sorry, "Gleichung" war der falsche Begriff) aus.

Zitat:

Also das n in A liegt haben wir ja schon gezeigt... durch den IA ..dachte ich

Es ist gezeigt, dass 1 in A liegt. Nicht, dass jedes beliebige n in A liegt!

Zitat:

Alles was ich verstehe ist das ziehl... was wir zeigen müssen... aber wieso müssen wir etwas zeigen...

Weil es formal nicht klar ist. Anschaulich logisch ist die Zielaussage, klar. Aber das liegt an deiner Vorstellung von den natürlichen Zahlen, die du schon hast. smile

Versuche die einmal zu vergessen und nimm nur die Peano-Axiome als alles, was du über die natürlichen Zahlen weißt.
Auch "n + 1" rechnen kannst du also erstmal nicht. (Das "n + 1" zu einem gegebenen n wird ja dann gerade dadurch
definiert, dass es der Nachfolger von n ist. Also kann man das erstmal nicht verwenden, an dieser Stelle.)

Zitat:

ich soll zeigen n liegt in A.. und n´ auch... aber das ist doch in A schon definiert.... also ist es doch gezeigt... durch den IA und der definition... ..

Naja. Insgesamt sollst du nachher gezeigt haben, dass jedes n in A liegt.
Aber jetzt (für den Induktionsschluss) musst du zeigen, dass aus n in A auch n' in A folgt.
Das heißt du _setzt voraus_, dass n in A gilt, für ein völlig beliebiges n. (Dass es zumindest ein solches n gibt wissen wir ja mit dem IA, denn 1 in A.)
Und daraus musst du jetzt folgern, dass zu diesem bestimmten n in A auch der Nachfolger n' in A liegt.
Da kommst du mit der Bedingung dafür, dass n (oder eben n') in A liegt dann weiter. Dafür brauchen wir die Ungleichung, nach der ich oben gefragt habe.

Zitat:

langsam komm ich mir echt blöd vor

Das ist vielleicht gar nichtmal schlecht Augenzwinkern

Wenn es wie hier darum geht, ganz formal solch eigentlich anschaulich klare Sachverhalte zu beweisen, dann muss man manchmal (oft) einfach _alles vergessen_, was man weiß. Und sich wirklich nur auf die gegebenen Voraussetzungen (hier die Peano-Axiome) beziehen und _ausschließlich_ damit arbeiten und argumentieren.

Gerade das macht es eben nicht ganz leicht, wenn es "eigentlich ja klar ist, dass das so ist".
Dann hilft es eben, alles haarklein auf die Definitionen herunterzubrechen.
(Deshalb will ich immer auf die Definition von A heraus.)

22.05.2011, 23:07

marie123

Auf diesen Beitrag antworten »

hujui... vielen dank für diese viele mühe die du dir hier gibst...

also ich versuch mal diese ungleichung aufzustellen

.....n ungleich n´ oder n= n´ - 1

22.05.2011, 23:17

carlf

Auf diesen Beitrag antworten »

$\begin{eqnarray*} n \neq n' \end{eqnarray*}$ , genau.
Dass n = n' - 1 ist, weißt du noch nicht! Und das ist _keinesfalls_ gleichbedeutend mit n ungleich n' !
Im ersten Fall, ist n nämlich mit n' schon sofort eindeutig bestimmt (und andersherum), im zweiten Fall könnten n und n' erstmal völlig unabhängig voneinander sein!

Die Bedingung für n in A ist, dass n und der Nachfolger n' voneinander verschieden sind, d.h.
$\begin{eqnarray*} n \in A \end{eqnarray*}$ gilt genau dann, wenn $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ erfüllt ist.

Wie lautet die Bedingung für n' in A jetzt?

22.05.2011, 23:20

marie123

Auf diesen Beitrag antworten »

müsste ja das selbe sein... also: n´ in A wenn n` ungleich n

22.05.2011, 23:24

carlf

Auf diesen Beitrag antworten »

Nein, eben nicht.
Setze mal m = n' und versuche die Bedingung für m in A aufzustellen.
Dann resubstituiere jedes Vorkommen von m in der Bedingung wieder durch n'.

22.05.2011, 23:29

marie123

Auf diesen Beitrag antworten »

Also m = n` wazu soll das führen...

dann ist eben n ungleich m das soll nicht sein laut P4 aber verstehen tue ich das jetz nicht..

22.05.2011, 23:36

carlf

Auf diesen Beitrag antworten »

Nein.
Für eine natürliche Zahl n gilt
$\begin{eqnarray*} n \in A \end{eqnarray*}$ ist genau dann erfüllt, wenn $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ ist, d.h. wenn n und der Nachfolger von n verschieden sind.

Für m gilt völlig analog
$\begin{eqnarray*} m \in A \end{eqnarray*}$ ist genau dann erfüllt, wenn $\begin{eqnarray*} m \neq m' \end{eqnarray*}$ ist, d.h. wenn m und der Nachfolger von m verschieden sind.

Das n und ein anderes, beliebiges m haben erstmal nichts miteinander zu tun!

Jetzt setze m = n'. Was ist dann m' und wie sieht die Bedingung hier aus?

22.05.2011, 23:40

marie123

Auf diesen Beitrag antworten »

Moment.... ich glaub in mir machts klick... hoffe ich.....

also m = n´ m ungleich m´ also ist n´ ungleich (n´)´

wehe das passt jetz wieder nicht dann spring ich in monitor Gott

22.05.2011, 23:45

carlf

Auf diesen Beitrag antworten »

Zitat:

Original von marie123
wehe das passt jetz wieder nicht dann spring ich in monitor Gott

Wie gut, dass du das nicht tun musst! Freude

Genau.
Für m = n' bedeutet das
$\begin{eqnarray*} n' \in A \end{eqnarray*}$ genau dann, wenn $\begin{eqnarray*} n' \neq n'' \end{eqnarray*}$ ist.

Gut, damit haben wir die Bedeutungen der Aussagen $\begin{eqnarray*} n \in A \end{eqnarray*}$ und $\begin{eqnarray*} n' \in A \end{eqnarray*}$ geklärt. Puh.. smile

Also zurück zur Aufgabe:
Wir sind bei dem Induktionsschritt, müssen also zeigen, dass aus n in A auch n' in A folgt.
Jetzt heißt n in A gerade $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ und n' in A gerade $\begin{eqnarray*} n' \neq n'' \end{eqnarray*}$ .

Du musst also aus $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ mithilfe der Peano-Axiome folgern, dass auch $\begin{eqnarray*} n' \neq n'' \end{eqnarray*}$ gilt.

22.05.2011, 23:50

marie123

Auf diesen Beitrag antworten »

ham wir das nicht gerade gemacht?

23.05.2011, 00:02

carlf

Auf diesen Beitrag antworten »

Nein, bisher haben wir nur geklärt, was n' in A _bedeutet_.
Wir müssen nun zeigen, dass aus n in A auch n' in A folgt.
Das heißt, falls die Bedingung für n erfüllt ist (also falls $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ gilt), dann gilt auch $\begin{eqnarray*} n' \in A \end{eqnarray*}$ (d.h. $\begin{eqnarray*} n' \neq n'' \end{eqnarray*}$ ).

Also für dich jetzt die relativ einfache kleine Beweisaufgabe:

Zitat:

Es gilt n in A, also $\begin{eqnarray*} n \neq n' \end{eqnarray*}$ .
Zeige, dass auch $\begin{eqnarray*} n' \neq n'' \end{eqnarray*}$ erfüllt ist.

Wenn du nicht weiterkommst (am besten nur dann, mach dir vorher selber Gedanken!), benutze die folgenden Tipps unten (wenn du den Text markierst, kannst du ihn lesen)

Zitat:

Tipp: Führe einen indirekten Beweis (heißt auch: Beweis durch Widerspruch).

Zitat:

Tipp 2: Tipp 1 heißt: Nimm an, es ist n' = n'' und zeige, dass dann auch n = n' ist. (Warum bist du dann fertig?)

Zitat:

Tipp 3: Du brauchst nur eines der Peano-Axiome!

Zitat:

Damit ist die Lösung schon fast gänzlich verraten, den Rest schaffst du nun hoffentlich alleine.
Ich glaub an dich! smile

Gute Nacht für heute,
carlf Wink

23.05.2011, 00:06

marie123

Auf diesen Beitrag antworten »

ok ich versuche das jetz mal alleine...
vielen vielen vielen dank für die viele mühe und vor allen dingen die gedult ..

gute nacht Wink

23.05.2011, 00:22

marie123

Auf diesen Beitrag antworten »

so ... also es hat was mit P4 zu tun... irgendwie sieht man das....

aber ich nuja wie gesagt bin da zu blöd für...

mein ansatz ist jetz :

n´ = m

wenn nun n`=m´ bedeutet das das m= n sein muss laut P4

allerdings ist m= n´ und somit wäre ja n=n` .. und das geht gegen die bedingung von der Menge A das n ungleich n´ ist .

das heißt also Menge A ist ungleich menge N ....

nuja dann stimmt ja die Behauptung nicht. Also ich hoffe nie wieder diese Aufgabe machen zu müssen.. hab ein wenig verstanden aber irgendwie nur halb.. trotz guter erklärung... und viel zeit..
nuja ich geb die aufgabe einfach so ab... man kann nicht alles verstehen glaub ich

23.05.2011, 12:02

carlf

Auf diesen Beitrag antworten »

Zitat:

Original von marie123
mein ansatz ist jetz :

n´ = m

wenn nun n`=m´ bedeutet das das m= n sein muss laut P4

allerdings ist m= n´ und somit wäre ja n=n` .. und das geht gegen die bedingung von der Menge A das n ungleich n´ ist .

Richtig, genauso funktioniert's! Freude

Wenn n in A liegt und n' nicht in A liegen würde, dann wäre n' = n''.
Aber mit (P4) bedeutet das auch n = n', was im Widerspruch zur Voraussetzung n in A steht.
Also ist die Annahme, dass n' nicht in A liegt (unter der Voraussetzung n in A) falsch, für jedes
n in A ist demnach auch der Nachfolger n' in A.

Zitat:

das heißt also Menge A ist ungleich menge N ....

Tut es nicht. Die Argumentation oben ist genau richtig, dieser Schluss den du ziehst ist falsch.

Denn wir haben jetzt insgesamt gezeigt:
IA: Die 1 liegt in A.
IS: Wenn n in A liegt, dann auch n'.

Das Induktionsaxiom (P5) sagt uns dann, dass bereits $\begin{eqnarray*} A = \mathbb N \end{eqnarray*}$ gelten muss.
Also ist jede natürliche Zahl von ihrem Nachfolger verschieden.

Grüße,
carlf

Neue Frage »

Antworten »

Induktion

Verwandte Themen