Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion

26.05.2012, 12:32

bird of the summer

Auf diesen Beitrag antworten »

Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion

Meine Frage:
Hallo,

wir haben im Skript den Beweis für das Kommutativgesetz durch vollständige Induktion gegeben und sollen nun analog dazu das Assoziativgesetz zeigen. Leider kann ich den Beweis im Skript nicht ganz nachvollziehen und habe daher natürlich Probleme mit dem anderen.
Ich schreibe euch mal den vorgegebenen Beweis und meine Fragen dazu auf (Ich hoffe es ist ok, wenn ich es so aufschreibe, mit diesem LaTex habe ich es einfach nicht hinbekommen. N soll hier das Zeichen für die natürlichen Zahlen sein):

z.z. Für alle n,m aus N: n+m = m+n

Beweis durch vollständige Induktion nach n
Es sei A={n|n+m = m+n für alle m aus N}

Induktionsanfang:
Es gilt 1 Element A, da 1+m = m+1

Induktionsvorraussetzung:
Es sei n Element A, also n+m = m+n für alle m Element N gegeben.

Induktionsschluss:
z.z. n+1 Element A
Beweis der Induktionsbehauptung
Es gilt (n+1)+m = (n+m)+1 <=> (m+n)+1 = m+(n+1)

Das ist der Beweis wie er im Skript steht. Nun die Frage, die mich wohl am meisten davon abhält diesen Beweis zu verstehen:
Warum brauche ich diese Menge A? Wozu definiere ich mir denn eine Menge in der genau das gilt, was ich eigentlich zeigen möchte? Was bringt mir das? Bei anderen Induktionsbeweisen haben wir sowas auch nie gemacht, warum muss ich das also gerade bei diesem Beweis machen und kann es nicht ohne diese Menge A zeigen?

Wie ihr seht, bin ich verwirrt! Trotzdem habe ich versucht analog dazu das Assoziativgesetz zu zeigen.

Meine Ideen:
z.z. Für alle n,m,k Element N: n+(m+k) = (n+m)+k

Beweis mittels vollständiger Induktion nach n
Es sei A={n|n+(m+k) = (n+m)+k für alle m,k Element N}

Induktionsanfang:
Es gilt 1 Element A, da für n=1 die Behauptung wie folgt lautet
1+(m+k) = (1+m)+k <=> 1+(m+k) = 1+ (m+k)
Für n=1 ist die Behauptung also wahr.
FRAGE: Darf ich hier einfach so die Klammern verschieben? Ich will ja eigentlich erst zeigen, dass man das darf.

Induktionsvorraussetzung
Es sei n Element A, also gilt für alle m,k Element N:
n+(m+k) = (n+m)+k

Induktionsschluss (von n auf n+1)
z.z. (n+1)+(m+k) = ((n+1)+m)+k
Beweis der Induktionsbehauptung
1+n+(m+k) = (1+n)+(m+k) = (n+1)+(m+k) = ((n+1)+m)+k =>Behauptung
FRAGE auch hier: Darf ich im Beweis einfach so Klammern verschieben, wenn ich doch eingentlich erst beweisen will, dass ich das darf?

Und was hat es mir bei diesem Beweis jetzt gebracht, dass ich mir eine Menge A definiert habe?

Ich wäre euch sehr dankbar für ein paar Tipps.
LG und einen schönen Samstag.

26.05.2012, 12:43

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Generell gilt: Es gibt keine echten Teilmengen A von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ , sodass

1) $\begin{eqnarray*} 1 \in A \end{eqnarray*}$
2) $\begin{eqnarray*} n \in A \Rightarrow n+1 \in A \end{eqnarray*}$

d.h., jede solche Teilmenge A muss ganz $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ sein... Das ist das sog. Induktionsprinzip...

Was den Induktionsschluss n -> n+1 in der 2. Behauptung betrifft, so ist

1+n+(m+k) = (1+n)+(m+k) = (n+1)+(m+k) = ((n+1)+m)+k =>Behauptung

