Beweis: 1hat keinen Vorgänger < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:50 Di 14.11.2006 | | Autor: | Knut_87 |
| Aufgabe | | Man beweise durch Induktion, dass die natürliche Zahl 1 keinen Vorgänger besitzt. [mm] (\IN:= [/mm] {1,2,...} |
Hallo,
ich habe ein großes Problem mit dieser Aufgabe. Man soll zeigen, dass 1 keinen Vorgänger hat, mithilfe der Induktion und ich habe keine Idee wie ich das tun soll. Beweise durch vollständige Induktion zu führen ist mir bekannt, jedoch komme ich in diesem Fall weder auf einen Ansatz noch auf eine Lösung.
Mein Lösungsweg wäre über Abbildungen (injektiv und nicht surjektiv) da es dann in der Bildmenge ein Element ohne Urbild gibt, jedoch ist dies ja nicht gefordert.
Ich wäre über jede Hilfe dankbar
gruß Knut
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Fragen in diesem Grundlagenbereich sind nicht zu beantworten, wenn man den Hintergrund der Vorlesung nicht kennt: Wie sind die Axiome der natürlichen Zahlen formuliert? Insbesondere: Wie ist das Induktionsaxiom gefaßt?
Du müßtest hier also in hinreichender Klarheit ausbreiten, wie in der Vorlesung vorgegangen wurde.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:15 Di 14.11.2006 | | Autor: | Knut_87 |
Hallo,
In der Vorlesung wurden die Peano-Axiome verwendet.
Die natürlichen Zahlen beginnen bei 1.
Gibt es eine Menge M ⊂ℕ und gilt
I) 1∈M
II) n∈M [mm] \to [/mm] S (n)∈M
dann M=ℕ
reicht das?
Gruß Knut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:26 Di 14.11.2006 | | Autor: | mathemak |
Hallo!
Aus dem Hochschulgeschäft bin ich schon länger raus, aber mir fällt der Name Peano ein.
Stichwort für eine Literatursuche in der Mathe-Bib Deines Vertrauens.
Gruß
mathemak
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:58 Di 14.11.2006 | | Autor: | Knut_87 |
Hey,
bislang hab ich dort nichts gefunden, das mich der Lösung näher bringt und das ich verwenden kann...
Daher ersuche ich ja hier um Hilfe 
gruß Knut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:25 Mi 15.11.2006 | | Autor: | Knut_87 |
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:45 Di 14.11.2006 | | Autor: | Knut_87 |
> ![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Peano-Axiome
>
>
da steht aber weiter unten:
>Peano selbst begann die natürlichen Zahlen in seinen Axiomen mit der 1 >statt mit der 0
außerdem geht das doch analog oder nicht?
Gruß Knut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:53 Di 14.11.2006 | | Autor: | Herby |
Hi,
joh, hast recht, das steht da im Kleingedruckten 
Liebe Grüße
Herby
|
|
|
| |
|
[mm]S[/mm] scheint ja die Nachfolger-Funktion zu sein. Welche Eigenschaften hat [mm]S[/mm] nach Vorlesung?
Ein Beweis müßte irgendwie indirekt laufen, etwa so:
Annahme: 1 hat einen Vorgänger
[mm]M[/mm] sei nun die Menge aller natürlichen Zahlen, die einen Vorgänger haben.
Nach Annahme ist [mm]1 \in M[/mm]. Jetzt zeige mit dem Induktionsaxiom, daß [mm]M = \mathbb{N}[/mm] gilt, daß also alle natürlichen Zahlen einen Vorgänger haben, und konstruiere damit einen Widerspruch. Wozu das ein Widerspruch sein soll, kann ich dir leider nicht sagen, da du die Axiome nicht vollständig beschrieben hast. Vermutlich werden da Eigenschaften von [mm]S[/mm] eine Rolle spielen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:29 Mi 15.11.2006 | | Autor: | Knut_87 |
| Aufgabe | Axiome:
[mm] \IN [/mm] beginnt mit 1
S: [mm] \IN \to \IN [/mm] S sei injektiv und expliziet nicht surjektiv
Wenn M [mm] \subseteq \IN [/mm] und [mm] 1\in [/mm] M und n [mm] \inM \to [/mm] S(n) [mm] \in [/mm] M
dann M= [mm] \IN [/mm]
|
Hi,
ich komme immer noch nicht weiter... ich hab es nun versucht, indem ich 1 einfach als Minimum von [mm] \IN [/mm] definiert hab, aber mir wurde nun mitgeteilt, dass es so nicht gefordert ist :-(
kann mir jemand helfen und die Aufgabe mit den oben genannten Axiomen lösen? (oder mir wenigsten einen Ansatz geben?)
Gruß Knut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:55 Mi 15.11.2006 | | Autor: | moudi |
Hallo Knut
Soweit ich die Peano-Axiome kenne, wobei die natürlichen Zahlen mit 0 beginnen, statt mit 1, ist es ein Axiom, das 0 keinen Vorgänger hat.
Ich zitiere "Zahlen", 3. Auflage, Ebbinghaus et al. Springer 1992, p.17
(P1) [mm] $0\in \IN$
[/mm]
(P2) Wenn [mm] $n\in\IN$, [/mm] dann [mm] $S(n)\in\IN$
[/mm]
(P3) Wenn [mm] $\red{n\in\IN}$, [/mm] dann [mm] $\red{S(n)\neq 0}$]
[/mm]
(P4) Wenn [mm] $0\in [/mm] E$ und wenn aus [mm] $n\in [/mm] E$ stets [mm] $S(n)\in [/mm] E$ folgt, ist [mm] $\IN\subset [/mm] E$.
(P5) Wenn [mm] $m,n\in \IN$, [/mm] folgt aus $S(m)=S(n)$, dass $m=n$ ist.
Warum man so etwas mit Induktion beweisen soll ist mir schleierhaft.
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:01 Mi 15.11.2006 | | Autor: | piet.t |
Hallo,
da stimme ich voll mit Dir überein.
Überhaupt ist die Formulierung der "Axiome" eher zweifelhaft:
1.) " [mm] \IN [/mm] beginnt mit 1" - was soll das überhaupt bedeuten, das ist so doch erst mal sehr schwammig.
2.) Wenn man eine surjektive Sukzessorabbildung zulässt dann kann man ja auch "endliche" natürliche Zahlen einführen:
sein N = [mm] \{1,2\} [/mm] und S:N [mm] \to [/mm] N mit S(1) = 2 und S(2) = 1 - das erfüllt m.E. alle o.g. Forderungen (ausser vielleicht das "beginnt mit", aber das ist mir eben auch noch nicht klar)...
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:09 Mi 15.11.2006 | | Autor: | Knut_87 |
Hi,
oben ist mir leider ein Tippfehler unterlaufen. die Funktion ist _nicht_surjektiv!
gruß Knut
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:28 Mi 15.11.2006 | | Autor: | piet.t |
O.K., nachdem jetzt die surjektiv-Frage geklärt ist wird das ganze schon klarer. Ich gebe Dir erstmal eine Starthilfe, wenn das noch nicht reicht kannst Du ja nochmal nachhaken.
Sei [mm] M=S(\IN) [/mm] - also die Menge aller Nachfolger von natürlichen Zahlen.
Angenommen 1 habe einen Vorgänger, d.h. 1 [mm] \in [/mm] M
Und jetzt kannst Du das Induktionsaxiom verwenden und damit zeigen, dass dann S surjektiv sein muss - ein Widerspruch zum 2. Axiom.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:18 Mi 15.11.2006 | | Autor: | Knut_87 |
Hallo,
langsam verzweifel ich an dieser Aufgabe... Ich bekomme es auch mit dieser Starthilfe nicht hin. Mein Problem liegt dabei irgendwie bei den Abbildungen... (surjektiv/injektiv) das muss ich mir so schnell wie möglich noch von einem Mitstudenten erklären lassen, da ich das alleine nicht in den Kopf bekomme :-/
Darf ich dich um die Lösung bitten?
Gruß (vom verzweifelten) Knut :-(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:34 Mi 15.11.2006 | | Autor: | piet.t |
Na dann wollen wir mal:
Sei also M die Menge aller Nachfolger, also [mm] M=S(\IN).
[/mm]
Wenn 1 einen Vorgänger v [mm] \in \IN [/mm] hat, dann ist f(v)=1, also ist 1 [mm] \in [/mm] M.
Wenn nun ein beliebiges n [mm] \in \IN [/mm] in M liegt, dann ist sein Nachfolger S(n) ja sicher auch in M (so ist M ja gerade definiert).
Nach dem Induktionsaxiom ist also [mm] M=\IN [/mm] und wir haben gezeigt, dass [mm] S(\IN) [/mm] = [mm] \IN [/mm] - und für eine Abbildung [mm] S:\IN \to \IN [/mm] bedeutet das ja gerade, dass S surjektiv ist - damit haben wir einen Widerspruch zum 2. Axiom.
Fertig - und eigentlich gar nicht mal so schlimm wenn man es mal gesehen hat.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:30 Mi 15.11.2006 | | Autor: | Knut_87 |
| Aufgabe | Sei also M die Menge aller Nachfolger, also $ [mm] M=S(\IN). [/mm] $
Wenn 1 einen Vorgänger v $ [mm] \in \IN [/mm] $ hat, dann ist f(v)=1, also ist 1 $ [mm] \in [/mm] $ M.
Wenn nun ein beliebiges n $ [mm] \in \IN [/mm] $ in M liegt, dann ist sein Nachfolger S(n) ja sicher auch in M (so ist M ja gerade definiert).
Nach dem Induktionsaxiom ist also $ [mm] M=\IN [/mm] $ und wir haben gezeigt, dass $ [mm] S(\IN) [/mm] $ = $ [mm] \IN [/mm] $ - und für eine Abbildung $ [mm] S:\IN \to \IN [/mm] $ bedeutet das ja gerade, dass S surjektiv ist - damit haben wir einen Widerspruch zum 2. Axiom. |
Hey,
danke erst mal, ich hab das nun gemacht, und folgendes raus:
M:= [mm] S(\IN) [/mm] also M:={n [mm] \in \IN [/mm] | n+1 [mm] \to [/mm] S(n)}
Fall 1) [mm] \not\in [/mm] M => fertig
Fall 2)
Annahme: 1 [mm] \in [/mm] M dann folgt, dass ein einen Vorgänger hat.
Induktionsannahme: 1 ist in M 1+1=S(1)
Linke Seite 1+1= (Nach Gesetz der Addition) S(1)
Rechte Seite S(1)=1+V(1)=1 (*)
Induktionsschritt: es gilt für ein beliebiges n die Formel n+1= S(n) also soll sie auch für n+1 gelten
(n+1) +1 = S(n+1)
linke Seite: n+1 +1= S(n) + 1 = S(n+1)
rechte Seite S(n+1)
linke Seite = rechte Seite damit gilt Die Formeln für alle n [mm] \in [/mm] M
Damit gilt M= [mm] \IN [/mm] nach Axiom I aber M ist nicht surjektiv (nach Voraussetzung, so dass die ein Widerspruch ist.
(*) ist das so richtig???
soweit richtig nach deinen Ausführungen? Nun frag ich mich, ob das mit der Induktion überhaupt richtig und sinnvoll ist -.- wenn theoretisch kann man es ja viel einfach mit dem Widerspruch beweisen oder damit, dass 1 Minimum ist (ohne Induktion) oder?
Außerdem seh ich den Beweis nicht ganz, denn 1 darf eigentlich in M liegen, ohne dass es einen Widerspruch gibt, weil ich ja sage, dass [mm] \IN [/mm] mit eins beginnt, von wo losgezählt wird, oder?
Oder binge ich gerade alles durcheinander?!
Gruß Knut
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:58 Do 16.11.2006 | | Autor: | piet.t |
Hallo Knut,
> Hey,
>
> danke erst mal, ich hab das nun gemacht, und folgendes
> raus:
>
> M:= [mm]S(\IN)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
also M:={n [mm]\in \IN[/mm] | n+1 [mm]\to[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
S(n)}
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]") Das verstehe ich jetzt nicht
Was soll denn [mm]n+1\to S(n)[/mm] bedeuten???
M ist die Menge aller Nachfolger, d.h. [mm]M:= \{n\in\IN |\exists m\in\IN \text{mit} S(m)=n\}[/mm]
>
> Fall 1)1 [mm]\not\in[/mm] M => fertig
>
> Fall 2)
> Annahme: 1 [mm]\in[/mm] M dann folgt, dass ein einen Vorgänger
> hat.
> Induktionsannahme: 1 ist in M 1+1=S(1)
1 [mm] \in [/mm] M ist nicht die Induktionsannahme (zwar eine Annahme, aber nicht die IA) sondern der Induktionsanfang: die erste Voraussetzung die erfüllt sein muss um mit dem Induktionsaxiom zu zeigen, dass [mm] M=\IN [/mm] ist.
> Linke Seite 1+1= (Nach Gesetz der Addition) S(1)
> Rechte Seite S(1)=1+V(1)=1 (*)
Eine "Vorgängerabbildung" V haben wir noch nirgends definiert, also lassen wir besser die Finger davon.
> Induktionsschritt: es gilt für ein beliebiges n die Formel
> n+1= S(n) also soll sie auch für n+1 gelten
> (n+1) +1 = S(n+1)
>
> linke Seite: n+1 +1= S(n) + 1 = S(n+1)
> rechte Seite S(n+1)
>
> linke Seite = rechte Seite damit gilt Die Formeln für alle
> n [mm]\in[/mm] M
>
Nein, im Induktionsschritt ist zu zeigen, dass wenn [mm] n\in [/mm] M (d.h. es gibt ein m [mm] \in \IN [/mm] mit S(m)=n), dann ist auch S(n) in M (d.h. es gibt ein [mm] m'\in \IN [/mm] mit S(m')=S(n) - was wird das wohl für ein m' sein?![[grins]](/images/smileys/grins.gif "[grins]") )
> Damit gilt M= [mm]\IN[/mm] nach Axiom I aber M ist nicht surjektiv
> (nach Voraussetzung, so dass die ein Widerspruch ist.
>
> (*) ist das so richtig???
>
> soweit richtig nach deinen Ausführungen? Nun frag ich mich,
> ob das mit der Induktion überhaupt richtig und sinnvoll ist
> -.- wenn theoretisch kann man es ja viel einfach mit dem
> Widerspruch beweisen oder damit, dass 1 Minimum ist (ohne
> Induktion) oder?
Den Widerspruch kriegt man aber nur, wenn man zeigt dass [mm] M=\IN [/mm] ist - und das geht ja nur über Induktion, oder hast Du einen anderen Vorschlag? (Wenn man wirklich nur von den Axiomen ausgeht kann eigentlich fast jeder Beweis für natürliche Zahlen nur ein Induktionsbeweis sein.)
Zur Sache mit dem Minimum: was heißt eigentlich Minimum? Was für eine Ordnung ist auf [mm] \IN [/mm] definiert, wie hängt diese mit der Abbildung S zusammen? Weider eine Menge undefinierter Begriffe, die man deshalb gar nicht ins Spiel bringen sollte.
Wenn man sich wie hier um grundlegende Sachen kümmert wird die Mathematik zwangsläufig sehr formal. Auch wenn die gewohnten Vorstellungen einem oft eine Beweisrichtung andeuten sollte man sie beim tatsächlichen Beweis doch besser ausblenden und sich wirklich nur auf das verlassen was geschrieben steht.
>
> Außerdem seh ich den Beweis nicht ganz, denn 1 darf
> eigentlich in M liegen, ohne dass es einen Widerspruch
> gibt, weil ich ja sage, dass [mm]\IN[/mm] mit eins beginnt, von wo
> losgezählt wird, oder?
Wenn S nicht surjektiv ist, dann bedeutet das doch gerade, dass es (mindestens) ein [mm] n\in\IN [/mm] gibt, das nicht als Bild einer anderen natürlichen Zahl unter S vorkommt. Unser Beweis geht eigentlich nur dahin, dass 1 dann gerade ein solches n ist.
Und 1 darf sehr wohl in [mm] \IN [/mm] liegen, allerdings darf [mm] S(\IN) [/mm] nicht gleich ganz [mm] \IN [/mm] sein (was wir ja per Induktion gezeigt hätten), denn [mm] S(\IN)=\IN [/mm] bedeutet ja gerade, dass S surjektiv ist.
>
> Oder binge ich gerade alles durcheinander?!
>
> Gruß Knut
>
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Do 16.11.2006 | | Autor: | Knut_87 |
Hallo,
ok, ich seh schon, ich werde diese Aufgabe wohl nicht lösen... ich weiß nicht warum, aber ich komme mit der Aufgabenstellugn etc nicht zu recht. Was mir irgendwie Sorgen macht ist, dass ich sonst alle Aufgaben kann, nur hier nichts anwenden kann bzw nicht einmal einmal weiß, was du meinst (mit deinen Hilfen) (z.b. was soll sonst die Induktionsannahme sein?!?!) so hatten wir das nicht -.- Ich kenne Induktionsbeweise bisher nur für Formlen...
kannst du mir also sagen, was die Induktionsannahme ist?
gruß Knut
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:31 Do 16.11.2006 | | Autor: | piet.t |
O.K., zerbröseln wir doch das Induktionsaxiom nochmal Schritt für Schritt. Im Axiom ist bei der Induktion immer von einer Menge M die Rede. In den Beispielen, die Du bisher gemacht hast ist das in der Regel die Menge aller Zahlen, für die z.B. eine bestimmte Formel gilt.
1.) "Ist 1 [mm] \in [/mm] M..." das ist der Induktionsanfang: z.B. die gegebene Formel ist für n=1 richtig.
2.) "...und aus n [mm] \in [/mm] M...." das ist die Induktionsannahme: für n [mm] \in \IN [/mm] gelte diese Formel
3.) "...folgt S(n) [mm] \in [/mm] M..." ist der Induktionsschluss: zeige, dass die Formel dann auch für S(n) = n+1 gilt.
4.) "...dann ist [mm] M=\IN". [/mm] Im Beispiel ist dann also gezeigt, dass die zu beweisende Formel für alle natürlichen Zahlen gilt.
In dieser Aufgabe ist M jetzt eben nicht eine Menge für die irgendeine rechnerische Identität richtig ist, sondern nur "alle Zahlen mit Vorgänger".
Der "Induktionsteil" vielleicht nochmal isoliert:
1.) Induktionsanfang: 1 hat einen Vorgänger. wir tun einfach mal so als hätte 1 einen, daraus folgern wir dann den Widerspruch.
2.) Induktionsannahme: [mm] n\in \IN [/mm] soll einen Vorgänger haben.
3.) Induktionsschluss: Wir müssen zeigen, dass S(n) einen Vorgänger hat. Den kann man aber einfach hinschreiben, das ist n. Hier haben wir die Induktionsannahme eigentlich gar nicht benötigt, aber egal...
4.) Das heißt jede natürliche Zahl hat einen Vorgänger(was aber laut dem "nicht surjektiv" aus dem 2. Axiom nicht sein darf).
Vielleicht ist es so ein klein bisschen klarer.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:03 Fr 17.11.2006 | | Autor: | Knut_87 |
Hallo,
ok, ich glaube ich habs verstanden :) vielen Dank!
Ich freue mich über die geduldige Hilfe!!
Gruß Knut
|
|
|
|
![[haee]](/images/smileys/haee.gif "[haee]"){kind=small}
![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]"){kind=small}
