Abzählbarkeit < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:32 Sa 06.12.2008 | | Autor: | ulla |
| Aufgabe | | Für nichtleere Mengen X und Y sei [mm] Y^{x}=\{f:X->Y\}. [/mm] Untersuchen sie die Mengen [mm] \IN^{\{0,1\}} [/mm] und [mm] \{0,1\}^{\IN} [/mm] auf Abzählbarkeit. |
Hallo,
leider weiß ich nicht wie ich dies untersuchen soll da wir recht wenig dazu gemacht haben. Kann mir jemand helfen?
Ich habe diese Aufgabe in keinem anderen Forum getsellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:36 Sa 06.12.2008 | | Autor: | pelzig |
Hallo
Du meinst sicherlich die Mengen [mm] $\{0,1\}^\IN$ [/mm] und [mm] $\IN^{\{0,1\}}$. [/mm] Fangen wir mal mit der zweiten Menge an.
Nach Definition ist [mm] $\IN^{\{0,1\}}=\{\varphi:\{0,1\}\to\IN\}$, [/mm] d.h. jede dieser Abbildungen [mm] $\varphi$ [/mm] ist eindeutig bestimmt durch ihr Bild auf 0 und 1. Mit anderen Worten: es gibt eine kanonische Bijektion [mm] $\IN^{\{0,1\}}\ni\varphi\mapsto (\varphi(0,\varphi(1))\in\IN^2$, [/mm] damit ist [mm] $\IN^{\{0,1\}}$ [/mm] gleichmächtig zu [mm] $\IN^2$ [/mm] und diese Menge ist abzählbar (Cantorsches Diagonalverfahren), also ist insbesondere [mm] $\IN^{\{0,1\}}$ [/mm] abzählbar.
Bei der ersten Menge sieht die Sache etwas anders aus. Die Elemente von [mm] $\{0,1\}^\IN$ [/mm] sind Abbildungen von [mm] $\IN$ [/mm] nach [mm] $\{0,1\}$. [/mm] Das scheinen irgendwie viel mehr zu sein als oben, denn um auch nur eine solche Abbildung zu beschreiben, muss ich bereits abzählbar viele Informationen, nämlich ihr Bild auf jeder natürlichen Zahl, angeben. Wir vermuten, dass diese Menge "zu groß" ist, um abzählbar zu sein, aber um das zu beweisen müssen wir uns schon etwas mehr anstrengen. Was wir zum Beispiel bräuchten wäre eine Surjektion in eine Menge, die bereits überabzählbar ist, z.B. [mm] $[0,1]\subset\IR$ [/mm] oder [mm] $\mathcal{P}(\IN)$ [/mm] (die Potenzmenge von [mm] $\IN$).
[/mm]
1) Betrachte die Surjektion (!) [mm] $\Phi:\{0,1\}^\IN\ni\varphi\mapsto\sum_{k=1}^\infty\frac{1}{2^{\varphi(k)}}\in[0,1]$. [/mm] Beachte, dass diese Abbildung keine Injektion ist...
2) Betrachte die (kanonische) Bijektion (!) [mm] $\Psi:\{0,1\}^\IN\ni\varphi\mapsto\{n\in\IN|\varphi(n)=1\}\in\mathcal{P}(\IN)$
[/mm]
Jetzt musst du sicherlich erstmal darüber schlafen und dann v.A. zeigen, dass diese Abbildungen auch die gewünschten Eigenschaften haben. Ich denke das genügt 
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:29 Sa 06.12.2008 | | Autor: | ulla |
Danke für deine Antwort .
den ersten Teil verstehe ich. Aber den zweiten Teil nicht. Ich verstehe nicht wie ich die Surjektivität und Bijektivität so zeigen kann! Kannst du mir vielleicht den Anfang mal hinschreiben oder mir irgentwie anders helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:58 Sa 06.12.2008 | | Autor: | pelzig |
> 1) [mm] $\Phi:\{0,1\}^\IN\ni\varphi\mapsto\sum_{k=1}^\infty\frac{1}{2^{\varphi(k)}}\in[0,1]$
[/mm]
Du weißt doch bestimmt dass du die reellen Zahlen als Dezimalbrüche zur Basis 2 entwickeln kannst. Jedes [mm] $x\in[0,1]$ [/mm] hat dann die Form [mm] $[0,a_1a_2a_3...]$ [/mm] für eine gewisse Folge [mm] $(a_n)_{n\in\IN}\subset\{0,1\}$ [/mm] (jedoch nicht eindeutig). Dann ist [mm] $\Phi((a_n))=x$.
[/mm]
> 2) [mm] $\Psi:\{0,1\}^\IN\ni\varphi\mapsto\{n\in\IN|\varphi(n)=1\}\in\mathcal{P}(\IN)$
[/mm]
Nimm dir doch mal ein paar Folgen und schau dir an was [mm] $\Psi$ [/mm] damit macht. Wenn du die Abbildung [mm] $\Psi$ [/mm] verstanden hast, sollte doch sonnenklar sein, warum die bijektiv ist.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:15 Sa 06.12.2008 | | Autor: | ulla |
Tut mir leid aber wir haben diese Formel die du unter 1) und 2) stehen hast noch nie durchgenommen, gibt es denn eine andere variante? Und wenn nicht dann weiß ich nicht wie ich es mit deiner lösen kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:28 Sa 06.12.2008 | | Autor: | pelzig |
> Tut mir leid aber wir haben diese Formel die du unter 1)
> und 2) stehen hast noch nie durchgenommen, gibt es denn
> eine andere variante? Und wenn nicht dann weiß ich nicht
> wie ich es mit deiner lösen kann.
Hmm ich verstehe die Frage nicht so richtig. Hast du verstanden was die Abbildungen machen? Oder hast du Probleme mit der Notation?
[mm] $\varphi:X\ni x\mapsto\varphi(x)\in [/mm] Y$ bedeutet: [mm] "$\varphi$ [/mm] ist eine Abbildung von der Menge X in die Menge Y, wobei ein Element [mm] $x\in [/mm] X$ abgebildet wird auf [mm] $\varphi(x)$."
[/mm]
Vielleicht wird es an einem konkreten Beispiel deutlicher:
[mm] $f:\IR\ni x\mapsto x^2\in\IR$ [/mm] bedeutet, "f ist eine Abbildung von [mm] $\IR^2$ [/mm] in [mm] $\IR$, [/mm] wobei [mm] $f(x)=x^2$ [/mm] für jedes [mm] $x\in\IR$.
[/mm]
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:35 Sa 06.12.2008 | | Autor: | ulla |
also ich hab die Aussage der "Formel " schon verstanden aber keine Ahnung wie ich es zeigen soll mit der Surjektivität und BIjektivität. Dazu hat mir uch deine 2 Antwort nicht geholfen. Also ich hab absolut keine Ahnung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:48 Sa 06.12.2008 | | Autor: | pelzig |
Verwirrung ist okay, aber du musst selbst tätig werden. Stelle eine konkrete Frage.
Wie ist Bijektivität definiert? Was ist eigentlich zu zeigen?
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:56 Sa 06.12.2008 | | Autor: | ulla |
Wie kann ich die Bijektivität und surjekivität hier zeigen? (außer mit den Antworten vorher) Wie sind beide definiert.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:08 Sa 06.12.2008 | | Autor: | pelzig |
Bleiben wir doch mal bei der zweiten Abbildung [mm] $\Psi:\{0,1\}^\IN\ni\varphi\mapsto\{n\in\IN|\varphi(n)=1\}\in\mathcal{P}(\IN)$
[/mm]
Behauptung: [mm] $\Psi$ [/mm] ist bijektiv, d.h. [mm] $\Psi$ [/mm] ist injektiv und surjektiv:
i) Surjektivität. Sei [mm] $X\subset\IN$ [/mm] eine beliebige Teilmenge der natürlichen Zahlen. Konstruiere nun eine Funktion [mm] $\varphi\in\{0,1\}^\IN$ [/mm] mit [mm] $\Psi(\varphi)=X$.
[/mm]
ii) Injektivität. Sei [mm] $\Psi(\varphi)=\Psi(\psi)$ [/mm] für zwei [mm] $\varphi,\psi\in\{0,1\}^\IN$. [/mm] Zeige nun, dass [mm] $\varphi=\psi$ [/mm] gilt, d.h. [mm] $\varphi(n)=\psi(n)$ [/mm] für alle [mm] $n\in\IN$.
[/mm]
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:26 Sa 06.12.2008 | | Autor: | ulla |
ich versteh das so nicht. Wie kann ich ie bijektivität den noch zeigen? Oder vielleicht bringt ich ein Lösungsansatz weiter?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Mo 08.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