so zu verstehen , dass hier N=1, M=n, K=m+k gesetzt und die schon beweisene Gültigkeit von

(N+M)+K = N+(M+K)

für N=1 verwendet wurde...

26.05.2012, 13:16

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Bisher habe ich es bei Induktionsbeweisen immer so gemacht, dass ich gezeigt habe, dass das ganze für n=1 gilt und dann habe ich gezeigt, dass das ganze dann auch für n+1 gilt. Ist das nicht eigentlich das gleiche wie es hier mit der Menge A auch gemacht wird? Warum brauche ich also diese Menge A und mache es nicht einfach so? Ich verstehe das einfach nicht.

Deine Erklärung zur zweiten Behauptung verstehe ich. Ist der Beweis 1+n+(m+k) = (1+n)+(m+k) = (n+1)+(m+k) = ((n+1)+m)+k =>Behauptung also richtig so??

26.05.2012, 13:45

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion

Zitat:

Original von bird of the summer
Bisher habe ich es bei Induktionsbeweisen immer so gemacht, dass ich gezeigt habe, dass das ganze für n=1 gilt und dann habe ich gezeigt, dass das ganze dann auch für n+1 gilt. Ist das nicht eigentlich das gleiche wie es hier mit der Menge A auch gemacht wird? Warum brauche ich also diese Menge A und mache es nicht einfach so? Ich verstehe das einfach nicht.

Es sind beides verschiedene Sprechweisen für ein und diesselbe Sache... Ich kann mir nicht vorstellen, dass dir jemand "einen Strick daraus dreht", wenn du es auf deine dir gewohnte Art machst... Augenzwinkern

Augenzwinkern

Zitat:

Original von bird of the summer
Deine Erklärung zur zweiten Behauptung verstehe ich. Ist der Beweis 1+n+(m+k) = (1+n)+(m+k) = (n+1)+(m+k) = ((n+1)+m)+k =>Behauptung also richtig so??

Hm, einerseits verstehst du das, andererseits stellst du diese Frage... verwirrt

verwirrt

Natürlich ist das richtig, was ist daran noch unklar?...

26.05.2012, 14:58

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Ach so! Super vielen Dank!

Ich frage immer lieber noch mal, ob es richtig ist, weil ich gerne auf Nummer sicher gehe. Es könnte ja doch sein, dass ich nur glaube es verstanden zu haben, es aber trotzdem falsch ist. =)

Darf ich hier gleich noch eine Frage stellen, auch wenn die nichts mit AG oder KG zu tun hat? Ist nur eine ganz kurze Frage.

Ich soll nämlich außerdem noch duch Induktion zeigen, dass
für alle n Element N: 4n kleiner gleich n^2 + 4

Beim Induktionsschluss stecke ich nun fest. Ich habe es versucht mit

n^2 + 4 + (2n+1) größer gleich 4n + 2n + 1 = 6n+ 1

Ich muss aber ja am Ende auf 4n+ 4 und nicht auf 6n+1 kommen. Was hab ich da denn jetzt falsch gemacht?

26.05.2012, 15:26

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Du musst eine Schlusskette der Art

$\begin{eqnarray*} 4(n+1) = 4n+4 \le... \le (n+1)^2+4 \end{eqnarray*}$

aufstellen, wobei du versuchen muss, das, was ich durch Pünktchen (...) angedeutet habe, mithilfe der Induktionsvoraussetzung (=Richtigkeit der Behauptung für n) aufzufüllen...

Anzeige

26.05.2012, 15:51

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Ich weiß, was ich rausbekommen muss, aber ich weiß einfach nicht wie. Alles was ich ausprobiere bringt mich nicht dahin wo ich hin will.

Wenn ich anfange mit 4n+4 auf der linken Seite, dann muss ich ja +4 auf der rechten Seite rechnen. Also habe ich
4n+4 kleiner gleich n^2 + 8

Aber wie bringe ich das jetzt auf (n+1)^2 + 4 ?? Ich habs mit quadr. Ergänzung probiert, aber das klappt nicht. Und die Ind. vorraussetzung hilft mir da auch nicht.

