Peano-Axiome (voll. Induktion) < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei die Menge der natürlichen Zahlen mit der 0 und der Nachfolgerfunktion s, also [mm] $\IN [/mm] = [mm] \{0,s(0), s(s(0)),...\}.$ [/mm] Darauf sei die Addition rekursiv definiert wie folgt:
m + 0 = m für alle $m [mm] \in \IN$
[/mm]
m + s(n) = s(m + n) für alle $m,n [mm] \in \IN$
[/mm]
Beweisen Sie:
a) Lemma 1: für alle $m [mm] \in \IN:$ [/mm] 0 + m = m (vollständige Induktion nach m)
b) Lemma 2: für alle $m,n [mm] \in \IN:$ [/mm] s(n) + m = s(n + m) (vollständige Induktion nach m)
c) Theorem: für alle $m,n [mm] \in \IN:$ [/mm] m + n = n + m (vollständige Induktion nach n) |
Hallo,
ich bin die Teilaufgabe a) wie unten angegangen, weiß aber nicht, ob das der richtige Weg ist, denn bei "Dann folgt:" würde ich nochmal das "Zu zeigen:" schreiben (die Aufgabe stammt übrigens aus der Vorlesung "Logik und diskrete Strukturen")...
Induktionsanfang m = 0: 0 + 0 = 0
Induktionsschritt $m [mm] \to [/mm] m + 1$
Induksionsvoraussetzung:
Für ein $m [mm] \in \IN$ [/mm] gelte 0 + m = m
Zu zeigen: 0 + (m + 1) = m + 1
Dann folgt:
Bin für jeden Hinweis wie immer sehr dankbar.
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:18 Mi 04.05.2011 | | Autor: | leduart |
Hallo
du brauchst m+1=s(m) und
m + s(n) = s(m + n) für alle $ m,n [mm] \in \IN [/mm] $
Gruss leduart
|
|
|
| |
|
| Aufgabe | Gegeben sei die Menge der natürlichen Zahlen mit der 0 und der Nachfolgerfunktion s, also $ [mm] \IN [/mm] = [mm] \{0,s(0), s(s(0)),...\}. [/mm] $ Darauf sei die Addition rekursiv definiert wie folgt:
m + 0 = m für alle $ m [mm] \in \IN [/mm] $
m + s(n) = s(m + n) für alle $ m,n [mm] \in \IN [/mm] $
Beweisen Sie:
a) Lemma 1: für alle $ m [mm] \in \IN: [/mm] $ 0 + m = m (vollständige Induktion nach m)
b) Lemma 2: für alle $ m,n [mm] \in \IN: [/mm] $ s(n) + m = s(n + m) (vollständige Induktion nach m)
c) Theorem: für alle $ m,n [mm] \in \IN: [/mm] $ m + n = n + m (vollständige Induktion nach n) |
Hallo leduart,
> du brauchst m+1=s(m) und
> m + s(n) = s(m + n) für alle [mm]m,n \in \IN[/mm]
wie kommt das m + 1 = s(m) zustande?
Ich sehe leider auch noch nicht, warum ich m + s(n) = s(m + n) für das Lemma 1 verwenden darf, obwohl ich b) und c) noch nicht bewiesen habe?
Gruß
el_grecco
|
|
|
| |
|
Hallo grec,
die Aufgabe ist schon sinnvoll aufgebaut. Du arbeitest sie am besten in der Reihenfolge a), b), c) durch, dann darfst Du auch Ergebnisse daraus jeweils weiterverwenden.
> Gegeben sei die Menge der natürlichen Zahlen mit der 0 und
> der Nachfolgerfunktion s, also [mm]\IN = \{0,s(0), s(s(0)),...\}.[/mm]
> Darauf sei die Addition rekursiv definiert wie folgt:
>
> m + 0 = m für alle [mm]m \in \IN[/mm]
>
>
> m + s(n) = s(m + n) für alle [mm]m,n \in \IN[/mm]
>
>
> Beweisen Sie:
>
> a) Lemma 1: für alle [mm]m \in \IN:[/mm] 0 + m = m (vollständige
> Induktion nach m)
> b) Lemma 2: für alle [mm]m,n \in \IN:[/mm] s(n) + m = s(n + m)
> (vollständige Induktion nach m)
> c) Theorem: für alle [mm]m,n \in \IN:[/mm] m + n = n + m
> (vollständige Induktion nach n)
Ich lasse das Gemüse mal stehen, dann ist es leichter weiter zu ziteren.
> > du brauchst m+1=s(m) und
> > m + s(n) = s(m + n) für alle [mm]m,n \in \IN[/mm]
>
> wie kommt das m + 1 = s(m) zustande?
s(m):=m+1 ist doch die Definition der Nachfolgerfunktion. Die 1 wird aus der Null definiert (der einzige unsaubere Schritt bei Peano, daher oft besser erst bei 1 begonnen):
s(0)=0+1=1, die 2 folgt daraus: s(1)=1+1=2 etc.
Dies ist die einzige Addition, die den Peano-Axiomen zugrundeliegt. Zu jeder existierenden Zahl darf eine 1 addiert werden. Das Ergebnis wird "Nachfolger" genannt.
> Ich sehe leider auch noch nicht, warum ich m + s(n) = s(m +
> n) für das Lemma 1 verwenden darf, obwohl ich b) und c)
> noch nicht bewiesen habe?
Wie gesagt, würde ich das auch nicht machen.
Grüße
reverend
|
|
|
| |
|
| Aufgabe | Gegeben sei die Menge der natürlichen Zahlen mit der 0 und der Nachfolgerfunktion s, also $ [mm] \IN [/mm] = [mm] \{0,s(0), s(s(0)),...\}. [/mm] $ Darauf sei die Addition rekursiv definiert wie folgt:
m + 0 = m für alle $ m [mm] \in \IN [/mm] $
m + s(n) = s(m + n) für alle $ m,n [mm] \in \IN [/mm] $
Beweisen Sie:
a) Lemma 1: für alle $ m [mm] \in \IN: [/mm] $ 0 + m = m (vollständige Induktion nach m)
b) Lemma 2: für alle $ m,n [mm] \in \IN: [/mm] $ s(n) + m = s(n + m) (vollständige Induktion nach m)
c) Theorem: für alle $ m,n [mm] \in \IN: [/mm] $ m + n = n + m (vollständige Induktion nach n) |
Hallo rev,
> s(m):=m+1 ist doch die Definition der Nachfolgerfunktion.
> Die 1 wird aus der Null definiert (der einzige unsaubere
> Schritt bei Peano, daher oft besser erst bei 1 begonnen):
> s(0)=0+1=1, die 2 folgt daraus: s(1)=1+1=2 etc.
>
> Dies ist die einzige Addition, die den Peano-Axiomen
> zugrundeliegt. Zu jeder existierenden Zahl darf eine 1
> addiert werden. Das Ergebnis wird "Nachfolger" genannt.
>
> > Ich sehe leider auch noch nicht, warum ich m + s(n) = s(m +
> > n) für das Lemma 1 verwenden darf, obwohl ich b) und c)
> > noch nicht bewiesen habe?
>
> Wie gesagt, würde ich das auch nicht machen.
vielen Dank für Deine Hilfe. Ich habe die a) erneut begonnen, bin mir aber nicht sicher, ob der neue Ansatz stimmt und vor allem lässt mir der letzte Schritt keine Ruhe...
s(m) := m + 1
Induktionsanfang m = 0: s(0) = 0 + 1 = 1
Induktionsschritt $ m [mm] \to [/mm] m + 1 $
Induktionsvoraussetzung:
Für ein $ m [mm] \in \IN [/mm] $ gelte s(m) = m + 1
Zu zeigen: s(m+1) = (m+1) + 1 = m + 2
Es gilt:
s(m+1) = s(m) + (m+1)
= m + 1 + m + 1
= 2m + 2
= 2(m + 1)
> Grüße
> reverend
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:31 Do 05.05.2011 | | Autor: | leduart |
Hallo
du weisst doch selbst, dass s(m+1)=m+1+1 ist und sicher NICHt 2m+2!
schreib deutlich hin was du zeigen willst, und was du jeweils benutzest.
gruss leduart
|
|
|
| |
|
| Aufgabe | Gegeben sei die Menge der natürlichen Zahlen mit der 0 und der Nachfolgerfunktion s, also $ [mm] \IN [/mm] = [mm] \{0,s(0), s(s(0)),...\}. [/mm] $ Darauf sei die Addition rekursiv definiert wie folgt:
m + 0 = m für alle $ m [mm] \in \IN [/mm] $
m + s(n) = s(m + n) für alle $ m,n [mm] \in \IN [/mm] $
Beweisen Sie:
a) Lemma 1: für alle $ m [mm] \in \IN: [/mm] $ 0 + m = m (vollständige Induktion nach m)
b) Lemma 2: für alle $ m,n [mm] \in \IN: [/mm] $ s(n) + m = s(n + m) (vollständige Induktion nach m)
c) Theorem: für alle $ m,n [mm] \in \IN: [/mm] $ m + n = n + m (vollständige Induktion nach n) |
Hallo leduart,
Lemma 1:
> du weisst doch selbst, dass s(m+1)=m+1+1 ist und sicher
> NICHt 2m+2!
> schreib deutlich hin was du zeigen willst, und was du
> jeweils benutzest.
Ich hoffe, dass das jetzt so stimmt, denn einen anderen Gedanken habe ich leider nicht (wahrscheinlich flößt mir der mächtige Begriff "Peano-Axiom" unbemerkt Angst ein):
s(m) := m + 1
Induktionsanfang m = 0: s(0) = 0 + 1 = 1
Induktionsschritt $ m [mm] \to [/mm] m + 1 $
Induktionsvoraussetzung:
Für ein $ m [mm] \in \IN [/mm] $ gelte s(m) = m + 1
Zu zeigen: s(m+1) = (m+1) + 1 = m + 2
Es gilt:
s(m+1) = s(m) + 1
= (m + 1) + 1
= m + 2
> gruss leduart
Danke
&
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:18 Do 05.05.2011 | | Autor: | leduart |
Hallo
ich dachte du wolltest
Lemma 1: für alle $ m [mm] \in \IN: [/mm] $ 0 + m = m (vollständige Induktion nach m)
zeigen?
du weisst m+0=m und m + s(n) = s(m + n) du willst 0+m=m in Lemma 1
in lemma 2: du willst s(n) + m = s(n + m)du hast die " axiome und Lemma 1
du schreibst: Zu zeigen: s(m+1) = (m+1) + 1 = m + 2 wo wird der Beweis gefragt?
Schreib wirklich auf, was du zeigen willst und warum das eines der gefragten lemmas ist!, auch wenns schon in der Aufgabe steht.
Gruss leduart
|
|
|
| |
|
| Aufgabe | Gegeben sei die Menge der natürlichen Zahlen mit der 0 und der Nachfolgerfunktion s, also $ [mm] \IN [/mm] = [mm] \{0,s(0), s(s(0)),...\}. [/mm] $ Darauf sei die Addition rekursiv definiert wie folgt:
m + 0 = m für alle $ m [mm] \in \IN [/mm] $
m + s(n) = s(m + n) für alle $ m,n [mm] \in \IN [/mm] $
Beweisen Sie:
a) Lemma 1: für alle $ m [mm] \in \IN: [/mm] $ 0 + m = m (vollständige Induktion nach m)
b) Lemma 2: für alle $ m,n [mm] \in \IN: [/mm] $ s(n) + m = s(n + m) (vollständige Induktion nach m)
c) Theorem: für alle $ m,n [mm] \in \IN: [/mm] $ m + n = n + m (vollständige Induktion nach n) |
Hallo leduart,
ich beginne besser bei Adam und Eva, denn irgendwie ist da der Wurm drinnen.
Lemma 1:
Induktionsanfang m = 0: 0 + 0 = 0
Induktionsschritt $ m [mm] \to [/mm] m + 1 $
Induksionsvoraussetzung:
Für ein $ m [mm] \in \IN [/mm] $ gelte 0 + m = m
Zu zeigen: 0 + (m + 1) = m + 1
Dann folgt:
0 + (m + 1) = (0 + m) + 1 = m + 1
Stimmt das so/Kann man das so akzeptieren?
Vielen Dank!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:08 Do 05.05.2011 | | Autor: | leduart |
Hallo
> Gegeben sei die Menge der natürlichen Zahlen mit der 0 und
> der Nachfolgerfunktion s, also [mm]\IN = \{0,s(0), s(s(0)),...\}.[/mm]
> Darauf sei die Addition rekursiv definiert wie folgt:
>
> m + 0 = m für alle [mm]m \in \IN[/mm]
>
> m + s(n) = s(m + n) für alle [mm]m,n \in \IN[/mm]
>
> Beweisen Sie:
>
> a) Lemma 1: für alle [mm]m \in \IN:[/mm] 0 + m = m (vollständige
> Induktion nach m)
> b) Lemma 2: für alle [mm]m,n \in \IN:[/mm] s(n) + m = s(n + m)
> (vollständige Induktion nach m)
> c) Theorem: für alle [mm]m,n \in \IN:[/mm] m + n = n + m
> (vollständige Induktion nach n)
> Hallo leduart,
>
> ich beginne besser bei Adam und Eva, denn irgendwie ist da
> der Wurm drinnen.
>
> Lemma 1:
>
> Induktionsanfang m = 0: 0 + 0 = 0
>
> Induktionsschritt [mm]m \to m + 1[/mm]
>
> Induksionsvoraussetzung:
> Für ein [mm]m \in \IN[/mm] gelte 0 + m = m
>
> Zu zeigen: 0 + (m + 1) = m + 1
wegen: m + s(n) = s(m + n) für alle $m,n [mm] \in \IN$
[/mm]
richtiger 0+S(m)=S(0+m)=_{nach ind Vors.!}S(m)=m+1
> Dann folgt:
>
> 0 + (m + 1) = (0 + m) + 1 = m + 1
Die Klammerregeln stehen ja nirgends! die kannst du dann als Lemma 4 oder 5 zeigen! (sie sind richtig, aber du hast es nicht aus den Vorgaben gezeigt!)
> Stimmt das so/Kann man das so akzeptieren?
siehe oben
wirklich IMMER sagen, was du benutzt.
Gruss leduart
|
|
|
|
