Abzählbar < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:14 Mi 03.08.2005 | | Autor: | Bastiane |
Hallo!
Hier eine Aufgabe zur Abzählbarkeit:
Man zeige:
i) Die Menge aller endlichen Teilmengen von [mm] \IN [/mm] ist abzählbar.
ii) Die Menge aller Teilmengen von [mm] \IN [/mm] ist überabzählbar.
i) würde ich so machen:
Also, da eine Vereinigung abzählbar vieler abzählbarer Mengen wieder abzählbar ist, zerlege ich meine Menge in abzählbar viele abzählbare Mengen:
[mm] \IN=\{\mbox{alle einelementigen Teilmengen}\}\cup\{\mbox{alle zweielementigen Teilmengen}\}\cup...\cup\{\mbox{alle n-elementigen Teilmengen}\}
[/mm]
Dies sind offensichtlich abzählbar viele Mengen (nämlich [mm] \IN=M_1\cup M_2\cup...\cup M_n [/mm] mit [mm] M_i=\{\mbox{alle i-elementigen Teilmengen}\} [/mm] (würde man das so erklären? oder reicht es, wenn man sagt, dass es abzählbar viele Mengen sind?). Und jede dieser abzählbar vielen Mengen ist wiederum abzählbar, denn die einelementigen Mengen kann man ja wieder ganz einfach abzählen: [mm] M_1=\{1\}\cup\{2\}\cup...\cup\{n\} [/mm] usw. Die k-elementigen Teilmengen könnte man doch dann mit der ![[]](/images/popup.gif) Catorschen Paarungsfunktion auch abzählen, oder nicht? (Ich kannte diese Funktion gar nicht, aber so wie ich das verstehe, lässt sich das damit machen.)
Und somit habe ich eine Vereinigung abzählbar vieler abzählbarer Menge, und diese ist nach einem Satz wiederum abzählbar, womit der gesucht Beweis erbracht wäre.
Stimmt das so?
Allerdings weiß ich leider nicht, wie ich ii) beweisen soll, könnte mir da jemand einen Hinweis geben?
Ach ja, und noch eine Frage: gibt es den Begriff "abzählbare Vereinigung"? Wenn ja, ist das das gleiche wie "Vereinigung abzählbar vieler Mengen"? Oder was ist damit gemeint?
Viele Grüße
Bastiane
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:47 Do 04.08.2005 | | Autor: | Hanno |
Hallo Christiane!
> Und somit habe ich eine Vereinigung abzählbar vieler abzählbarer Menge, und diese ist nach einem Satz wiederum abzählbar, womit der gesucht Beweis erbracht wäre.
> Stimmt das so?
Ja, das ist richtig! ![[ok]](/images/smileys/ok.gif "[ok]")
> Allerdings weiß ich leider nicht, wie ich ii) beweisen soll, könnte mir da jemand einen Hinweis geben?
Na klar :) Es gibt hier zwei Möglichkeiten, die du dir beide auf Grund ihrer Nützlichkeit und Eleganz einprägen solltest. Bijektionen muss man oft konstruieren, dafür ist (2) ein schönes Beispiel.
(1) Beweis von: Es gibt keine Bijektion von [mm] $\IN$ [/mm] nach [mm] ${\cal P}(\IN)$.
[/mm]
Beweis durch Widerspruch. Nehmen wir an, es gäbe eine solche bijektive Abbildung [mm] $f:\IN\to{\cal P}(\IN)$. [/mm] Betrachten wir nun die Menge $M$ der [mm] $n\in \IN$ [/mm] mit [mm] $n\notin [/mm] f(n)$. Da $f$ bijektiv ist, existiert ein [mm] $m\in \IN$ [/mm] mit $f(m)=M$. Nehmen wir an, es sei [mm] $m\in [/mm] M$. Dann folgte aus der Definition von $M$ sofort [mm] $m\notin [/mm] f(m)=M$ - Widerspruch. Nehmen wir an, es sei [mm] $m\notin [/mm] M$, dann folgte aus der Definition von $M$ sofort [mm] $m\in [/mm] M$ - Widerspruch. Damit kann die genannte Bijektion $f$ nicht existieren.
(2) Beweis von: [mm] $\IR$ [/mm] ist gleichmächtig zu [mm] ${\cal P}(\IN)$.
[/mm]
Es sei [mm] $x\in\IR$ [/mm] mit [mm] $x=\summe_{n=-\infty}^{\infty} 2^n a_n$ [/mm] mit [mm] $a_n\in\{0,1\}, n\in\IZ$. [/mm] Definiere [mm] $f:\IR\to{\cal P}(\IZ)$ [/mm] durch [mm] $f(x)=\{n\in \IZ\vert a_n=1\}$. [/mm] Dann ist (Beweis überlasse ich dir) $f$ eine Bijektion. Damit ist [mm] $\vert {\cal P}(\IZ)\vert [/mm] = [mm] \vert\IR\vert$. [/mm] Komposition mit einer Bijektion von [mm] ${\cal P}(\IZ)$ [/mm] nach [mm] ${\cal P}(\IN)$ [/mm] führt dann zum gewünschten Ergebnis. Damit ist [mm] ${\cal P}(\IN)$ [/mm] überabzählbar, es kann folglich keine Bijektion von [mm] $\IN$ [/mm] auf [mm] ${\cal P}(\IN)$ [/mm] geben.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:51 Do 04.08.2005 | | Autor: | Bastiane |
Hallo Hanno!
Danke für die Antwort.
> (1) Beweis von: Es gibt keine Bijektion von [mm]\IN[/mm] nach [mm]{\cal P}(\IN)[/mm].
Also erstmal direkt eine Frage: in meinem Buch steht Abzählbarkeit nicht mit einer bijektiven sondern nur mit einer surjektiven Abbildung definiert. Warum?
> Beweis durch Widerspruch. Nehmen wir an, es gäbe eine
> solche bijektive Abbildung [mm]f:\IN\to{\cal P}(\IN)[/mm].
> Betrachten wir nun die Menge [mm]M[/mm] der [mm]n\in \IN[/mm] mit [mm]n\notin f(n)[/mm].
> Da [mm]f[/mm] bijektiv ist, existiert ein [mm]m\in \IN[/mm] mit [mm]f(m)=M[/mm].
Irgendwie verstehe ich diesen letzten Satz nicht so ganz. Wieso folg solch ein m aus der Bijektivität?
Viele Grüße
Christiane
![[hand]](/images/smileys/hand.gif "[hand]")
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:15 Do 04.08.2005 | | Autor: | Hanno |
Hallo Christiane.
> Also erstmal direkt eine Frage: in meinem Buch steht Abzählbarkeit nicht mit einer bijektiven sondern nur mit einer surjektiven Abbildung definiert. Warum?
Hier liegt wohl ein Fehler meinerseits vor. Die Definition der Abzählbarkeit über die Existenz einer Surjektion sollte richtig sein. Schließlich sind auch endliche Mengen abzählbar. Für abzählbar unendliche Mengen sind die Existenz einer Surjektion und die einer Bijektion äquivalent, wenn ich mich recht entsinne, da es in diesem Falle auch eine Surjektion von der zu untersuchenden Menge auf die Menge der natürlichen Zahlen gibt. Dann folgt [nach Schröder-Bernstein], dass es wegen der Existenz zweier surjektiver Abbildungen zwischen den Mengen (oder, was das gleiche ist, zweier injektiver Abbildungen) auch eine bijektive Abbildung existiert.
Dies gilt z.B. auch in der Aufgabe, die du zu lösen hast. Eine Injektion von [mm] $\IN$ [/mm] nach [mm] ${\cal P}(\IN)$ [/mm] ist schließlich leicht zu finden. Gäbe es nun auch eine Surjektion von [mm] $\IN$ [/mm] nach [mm] ${\cal P}(\IN)$, [/mm] d.h. eine Injektion von [mm] ${\cal P}(\IN)$, [/mm] dann folgte die Existenz einer Bijektion. Wollen wir also die Überabzählbarkeit von [mm] ${\cal P}(\IN)$ [/mm] beweisen, dann können wir für den Widerspruchsbeweis annehmen, dass eine bijektive Abbildunge existierte.
> Irgendwie verstehe ich diesen letzten Satz nicht so ganz. Wieso folg solch ein m aus der Bijektivität?
Die Menge $M$ ist eine Teilmenge der natürlichen Zahlen, $f$ nach Voraussetzung eine Bijektion von [mm] $\IN$ [/mm] nach [mm] ${\cal P}(\IN)$. [/mm] Es gibt daher zu jeder Teilmenge [mm] $X\subset\IN$ [/mm] ein [mm] $x\in\IN$ [/mm] mit $f(x)=X$; insbesondere gibt es ein solches $x$, im Beweis als $m$ bezeichnet, auch für die Menge $M$. Klar?
Liebe Grüße,
Hanno
|
|
|
|