26.05.2012, 16:03

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Hm, kapier ich nicht... verwirrt

verwirrt

Du musst doch insgesamt zeigen, dass

$\begin{eqnarray*} n^2+8 \le (n+1)^2+4 = n^2+2n+5 \end{eqnarray*}$

gilt, und dass

$\begin{eqnarray*} 8 \le 2n+5 \quad \forall n \ge 1 \end{eqnarray*}$

gilt, ist doch trivial, oder überseh ich da was?

26.05.2012, 16:30

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Warum muss ich zeigen, dass

$\begin{eqnarray*} n^2+8 \le (n+1)^2+4 \end{eqnarray*}$ ??

Ich verstehe das einfach nicht. Tut mir leid.

26.05.2012, 16:38

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Als ich oben sagte

Zitat:

Original von Mystic
Du musst eine Schlusskette der Art

$\begin{eqnarray*} 4(n+1) = 4n+4 \le... \le (n+1)^2+4 \end{eqnarray*}$

aufstellen, wobei du versuchen muss, das, was ich durch Pünktchen (...) angedeutet habe, mithilfe der Induktionsvoraussetzung (=Richtigkeit der Behauptung für n) aufzufüllen...

hast du geantwortet:

Zitat:

Original von bird of the summer
Ich weiß, was ich rausbekommen muss, aber ich weiß einfach nicht wie.

Jetzt habe ich aber den Eindruck, du weißt eben nicht, was rauskommen soll am Ende, nämlich (s.o.)

$\begin{eqnarray*} \ldots \le (n+1)^2+4 \end{eqnarray*}$

Beachte: Du musst die Behauptung beweisen, die sich ergibt, wenn man überall n durch n+1 ersetzt...

26.05.2012, 16:48

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Das weiß ich. Aber ich komme nicht auf die Zwischenschritte!
Ich weiß wie der Anfang aussehen muss und ich weiß was am Ende rauskommen muss, aber es ist mir ein Rätsel wie ich das duch Äquivalenzumfomungen erreichen soll!
Ich schreibe jetzt lieber nicht, wie viele Stunden ich schon an dieser Aufgabe sitze, weil das echt schon peinlich ist!

26.05.2012, 16:54

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion

Zitat:

Original von bird of the summer
Das weiß ich. Aber ich komme nicht auf die Zwischenschritte!

Aber die Zwischenschritte habe ich doch hier im Detail ausgeführt.. Was genau ist dir daran unklar?

26.05.2012, 17:04

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Mir ist unklar wie du auf

$\begin{eqnarray*} n^2+8 \le (n+1)^2+4 \end{eqnarray*}$ kommst? Also mir ist schon klar, dass das so sein muss, aber uns wurde gesagt, dass wir am Ende ja zeigen sollen, dass man für n auch n+1 einsetzen kann. Aber wir dürfen für n doch nicht einfach so n+1 einsetzen, sondern durch Äquivalenzumformungen darauf kommen. Und durch welche Äquivalenzumformung kommt man denn auf $\begin{eqnarray*} (n+1)^2+4 \end{eqnarray*}$ bzw auf
$\begin{eqnarray*} n^2+2n+5 \end{eqnarray*}$ ?

26.05.2012, 23:07

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Es geht hier nicht um Äquivalenzumformungen (da hast du was gründlich missverstanden!), sondern es geht hier darum, ob diese Kette von Ungleichungen (natürlich unter der Voraussetzung, dass die Behauptung für n stimmt!) insgesamt richtig ist... Und das ist sie, oder kannst du mir eine Ungleichung daraus nennen, welche falsch wäre? verwirrt

verwirrt

27.05.2012, 10:42

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Hmm, da in der Uni nie was erklärt wird, ist es leicht viele Dinge zu missverstehen. Ich verstehe es immer noch nicht.
Aber vielen lieben dank für deine Hilfe und deine Geduld!

