g: ℕ × ℕ → ℕ, g(m,0):= m und g(m,f(n)):=f(g(m,n)). Mit Doppelinduktion zeigen g(m,n)=g(n,m)

Question

Die Aufgabe ist:

Sei f : ℕ → ℕ\{0} die Nachfolgerabbildung und die Funktion g : ℕ × ℕ → ℕ die induktiv durch g(m,0) = m und g(m,f(n))=f(g(m,n)) festgelegt ist. Zeige mittels Doppelinduktion, dass g(m,n)=g(n,m).

Meine Ideen:
Ich bin mir nun nicht sicher, was ich zeigen muss.

g(m,f(n)) = f(g(m,n)) = f(g(n,m)) 

oder 

g(f(n),m) = f(g(n,m)) ?

Oder ist das ein komplett falscher Ansatz?

Und kann ich davon ausgehen, dass g(m,n) = m + n? Weil g(m,0) = m und ich kann ja beweisen, dass g(m,1) = m + 1 ist... und dann ist es ja g(n,m) = n + m = m + n . Aber ich glaube, dass darf ich gar nicht annehmen, oder?

Comments

Was genau ist eine "Doppelinduktion"? Google bietet an:

- Die Doppelinduktion ist eine hypnotische Technik, bei der zwei Hypnotiseure auf den Klienten einsprechen.

- Darunter versteht man eine Basis-Konfusionstechnik aus dem Fachbereich der Hypnose.

- Doppelinduktion Induktionskochplatte Kochplatte Herd Induktionsfeld Kochen

---

Ja, das wüsste ich auch gerne. Etwas anderes als google habe ich auch nicht dazu.

---

Was genau ist eine "Doppelinduktion"?

Hier hat mal jemand versucht, das zu erklären.

Beachte aber :  Zwei Furchen auf dem Acker ergeben noch kein vollständig gepflügtes Feld.

---

@Anna

Ich hab den Begriff noch nie gehoert oder gelesen. Allerdings hoere ich auch nicht Deine Vorlesung. Deshalb frage ich Dich!

Wenn man das f ausformuliert, hat man g(m, 0) = m und g(m, n+1) = g(m, n) + 1. Das entspricht der Definition der Addition in den natuerlichen Zahlen nach Peano, also g(m, n) = m + n.

Man nennt so etwas eine rekursive Definition oder auch eine Definition durch vollstaendige Induktion. Dass das einen Sinn ergibt sichert der Rekursionssatz von Dedekind.

Was Du hier zeigen sollst ist also das Kommutativgesetz der Addition in den natuerlichen Zahlen auf Basis der Definition der Addition nach Peano. Beweisen tut man das mit einer stinknormalen Induktion z.B. nach n, wobei man dann m als Parameter betrachtet.

---

vielen dank erst einmal!

also, der Begriff Doppelinduktion ist noch nie in der Vorlesung gefallen, also habe ich auch nicht mehr zur Verfügung...

ich hatte jetzt schon von selbst bewiesen, dass g(m,n) = m + n ist. Allerdings dachte ich, dass ich m + n = n + m nun wirklich als gegeben ansehen kann ... Muss ich das wirklich auch noch beweisen?

---

Allerdings dachte ich, dass ich m + n = n + m nun wirklich als gegeben ansehen kann ...

Warum soll das als gottgegeben hinzunehmen sein? In welchem Zusammenhang steht die Aufgabe? Um was geht es gerade so in der Vorlesung? Warum steht da f(n) statt n+1? Peano-Axiome vielleicht?

---

Ja, Peano-Axiome hatten wir.

Ich weiß nie, was ich jetzt schon annehmen darf und was nicht. Manchmal "wissen" wir simple Sachen und manchmal nicht... Ich definiere ja auch nicht jedes Mal die Addition, wenn ich sie brauche...

Das heißt also, ich muss sowohl beweisen, dass g(m,n) = m + n ist als auch, dass m + n = n + m? Und muss ich dann noch zeigen, dass g(n,m) = n + m ist?

Danke für die Hilfe

---

Ich kann dir leider nicht helfen. Aber ich verzweifle auch gerade an der kompletten Übungsserie..:( (abgesehen von 1a)

Hast du die zweite hinbekommen?

---

haha hallo mitleidende!

also nein, ich habe die 2. aufgegeben, da ich nicht einmal sicher bin, was genau die Ausgangsformel ausformuliert heißen soll.
Naja, wir sind sicher nicht die Einzigen, denen es so geht, allerdings sind die Aufgaben auch nur bedingt besser als letzte Woche.
In einem anderem Forum wurde sogar schon geraten, dass wir uns solche aufgaben nicht gefallen lassen sollen. (in Bezug auf 3b)... Vielleicht sollten wir uns wirklich mal beschweren.

---

.........................................

---

Versuchen kann man es mit dem Beschwerden ja mal.

Aber ich glaube nicht, dass es großartig was bringt. So weit ich weiß, geht er nächstes Jahr in Rente und das ist jetzt nur noch Durchhalten..:/

Üben wir also unsere Frustrationagrenze xD

---

Schreibfehler bei 3) ?

Richtig ist jedenfalls Folgendes :

Um   g(m,n) = g(n,m)  nachzuweisen, wird Induktion nach n gemacht.

Induktionsanfang : g(m,0) = g(0,m) nachweisen.
   Dies geschieht durch Induktion nach m.
   Induktionsanfang :  m = 0
   Induktionsschritt :  g(f(m),0) = g(0,f(m))  nachweisen.

Induktionsschritt :  g(m,f(n)) = g(f(n),m)  nachweisen.
   Hinweis : Dazu muss noch ein Hilfssatz (ebenfalls mit Induktion) bewiesen werden.

---

Nein. 3) ist genau so gemeint, wie es da steht. Mit 1) & 2) weiss ich z.B. schon P(0, n) für alle n. Das kann ich jetzt auch alles so zum Folgern von P(1, 0) benutzen. Dann weiss ich P(1, n) für alle n. Das kann ich wieder alles zum Folgern von P(2, 0) benutzen, usw.

Answer 1

Doppelinduktion für eine Aussage ∀m,n: P(m, n) geht so:

1) P(0, 0) verifizieren.

2) m als Parameter betrachten und den Induktionsschritt bzgl. n machen.

P(m, n) ⇒ P(m, n+1)

3) Induktionsanfaenge für m ≥ 1 nachliefern. m ist jetzt Induktionsvariable.

[ ∀n: P(m, n) ] ⇒ P(m+1, 0)

Quelle: https://www.math.uni-hamburg.de/home/schacht/lnotes/Grundlagen.pdf, S. 28

Ein Beweis zum eigentlichen Thema findet sich z.B. in http://www.math.uni-hamburg.de/home/riemenschneider/anvorl1.pdf S. 63. Da kommt tatsaechlich eine Doppelinduktion vor, aber nicht in voller Allgemeinheit. Man koennte auch zwei normale Induktionen hintereinander machen und auf den Begriff verzichten.

Falls jemand ein Beispiel hat, in dem 3) wirklich benutzt wird und nicht nur P(m, 0) ⇒ P(m+1, 0), waere ich interessiert. Ansonsten scheint der Begriff Doppelinduktion ueberfluessig und wirklich nur eine "Basis-Konfusionstechnik".