Doppelinduktion

25.10.2017, 15:17

neelhtak

Doppelinduktion

Meine Frage:
Hallo!

Die Aufgabe ist:

"Sei $\begin{eqnarray*} f : \mathbb{N} \to \mathbb{N} \setminus \{ 0\} \end{eqnarray*}$ die Nachfolgerabbildung und die Funktion $\begin{eqnarray*} g : \mathbb{N} \times \mathbb{N} \to \mathbb{N} \end{eqnarray*}$ die induktiv durch $\begin{eqnarray*} g(m,0) = m \end{eqnarray*}$ und $\begin{eqnarray*} g(m,f(n)) = f(g(m,f(n)) \end{eqnarray*}$ festgelegt ist. Zeige mittels Doppelinduktion, dass $\begin{eqnarray*} g(m,n) = g(n,m) \end{eqnarray*}$ .

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

$\begin{eqnarray*} g(m,f(n)) = f(g(m,n)) = f(g(n,m)) \end{eqnarray*}$

oder

$\begin{eqnarray*} g(f(n),m) = f(g(n,m)) \end{eqnarray*}$

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?

Vielen Dank im Voraus.

25.10.2017, 15:25

klarsoweit

Auf diesen Beitrag antworten »

RE: Doppelinduktion

Zitat:

Original von neelhtak
und $\begin{eqnarray*} g(m,f(n)) = f(g(m,f(n)) \end{eqnarray*}$ festgelegt ist.

Steht das so in der Aufgabe?

25.10.2017, 15:32

neelhtak

Auf diesen Beitrag antworten »

RE: Doppelinduktion

Zitat:

Original von klarsoweit

Zitat:

Original von neelhtak
und $\begin{eqnarray*} g(m,f(n)) = f(g(m,f(n)) \end{eqnarray*}$ festgelegt ist.

Steht das so in der Aufgabe?

Sorry nein...

$\begin{eqnarray*} g(m,f(n)) = f(g(m,n)) \end{eqnarray*}$

25.10.2017, 15:33

Leopold

Auf diesen Beitrag antworten »

Es kann hilfreich sein, sich, bevor man mit der eigentlichen Aufgabe beginnt, zu überlegen, welche elementare Rechenoperation $\begin{align*} g(m,n) \end{align*}$ letztlich definiert. Und deren Kommutativität soll hier gezeigt werden.

25.10.2017, 15:36

neelhtak

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Es kann hilfreich sein, sich, bevor man mit der eigentlichen Aufgabe beginnt, zu überlegen, welche elementare Rechenoperation $\begin{align*} g(m,n) \end{align*}$ letztlich definiert. Und deren Kommutativität soll hier gezeigt werden.

okay, dass heißt also es soll auf $\begin{eqnarray*} g(m,n) = m + n = n + m = g(n,m) \end{eqnarray*}$ hinaus laufen?

25.10.2017, 16:38

neelhtak

Auf diesen Beitrag antworten »

Also meine Lösung wäre jetzt:

$\begin{eqnarray*} g(m,n) = m + n \end{eqnarray*}$

Beweis:

$\begin{eqnarray*} IA: n = 0, g(m,0) = m + 0 = m \end{eqnarray*}$

Stimmt laut Definition

$\begin{eqnarray*} IS: g(m,n) = m + n g(m, n+1) = m + n + 1 = g(m, f(n)) = g(m,n) + 1 = g(m, f(n)) = f(g(m,n)) \end{eqnarray*}$

g(m,n) = m + n stimmt also laut Definition für alle n,m aus N

und aufgrund der Kommutativitätfür die Addition gilt:

$\begin{eqnarray*} g(m,n) = m + n = n + m = g(n,m) \end{eqnarray*}$

Deshalb stimmt g(m,n) = g(n,m).

Oder habe ich das falsch verstanden? Und muss ich noch etwas spezielles wegen der Doppelinduktion machen?

Neue Frage »

Antworten »

Doppelinduktion

Verwandte Themen