Abzählbarkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:59 Do 15.11.2012 | | Autor: | Zero_112 |
| Aufgabe | Finde heraus, ob die Menge D abzählbar oder überabzählbar ist.
D := { B [mm] \subset \IN [/mm] : B ist entweder endlich oder [mm] \IN [/mm] \ B ist endlich} |
Ich habe mit dieser Aufgabe einige Schwierigkeiten. Ich habe hier ja eine Menge von echten Teilmengen B von [mm] \IN [/mm] für die folgendes gilt:
|B| < [mm] \infty [/mm] oder [mm] |\IN [/mm] \ B| < [mm] \infty. [/mm] Jetzt nehme ich mal an, diese Menge sei abzählbar, dann würde ja eine bijektive Abbildung zwischen D und [mm] \IN [/mm] existieren:
B [mm] \to \IN [/mm]
x [mm] \mapsto [/mm] ?
Ich finde nur leider keine Abbildung, weil ich mir gar nicht vorstellen kann wie eine solche aussehen soll, denn ich habe ja eine Menge von Mengen. Ich finde auch keinen anderen Ansatz, der irgendwie hilfreich ist. Vielleicht kann man ja zeigen, dass die Menge nicht überabzählbar ist, d.h. die Mächtigkeit von B nicht größer ist als die der natürlichen Zahlen. Aber auch hier finde ich keinen Lösungsweg :(
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:54 Do 15.11.2012 | | Autor: | rainerS |
Hallo!
> Finde heraus, ob die Menge D abzählbar oder
> überabzählbar ist.
>
> [mm]D := \{ B \subset \IN : \text{$B$ ist entweder endlich oder $\IN \setminus B$ ist endlich}\}[/mm]
> Ich habe mit dieser Aufgabe einige Schwierigkeiten. Ich
> habe hier ja eine Menge von echten Teilmengen B von [mm]\IN[/mm]
> für die folgendes gilt:
> |B| < [mm]\infty[/mm] oder [mm]|\IN[/mm] \ B| < [mm]\infty.[/mm] Jetzt nehme ich mal
> an, diese Menge sei abzählbar, dann würde ja eine
> bijektive Abbildung zwischen D und [mm]\IN[/mm] existieren:
>
> B [mm]\to \IN[/mm]
> x [mm]\mapsto[/mm] ?
>
> Ich finde nur leider keine Abbildung, weil ich mir gar
> nicht vorstellen kann wie eine solche aussehen soll, denn
> ich habe ja eine Menge von Mengen. Ich finde auch keinen
> anderen Ansatz, der irgendwie hilfreich ist. Vielleicht
> kann man ja zeigen, dass die Menge nicht überabzählbar
> ist, d.h. die Mächtigkeit von B nicht größer ist als die
> der natürlichen Zahlen. Aber auch hier finde ich keinen
> Lösungsweg :(
So auf den ersten Blick scheint mir, dass die beiden Teilmengen [mm]\{B\subset\IN\mid \text{$B$ ist endlich}\}[/mm] und [mm]\{B\subset\IN\mid \text{$\IN\setminus B$ ist endlich}\}[/mm] die gleiche Mächtigkeit haben.
Zeige doch erst einmal, dass die Menge der endlichen Teilmengen von [mm] $\IN$ [/mm] abzählbar ist. Tipp: Binärdarstellung einer Zahl.
Dann bleibt noch die Frage, ob [mm]\{B\subset\IN\mid \text{$\IN\setminus B$ ist endlich}\}[/mm] abzählbar ist.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:30 Do 15.11.2012 | | Autor: | Zero_112 |
Die Binärdarstellung einer Zahl kenne ich noch nicht und darf ich demnach gar nicht verwenden. Ich kenne nur die Methode : "Finde eine bijektive Abbildung zwischen der zu betrachtenden Menge und [mm] \IN [/mm] ".
Ich denke, dass [mm] D_1:= [/mm] { [mm] B\subset\IN [/mm] : |B| < [mm] \infty [/mm] } abzählbar unendlich ist, da [mm] \IN [/mm] abzählbar unendlich ist und es deshalb abzählbar unendlich endliche Teilmengen von [mm] \IN [/mm] geben muss. Ich weiß aber irgendwie nicht wie ich das zeigen soll, da ich keine Bijektion finde. Das müsste ja ungefähr so aussehen:
[mm] B_1 [/mm] --- 1
[mm] B_2 [/mm] --- 2
[mm] B_3 [/mm] --- 3
.
.
.
[mm] B_n [/mm] --- n [mm] n\in\IN
[/mm]
oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:28 Fr 16.11.2012 | | Autor: | Marcel |
Hallo,
> Die Binärdarstellung einer Zahl kenne ich noch nicht und
> darf ich demnach gar nicht verwenden. Ich kenne nur die
> Methode : "Finde eine bijektive Abbildung zwischen der zu
> betrachtenden Menge und [mm]\IN[/mm] ".
dürft ihr denn schon verwenden, dass abzählbare Vereinigungen
abzählbarer Mengen abzählbar sind?
Es ist nämlich
[mm] $$\{B \subseteq \IN: |B| < \infty\}=\bigcup_{i=1}^\infty \{B \subseteq \IN: |B|=i\}=\bigcup_{j \in \IN}\{B \subseteq \IN: |B|=j\}\,,$$
[/mm]
so dass es reicht, zu zeigen, dass für jedes $k [mm] \in \IN$ [/mm] die Menge
[mm] $$\{B \subseteq \IN: |B|=k\}$$
[/mm]
abzählbar ist.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:41 So 18.11.2012 | | Autor: | Zero_112 |
> dürft ihr denn schon verwenden, dass abzählbare
> Vereinigungen
> abzählbarer Mengen abzählbar sind?
Ja dürfen wir.
> Es ist nämlich
> [mm]\{B \subseteq \IN: |B| < \infty\}=\bigcup_{i=1}^\infty \{B \subseteq \IN: |B|=i\}=\bigcup_{j \in \IN}\{B \subseteq \IN: |B|=j\}\,,[/mm]
>
> so dass es reicht, zu zeigen, dass für jedes [mm]k \in \IN[/mm] die
> Menge
> [mm]\{B \subseteq \IN: |B|=k\}[/mm]
> abzählbar ist.
Diese Gleichheiten habe ich allerdings nicht ganz verstanden. Warum wird von [mm] i\in\IN [/mm] nach [mm] j\in\IN [/mm] zu [mm] k\in\IN [/mm] gewechselt? Also warum darf ich das einfach so sagen? Kann man das auch mit dem Cantor'schen Diagonalprozess beweisen? Also indem ich sage [mm] D_1 [/mm] := {B [mm] \subseteq \IN: [/mm] |B| < [mm] \infty\}, D_1= \bigcup_{i=1}^{n} D_1_i [/mm] und dann annehme, dass [mm] D_1_i [/mm] = { [mm] E_i,_1 [/mm] ; [mm] E_i,_2 [/mm] ; [mm] E_i,_3 [/mm] ....} und dann sone Tabelle erstelle und das mit dem Diagonalprozess zeige ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:02 So 18.11.2012 | | Autor: | Marcel |
Hallo,
>
> > dürft ihr denn schon verwenden, dass abzählbare
> > Vereinigungen
> > abzählbarer Mengen abzählbar sind?
>
> Ja dürfen wir.
>
> > Es ist nämlich
> > [mm]\{B \subseteq \IN: |B| < \infty\}=\bigcup_{i=1}^\infty \{B \subseteq \IN: |B|=i\}=\bigcup_{j \in \IN}\{B \subseteq \IN: |B|=j\}\,,[/mm]
>
> >
> > so dass es reicht, zu zeigen, dass für jedes [mm]k \in \IN[/mm] die
> > Menge
> > [mm]\{B \subseteq \IN: |B|=k\}[/mm]
> > abzählbar ist.
>
> Diese Gleichheiten habe ich allerdings nicht ganz
> verstanden. Warum wird von [mm]i\in\IN[/mm] nach [mm]j\in\IN[/mm] zu [mm]k\in\IN[/mm]
> gewechselt?
das hat keinen tieferen Sinn - ich mache das nur manchmal, weil bei
manchen sonst, wenn sie eine Mengengleichheit zeigen wollen, dann
das [mm] $j\,$ [/mm] linkerhand mit dem [mm] $j\,$ [/mm] rechterhand identifizieren. Wenn ich
die Indizes umbenenne, laufen sie nicht in diese Gefahr. Du kannst auch
überall nur $i [mm] \in \IN$ [/mm] schreiben und dann das $i [mm] \in \IN$ [/mm] benutzen.
> Also warum darf ich das einfach so sagen?
Na, wenn ich eine Mengengleichheit hinschreibe, und mir jemand sagt,
dass er sie nicht direkt einsieht, dann schlage ich doch vor: Derjenige
soll sie doch bitte beweisen. Also leg' mal los: Wenn Dir das nicht gelingt,
dann beweise ich es halt für Dich oder helfe Dir beim Beweis. Das zweite
Gleichheitszeichen ist aber fast trivial.
> Kann
> man das auch mit dem Cantor'schen Diagonalprozess beweisen?
> Also indem ich sage [mm]D_1[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
:= {B [mm]\subseteq \IN:[/mm] |B| <
> [mm]\infty\}, D_1= \bigcup_{i=1}^{n} D_1_i[/mm] und dann annehme,
> dass [mm]D_1_i[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= { [mm]E_i,_1[/mm] ; [mm]E_i,_2[/mm] ; [mm]E_i,_3[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
....} und dann sone
> Tabelle erstelle und das mit dem Diagonalprozess zeige ?
Keine Ahnung - das sage ich Dir, wenn Du mir zeigst, wie dann Dein Beweis
konkret aussieht. Aber ich tippe drauf, dass man auch einen Beweis via
des Cantorschen Diagonalverfahrens hinbekommt - denn wie kann man
etwa beweisen, dass abzählbare Vereinigungen abzählbarer Mengen
abzählbar sind?
Ist Dir denn klar, warum für jedes $i \in \IN$ die Menge $\{B \subseteq \IN: |B|=i\}\,$
abzählbar ist?
Ich denke, dass man das zeigen kann, indem man beweist, dass gilt:
$$\{B \subseteq \IN: |B|=i\}=\bigcup_{\substack{n \in \IN\\n \ge i}}\{A \subseteq \{1,...,n\}: |A|=i\}$$
Gruß,
Marcel
|
|
|
|