27.05.2012, 11:27

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Ok, letzter Versuch...Gehen wir den Schluss von n auf n+1 noch einmal in allen Details durch...

Gleich eines vorweg: Wir werden zwischendurch einmal die Ungleichung

$\begin{eqnarray*} 4 \le 2n+1 \end{eqnarray*}$

benötigen, die aber erst ab n=2 richtig ist... Dies bedeutet insbesondere (was ich bisher leider
auch übersehen habe! unglücklich

unglücklich

), dass man für die in Rede stehenden Behauptung

$\begin{eqnarray*} 4n \le n^2+4 \quad \forall n \in \mathbb N \end{eqnarray*}$

die Fälle n=0,1,2 noch direkt überprüfen muss, was aber kein Problem machen sollte...

Wenden wir uns also nun dem Schluss von n auf n+1 zu... Das erklärte Ziel ist es also zu zeigen, dass gilt

$\begin{eqnarray*} 4n \le n^2+4 \Rightarrow 4(n+1) \le (n+1)^2+4 \quad \forall n \ge 2 \end{eqnarray*}$

Ich habe in der entsprechenden Schlusskette

$\begin{eqnarray*} 4(n+1) \underbrace{=}_{(1)}4n+4 \underbrace{\le}_{(2)} (n^2+4)+4 \underbrace{\le}_{(3)}(n^2+2n+1)+4 \underbrace{=}_{(4)}(n+1)^2+4 \end{eqnarray*}$

nun allen Ungleichungen und Gleichungen eine Nummer zugeteilt und du brauchst mir jetzt nur zu sagen, welche der Umformungen bzw. Abschätzungen (1)-(4) du davon nicht verstehst und ich werde dann gerne noch genauer darauf eingehen... Augenzwinkern

Augenzwinkern

27.05.2012, 12:57

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Du gibst ja echt nicht auf zu versuchen mir das zu erklären! Cool! Vielen, vielen Dank!

Schritt 3 verstehe ich nicht so ganz. Du wirst wohl für n n+1 eingesetzt haben, aber mein Dozent hat uns gesagt, dass wir das nur für uns heimlich auf einem Extrablatt einsetzen dürfen und hinschreiben sollen wir es dann aber ausschließlich quasi rückwärts, sodass es aussieht als hätte man eben nur Äquivalenzumformungen gemacht. Diese Aussage von ihm hat mich igendwie voll verwirrt, sodass ich mich nicht mehr traue einfach irgendwo n+1 einzusetzen...

27.05.2012, 13:17

Mystic

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion

Zitat:

Original von bird of the summer
Schritt 3 verstehe ich nicht so ganz. Du wirst wohl für n n+1 eingesetzt haben, aber mein Dozent hat uns gesagt, dass wir das nur für uns heimlich auf einem Extrablatt einsetzen dürfen und hinschreiben sollen wir es dann aber ausschließlich quasi rückwärts, sodass es aussieht als hätte man eben nur Äquivalenzumformungen gemacht. Diese Aussage von ihm hat mich igendwie voll verwirrt, sodass ich mich nicht mehr traue einfach irgendwo n+1 einzusetzen...

Was dein Dozent da sagt, sag ich auch selbst immer, mit einem Wort, er hat 100% recht! Big Laugh

Big Laugh

Ich habe auch tatsächlich nix eingesetzt hier, sondern die Ungleichung vom Anfang, also

$\begin{eqnarray*} 4 \le 2n+1 \quad \forall n \ge 2 \end{eqnarray*}$

vewendet... Hast du auf die total vergessen? verwirrt

verwirrt

27.05.2012, 14:47

bird of the summer

Auf diesen Beitrag antworten »

RE: Beweis Kommutativ - und Assoziativgesetz durch vollständige Induktion
Ich hab die nicht vergessen...nur erfolgreich verdrängt.
Man mag es kaum glauben, aber ich habe es tatsächlich verstanden! Juhuu! Das macht alles absolut Sinn. Genial!

Danke, danke, danke!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »