Abzählbarkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Entscheiden Sie, welche der folgenden Mengen abzählbar, höchst Abzählbar oder überabzählbar sind. Begründen Sie ihre Antwort.
Die Menge [mm] \{f: \IN->\IN: f(2n)=0 \forall n \in \IN \} [/mm] |
Hallo. Also in den Lösungen steht beschrieben, dass es sich um eine überabzählbare Menge handelt. Überabzählbar heißt ja, dass es injektiv ist....versteh ich aber nicht ganz.
[mm] \IN->\IN [/mm] ist doch bijektiv, weil es ja genau das gleiche ist oder? und f(2n)=0 kann doch nur die 0 sein, die da rein passt....könnte jemand mir da etwas genaures erzählen?
|
|
| |
|
Hallo,
ich glaube, du hast da einen verständnismäßigen Hänger. Untersucht wird eine Menge der Form [mm] \IN\times\IN. [/mm] Und untersuchen sollst du, ob es eine Bijektion gibt ziwschen der beschriebenen Menge aller Tupel (n|f(n)) gibt, wobei f nur für gerade Zahlen definiert ist.
obiges war Unsinn. Es geht natürlich um eine Menge der Form [mm] \IN^{IN}, [/mm] alles weitere steht in den anderen Beiträgen.
Sorry für meinen Fehler!
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:06 Fr 04.05.2012 | | Autor: | durden88 |
Also...könntest du das vielleicht nochmal für ´´Dummies´´ erklären? Ok n ist nur für gerade Zahlen definiert, aber wieso ist da ein =0? Was sind Tupel? Das kenn ich nur aus der Stochastik...
> Hallo,
>
> ich glaube, du hast da einen verständnismäßigen Hänger.
> Untersucht wird eine Menge der Form [mm]\IN\times\IN.[/mm] Und
> untersuchen sollst du, ob es eine Bijektion gibt ziwschen
> der beschriebenen Menge aller Tupel (n|f(n)) gibt, wobei f
> nur für gerade Zahlen definiert ist.
>
>
> Gruß, Diophant
|
|
|
| |
|
moin durden,
Deine zu untersuchende Menge ist die Menge aller Abbildungen $f$ von [mm] $\IN$ [/mm] nach [mm] $\IN$, [/mm] für die $f(n) = 0$ falls $n$ gerade ist.
Das heißt etwa die Folge:
[mm] $(1,0,2,0,3,0,4,0,5,0,\ldots [/mm] )$ wäre in der Menge (dieses Tupel steht einfach für die Funktionswerte, also [mm] $(f(0),f(1),f(2),\ldots [/mm] )$)
Anstelle der 1,2,etc. hättest du auch beliebige andere natürliche Zahlen nehmen können.
Du hast also auf jeden Fall unendlich viele Abbildungen in der Menge drinn; die Frage ist, ob sie abzählbar sind oder nicht.
Weißt du, wie genau Abzählbarkeit definiert ist?
Sollte es noch weitere Fragen geben immer her damit.
lg
Schadow
edit: Tatsache, $0 [mm] \in \IN$ [/mm] sollte scheinbar hier gefordert werden, danke an Marcel.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:19 Sa 05.05.2012 | | Autor: | durden88 |
ja vielen Dank, werden bestimmt noch ein paar Fragen kommen :) . Also unsere Definition war:
´´Wir nennen eine Menge A abzählbar, falls es eine Bijektion f: [mm] \IN [/mm] → A gibt. A heißt höchstens abzählbar, falls es eine Surjektion f : [mm] \IN [/mm] → A gibt. Ansonsten heißt A überabzählbar.´´
> moin durden,
>
> Deine zu untersuchende Menge ist die Menge aller
> Abbildungen [mm]f[/mm] von [mm]\IN[/mm] nach [mm]\IN[/mm], für die [mm]f(n) = 0[/mm] falls [mm]n[/mm]
> gerade ist.
Dieses mit dem =0 verwirrt mich total. Die Menge aller Abbildungen falls n gerade ist also 2,4,6,8,etc. kann ich mir vorstellen, aber dieses gleich 0?
> Das heißt etwa die Folge:
> [mm](1,0,2,0,3,0,4,0,5,0,\ldots )[/mm] wäre in der Menge (dieses
> Tupel steht einfach für die Funktionswerte, also
> [mm](f(1),f(2),f(3),\ldots )[/mm])
Ok, aber wieso sind da zwischen den Funktionswerten immer eine 0?
> Anstelle der 1,2,etc. hättest
> du auch beliebige andere natürliche Zahlen nehmen
> können.
> Du hast also auf jeden Fall unendlich viele Abbildungen in
> der Menge drinn; die Frage ist, ob sie abzählbar sind oder
> nicht.
Ich weiß, dass die Funktion überabzählbar ist (aus den Lösungen) also injektiv ist. Das heißt die Zielmenge muss größer sein als die Ausgangsmenge. Aber warum :D
> Weißt du, wie genau Abzählbarkeit definiert ist?
>
> Sollte es noch weitere Fragen geben immer her damit.
>
> lg
>
> Schadow
Vielen lieben dank für die Antworten.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:29 Sa 05.05.2012 | | Autor: | Marcel |
Hallo,
> ja vielen Dank, werden bestimmt noch ein paar Fragen kommen
> :) . Also unsere Definition war:
>
> ´´Wir nennen eine Menge A abzählbar, falls es eine
> Bijektion f: [mm]\IN[/mm] → A gibt. A heißt höchstens
> abzählbar, falls es eine Surjektion f : [mm]\IN[/mm] → A gibt.
> Ansonsten heißt A überabzählbar.´´
>
>
> > moin durden,
> >
> > Deine zu untersuchende Menge ist die Menge aller
> > Abbildungen [mm]f[/mm] von [mm]\IN[/mm] nach [mm]\IN[/mm], für die [mm]f(n) = 0[/mm] falls [mm]n[/mm]
> > gerade ist.
> Dieses mit dem =0 verwirrt mich total. Die Menge aller
> Abbildungen falls n gerade ist also 2,4,6,8,etc.
da kapiere ich nicht, was Du eigentlich fragst - denn mir ist Deine Frage nicht klar. Wahrscheinlich, weil Dir die Aufgabe und die Notationen immer noch nicht klar sind!
> kann ich
> mir vorstellen, aber dieses gleich 0?
> > Das heißt etwa die Folge:
> > [mm](1,0,2,0,3,0,4,0,5,0,\ldots )[/mm] wäre in der Menge
> (dieses
> > Tupel steht einfach für die Funktionswerte, also
> > [mm](f(1),f(2),f(3),\ldots )[/mm])
> Ok, aber wieso sind da
> zwischen den Funktionswerten immer eine 0?
Schau' in die Definition von [mm] $M\,$ [/mm] (wobei Schadowmaster hier [mm] $f(0)\,$ [/mm] auch hätte hinschreiben müssen - andernfalls ist die Aufgabe nicht gut gestellt, denn sonst würde man mit [mm] $\IN=\IN \setminus \{0\}$ [/mm] und [mm] $\IN_0:=\IN \cup \{0\}$ [/mm] in [mm] $M\,$ [/mm] Abbildungen [mm] $\IN \to \IN_0$ [/mm] betrachten!)
Na, wir machens mal ganz elementar:
Du hast die Menge [mm] $M:=\{f: \IN \to \IN: f(2n)=0\;\forall n \in \IN\}\,.$
[/mm]
Was sind die Elemente $x [mm] \in [/mm] M$? Nun ja:
Es gilt $x [mm] \in [/mm] M$ genau dann (per Definitionem von [mm] $M\,$), [/mm] wenn $x: [mm] \IN \to \IN$ [/mm] eine Abbildung ist, die erfüllt $x(2n)=0$ für alle $n [mm] \in \IN\,.$
[/mm]
Die Elemente aus [mm] $M\,$ [/mm] sind also ABBILDUNGEN. Eine solche Abbildung kann man auch mit einem Element des entsprechenden kartesischen Produkts identifizieren:
Wenn Du das tust, dann bekommst Du die von Schadowmaster benutzte Schreibweise, wo man eine Abbildung eigentlich in einer altbekannten Schreibweise schreibt: Was sind denn (unendliche) Folgen?
Und dazu schreibe ich auch gleich noch mehr...
Aber vorweg, damit Du das ganze überhaupt erstmal verstehst, wie [mm] $M\,$ [/mm] aufgebaut ist, machen wir mal ein paar Beispiele:
Wir definieren
[mm] $f_1: \IN \to \IC$ [/mm] durch [mm] $f(n):=e^n\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] ungerade, und [mm] $f(n):=0\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] gerade.
[mm] $f_2: \IN \to \IN$ [/mm] durch [mm] $f(n):=e^n\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] ungerade, und [mm] $f(n):=0\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] gerade.
[mm] $f_3: \IN \to \IR$ [/mm] durch [mm] $f(n):=[e^n]\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] ungerade, und [mm] $f(n):=0\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] gerade.
[mm] $f_4: \IN \to \IN$ [/mm] durch [mm] $f(n):=[e^n]\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] ungerade, und [mm] $f(n):=0\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] gerade.
[mm] $f_5: \IR \to [0,\infty)$ [/mm] durch [mm] $f(x):=e^x\,,$ [/mm]
[mm] $f_6: \IN \to \IN$ [/mm] durch [mm] $f(n):=2^n\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] ungerade, und [mm] $f(n):=0\,,$ [/mm] falls $n [mm] \in \IN$ [/mm] gerade.
Welche der Abbildungen ist [mm] $\in M\,$? $f_5\,$ [/mm] können wir ausschließen, weil [mm] $f_5$ [/mm] den Definitionsbereich [mm] $\IR \not=\IN$ [/mm] hat. [mm] $f_1$ [/mm] und [mm] $f_3$ [/mm] können wir ausschließen, weil beide einen Zielbereich [mm] $\not=\IN$ [/mm] haben. [mm] $f_3$ [/mm] kann man allerdings so abändern, dass die abgeänderte Funktion dann doch ein Element von [mm] $M\,$ [/mm] ist (und das habe ich auch getan) - die abgeänderte Funktion braucht dann natürlich einen neuen Namen! (Sie heißt dann [mm] $f_4\,.$)
[/mm]
Wie sieht es mit [mm] $f_2$ [/mm] aus? [mm] $f_2$ [/mm] ist so gar nicht wohldefiniert, ich habe da nämlich etwas stehen, was nicht sein kann: Betrachtet man nämlich die Abbildung $g: [mm] \IN \to \IR$ [/mm] mit [mm] $g(n):=e^n\,,$ [/mm] so folgt [mm] $\IN \not\subseteq \text{Bild}(g)=g(\IN)\,:$ [/mm] Beispielsweise ist [mm] $e^1=e \in [/mm] (2,3)$ und damit [mm] $e^1=e \notin \IN\,.$
[/mm]
Nun gilt aber [mm] $f_4 \in [/mm] M:$
Denn: [mm] $f_4: \IN \to \IN$ [/mm] ist wirklich eine wohldefinierte Abbildung, die die Bedingungen aus [mm] $M\,$ [/mm] erfüllt. Ist Dir das klar? (Ohne große Argumente zu suchen folgt das schnell aus der Definition der Gaußklammer (als Funktion ist sie monoton wachsend), weil $x [mm] \mapsto e^x$ [/mm] auf [mm] $\IR$ [/mm] streng wächst und weil [mm] $[e^0]=[1]=1\,.$)
[/mm]
Dass [mm] $f_6 \in [/mm] M$ gilt, ist ebenso schnell einzusehen.
Und jetzt komme ich nochmal zu Schadowmasters Schreibweise als Unendlich-Tupel, wenn man Funktionen als Element eines kartesischen Produkts auffasst:
Jede Funktion $f: [mm] \IN \to \IN$ [/mm] kann man einfach schreiben als folgendes Tupel mit (abzählbar) unendlich vielen Komponenten
[mm] $$(f(0),\;f(1),\;f(2),\;f(3),\;f(4),\;f(5),\;\ldots)$$
[/mm]
Sowas kennst Du eigentlich sicher: So schreibt man eigentlich auch Folgen:
[mm] $$(f(j))_{j \in \IN}\,.$$
[/mm]
Meist sieht man die Funktionsvorschrift deswegen auch in der Folgennotation, weil in [mm] $(f(j))_{j \in \IN}$ [/mm] oft einfach für [mm] $f(j)\,$ [/mm] diese eingesetzt wird. Ein wenig unklar in dieser Notation ist, welcher Zielbereich die Folge hat - deswegen sagt man meist sowas wie "... eine Folge ... mit Werten in [mm] $\IN$" [/mm] oder ähnliches.
Also nun auch dazu ein Beispiel:
Es gilt für [mm] $f_6: \IN \to \IN:$
[/mm]
[mm] $$f_6(0)=0,\;f_6(1)=2^1=2,\;f_6(2)=0,\;f_6(3)=2^3=8,\;f_6(4)=0,\;f_6(5)=2^5=32,\;f_6(6)=0,\;f_6(7)=2^7=128,\;f_6(8)=0,\;f_6(9)=2^9=512,\;f_6(1)=0,\;\ldots$$
[/mm]
Schreibe ich diese Funktion nun als unendliches Tupel, d.h. ich fasse [mm] $f_6$ [/mm] als Element des kartesischen Produktes [mm] $\produkt_{j \in \IN} \IN=\IN^{\IN}$ [/mm] auf, so sieht [mm] $f_6$ [/mm] (wie in Folgennotation) so aus
[mm] $$(0,2,0,8,0,32,0,128,0,512,0,\ldots)$$
[/mm]
Und diese Schreibweise ist halt sehr günstig, um zu erkennen, welche Funktionen [mm] $\IN \to \IN$ [/mm] zu [mm] $M\,$ [/mm] gehören:
In "Folgennotation" kannst Du sagen: Nur dann, wenn eine Folge vorliegt, die an jedem geraden Index den Wert [mm] $0\,$ [/mm] annimmt, und die an allen anderen Stellen Werte aus [mm] $\IN$ [/mm] annimmt, dann beschreibt diese Folge ein Element aus [mm] $M\,.$ [/mm]
Hierbei siehst Du auch: Obwohl [mm] $f_3 \notin [/mm] M$ und aber [mm] $f_4 \in [/mm] M$ gilt, würdest Du in Folgennotation beide als Element von [mm] $M\,$ [/mm] ansehen. Denn in der Folgennotation würdest Du automatisch davon ausgehen, dass [mm] $f_3\,,$ [/mm] weil das Bild der Funktion (also die Menge aller angenommenen Funktionswerte) eine Teilmenge von [mm] $\IN$ [/mm] ist, eigentlich das gleiche ist wie [mm] $f_4\,.$ [/mm] Nur wenn man explizit dazuschreibt, dass [mm] $f_3$ [/mm] eine Folge mit Werten in [mm] $\IR$ [/mm] sein soll, würdest Du in Folgennotation dann auch [mm] $f_3 \notin [/mm] M$ erkennen können.
Also anstatt zu fragen: Wie sehen Elemente aus [mm] $M\,$ [/mm] aus? Was man natürlich einfach erstmal beantworten würde per: "Naja, das sind Abbildungen [mm] $\IN \to \IN\,,$ [/mm] die an allen geraden natürlichen Zahlen den Wert [mm] $0\,$ [/mm] annehmen!", kann man auch so vorgehen:
Wenn man eine Funktion hat, die auf [mm] $\IN$ [/mm] definiert ist, so muss sie, um in [mm] $M\,$ [/mm] liegen zu können, erstmal den Zielbereich [mm] $\IN$ [/mm] haben. Wir betrachten nun nur Funktionen, deren Bild jedenfalls eine (nicht notwendig echte) Teilmenge von [mm] $\IN$ [/mm] ist - und bei der Tupelschreibweise gehen wir davon aus, dass, wenn jede Komponente in [mm] $\IN$ [/mm] liegt, diese auch den Zielbereich [mm] $\IN$ [/mm] hat.
Wenn ich also die Folge
[mm] $$(n*0.5)_{n \in \IN}$$
[/mm]
habe, dann gehört diese (bzw. die Funktion, die diese Folge repräsentiert) nicht zu [mm] $M\,.$
[/mm]
Die Folge
[mm] $$((-1)^n)_{n \in \IN}$$
[/mm]
sicher auch nicht.
Die Folge
[mm] $$(2^n)_{n \in \IN}$$
[/mm]
gehört auch nicht zu [mm] $M\,:$
[/mm]
Es ist
[mm] $$(2^n)_{n \in \IN}=(1,\;2,\;4,\;8,\;16,\;\ldots)$$
[/mm]
und man sieht, dass an der zweiten Stelle eben keine Null steht, sondern eine [mm] $2\,,$ [/mm] und alleine deswegen kann diese Folge nicht zu [mm] $M\,$ [/mm] gehören.
[mm] $f_6$ [/mm] habe ich ja schon oben als Folge geschrieben:
[mm] $$(0,2,0,8,0,32,0,128,0,512,0,\ldots)$$
[/mm]
(Bemerkung: Schadowmaster hatte übersehen, dass bei Euch wohl $0 [mm] \in \IN$ [/mm] gelten muss, denn andernfalls macht es keinen Sinn, zu sagen, dass $f: [mm] \IN \to \IN$ [/mm] sei, wenn [mm] $f\,$ [/mm] auch den Wert [mm] $0\,$ [/mm] annehmen kann!)
Die Folge
[mm] $$(0,2,0,8,0,32,0,128,0,512,0,\ldots)$$
[/mm]
gehört also zu [mm] $M\,.$
[/mm]
Anders gesagt:
Anstatt zu fragen:
Ist [mm] $M:=\{f: \IN \to \IN: f(2n)=0\forall n \in \IN}$ [/mm] abz., h.abz. oder ü-abz., kann man auch in vollkommen gleichwertiger Weise fragen:
Ist
[mm] $$\tilde{M}:=\{(a_k)_{k \in \IN}:\;(a_k)_{k \in \IN}\text{ ist eine Folge mit Werten in }\IN\text{, die zudem erfüllt }a_{2k}=0\text{ für alle }k \in \IN\}$$
[/mm]
abz., h.abz. oder ü-abz.?
Und [mm] $\tilde{M}$ [/mm] enthält halt alle (unendlich-)Tupel der Form
[mm] $$(0,n_1,0,n_2,0,n_3,0,n_4,\ldots)$$
[/mm]
sofern alle [mm] $n_j \in \IN$ [/mm] für alle $j [mm] \in \IN$ [/mm] sind. (Beachte: In der letzten Tupel-Notation meine ich nun NICHT, dass [mm] $n_j$ [/mm] mit irgendeinem Funktionswert identifiziert werden sollte.)
Also grob gesagt kann man mal andeuten:
Es gilt etwa
[mm] $$\{(0,0,0,0,\ldots),\;(0,2,0,1,0,0,1,0,12,0,\ldots),\;(0,35,0,346645,0,232,0,7,\ldots)\} \subseteq \tilde{M}$$
[/mm]
aber
[mm] $$(0,0,0,0,0,1,0,0,0,0,\ldots) \notin \tilde{M}\,.$$
[/mm]
(An der SECHSTEN Stelle steht ein Eintrag ungleich Null!)
P.S.
Mit dem Cantorschen Diagonalverfahren ist leicht einzusehen, dass [mm] $\IN^\IN=\{r: \IN \to \IN\}$ [/mm] überabzählbar ist. Um Deine Aufgabe damit möglichst elegant zu lösen: Gib' eine Bijektion $M [mm] \to \IN^{\IN}$ [/mm] an.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:09 So 06.05.2012 | | Autor: | durden88 |
> Hallo,
>
> > ja vielen Dank, werden bestimmt noch ein paar Fragen kommen
> > :) . Also unsere Definition war:
> >
> > ´´Wir nennen eine Menge A abzählbar, falls es eine
> > Bijektion f: [mm]\IN[/mm] → A gibt. A heißt höchstens
> > abzählbar, falls es eine Surjektion f : [mm]\IN[/mm] → A gibt.
> > Ansonsten heißt A überabzählbar.´´
> >
> >
> > > moin durden,
> > >
> > > Deine zu untersuchende Menge ist die Menge aller
> > > Abbildungen [mm]f[/mm] von [mm]\IN[/mm] nach [mm]\IN[/mm], für die [mm]f(n) = 0[/mm] falls [mm]n[/mm]
> > > gerade ist.
> > Dieses mit dem =0 verwirrt mich total. Die Menge aller
> > Abbildungen falls n gerade ist also 2,4,6,8,etc.
>
> da kapiere ich nicht, was Du eigentlich fragst - denn mir
> ist Deine Frage nicht klar. Wahrscheinlich, weil Dir die
> Aufgabe und die Notationen immer noch nicht klar sind!
>
> > kann ich
> > mir vorstellen, aber dieses gleich 0?
> > > Das heißt etwa die Folge:
> > > [mm](1,0,2,0,3,0,4,0,5,0,\ldots )[/mm] wäre in der Menge
> > (dieses
> > > Tupel steht einfach für die Funktionswerte, also
> > > [mm](f(1),f(2),f(3),\ldots )[/mm])
> > Ok, aber wieso sind da
> > zwischen den Funktionswerten immer eine 0?
>
> Schau' in die Definition von [mm]M\,[/mm] (wobei Schadowmaster hier
> [mm]f(0)\,[/mm] auch hätte hinschreiben müssen - andernfalls ist
> die Aufgabe nicht gut gestellt, denn sonst würde man mit
> [mm]\IN=\IN \setminus \{0\}[/mm] und [mm]\IN_0:=\IN \cup \{0\}[/mm] in [mm]M\,[/mm]
> Abbildungen [mm]\IN \to \IN_0[/mm] betrachten!)
>
> Na, wir machens mal ganz elementar:
> Du hast die Menge [mm]M:=\{f: \IN \to \IN: f(2n)=0\;\forall n \in \IN\}\,.[/mm]
>
> Was sind die Elemente [mm]x \in M[/mm]? Nun ja:
> Es gilt [mm]x \in M[/mm] genau dann (per Definitionem von [mm]M\,[/mm]),
> wenn [mm]x: \IN \to \IN[/mm] eine Abbildung ist, die erfüllt
> [mm]x(2n)=0[/mm] für alle [mm]n \in \IN\,.[/mm]
>
> Die Elemente aus [mm]M\,[/mm] sind also ABBILDUNGEN. Eine solche
> Abbildung kann man auch mit einem Element des
> entsprechenden kartesischen Produkts identifizieren:
> Wenn Du das tust, dann bekommst Du die von Schadowmaster
> benutzte Schreibweise, wo man eine Abbildung eigentlich in
> einer altbekannten Schreibweise schreibt: Was sind denn
> (unendliche) Folgen?
> Und dazu schreibe ich auch gleich noch mehr...
>
> Aber vorweg, damit Du das ganze überhaupt erstmal
> verstehst, wie [mm]M\,[/mm] aufgebaut ist, machen wir mal ein paar
> Beispiele:
> Wir definieren
> [mm]f_1: \IN \to \IC[/mm] durch [mm]f(n):=e^n\,,[/mm] falls [mm]n \in \IN[/mm]
> ungerade, und [mm]f(n):=0\,,[/mm] falls [mm]n \in \IN[/mm] gerade.
> [mm]f_2: \IN \to \IN[/mm] durch [mm]f(n):=e^n\,,[/mm] falls [mm]n \in \IN[/mm]
> ungerade, und [mm]f(n):=0\,,[/mm] falls [mm]n \in \IN[/mm] gerade.
> [mm]f_3: \IN \to \IR[/mm] durch [mm]f(n):=[e^n]\,,[/mm] falls [mm]n \in \IN[/mm]
> ungerade, und [mm]f(n):=0\,,[/mm] falls [mm]n \in \IN[/mm] gerade.
> [mm]f_4: \IN \to \IN[/mm] durch [mm]f(n):=[e^n]\,,[/mm] falls [mm]n \in \IN[/mm]
> ungerade, und [mm]f(n):=0\,,[/mm] falls [mm]n \in \IN[/mm] gerade.
> [mm]f_5: \IR \to [0,\infty)[/mm] durch [mm]f(x):=e^x\,,[/mm]
> [mm]f_6: \IN \to \IN[/mm] durch [mm]f(n):=2^n\,,[/mm] falls [mm]n \in \IN[/mm]
> ungerade, und [mm]f(n):=0\,,[/mm] falls [mm]n \in \IN[/mm] gerade.
>
> Welche der Abbildungen ist [mm]\in M\,[/mm]? [mm]f_5\,[/mm] können wir
> ausschließen, weil [mm]f_5[/mm] den Definitionsbereich [mm]\IR \not=\IN[/mm]
> hat. [mm]f_1[/mm] und [mm]f_3[/mm] können wir ausschließen, weil beide
> einen Zielbereich [mm]\not=\IN[/mm] haben. [mm]f_3[/mm] kann man allerdings
> so abändern, dass die abgeänderte Funktion dann doch ein
> Element von [mm]M\,[/mm] ist (und das habe ich auch getan) - die
> abgeänderte Funktion braucht dann natürlich einen neuen
> Namen! (Sie heißt dann [mm]f_4\,.[/mm])
>
> Wie sieht es mit [mm]f_2[/mm] aus? [mm]f_2[/mm] ist so gar nicht
> wohldefiniert, ich habe da nämlich etwas stehen, was nicht
> sein kann: Betrachtet man nämlich die Abbildung [mm]g: \IN \to \IR[/mm]
> mit [mm]g(n):=e^n\,,[/mm] so folgt [mm]\IN \not\subseteq \text{Bild}(g)=g(\IN)\,:[/mm]
> Beispielsweise ist [mm]e^1=e \in (2,3)[/mm] und damit [mm]e^1=e \notin \IN\,.[/mm]
>
> Nun gilt aber [mm]f_4 \in M:[/mm]
> Denn: [mm]f_4: \IN \to \IN[/mm] ist
> wirklich eine wohldefinierte Abbildung, die die Bedingungen
> aus [mm]M\,[/mm] erfüllt. Ist Dir das klar? (Ohne große Argumente
> zu suchen folgt das schnell aus der Definition der
> Gaußklammer (als Funktion ist sie monoton wachsend), weil
> [mm]x \mapsto e^x[/mm] auf [mm]\IR[/mm] streng wächst und weil
> [mm][e^0]=[1]=1\,.[/mm])
>
> Dass [mm]f_6 \in M[/mm] gilt, ist ebenso schnell einzusehen.
>
> Und jetzt komme ich nochmal zu Schadowmasters Schreibweise
> als Unendlich-Tupel, wenn man Funktionen als Element eines
> kartesischen Produkts auffasst:
> Jede Funktion [mm]f: \IN \to \IN[/mm] kann man einfach schreiben
> als folgendes Tupel mit (abzählbar) unendlich vielen
> Komponenten
> [mm](f(0),\;f(1),\;f(2),\;f(3),\;f(4),\;f(5),\;\ldots)[/mm]
>
> Sowas kennst Du eigentlich sicher: So schreibt man
> eigentlich auch Folgen:
> [mm](f(j))_{j \in \IN}\,.[/mm]
>
> Meist sieht man die Funktionsvorschrift deswegen auch in
> der Folgennotation, weil in [mm](f(j))_{j \in \IN}[/mm] oft einfach
> für [mm]f(j)\,[/mm] diese eingesetzt wird. Ein wenig unklar in
> dieser Notation ist, welcher Zielbereich die Folge hat -
> deswegen sagt man meist sowas wie "... eine Folge ... mit
> Werten in [mm]\IN[/mm]" oder ähnliches.
>
> Also nun auch dazu ein Beispiel:
> Es gilt für [mm]f_6: \IN \to \IN:[/mm]
>
> [mm]f_6(0)=0,\;f_6(1)=2^1=2,\;f_6(2)=0,\;f_6(3)=2^3=8,\;f_6(4)=0,\;f_6(5)=2^5=32,\;f_6(6)=0,\;f_6(7)=2^7=128,\;f_6(8)=0,\;f_6(9)=2^9=512,\;f_6(1)=0,\;\ldots[/mm]
>
> Schreibe ich diese Funktion nun als unendliches Tupel, d.h.
> ich fasse [mm]f_6[/mm] als Element des kartesischen Produktes
> [mm]\produkt_{j \in \IN} \IN=\IN^{\IN}[/mm] auf, so sieht [mm]f_6[/mm] (wie
> in Folgennotation) so aus
> [mm](0,2,0,8,0,32,0,128,0,512,0,\ldots)[/mm]
>
> Und diese Schreibweise ist halt sehr günstig, um zu
> erkennen, welche Funktionen [mm]\IN \to \IN[/mm] zu [mm]M\,[/mm] gehören:
> In "Folgennotation" kannst Du sagen: Nur dann, wenn eine
> Folge vorliegt, die an jedem geraden Index den Wert [mm]0\,[/mm]
> annimmt, und die an allen anderen Stellen Werte aus [mm]\IN[/mm]
> annimmt, dann beschreibt diese Folge ein Element aus [mm]M\,.[/mm]
> Hierbei siehst Du auch: Obwohl [mm]f_3 \notin M[/mm] und aber [mm]f_4 \in M[/mm]
> gilt, würdest Du in Folgennotation beide als Element von
> [mm]M\,[/mm] ansehen. Denn in der Folgennotation würdest Du
> automatisch davon ausgehen, dass [mm]f_3\,,[/mm] weil das Bild der
> Funktion (also die Menge aller angenommenen Funktionswerte)
> eine Teilmenge von [mm]\IN[/mm] ist, eigentlich das gleiche ist wie
> [mm]f_4\,.[/mm] Nur wenn man explizit dazuschreibt, dass [mm]f_3[/mm] eine
> Folge mit Werten in [mm]\IR[/mm] sein soll, würdest Du in
> Folgennotation dann auch [mm]f_3 \notin M[/mm] erkennen können.
>
> Also anstatt zu fragen: Wie sehen Elemente aus [mm]M\,[/mm] aus? Was
> man natürlich einfach erstmal beantworten würde per:
> "Naja, das sind Abbildungen [mm]\IN \to \IN\,,[/mm] die an allen
> geraden natürlichen Zahlen den Wert [mm]0\,[/mm] annehmen!", kann
> man auch so vorgehen:
> Wenn man eine Funktion hat, die auf [mm]\IN[/mm] definiert ist, so
> muss sie, um in [mm]M\,[/mm] liegen zu können, erstmal den
> Zielbereich [mm]\IN[/mm] haben. Wir betrachten nun nur Funktionen,
> deren Bild jedenfalls eine (nicht notwendig echte)
> Teilmenge von [mm]\IN[/mm] ist - und bei der Tupelschreibweise gehen
> wir davon aus, dass, wenn jede Komponente in [mm]\IN[/mm] liegt,
> diese auch den Zielbereich [mm]\IN[/mm] hat.
>
> Wenn ich also die Folge
> [mm](n*0.5)_{n \in \IN}[/mm]
> habe, dann gehört diese (bzw. die
> Funktion, die diese Folge repräsentiert) nicht zu [mm]M\,.[/mm]
>
> Die Folge
> [mm]((-1)^n)_{n \in \IN}[/mm]
> sicher auch nicht.
>
> Die Folge
> [mm](2^n)_{n \in \IN}[/mm]
> gehört auch nicht zu [mm]M\,:[/mm]
> Es ist
> [mm](2^n)_{n \in \IN}=(1,\;2,\;4,\;8,\;16,\;\ldots)[/mm]
> und man
> sieht, dass an der zweiten Stelle eben keine Null steht,
> sondern eine [mm]2\,,[/mm] und alleine deswegen kann diese Folge
> nicht zu [mm]M\,[/mm] gehören.
>
> [mm]f_6[/mm] habe ich ja schon oben als Folge geschrieben:
> [mm](0,2,0,8,0,32,0,128,0,512,0,\ldots)[/mm]
>
> (Bemerkung: Schadowmaster hatte übersehen, dass bei Euch
> wohl [mm]0 \in \IN[/mm] gelten muss, denn andernfalls macht es
> keinen Sinn, zu sagen, dass [mm]f: \IN \to \IN[/mm] sei, wenn [mm]f\,[/mm]
> auch den Wert [mm]0\,[/mm] annehmen kann!)
>
> Die Folge
> [mm](0,2,0,8,0,32,0,128,0,512,0,\ldots)[/mm]
> gehört also zu [mm]M\,.[/mm]
Bis hierhin konnte ich folgen. Vielen lieben Dank für die vielen Erklärungen, jetzt bin ich erstmal schlauer und versteh das Prinzip was mehr!! Also ich will nochmal aufschreiben, wie wir in der Vorlesung definiert haben und wie wir dann auch vorgegangen sind: Wir nennen eine Menge A abzählbar, falls es eine Bijektion f : [mm] \IN [/mm] → A gibt. A heißt höchstens abzählbar, falls es eine Surjektion f : N → A gibt. Ansonsten heißt A überabzählbar.
Unser M, welches wir oben definiert hatten ist in diesem Falle mein A richtig? Und da ja immer [mm] \IN->A [/mm] gilt, gehe ich immer von den natürlichen Zahlen aus? Das heißt ja eigendlich, das mein M mehr Elemente als [mm] \IN [/mm] haben muss um injektiv zu sein?
> Anders gesagt:
> Anstatt zu fragen:
> Ist [mm]M:=\{f: \IN \to \IN: f(2n)=0\forall n \in \IN}[/mm] abz.,
> h.abz. oder ü-abz., kann man auch in vollkommen
> gleichwertiger Weise fragen:
> Ist
> [mm]\tilde{M}:=\{(a_k)_{k \in \IN}:\;(a_k)_{k \in \IN}\text{ ist eine Folge mit Werten in }\IN\text{, die zudem erfüllt }a_{2k}=0\text{ für alle }k \in \IN\}[/mm]
>
> abz., h.abz. oder ü-abz.?
Ich glaube so haben wir das gemacht: Die Menge S [mm] \{f:\IN->\IN: f(2n)=0 für alle n\in \IN\} [/mm] ist überabzählbar. Warum? Sei A [mm] \subseteq \{n\in \IN| n (ungerade)\}, [/mm] dann ist [mm] f_A:\IN->\IN [/mm] mit f(2n)=0 für ,alle, n und f(m)=1 für m [mm] \in [/mm] A, f(m)=0 für [mm] m\in T\A [/mm] ein Element von S. Dies sind überabzählbar viele, da T unendlich abzählbar ist und somit [mm] \delta(F) [/mm] überabzählbar ist.
Den Beweis verstehe ich nicht, ich finde deine Erklärung da leichter.
> Und [mm]\tilde{M}[/mm] enthält halt alle (unendlich-)Tupel der
> Form
> [mm](0,n_1,0,n_2,0,n_3,0,n_4,\ldots)[/mm]
> sofern alle [mm]n_j \in \IN[/mm] für alle [mm]j \in \IN[/mm] sind.
> (Beachte: In der letzten Tupel-Notation meine ich nun
> NICHT, dass [mm]n_j[/mm] mit irgendeinem Funktionswert identifiziert
> werden sollte.)
>
> Also grob gesagt kann man mal andeuten:
> Es gilt etwa
>
> [mm]\{(0,0,0,0,\ldots),\;(0,2,0,1,0,0,1,0,12,0,\ldots),\;(0,35,0,346645,0,232,0,7,\ldots)\} \subseteq \tilde{M}[/mm]
>
> aber
> [mm](0,0,0,0,0,1,0,0,0,0,\ldots) \notin \tilde{M}\,.[/mm]
> (An der
> SECHSTEN Stelle steht ein Eintrag ungleich Null!)
>
> P.S.
> Mit dem Cantorschen Diagonalverfahren ist leicht
> einzusehen, dass [mm]\IN^\IN=\{r: \IN \to \IN\}[/mm] überabzählbar
> ist. Um Deine Aufgabe damit möglichst elegant zu lösen:
> Gib' eine Bijektion [mm]M \to \IN^{\IN}[/mm] an.
Das habe ich nicht ganz verstanden. Ist das Cantorsche Diagonalverahren ein Standardverfahren um auf Abzählbarkeit, Überabzahlbarkeit und Höchst Abzählbarkeit zu prüfen bzw. gibt es ein solches?
Ich bedanke mich, vielen lieben Dank
> Gruß,
> Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:13 So 06.05.2012 | | Autor: | Marcel |
Hallo,
> > ...
> > Die Folge
> > [mm](0,2,0,8,0,32,0,128,0,512,0,\ldots)[/mm]
> > gehört also zu [mm]M\,.[/mm]
> Bis hierhin konnte ich folgen. Vielen lieben Dank für
> die vielen Erklärungen, jetzt bin ich erstmal schlauer und
> versteh das Prinzip was mehr!! Also ich will nochmal
> aufschreiben, wie wir in der Vorlesung definiert haben und
> wie wir dann auch vorgegangen sind: Wir nennen eine Menge A
> abzählbar, falls es eine Bijektion f : [mm]\IN[/mm] → A gibt. A
> heißt höchstens abzählbar, falls es eine Surjektion f
> : N → A gibt. Ansonsten heißt A überabzählbar.
>
> Unser M, welches wir oben definiert hatten ist in diesem
> Falle mein A richtig?
natürlich: Du willst doch [mm] $M\,$ [/mm] auf abz.,h. abz. oder ü.abz. untersuchen!
> Und da ja immer [mm]\IN->A[/mm] gilt, gehe ich
> immer von den natürlichen Zahlen aus?
Du drückst Dich unglücklich aus: Die Eigenschaften abz., h. abz. und ü.-abz. untersucht man (gemäßt Euren Definitionen), indem man hinterfragt, ob es Funktionen [mm] $\IN \to [/mm] A$ mit gewissen Eigenschaften gibt.
> Das heißt ja
> eigendtlich, das mein M mehr Elemente als [mm]\IN[/mm] haben muss um
> injektiv zu sein?
Das ist so die grobe Vorstellung. Sie funktioniert auch bei "endlichen Mengen" (als Definitionsbereich) noch gut: Wenn [mm] $E\,$ [/mm] eine Menge ist und es eine injektive Abbildung (kurz: Injektion) von [mm] $\{1,...,n\} \to [/mm] E$ gibt, dann hat [mm] $E\,$ [/mm] mindestens [mm] $n\,$ [/mm] Elemente: $|E| [mm] \ge n\,.$ [/mm] Nur, wenn man [mm] $\{1,...,n\}$ [/mm] durch unendliche Mengen ersetzt, muss man aufpassen: Es gibt halt verschiedene Formen der Unendlichkeit - grob gesagt!
Ich stelle mir das immer so vor: Wenn man zwei unendliche Mengen [mm] $U_1$ [/mm] und [mm] $U_2$ [/mm] hat, dann besagt die Existenz einer Injektion [mm] $E_1 \to E_2\,,$ [/mm] dass ich alles an dem Vorrat, was ich in [mm] $E_1$ [/mm] gesammelt habe, "so auf [mm] $E_2$ [/mm] 'verteilt' werden kann, dass zumindest an keiner Stelle aus [mm] $E_2$ [/mm] mehr als ein Ding aus [mm] $E_1$ [/mm] vorliegt". Anders gesagt: Wenn die Elemente in [mm] $E_2$ [/mm] Personen wären, dann würde die Anwendung der Injektion mir eine Möglichkeit geben, beim Durchlauf durch alle Personen aus [mm] $E_2$ [/mm] alle Dinge aus [mm] $E_1\,$ [/mm] wieder zusammensammeln zu können, und zwar selbst dann, wenn ich aus [mm] $E_2$ [/mm] nach Anwendung der Injektion die Personen, die mit leeren Händen dastehen, nach Hause schicken würde!
> > Anders gesagt:
> > Anstatt zu fragen:
> > Ist [mm]M:=\{f: \IN \to \IN: f(2n)=0\forall n \in \IN}[/mm]
> abz.,
> > h.abz. oder ü-abz., kann man auch in vollkommen
> > gleichwertiger Weise fragen:
> > Ist
> > [mm]\tilde{M}:=\{(a_k)_{k \in \IN}:\;(a_k)_{k \in \IN}\text{ ist eine Folge mit Werten in }\IN\text{, die zudem erfüllt }a_{2k}=0\text{ für alle }k \in \IN\}[/mm]
>
> >
> > abz., h.abz. oder ü-abz.?
> Ich glaube so haben wir das gemacht: Die Menge S
> [mm]\{f:\IN->\IN: f(2n)=0 für alle n\in \IN\}[/mm] ist
> überabzählbar. Warum? Sei A [mm]\subseteq \{n\in \IN| n (ungerade)\},[/mm]
> dann ist [mm]f_A:\IN->\IN[/mm] mit
Im folgenden steht sicher [mm] $f_\red{A}(2n)$ [/mm] und [mm] $f_\red{A}(m)\,,$ [/mm] korrekt?!
> f(2n)=0 für ,alle, n und f(m)=1
> für m [mm]\in[/mm] A, f(m)=0 für [mm]m\in T\A[/mm] ein Element von S.
Was ist [mm] $T\,$? [/mm] Ich vermute, dass [mm] $T=\IN \setminus S\,.$ [/mm] Korrekt? Und am Ende ist, genauer gesagt, gemeint, dass [mm] $f_A \in S\,$ [/mm] gilt, und komischerweise hies dieses [mm] $S\,$ [/mm] bei uns doch [mm] $M\,$?!
[/mm]
> Dies
> sind überabzählbar viele, da T unendlich abzählbar ist
> und somit [mm]\delta(F)[/mm] überabzählbar ist.
Was ist [mm] $\delta(F)$?
[/mm]
> Den Beweis verstehe ich nicht, ich finde deine Erklärung
> da leichter.
Ich müsste mehr von dem Beweis sehen, um zu erkennen, was da gemacht wird. Was auf jeden Fall klar ist:
Die sagen halt, dass, wenn man $A [mm] \subseteq 2\IN+\{1\}$ [/mm] (also [mm] $A\,$ [/mm] ist IRGENDEINE Teilmenge der ungeraden nat. Zahlen) hat, man dann eine Funktion [mm] $f_A: \IN \to \IN$ [/mm] so definiert, dass sie an allen ungeraden nat. Stellen den Wert [mm] $1\,$ [/mm] hat, und ansonsten verschwindet.
Weißt Du, was für eine Menge [mm] $X\,$ [/mm] und $A [mm] \subseteq [/mm] X$ die Indikatorfunktion ist? Im Prinzip steht oben nichts anderes:
Für eine Teilmenge [mm] $A\,$ [/mm] der ungeraden natürlichen Zahlen betrachtet man deren Indikatorfunktion.
Ich schreibe später unten daher einfach [mm] $1_A$ [/mm] für die Funktion
[mm] $$1_A:\;\;\begin{cases} \IN \to \IN \\ n \mapsto 1_A(n):=\begin{cases} 1, & \mbox{für } n \in A \\ 0, & \mbox{für } n \in \IN \setminus A \end{cases}\end{cases}\,,$$
[/mm]
wenn $A [mm] \subseteq \IN$ [/mm] ist.
Und da für $A [mm] \subseteq 2\IN+\{1\}$ [/mm] wegen [mm] $\subseteq (2\IN+\{1\}) \subseteq \IN$ [/mm] auch $A [mm] \subseteq \IN$ [/mm] gilt, habe ich die von Euch betrachteten [mm] $A\,$ [/mm] auch in dieser Schreibweise erfasst.
Aber machen wir mal ein Beispiel:
Beispielsweise ist für [mm] $A_1:=\{3,5,11,15\}$ [/mm] dann
[mm] $$\underbrace{f_{A_1}}_{=1_{A_1}}(x)=\begin{cases} 1, & \mbox{für } x \in\{3,5,11,15\} \\ 0, & \mbox{für } n \in \IN \setminus \{3,5,11,15\} \end{cases}\,.$$
[/mm]
Insbesondere siehst Du, dass [mm] $f_{A_1}$ [/mm] an allen Stellen $x [mm] \in 2\IN$ [/mm] den Wert [mm] $0\,$ [/mm] annimmt - und wie gesagt, in "Folgennotation" wäre das vielleicht sogar noch besser/schneller zu erkennen (ich markiere die "geraden Stellen" mal blau - dort muss die [mm] $\textbf{\blue{0}}$ [/mm] notwendigerweise schonmal stehen, wenn [mm] $f_{A_1}$ [/mm] zu [mm] $S\,$ [/mm] gehört, was [mm] $f_{A_1}$ [/mm] auch tut):
[mm] $$(\underbrace{\textbf{\blue{0}}}_{0-\text{te Stelle}},0,\textbf{\blue{0}},1,\textbf{\blue{0}},\overbrace{1}^{5-\text{te Stelle}},\textbf{\blue{0}},0,\textbf{\blue{0}},0,\textbf{\blue{0}},1,\textbf{\blue{0}},0,\textbf{\blue{0}},1,\textbf{\blue{0}},0,\textbf{\blue{0}},0,\textbf{\blue{0}},0,\textbf{\blue{0}},0,\textbf{\blue{0}},\ldots)$$
[/mm]
Du siehst, dass hier nur an endlich vielen Stellen eine [mm] $1\,$ [/mm] auftaucht - das [mm] $\ldots$ [/mm] am Ende soll andeuten, dass unendlich viele 0en folgen. Und dass da unendlich viele Nullen folgen, ergibt sich daraus, dass [mm] $A\,$ [/mm] endlich ist.
Das muss aber nicht sein. Du kennst auch unendliche Teilmengen der ungeraden Zahlen. Entweder nimmst Du direkt einfach mal [mm] $A=2\IN+\{1\}\,,$ [/mm] oder Du entfernst halt endlich viele Elemente aus [mm] $2\IN+\{1\}$ [/mm] oder aber, was man auch gerne oft im Hinterkopf hat: Ist [mm] $\IP\,$ [/mm] die Menge der Primzahlen, so ist [mm] $\IP \setminus \{2\} \subseteq (2\IN+\{1\})$ [/mm] eine unendliche Menge (ungerader Zahlen).
Und die Aussage in dem Beweis, den ihr vorgeführt bekommen habt, ist folgende:
Die Menge
[mm] $$\{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\underbrace{1_A}_{\text{Indikatorfunktion bzgl. }A \text{ für }A \subseteq \IN}:\;\;A \subseteq (2\IN+\{1\})\}$$
[/mm]
ist überabzählbar.
Ich nehme mal an, dass ihr an anderer Stelle mal bewiesen habt, dass die Menge aller Folgen, die nur Werte in [mm] $\{0,1\}$ [/mm] annehmen (das wäre dann [mm] $\{0,1\}^\IN$) [/mm] überabzählbar ist. Das wird bei der Argumentation sicher benutzt - andernfalls verstehe ich sie nicht bzw. wäre sie mir zu kurz!
> > Und [mm]\tilde{M}[/mm] enthält halt alle (unendlich-)Tupel der
> > Form
> > [mm](0,n_1,0,n_2,0,n_3,0,n_4,\ldots)[/mm]
> > sofern alle [mm]n_j \in \IN[/mm] für alle [mm]j \in \IN[/mm] sind.
> > (Beachte: In der letzten Tupel-Notation meine ich nun
> > NICHT, dass [mm]n_j[/mm] mit irgendeinem Funktionswert identifiziert
> > werden sollte.)
> >
> > Also grob gesagt kann man mal andeuten:
> > Es gilt etwa
> >
> >
> [mm]\{(0,0,0,0,\ldots),\;(0,2,0,1,0,0,1,0,12,0,\ldots),\;(0,35,0,346645,0,232,0,7,\ldots)\} \subseteq \tilde{M}[/mm]
>
> >
> > aber
> > [mm](0,0,0,0,0,1,0,0,0,0,\ldots) \notin \tilde{M}\,.[/mm]
> >
> (An der
> > SECHSTEN Stelle steht ein Eintrag ungleich Null!)
> >
> > P.S.
> > Mit dem Cantorschen Diagonalverfahren ist leicht
> > einzusehen, dass [mm]\IN^\IN=\{r: \IN \to \IN\}[/mm] überabzählbar
> > ist. Um Deine Aufgabe damit möglichst elegant zu lösen:
> > Gib' eine Bijektion [mm]M \to \IN^{\IN}[/mm] an.
> Das habe ich nicht ganz verstanden. Ist das Cantorsche
> Diagonalverahren ein Standardverfahren um auf
> Abzählbarkeit, Überabzahlbarkeit und Höchst
> Abzählbarkeit zu prüfen bzw. gibt es ein solches?
Cantor war ein sehr schlauer Mensch: Er hat etwa mit einem Diagonalverfahren gezeigt, dass die Menge der rationalen Zahlen abzählbar, also gleichmächtig zu [mm] $\IN\,$ [/mm] ist.
Er hat aber auch mit einem zweiten Diagonalargument gezeigt, dass die Menge der reellen Zahlen (oder das Intervall [mm] $[0,1]\,$) [/mm] überabzählbar ist. Da geht man erstmal davon aus, dass dem nicht so wäre, nimmt also an, es gäbe eine Abzählung und baut sich dann einen Widerspruch "entlang gewisser Diagonalwerte" auf.
Schau einfach mal bei Wiki: Cantors erstes Diagonalargument oder Cantors zweites Diagonalargument. Diese Strategien kann man auch in anderen Bereichen oft fast genauso anwenden.
![[]](/images/popup.gif) Hier kannst Du ja mal etwa reingucken! (Ich hab' da mal nur schnell reingeguckt, aber mir schien, dass man den Beweis des 2. Diagonalverfahrens (Seite 11) fast wortwörtlich übernehmen kann, wenn man zeigen will, dass die Menge der 0,1-Folgen überabz. ist. Die [mm] $x_n\,$ [/mm] wären dann die einzelnen Funktionen, und nach dem Gleichheitszeichen schreibt man dann halt die zugehörige Folge als unendlicher Vektor. Dabei läßt Du dann halt das [mm] $0,\,$ [/mm] weg und schreibst wegen der Tupel-Notation dann noch Klammern drumherum.)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:25 Mo 07.05.2012 | | Autor: | durden88 |
Also ich danke vielmals für die Erklärungen. Vielleicht können wir ne zweite Aufgabe um zu prüfen, ob ich es kapiert habe.
[mm] \{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}. [/mm] Das heißt ja, alle ungeraden Zahlen werden dort genommen, im Tupel beschrieben mit [mm] 0\in \IN: [/mm]
[mm] \{1,2,3,4,5,6,7,8,....\}, [/mm] aber da ist ja die 0 nicht drin. Also ist es nur eine Teilmenge von [mm] \IN [/mm] so ist die Abbildung höchst abzählbar.
Ist das soweit richtig? Und nun...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:48 Mo 07.05.2012 | | Autor: | fred97 |
> Also ich danke vielmals für die Erklärungen. Vielleicht
> können wir ne zweite Aufgabe um zu prüfen, ob ich es
> kapiert habe.
>
> [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
Ist f aus obiger Menge, so ist f auf [mm] \IN [/mm] konstant !
> Das
> heißt ja, alle ungeraden Zahlen werden dort genommen, im
> Tupel beschrieben mit [mm]0\in \IN:[/mm]
> [mm]\{1,2,3,4,5,6,7,8,....\},[/mm] aber da ist ja die 0 nicht drin.
Mir ist nicht klar, was Du meinst.
> Also ist es nur eine Teilmenge von [mm]\IN[/mm] so ist die Abbildung
> höchst abzählbar.
Eine Abbildung ist nicht abzählbar. Den Begriff gibts nur für Mengen.
Sollst Du entscheiden , ob
[mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
abzählbar ist oder nicht ?
FRED
>
> Ist das soweit richtig? Und nun...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:15 Mo 07.05.2012 | | Autor: | durden88 |
> > Also ich danke vielmals für die Erklärungen. Vielleicht
> > können wir ne zweite Aufgabe um zu prüfen, ob ich es
> > kapiert habe.
> >
> > [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
>
> Ist f aus obiger Menge, so ist f auf [mm]\IN[/mm] konstant !
>
> > Das
> > heißt ja, alle ungeraden Zahlen werden dort genommen, im
> > Tupel beschrieben mit [mm]0\in \IN:[/mm]
> > [mm]\{1,2,3,4,5,6,7,8,....\},[/mm] aber da ist ja die 0 nicht drin.
>
> Mir ist nicht klar, was Du meinst.
>
>
> > Also ist es nur eine Teilmenge von [mm]\IN[/mm] so ist die Abbildung
> > höchst abzählbar.
>
>
> Eine Abbildung ist nicht abzählbar. Den Begriff gibts nur
> für Mengen.
>
> Sollst Du entscheiden , ob
>
> [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
>
> abzählbar ist oder nicht ?
ja....
> FRED
> >
> > Ist das soweit richtig? Und nun...
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:20 Mo 07.05.2012 | | Autor: | fred97 |
> > > Also ich danke vielmals für die Erklärungen. Vielleicht
> > > können wir ne zweite Aufgabe um zu prüfen, ob ich es
> > > kapiert habe.
> > >
> > > [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
>
> >
> > Ist f aus obiger Menge, so ist f auf [mm]\IN[/mm] konstant !
> >
> > > Das
> > > heißt ja, alle ungeraden Zahlen werden dort genommen, im
> > > Tupel beschrieben mit [mm]0\in \IN:[/mm]
> > > [mm]\{1,2,3,4,5,6,7,8,....\},[/mm] aber da ist ja die 0 nicht drin.
> >
> > Mir ist nicht klar, was Du meinst.
> >
> >
> > > Also ist es nur eine Teilmenge von [mm]\IN[/mm] so ist die Abbildung
> > > höchst abzählbar.
> >
> >
> > Eine Abbildung ist nicht abzählbar. Den Begriff gibts nur
> > für Mengen.
> >
> > Sollst Du entscheiden , ob
> >
> > [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}.[/mm]
> >
> > abzählbar ist oder nicht ?
> ja....
Ich hab Dir ja schon gesagt, dass jedes f aus der Menge
[mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}[/mm]
eine auf [mm] \IN [/mm] konstante Funktion ist, also ist mit einem c [mm] \in \IN: [/mm] f(n)=c für alle n [mm] \in \IN.
[/mm]
"Wieviele" Elemente hat also [mm]\{f: \IN-> \IN : f(n) = f(n + 1) \forall n \in \IN\}[/mm] ?
FRED
> > FRED
> > >
> > > Ist das soweit richtig? Und nun...
> >
>
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 19:56 Sa 05.05.2012 | | Autor: | Marcel |
Hallo Schadow,
> moin durden,
>
> Deine zu untersuchende Menge ist die Menge aller
> Abbildungen [mm]f[/mm] von [mm]\IN[/mm] nach [mm]\IN[/mm], für die [mm]f(n) = 0[/mm] falls [mm]n[/mm]
> gerade ist.
> Das heißt etwa die Folge:
> [mm](1,0,2,0,3,0,4,0,5,0,\ldots )[/mm] wäre in der Menge (dieses
> Tupel steht einfach für die Funktionswerte, also
> [mm](f(1),f(2),f(3),\ldots )[/mm])
bei Dir ist $0 [mm] \notin \IN\,,$ [/mm] aber bei der Aufgabe muss $0 [mm] \in \IN$ [/mm] sein, weil sonst Funktionen $f: [mm] \IN \to \IN$ [/mm] insbesondere $f(n) [mm] \in \IN$ [/mm] und damit $f(n) [mm] \not=0$ [/mm] für alle $n [mm] \in \IN$ [/mm] erfüllen würden.
(Anders gesagt: Für [mm] $\IN=\IN \setminus \{0\}$ [/mm] wäre [mm] $M=\emptyset$ [/mm] eine sehr triviale Menge, deren Untersuchung noch trivialer wäre...)
Ist mir aber auch erst sehr spät beim Schreiben meiner Antwort klargeworden! (Ich bevorzuge auch die Notationen [mm] $\IN=\IN \setminus \{0\}$ [/mm] und [mm] $\IN_0:=\IN \cup \{0\}\,.$)
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 19:50 Sa 05.05.2012 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> ich glaube, du hast da einen verständnismäßigen Hänger.
> Untersucht wird eine Menge der Form [mm]\IN\times\IN.[/mm]
das kann so nicht sein, auch, wenn Du Funktionen als zweistellige Relationen auffasst. Ich hab' Dir auch noch in einer PN was dazu geschrieben!
[mm] $\IN \times \IN$ [/mm] kann man mit [mm] $\IQ$ [/mm] identifizieren - allgemein sind Mengen [mm] $\IN^E$ [/mm] mit [mm] $E\,$ [/mm] endlich immer abzählbar!
> Und
> untersuchen sollst du, ob es eine Bijektion gibt ziwschen
> der beschriebenen Menge aller Tupel (n|f(n)) gibt, wobei f
> nur für gerade Zahlen definiert ist.
Auch hier: Gerade an den geraden nat. Zahlen sind solche [mm] $f\,$ [/mm] sehr uninteressant definiert: Dort nehmen sie den Wert Null an. Insbesondere ist ein solches [mm] $f\,$ [/mm] aber an diesen Stellen definiert - denn das steht im Definitionsbereich von [mm] $f\,$ [/mm] mit drin!
Und an den ungeraden nat. Zahlen sind solche [mm] $f\,$ [/mm] auch definiert: Dort wird je nach betrachteter Stelle irgendeine Zahl aus [mm] $\IN$ [/mm] angenommen.
Die Sprechweise, dass Funktionen an Stellen, wo sie verschwinden, nicht definiert sind, sollte man nicht benutzen: Sie impliziert falsches!
Denn: Wenn ich $f: [mm] \IN \to \IN$ [/mm] mit $f(n):=n$ für ungerade [mm] $n\,$ [/mm] und sonst $f(n):=0$ betrachte, und Du dann sagst, dass [mm] $f\,$ [/mm] auf den geraden nat. Zahlen nicht definiert sei, gehe ich davon aus, dass [mm] $2\IN \not\subseteq D_f$ [/mm] gilt: Aber es ist [mm] $2\IN \subseteq \IN\,.$
[/mm]
Anders gesagt: Wenn Du sagst, dass [mm] $f\,$ [/mm] nur auf ungeraden nat. Zahlen definiert ist und Werte in [mm] $\IN$ [/mm] annimmt, gehe ich davon aus, dass etwa $f: [mm] D_f:=2\IN+\{1\} \to \IN$ [/mm] gilt...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:17 Sa 05.05.2012 | | Autor: | Diophant |
Hallo Marcel,
vielen Dank für deine Korrektur. Da bin ich in der Tat einem fatalen Denkfehler aufgesessen, den ich durch ein wenig Nachdenken hätte vermeiden können.
@durden88:
Betrachte bitte meinen Beitrag als nichtig, die anderen Beiträge sind ja vollkommen ausreichend, deine Frage zu klären.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:37 So 06.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
