Induktion Gesetze < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Lösungsweg:
a) I.Anfang: n = 1: p(0, 1) = 1
I.Vorauss.: n $ [mm] \in [/mm] $N: p(0, n) = n
I.Schritt: n $ [mm] \to [/mm] $n + 1
I.Beweis: p(0, n + 1) = n + 1
b) I.Anfang: n = 1: p(2, m) = s(p(1, m))
I.Vorauss.: n $ [mm] \in [/mm] $N: p(s(n), m) = s(p(n, m))
I.Schritt: n $ [mm] \to [/mm] $n + 1
I.Beweis: p(s(n + 1), m) = s(p(n + 1, m))
c) I.Anfang: n = 1: p(1, m) = p(m, 1)
I.Vorauss.: n $ [mm] \in [/mm] $N: p(n, m) = p(m, n)
I.Schritt: n $ [mm] \to [/mm] $n + 1
I.Beweis: p(n + 1, m) = p(m, n + 1)
Soweit bin ich gekommen, allerdings weiß ich nicht, wie der Beweis nun fortgesetzt werden muss...
Danke im Voraus für Eure Hilfe!
Gruß Ptolemaios
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:41 Do 03.05.2012 | | Autor: | barsch |
Hallo Ptolemaios!
> Gegeben seien die Menge der natürlichen Zahlen [mm]\IN[/mm], die
> Nachfolge-Funktion s : [mm]\IN \to \IN[/mm] (s(n):= n + 1), die
> Abbildung P : [mm](\IN[/mm] x [mm]\IN)[/mm] [mm]\to[/mm][mm]\IN[/mm]& die folgenden beiden
> Gesetze:
>
> p(n, 0) = n
> p(n, s(m)) = s(p(n, m))
>
> Beweisen Sie folgende, weitere Gesetze (mit vollständiger
> Induktion).
>
> a) p(0, n) = n [mm]\forall[/mm]n [mm]\in[/mm]N
> b) p(s(n), m) = s(p(n, m)) [mm]\forall[/mm]n, m [mm]\in[/mm]X
> c) p(n, m) = p(m, n) [mm]\forall[/mm]n, m [mm]\in[/mm]X
>
> Lösungsweg:
> a) I.Anfang: n = 1: p(0, 1) = 1
> I.Vorauss.: Es gelte für ein n [mm]\in[/mm]N: p(0, n) = n
> I.Schritt: n [mm]\to[/mm]n + 1
> I.Beweis: p(0, n + 1) = n + 1
>
> b) I.Anfang: n = 1: p(2, m) = s(p(1, m))
> I.Vorauss.: Es gelte für ein n [mm]\in[/mm]N: p(s(n), m) = s(p(n,
> m))
> I.Schritt: n [mm]\to[/mm]n + 1
> I.Beweis: p(s(n + 1), m) = s(p(n + 1, m))
>
> c) I.Anfang: n = 1: p(1, m) = p(m, 1)
> I.Vorauss.: Es gelte für ein n [mm]\in[/mm]N: p(n, m) = p(m, n)
> I.Schritt: n [mm]\to[/mm]n + 1
> I.Beweis: p(n + 1, m) = p(m, n + 1)
>
>
> Soweit bin ich gekommen, allerdings weiß ich nicht, wie
> der Beweis nun fortgesetzt werden muss...
> Danke im Voraus für Eure Hilfe!
Sei mir nicht böse, aber Lösungen sind das keine. Das sind - wie du eingangs richtig erwähnst - Lösungswege, die noch mit Leben gefüllt werden müssen.
Du musst z.B. zeigen:
a) p(0, n) = n [mm]\forall[/mm]n [mm]\in[/mm]N
Das sollst du mit Hilfe vollständiger Induktion zeigen. Verwenden darfst du
- s : [mm]\IN \to \IN[/mm] , s(n):= n + 1
- [mm]P : \IN \times \IN\to\IN[/mm] mit [mm]1. \ \ p(n,0)=n[/mm] und [mm]2. \ \ p(n,s(m)) = s(p(n, m))[/mm]
> Lösungsweg:
> a) I.Anfang: n = 1: p(0, 1) = 1
du hast nur hingeschrieben, was zu zeigen ist. Ziel ist, so umzuformen, dass du mit 1. und 2. arbeiten kannst.
[mm]p(0,1)=p(0,s(0))\stackrel{\mathrm{2.}}=s(p(0,0))\stackrel{\mathrm{1.}}=s(0)=0+1=1[/mm]
> I.Vorauss.: Es gelte für ein n [mm]\in[/mm]N: p(0, n) = n
> I.Schritt: n [mm]\to[/mm]n + 1
Also: [mm]p(0,n+1)=p(0,s(n))=s(p(0,n))\stackrel{\mathrm{IV.}}=s(n)=n+1[/mm], da nach IV. [mm]p(0,n)=n[/mm].
> Gruß Ptolemaios
Das war die a). Fehlen noch b) und c). Versuche die zu lösen und bei Rückfragen einfach melden.
Gruß
barsch
|
|
|
| |
|
Danke für Deine Antwort. Nun habe ich verstanden, wie man vorgehen muss. Allerdings kommt ab dem Aufgabenteil b) noch die Variable m dazu. Ich habe es mal für den I.Anfang bei b) versucht:
n = 1: p(s(n), m) = p(s(1), m) [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(1, m)) und hier weiß ich dann nicht was für einen Wert m hat und wie ich weiter damit umgehen soll. Ist m = 0 so würde [mm] \stackrel{\mathrm{1.}}= [/mm] s(1) = 2 rauskommen. Ist m = 1 so würde [mm] \stackrel{\mathrm{1.}}= [/mm] s(2) = 3 rauskommen.
Kannst Du mir erklären wie man m behandelt?
Gruß Ptolemaios
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:31 Do 03.05.2012 | | Autor: | barsch |
Hallo!
> Danke für Deine Antwort. Nun habe ich verstanden, wie man
> vorgehen muss. Allerdings kommt ab dem Aufgabenteil b) noch
> die Variable m dazu. Ich habe es mal für den I.Anfang bei
> b) versucht:
>
> n = 1: p(s(n), m) = p(s(1), m) [mm]\stackrel{\mathrm{2.}}=[/mm]
> s(p(1, m))
Der Teufel steckt - wie immer - im Detail. So geht es nicht. Siehe dir 2. noch einmal an.
- [mm] P : \IN \times \IN\to\IN [/mm] mit [mm] 1. \ \ p(n,0)=n [/mm] und [mm] 2. \ \ p(n,s(m)) = s(p(n, m)) [/mm]
Das Argument s(.) steht nicht an erster, sondern an zweiter Stelle!
> und hier weiß ich dann nicht was für einen
> Wert m hat und wie ich weiter damit umgehen soll. Ist m = 0
> so würde [mm]\stackrel{\mathrm{1.}}=[/mm] s(1) = 2 rauskommen. Ist
> m = 1 so würde [mm]\stackrel{\mathrm{1.}}=[/mm] s(2) = 3
> rauskommen.
> Kannst Du mir erklären wie man m behandelt?
Mir ist auch nur eine "unschöne" Lösung eingefallen. Ich kann mal andeuten, was ich meine:
Wir führen die Induktion über n durch und halten m fest. m sei also feste natürliche Zahl.
Zu zeigen: p(s(n), m) = s(p(n, m))
IA.: n=1
Wir betrachten zuerst den linken Teil der Gleichung:
[mm]p(s(1),m)=p(2,m)=p(2,s(m-1))\stackrel{\mathrm{2.}}=s(p(2,m-1)=s(p(2,s(m-2))\stackrel{\mathrm{2.}}=s(s(p(2,m-2)))=...=\underbrace{s(....(s}_{\textrm{m-mal}}(p(2,0)))...)\stackrel{\mathrm{1.}}=\underbrace{s(....(s}_{\textrm{m-mal}}(2))...)=2+\underbrace{1+...+1}_{\textrm{m-mal}}=2+m[/mm]
Rechte Seite der Gleichung. Selber "Trick":
[mm]s(p(1,m))=...=\underbrace{\underbrace{s}_{1-mal}(\underbrace{s(...(s}_{m-mal}}_{(m+1)-mal}(p(1,0))...))=\underbrace{\underbrace{s}_{1-mal}(\underbrace{s(...(s}_{m-mal}}_{(m+1)-mal}(1)...))=1+1+\underbrace{1+...+1}_{m-mal}=1+1+m=2+m[/mm]
Somit gilt: [mm]p(s(1),m)=s(p(1,m))[/mm]
IV.:...
IS.:...
> Gruß Ptolemaios
Das ist die einzige Idee, die mir im Augenblick einfällt.
Gruß
barsch
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:44 Fr 04.05.2012 | | Autor: | tobit09 |
Hallo Ptolemaios,
ein Hinweis vorweg: Bei euch ist 0 offensichtlich eine natürliche Zahl. Daher muss bei Induktion nach n der Induktionsanfang den Fall n=0 und nicht n=1 behandeln.
Bei b) ist es ungünstig, Induktion nach n zu führen. Betrachte stattdessen ein festes n und führe Induktion nach m.
Viele Grüße
Tobias
|
|
|
| |
|
Tut mir Leid Tobi, das verstehe ich nicht. Warum bei der a) n = 0 behandeln?
Dann enstteht: p(0, 0) = p(0, s(-1)) [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(-1, 0)) [mm]\stackrel{\mathrm{1.}}=[/mm] s(-1) = -1 + 1 =0
Wäre das dann richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:14 Fr 04.05.2012 | | Autor: | tobit09 |
> Warum bei der a)
> n = 0 behandeln?
Weil die Aussage für alle [mm] $n\in\IN$ [/mm] gezeigt werden soll, also auch für $n=0$.
> Dann enstteht: p(0, 0) = p(0, s(-1))
> [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(-1, 0)) [mm]\stackrel{\mathrm{1.}}=[/mm]
> s(-1) = -1 + 1 =0
> Wäre das dann richtig?
Nein. 0 lässt sich nicht als s(-1) schreiben, denn -1 ist keine natürliche Zahl, aber s eine Abbildung mit Definitionsbereich [mm] $\IN$.
[/mm]
Es gilt nach 1.:
$p(0,0)=0$.
|
|
|
| |
|
Aber s(n) := n + 1. Sodass wenn p(0, 0) [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(0, 0) [mm]\stackrel{\mathrm{1.}}=[/mm] s(0) = 0 + 1 = 1 [mm]\neq[/mm] 0
Also stimmt für n = 0, der Induktionsanfang nicht?
Zur b) Du meintest ein festes n und Induktion nach m. Also kann ich für n die 1 wählen, reicht das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:08 Fr 04.05.2012 | | Autor: | tobit09 |
> Aber s(n) := n + 1. Sodass wenn p(0, 0)
> [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(0, 0) [mm]\stackrel{\mathrm{1.}}=[/mm]
> s(0) = 0 + 1 = 1 [mm]\neq[/mm] 0
Der erste Schritt der Gleichungskette stimmt nicht.
> Zur b) Du meintest ein festes n und Induktion nach m. Also
> kann ich für n die 1 wählen, reicht das?
Nein; sorry für meine missverständliche Formulierung. Gemeint war: Sei [mm] $n\in\IN$. [/mm] Zeige per Induktion nach $m$, dass die Gleichung aus b) für dieses $n$ und alle [mm] $m\in\IN$ [/mm] gilt.
|
|
|
| |
|
zur a) Behauptung: p(0, n) = n [mm]\forall[/mm] n [mm]\in[/mm] [mm]\IN[/mm]
I.Anfang: n = 0: p(0, 0) = 0
I.Vorauss.: [mm]\in[/mm] [mm]\IN[/mm]: p(0, n) = n
I.Schritt: n [mm]\to[/mm] n + 1
I.Beweis: p(0, n + 1) = p(0,s(n)) = s(p(0, n)) [mm]\stackrel{\mathrm{IV.}}=[/mm] s(n) = n + 1
Ist das so korrekt?
zur b) Sorry ich verstehe es immer noch nicht. Soll n = m sein, also soll ich für beide den selben Wert einsetzen? Ich habe eine solche Induktion mit n, m noch nie bisher gemacht...
Gruß & danke
Ptolemaios
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:04 Sa 05.05.2012 | | Autor: | tobit09 |
> zur a) Behauptung: p(0, n) = n [mm]\forall[/mm] n [mm]\in[/mm] [mm]\IN[/mm]
> I.Anfang: n = 0: p(0, 0) = 0
> I.Vorauss.: Es gelte für ein n [mm]\in[/mm] [mm]\IN[/mm]: p(0, n) = n
> I.Schritt: n [mm]\to[/mm] n + 1
> I.Beweis: p(0, n + 1) = p(0,s(n)) = s(p(0, n))
> [mm]\stackrel{\mathrm{IV.}}=[/mm] s(n) = n + 1, da nach IV. p(0, n)
> = n gilt.
>
> Ist das so korrekt?
![[ok]](/images/smileys/ok.gif "[ok]") Ja!
> zur b) Sorry ich verstehe es immer noch nicht. Soll n = m
> sein, also soll ich für beide den selben Wert einsetzen?
Nein.
> Ich habe eine solche Induktion mit n, m noch nie bisher
> gemacht...
Wenn du möchtest, kannst du als Vorübung die behauptete Gleichung mal für z.B. $n=587$ per Induktion nach $m$ für alle [mm] $m\in\IN$ [/mm] zeigen. So hast du wie gewohnt nur eine Variable.
Wenn du das geschafft hast, wird es dir vermutlich nicht schwer fallen, $n=587$ durch beliebiges $n$ zu ersetzen.
|
|
|
| |
|
zur b) Behauptung: p(s(n), m) = s(p(n, m)) [mm]\forall[/mm] n, m [mm]\in[/mm] X
I.Anfang: m = 0: p(s(n), 0) = s(p(n, 0))
[mm]\Rightarrow[/mm] p(n + 1, 0) = s(n)
[mm]\Rightarrow[/mm] n + 1 = n + 1
I.Vorauss.: n, m [mm]\in[/mm] X: p(s(n), m) = s(p(n, m))
I.Schritt: m [mm]\to[/mm] m + 1
I.Beweis: p(s(n), m + 1) = s(p(n, m + 1))
[mm]\Rightarrow[/mm] p(n + 1, m + 1) = s(n, m + 1)
[mm]\Rightarrow[/mm] n + 1 + m + 1 = n + 1 + m + 1
Wäre es so korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:56 Sa 05.05.2012 | | Autor: | tobit09 |
> zur b) Behauptung: p(s(n), m) = s(p(n, m)) [mm]\forall[/mm] n, m [mm]\in[/mm]
> X
> I.Anfang: m = 0: p(s(n), 0) = s(p(n, 0))
> [mm]\Rightarrow[/mm] p(n + 1, 0) = s(n)
> [mm]\Rightarrow[/mm] n + 1 = n + 1
Wenn du deine Gedanken wie folgt aufschreibst, stimmt es:
$p(s(n),0)=p(n+1,0)=n+1=s(n)=s(p(n,0))$.
> I.Vorauss.: Es gelte für ein n, m [mm]\in[/mm] X: p(s(n), m) =
> s(p(n, m))
> I.Schritt: m [mm]\to[/mm] m + 1
> I.Beweis: p(s(n), m + 1) = s(p(n, m + 1))
> [mm]\Rightarrow[/mm] p(n + 1, m + 1) = s(n, m + 1)
> [mm]\Rightarrow[/mm] n + 1 + m + 1 = n + 1 + m + 1
Ich tue jetzt mal so, als hättest du eine Gleichungskette vorgelegt in der Art, wie ich sie beim Induktionsanfang vorgeführt habe:
$p(s(n),m+1)=p(n+1,m+1)=n+1+m+1=s(n,m+1)=s(p(n,m+1))$.
Das zweite Gleichheitszeichen ist dann unbegründet. Zunächst weißt du nach 2. ja nur $p(n+1,s(m))=s(p(n+1,m))$.
$s(n,m+1)$ macht keinen Sinn.
Was du grundsätzlich zu tun hast, scheinst du dagegen verstanden zu haben.
|
|
|
| |
|
zur b) p(s(n), m) = s(p(n, m)) [mm]\forall n, m \in X
[/mm]
I.Anfang: m = 0: p(s(n), 0) = p(n + 1,0) = n + 1 = s(n) = s(p(n, 0))
I.Vorauss.: n, m [mm]\in X[/mm]: p(s(n), m) = s(p(n, m))
I.Schritt: m [mm]\to[/mm] m + 1
I.Beweis: p(s(n), m + 1) = p(n + 1, s(m)) [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(n + 1, m)) = s(p(s(n)), m) [mm]\stackrel{\mathrm{IV.}}=[/mm] s(s(p(n, m))) = s(p(n +1, m + 1)
Wäre es so korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:28 Sa 05.05.2012 | | Autor: | tobit09 |
> zur b)zu zeigen: p(s(n), m) = s(p(n, m)) [mm]\forall n, m \in X
[/mm]
X ist die Menge der natürlichen Zahlen?
> I.Anfang: m = 0: p(s(n), 0) = p(n + 1,0) = n + 1 = s(n) =
> s(p(n, 0))
> I.Vorauss.: Es gelte für ein n, m [mm]\in X[/mm]: p(s(n), m) =
> s(p(n, m))
> I.Schritt: m [mm]\to[/mm] m + 1
> I.Beweis: p(s(n), m + 1) = p(n + 1, s(m))
> [mm]\stackrel{\mathrm{2.}}=[/mm] s(p(n + 1, m)) = s(p(s(n)), m)
> [mm]\stackrel{\mathrm{IV.}}=[/mm] s(s(p(n, m))) = s(p(n +1, m + 1),
> da nach Defintion s(n) := n + 1
Bis auf das zu viel dahingeratene "+1":
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:41 Sa 05.05.2012 | | Autor: | Ptolemaios |
Hat sich geklärt...
Danke nochmal!
Gruß Ptolemaios
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:40 So 06.05.2012 | | Autor: | Loddar |
Hallo!
Noch so eine Ego-Aktion! ![[motz]](/images/smileys/motz.gif "[motz]")
Das ist nicht fair, wenn Du hier Deine Fragen unkenntlich machst, nachdem Du brav Deine Antwort erhalten hast.
Loddar
|
|
|
|
