ω-Nachfolgerfunktion < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:07 Sa 04.01.2014 | | Autor: | Vidane |
| Aufgabe | | Ein einfacher Beweis durch vollständige Induktion zeigt, dass es zu jeder natürlichen Zahl n genau eine [mm] \omega-Nachfolgerfunktion [/mm] mit dem Definitionsbereich n gibt. |
Hey Leute,
Ich denke, die Aufgabe dürfte echt nicht so schwer sein, es würde mir wirklich helfen, wenn ihr das mal kurz durchlest. Ich hab alles recht ausführlich verfasst. Jeder kleiner Hinweis würde mir sehr helfen.
Die Aufgabenstellung ist ein Zitat aus dem Buch "Naive Mengenlehre" von Halmos. Dieser überlasst den Beweis dem Leser. Leider habe ich etwas Probleme mit dem "einfachen" Beweis.
Vielleicht eine Klärung der Begrifflichkeiten:
- Der Nachfolger x+1 einer Menge x wird als $x [mm] \cup \left\{ x\right\}$ [/mm] definiert.
- [mm] \omega [/mm] ist die kleinste Menge, die 0 enthält und mit einer Menge x auch stets deren Nachfolger x+1
- Eine [mm] \omega-Nachfolgerfunktion [/mm] (ω-Nff) erfüllt folgende Kriterien:
-- Deren Def.bereich ist die Menge aller strengen Vorgänger einer natürlichen Zahl n (d.h. dom(f)=n).
-- [mm] f(0)=\omega
[/mm]
-- f(m+1)=f(m)+1 für alle m+1<n
Das heißt:
[mm] f(0)=\omega, f(0+1)=f(1)=\omega+1, f(2)=\omega+2, [/mm] ... , [mm] f(n-1)=\omega+n-1
[/mm]
Nun gut, nun zu meinem Beweisansatz mittels vollst. Induktion über n:
Induktionsanfang (n=1):
Jetzt ist dom(f)=1. Da der Definitionsbereich nun nur die strengen Vorgänger von 1 enthält, ist lediglich die 0 im Def.bereich von f. Da wir wissen, dass f [mm] \omega-Nachfolgerfunktion [/mm] ist, gilt [mm] f(0)=\omega. [/mm] Mehr hat die Funktion nicht zu bieten. Jetzt muss ich ja zeigen, dass es nur ein einziges solches f gibt.
Angenommen, es gibt eine weitere [mm] \omega-Nachfolgerfunktion [/mm] g. Diese hat auch dom(g)=1 und [mm] g(0)=\omega. [/mm] Jetzt müsste ich f=g folgern. Kann ich das einfach machen?
Induktionsbehauptung (n):
Für dom(f)=n gibt es genau eine [mm] \omega-Nachfolgerfunktion [/mm] f.
Da m+1<n gilt, geht dies so weit bis [mm] f(n-1)=f(n-2)+1=\omega+n-1.
[/mm]
Induktionsschritt n->n+1:
Jetzt gilt dom(f)=n+1. Also kommt lediglich die natürliche Zahl n in den Definitionsbereich von f hinzu.
Also zusätzlich zur Ind.beh. gilt [mm] f(n)=f(n-1)+1=\omega+n. [/mm] Dies gilt ja jetzt, da f eine [mm] \omega-Nachfolgerfunktion [/mm] ist.
Jetzt muss ich noch zeigen dass es nur genau ein solches f zu dom(f)=n+1 gibt.
Okay mein Versuch: Da nach Ind.beh. das f eindeutig ist bis n, müssen wir nur noch zeigen, dass wenn wir dieses n hinzunehmen in den Def.bereich, dass f immer noch eindeutig ist.
Angeommen, es gibt eine weitere [mm] \omega-Nachfolgerfunktion [/mm] g mit dom(g)=n+1.
Dieses g muss auch [mm] g(0)=\omega [/mm] und g(m+1)=g(m)+1 für alle m+1<n haben.
Also naiv gesprochen, nimmt g dieselben Werte an denselben Stellen an. Reicht dies schon?
Ich wäre für jegliche Hilfe sehr dankbar,
Dankeschön,
Vidane.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:28 So 05.01.2014 | | Autor: | DieAcht |
Hallo,
> Ein einfacher Beweis durch vollständige Induktion zeigt,
> dass es zu jeder natürlichen Zahl n genau eine
> [mm]\omega-Nachfolgerfunktion[/mm] mit dem Definitionsbereich n
> gibt.
> Hey Leute,
>
> Ich denke, die Aufgabe dürfte echt nicht so schwer sein,
> es würde mir wirklich helfen, wenn ihr das mal kurz
> durchlest. Ich hab alles recht ausführlich verfasst. Jeder
> kleiner Hinweis würde mir sehr helfen.
>
> Die Aufgabenstellung ist ein Zitat aus dem Buch "Naive
> Mengenlehre" von Halmos. Dieser überlasst den Beweis dem
> Leser. Leider habe ich etwas Probleme mit dem "einfachen"
> Beweis.
>
> Vielleicht eine Klärung der Begrifflichkeiten:
> - Der Nachfolger x+1 einer Menge x wird als [mm]x \cup \left\{ x\right\}[/mm]
> definiert.
> - [mm]\omega[/mm] ist die kleinste Menge, die 0 enthält und mit
> einer Menge x auch stets deren Nachfolger x+1
> - Eine [mm]\omega-Nachfolgerfunktion[/mm] (ω-Nff) erfüllt
> folgende Kriterien:
> -- Deren Def.bereich ist die Menge aller strengen
> Vorgänger einer natürlichen Zahl n (d.h. dom(f)=n).
> -- [mm]f(0)=\omega[/mm]
> -- f(m+1)=f(m)+1 für alle m+1<n
>
> Das heißt:
> [mm]f(0)=\omega, f(0+1)=f(1)=\omega+1, f(2)=\omega+2,[/mm] ... ,
> [mm]f(n-1)=\omega+n-1[/mm]
>
Interessante Herleitung. Persönlich finde ich die Peano-Axiome besser, aber darum geht es hier nicht.
>
> Nun gut, nun zu meinem Beweisansatz mittels vollst.
> Induktion über n:
Zu zeigen:
Für alle [mm] n\in\IN_0 [/mm] existiert genau eine eindeutige [mm] $\omega$-Nff [/mm] mit $dom(f)=n$
Zunächst beginnt hier die Induktion bei $n=0$ und $n=1$.
Sei $n:=0$, dann gilt:
[mm] f(0)=:\omega
[/mm]
Nach der Definition ist [mm] \omega [/mm] die kleinste Menge,
die $0$ enthält und es gibt keine Vorgänger, sodass gilt:
[mm] $dom(f(0))=dom(\omega)=0.
[/mm]
> Induktionsanfang (n=1):
> Jetzt ist dom(f)=1.
![[notok]](/images/smileys/notok.gif "[notok]")
Du sollst zeigen, dass $dom(f(1))=1$ gilt!
> Da der Definitionsbereich nun nur die
> strengen Vorgänger von 1 enthält, ist lediglich die 0 im
> Def.bereich von f. Da wir wissen, dass f
> [mm]\omega-Nachfolgerfunktion[/mm] ist, gilt [mm]f(0)=\omega.[/mm] Mehr hat
> die Funktion nicht zu bieten. Jetzt muss ich ja zeigen,
> dass es nur ein einziges solches f gibt.
> Angenommen, es gibt eine weitere [mm]\omega-Nachfolgerfunktion[/mm]
> g. Diese hat auch dom(g)=1 und [mm]g(0)=\omega.[/mm] Jetzt müsste
> ich f=g folgern. Kann ich das einfach machen?
Du nimmst hier Dinge an, die du aus den Natürlichen Zahlen folgst. Das stimmt so nicht!
Es gilt:
[mm] dom(f(1))=dom(f(0+1))=:dom(f(0)+1)=dom(f(1))=dom(\omega+1)=1
[/mm]
>
> Induktionsbehauptung (n):
> Für dom(f)=n gibt es genau eine [mm]\omega-Nachfolgerfunktion[/mm]
> f.
Es gäbe für ein beliebiges, aber festes, [mm] n\in\IN_0 [/mm] genau eine eindeutige [mm] $\omega$-Nff [/mm] mit $dom(f)=n$
Zu zeigen:
Für [mm] $n\to [/mm] n+1$ gibt es genau eine eindeutige [mm] $\omega$-Nff [/mm] mit $dom(f(n+1))=n+1$
> Da m+1<n gilt, geht dies so weit bis
> [mm]f(n-1)=f(n-2)+1=\omega+n-1.[/mm]
>
> Induktionsschritt n->n+1:
> Jetzt gilt dom(f)=n+1. Also kommt lediglich die
> natürliche Zahl n in den Definitionsbereich von f hinzu.
> Also zusätzlich zur Ind.beh. gilt [mm]f(n)=f(n-1)+1=\omega+n.[/mm]
> Dies gilt ja jetzt, da f eine [mm]\omega-Nachfolgerfunktion[/mm]
> ist.
> Jetzt muss ich noch zeigen dass es nur genau ein solches f
> zu dom(f)=n+1 gibt.
>
> Okay mein Versuch: Da nach Ind.beh. das f eindeutig ist bis
> n, müssen wir nur noch zeigen, dass wenn wir dieses n
> hinzunehmen in den Def.bereich, dass f immer noch eindeutig
> ist.
> Angeommen, es gibt eine weitere [mm]\omega-Nachfolgerfunktion[/mm]
> g mit dom(g)=n+1.
> Dieses g muss auch [mm]g(0)=\omega[/mm] und g(m+1)=g(m)+1 für alle
> m+1<n haben.
> Also naiv gesprochen, nimmt g dieselben Werte an denselben
> Stellen an. Reicht dies schon?
Hier das gleiche Problem wie oben.
Du nimmst an, dass $dom(f(n))=n$ für alle [mm] n\in\IN [/mm] gilt und willst zeigen,
dass $dom(f(n))=n$ eindeutig ist.
>
> Ich wäre für jegliche Hilfe sehr dankbar,
> Dankeschön,
> Vidane.
Das ist leider alles ziemlich chaotisch.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:34 So 05.01.2014 | | Autor: | Vidane |
Zunächst einmal vielen Dank für deine Antwort. Mir war nicht klar, dass ich die Eindeutigkeit mit dem Wert der Domain herleiten soll. Macht natürlich Sinn, dankeschön.
> Zu zeigen:
>
> Für alle [mm]n\in\IN_0[/mm] existiert genau eine eindeutige
> [mm]\omega[/mm]-Nff mit [mm]dom(f)=n[/mm]
>
> Zunächst beginnt hier die Induktion bei [mm]n=0[/mm] und [mm]n=1[/mm].
>
> Sei [mm]n:=0[/mm], dann gilt:
>
> [mm]f(0)=:\omega[/mm]
>
> Nach der Definition ist [mm]\omega[/mm] die kleinste Menge,
> die [mm]0[/mm] enthält und es gibt keine Vorgänger, sodass gilt:
>
> [mm]$dom(f(0))=dom(\omega)=0.[/mm]
Alles klar.
>
>
> Du sollst zeigen, dass [mm]dom(f(1))=1[/mm] gilt!
>
> Du nimmst hier Dinge an, die du aus den Natürlichen Zahlen
> folgst. Das stimmt so nicht!
>
> Es gilt:
>
> [mm]dom(f(1))=dom(f(0+1))=:dom(f(0)+1)=dom(f(1))=dom(\omega+1)=1[/mm]
>
Was ich hier nicht ganz verstehe, ist, dass du zwei Umformungen machst, um dann wieder bei $dom(f(1))$ landest. Hättest du vorher nicht [mm] f(1)=\omega+1 [/mm] setzen können?
Und dass aus [mm] dom(\omega+1)=1 [/mm] folgt, macht schon irgendwie Sinn, aber könnte ich dann nicht einfach analog für den Schritt das zeigen:
[mm] $dom(f(n+1))=:dom(f(n)+1)=dom(f(n+1))=dom(\omega+n+1)=n+1$
[/mm]
Da hätte ich ja noch nicht einmal die Ind.beh. benutzt. Wäre seltsam.
Kann man sagen, dass $dom(f(0)+1)=dom(f(0))+1$ gilt? Macht ja schon irgendwie Sinn, weil die Domain hier ja die Anzahl der strengen Vorgänger angibt und wenn +1 auf die Funktion addiert, also den Nachfolger bildet, dann hat die Funktion eben einen Vorgänger mehr, d.h. dom+1. Kann man das machen?
Dann könnte ich setzen:
$dom(f(n+1))=dom(f(n)+1)=dom(f(n))+1$, jetzt benutzt man die Ind.beh., also $dom(f(n))=n$. Also folgt für $dom(f(n))+1=n+1$, was zu zeigen war. Vorausgesetzt man darf das machen.
>
> Es gäbe für ein beliebiges, aber festes, [mm]n\in\IN_0[/mm] genau
> eine eindeutige [mm]\omega[/mm]-Nff mit [mm]dom(f)=n[/mm]
>
> Zu zeigen:
>
> Für [mm]n\to n+1[/mm] gibt es genau eine eindeutige [mm]\omega[/mm]-Nff mit
> [mm]dom(f(n+1))=n+1[/mm]
>
> Hier das gleiche Problem wie oben.
>
> Du nimmst an, dass [mm]dom(f(n))=n[/mm] für alle [mm]n\in\IN[/mm] gilt und
> willst zeigen,
> dass [mm]dom(f(n))=n[/mm] eindeutig ist.
>
>
> Das ist leider alles ziemlich chaotisch.
Ja, tut mir leid. Ich war ja dann doch ziemlich auf dem Holzweg. Danke für die Klärung.
>
>
> Gruß
> DieAcht
Dankeschön,
Gruß Vidane.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:16 So 05.01.2014 | | Autor: | DieAcht |
> Zunächst einmal vielen Dank für deine Antwort. Mir war
> nicht klar, dass ich die Eindeutigkeit mit dem Wert der
> Domain herleiten soll. Macht natürlich Sinn, dankeschön.
>
> > Zu zeigen:
> >
> > Für alle [mm]n\in\IN_0[/mm] existiert genau eine eindeutige
> > [mm]\omega[/mm]-Nff mit [mm]dom(f)=n[/mm]
> >
> > Zunächst beginnt hier die Induktion bei [mm]n=0[/mm] und [mm]n=1[/mm].
> >
> > Sei [mm]n:=0[/mm], dann gilt:
> >
> > [mm]f(0)=:\omega[/mm]
> >
> > Nach der Definition ist [mm]\omega[/mm] die kleinste Menge,
> > die [mm]0[/mm] enthält und es gibt keine Vorgänger, sodass gilt:
> >
> > [mm]$dom(f(0))=dom(\omega)=0.[/mm]
>
> Alles klar.
>
> >
> >
> > Du sollst zeigen, dass [mm]dom(f(1))=1[/mm] gilt!
> >
> > Du nimmst hier Dinge an, die du aus den Natürlichen Zahlen
> > folgst. Das stimmt so nicht!
> >
> > Es gilt:
> >
> >
> [mm]dom(f(1))=dom(f(0+1))=:dom(f(0)+1)=dom(f(1))=dom(\omega+1)=1[/mm]
> >
>
> Was ich hier nicht ganz verstehe, ist, dass du zwei
> Umformungen machst, um dann wieder bei [mm]dom(f(1))[/mm] landest.
> Hättest du vorher nicht [mm]f(1)=\omega+1[/mm] setzen können?
![[ok]](/images/smileys/ok.gif "[ok]")
Das $f(1)$ hat dort nichts zu suchen!
> Und dass aus [mm]dom(\omega+1)=1[/mm] folgt, macht schon irgendwie
> Sinn, aber könnte ich dann nicht einfach analog für den
> Schritt das zeigen:
> [mm]dom(f(n+1))=:dom(f(n)+1)=dom(f(n+1))=dom(\omega+n+1)=n+1[/mm]
> Da hätte ich ja noch nicht einmal die Ind.beh. benutzt.
> Wäre seltsam.
Die Behauptung ist rekursiv und das musst du im Induktionsschritt zeigen. Siehe unten.
>
> Kann man sagen, dass [mm]dom(f(0)+1)=dom(f(0))+1[/mm] gilt? Macht ja
> schon irgendwie Sinn, weil die Domain hier ja die Anzahl
> der strengen Vorgänger angibt und wenn +1 auf die Funktion
> addiert, also den Nachfolger bildet, dann hat die Funktion
> eben einen Vorgänger mehr, d.h. dom+1. Kann man das
> machen?
>
> Dann könnte ich setzen:
> [mm]dom(f(n+1))=dom(f(n)+1)=dom(f(n))+1[/mm], jetzt benutzt man die
> Ind.beh., also [mm]dom(f(n))=n[/mm]. Also folgt für
> [mm]dom(f(n))+1=n+1[/mm], was zu zeigen war. Vorausgesetzt man darf
> das machen.
Ich befürchte, dass man das hier nicht benutzen soll.
>
> >
> > Es gäbe für ein beliebiges, aber festes, [mm]n\in\IN_0[/mm] genau
> > eine eindeutige [mm]\omega[/mm]-Nff mit [mm]dom(f)=n[/mm]
> >
> > Zu zeigen:
> >
> > Für [mm]n\to n+1[/mm] gibt es genau eine eindeutige [mm]\omega[/mm]-Nff mit
> > [mm]dom(f(n+1))=n+1[/mm]
Es gilt:
[mm] dom(f(n+1))\overbrace{=}^{IV}=dom(f(n)+1)=dom(f(n-1)+1+1)=\ldots=dom(f(0)+\underbrace{1+\ldots+1}_{n-mal})=dom(1+\underbrace{1+\ldots+1}_{n-mal})=dom(\underbrace{1+\ldots+1}_{(n+1)-mal})=n+1
[/mm]
>
>
>
> >
> > Hier das gleiche Problem wie oben.
> >
> > Du nimmst an, dass [mm]dom(f(n))=n[/mm] für alle [mm]n\in\IN[/mm] gilt und
> > willst zeigen,
> > dass [mm]dom(f(n))=n[/mm] eindeutig ist.
> >
> >
> > Das ist leider alles ziemlich chaotisch.
>
> Ja, tut mir leid. Ich war ja dann doch ziemlich auf dem
> Holzweg. Danke für die Klärung.
> >
> >
> > Gruß
> > DieAcht
>
> Dankeschön,
> Gruß Vidane.
>
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:02 So 05.01.2014 | | Autor: | Vidane |
Okay, dankeschön für deine Antwort. Folgendes noch:
> Es gilt:
>
> [mm]dom(f(n+1))\overbrace{=}^{IV}=dom(f(n)+1)=dom(f(n-1)+1+1)=\ldots=dom(f(0)+\underbrace{1+\ldots+1}_{n-mal})=dom(1+\underbrace{1+\ldots+1}_{n-mal})=dom(\underbrace{1+\ldots+1}_{(n+1)-mal})=n+1[/mm]
Okay, ich verstehe das Prinzip, aber du meinst schon [mm] f(0)=\omega [/mm] oder? Und es müssten, glaube ich, schon gleich n+1 Einsen sein. Also folgendes:
[mm]dom(f(n+1))\overbrace{=}^{IV}=dom(f(n)+1)=dom(f(n-1)+1+1)=\ldots=dom(f(0)+\underbrace{1+\ldots+1}_{n+1-mal})=dom(\omega+\underbrace{1+\ldots+1}_{n+1-mal})=n+1[/mm]
Und dann noch die Frage: Wir benutzen hier ja ganze Zeit, dass [mm] dom(\omega+m)=m [/mm] (für irgendeine nat.Zahl m) gilt.
Ich dachte erst, dass mir das klar wäre, aber kannst du mir bitte nochmal kurz erklären, wieso das gilt?
Dankeschön,
Gruß Vidane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:03 So 05.01.2014 | | Autor: | DieAcht |
Hallo,
Ich hatte Probleme das hier zu formulieren.
Der Edition spinnt bei mir ein wenig heute.
Auf jeden Fall hast du Recht!
Ich hatte mich verschrieben, aber es sind nicht "direkt" $n+1$ Einsen.
Siehe unten.
> Und dann noch die Frage: Wir benutzen hier ja ganze Zeit, > dass [mm] dom(\omega+m)=m [/mm] (für irgendeine nat.Zahl m) gilt.
> Ich dachte erst, dass mir das klar wäre, aber kannst du > mir bitte nochmal kurz erklären, wieso das gilt?
Das habe ich in dem Beweis mit einwirken lassen.
Siehe unten (Beachte die Klammersetzung im Induktionsschritt!).
[Dateianhang nicht öffentlich]
Ich hoffe, dass das nun etwas klarer ist.
Schönen Gruß
DieAcht
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:37 So 05.01.2014 | | Autor: | Vidane |
Ahhh alles klar, perfekt, vielen vielen Dank =)
|
|
|
|
