Bijektion auf P(IN) < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:48 Di 23.10.2007 | | Autor: | quest |
| Aufgabe | Es sei bekannt, das für jede Menge A gilt |P(A)| > |A| (Kardinalität der Potenzmenge).
Zeige, dass die Menge
$$ R = [mm] \{ \sum_{i=0}^{\infty} a_i x^i | a_i \in \{0,1\} \forall i \in \IN_0 \} [/mm] $$ nicht abzählbar ist.
Zeige dazu, dass R und [mm] P(\IN_0) [/mm] gleichmächtig sind und wende das Resultat von oben an. |
Liebe Vorhelfer.
Wie man sich vorstellen kann, hab ich mit dem Beweis so meine Schwierigkeiten. Ich habe schon ein wenig gesucht und gegoogelt, aber noch nichts passendes gefunden.
Ziel ist es, also die Gleichmächtigkeit von R und [mm] P(\IN_0) [/mm] zu zeigen. Dazu muss ich eine Bijektion von R auf [mm] P(\IN_0) [/mm] konstruieren.
Ich habe im Internet etwas über Cantor- und erstes Diagonalargument gelesen, und glaube, dass man das hier auch anwenden kann. Nur ist mein Blick noch ein wenig verklärt. Vor allem hat Cantor damit ja einen Widerspruchsbeweis geführt um eben die gegebene Aussage, also für jede Menge gilt |P(A)| > |A| zu beweisen. Ich muss hier ja eine Abbildung konstruieren.
Ich muss also jeder Menge A von Teilmengen aus [mm] P(\IN_0) [/mm] eindeutig ein Reihe r [mm] \in [/mm] R finden.
Zu jeder Reihe ist doch eine Folge von Koeffizienten zugedacht. Also r = (0,0,1,1,0,1,...) usw., eigentlich muss ich damit doch jedem A [mm] \in P(\IN_0) [/mm] nur eine eindeutige Folge von Koeffizienten zuordnen, oder? Wenn das stimmt, wie kann ich für jedes A eine "neue" Folge von Koeffizienten konstruieren?
Grüße und dank für die Hilfe
quest
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:14 Di 23.10.2007 | | Autor: | statler |
Hi!
> Es sei bekannt, das für jede Menge A gilt |P(A)| > |A|
> (Kardinalität der Potenzmenge).
>
> Zeige, dass die Menge
> [mm]R = \{ \sum_{i=0}^{\infty} a_i x^i | a_i \in \{0,1\} \forall i \in \IN_0 \}[/mm]
> nicht abzählbar ist.
>
> Zeige dazu, dass R und [mm]P(\IN_0)[/mm] gleichmächtig sind und
> wende das Resultat von oben an.
> Wie man sich vorstellen kann, hab ich mit dem Beweis so
> meine Schwierigkeiten. Ich habe schon ein wenig gesucht und
> gegoogelt, aber noch nichts passendes gefunden.
>
> Ziel ist es, also die Gleichmächtigkeit von R und [mm]P(\IN_0)[/mm]
> zu zeigen. Dazu muss ich eine Bijektion von R auf [mm]P(\IN_0)[/mm]
> konstruieren.
So isset!
> Ich habe im Internet etwas über Cantor- und erstes
> Diagonalargument gelesen, und glaube, dass man das hier
> auch anwenden kann. Nur ist mein Blick noch ein wenig
> verklärt. Vor allem hat Cantor damit ja einen
> Widerspruchsbeweis geführt um eben die gegebene Aussage,
> also für jede Menge gilt |P(A)| > |A| zu beweisen. Ich muss
> hier ja eine Abbildung konstruieren.
Eben! Mit dem Diagonalargument zeigst du das, was dir in der Aufgabenstellung als bekannt vorgegeben ist.
> Ich muss also jeder Menge A von Teilmengen aus [mm]P(\IN_0)[/mm]
> eindeutig ein Reihe r [mm]\in[/mm] R finden.
Nee! Du mußt zu jedem Element von [mm] P(\IN_{0}), [/mm] also zu jeder Teilmenge von [mm] \IN_{0}, [/mm] eindeutig eine Reihe r finden. Und das geht ganz intuitiv, da kann fast nichts schiefgehen.
> Zu jeder Reihe ist doch eine Folge von Koeffizienten
> zugedacht. Also r = (0,0,1,1,0,1,...) usw., eigentlich muss
> ich damit doch jedem A [mm]\in P(\IN_0)[/mm] nur eine eindeutige
> Folge von Koeffizienten zuordnen, oder? Wenn das stimmt,
> wie kann ich für jedes A eine "neue" Folge von
> Koeffizienten konstruieren?
Nehmen wir in diesem Beispiel mal an, daß die 3 Punkte für lauter Nullen stehen, welches A würdest du vernünftigerweise zuordnen?
Hilfe (oder Verwirrung): Die Einsen stehen an der 2., 3. und 5. Stelle, auch wenn es dir anders vorkommt.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:38 Di 23.10.2007 | | Autor: | quest |
hallo statler,
danke schon mal für deine antwort, ich bin mir nur nicht sicher, ob ich die voll verstanden habe.
also wie schon gesagt, ich muss jeder Menge A [mm] \subset P(\IN_0) [/mm] eindeutig eine Reihe r [mm] \in [/mm] R zuordnen.
Diese Reihe ist doch die Folge der Koeffizienten bestimmt, also durch die Folge der Nullen und Einsen.
Als Beispiel war jetzt eine Reihe r mit Koeffizienten
[mm] a_r [/mm] = (0,0,1,1,0,1,...) wobei dannach nur noch Nullen kommen.
Die Frage ist nun, welches A [mm] \subset P(\IN_0) [/mm] ich diesem zuordnen soll. Z.B. die Menge A = {2,3,5 } ?
Das würde ja zu den "Positionen" der Einsen passen.
Gruß und dank,
quest
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:36 Mi 24.10.2007 | | Autor: | statler |
Guten Morgen Quest!
> danke schon mal für deine antwort, ich bin mir nur nicht
> sicher, ob ich die voll verstanden habe.
>
> also wie schon gesagt, ich muss jeder Menge A [mm]\subset P(\IN_0)[/mm]
> eindeutig eine Reihe r [mm]\in[/mm] R zuordnen.
Noch mal, weil es wirklich wichtig ist: Die Menge A ist Element der Potenzmenge, es muß also heißen A [mm]\in P(\IN_0)[/mm]! Solange dir dieser Unterschied nicht sonnenklar, schicken wir dich zurück auf 'Start'.
> Diese Reihe ist doch die Folge der Koeffizienten bestimmt,
> also durch die Folge der Nullen und Einsen.
>
> Als Beispiel war jetzt eine Reihe r mit Koeffizienten
> [mm]a_r[/mm] = (0,0,1,1,0,1,...) wobei dannach nur noch Nullen
> kommen.
>
> Die Frage ist nun, welches A [mm]\subset P(\IN_0)[/mm] ich diesem
> zuordnen soll. Z.B. die Menge A = {2,3,5 } ?
- gleicher Fehler wie oben -
> Das würde ja zu den "Positionen" der Einsen passen.
Jetzt ist es dir im Prinzip anscheinend klar, es bleibt die Aufgabe, alles in allgemeiner Form und Mathe-Speak hinzuschreiben.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 01:15 Do 25.10.2007 | | Autor: | quest |
hallo statler,
ja ich hab jetzt gesehen was du meintest. naturlich muss ich zu jedem element a [mm] \in P(\IN_0) [/mm] eine Reihe finden, es ist nur so, dass die Elemente in [mm] P(\IN_0) [/mm] eben Teilmengen von [mm] \IN [/mm] sind. Das hab ich damit verwechselt.
Die Herausforderung wird wohl der Mathe-Speak sein.
Ich hätte jetzt mal so angefangen:
Zunächst die Überlegung, dass jede Reihe r [mm] \in [/mm] R, durch seine Koeffizienten bestimmt ist. D.h. es genügt jeder Reihe r, die durch eine Koeffizientenfolge definiert ist ein b [mm] \in P(\IN_0) [/mm] zuzuweisen. Und dass soll meine Bijektion, nennen wir sie mal f machen.
Also ich hab eine Folge [mm] $a_k [/mm] = [mm] (a_0, a_1, a_2, ..a_n)$, [/mm] wobei n ja doch auch [mm] \infty [/mm] sein kann, oder? Die [mm] $a_i$ [/mm] sind 0 oder 1. Dann weiße jeder solchen Folge, ein b [mm] \in P(\IN_0) [/mm] zu, sodass in b die Elemente {i} vorkommen für alle [mm] $a_i [/mm] = 1$.
Das wäre doch so grob der Gedanke mal formuliert, wenn ich das vorhin richtig verstanden habe.
Aber wie zeige ich denn von sowas injektivität oder surjektivität???
Ich kann da ja nicht "Beispielhaft" argumentieren, sondern muss das allgemein formulieren.
Hast du nen Tipp, wie man das aufschreiben kann oder wo ich diesbezüglich was nachlesen kann?
Grüße und dank
quest
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:54 Fr 09.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
