Weiss einer warum die Menge {0,1}^n überabzählbar ist?
Also ich hab versucht ne bijektion auf reelle Zahlen zu finden, was ja net so schwer wäre, wenn ich wüsste wie mal irrationale Zahlen im Dualsystem darstellt bzw ob es überhaubt geht... grummel.
Benachrichtigungen
Alles löschen
Studium, Ausbildung und Beruf
4
Beiträge
3
Benutzer
0
Reactions
516
Ansichten
3 Antworten
Hallo Loxodonta,
man kann irrationale Zahlen im Dualsystem darstellen. Jede Zahl zwischen Null und 1 läßt sich als Summe a_i*2^{-i} schreiben, wobei i von 1 bis unendlich läuft und die a_i Nullen oder Einsen sind.
Die a_i zu einer Zahl r findet man so:
a_1 ist Null, wenn r<=0,5
a_1 ist 1, wenn r>0,5
Wenn man a_1,...,a_n bestimmt hat dann ist
Summe der a_i*2^{-i} < r <= Summe der a_i*2{-i} + 2^{-n}
i=1 bis n i=1 bis n
Jetzt setzt man
a_{n+1} auf Null, wenn r <= Summe der a_i*2{-i} + 1/2 * 2^{-n}
i=1 bis n
und sonst auf 1
In beiden Fällen gilt auch für die Summe der ersten n+1 Produkte:
Summe der a_i*2{-i} < r <= Summe der a_i*2{-i} + 2^{-(n+1)}
i=1 bis n+1 i=1 bis n+1
Ich hoffe, ich habe das einigermaßen verständlich formuliert.
jo klar, Danke,
beim Lesen allerdings hatte ich dann das Gefühl auch selbst hätte drauf kommen zu können, aber das ist ja immer so... ;-)
Ist zwar schon alt, aber ich hab grad Lust drauf.
Die eleganteste Metheode ist imo die Menge {0,1}^N bijektiv auf die Potenzmenge von N abzubilden.
Dafür wird eine Teilmenge von N ihre charakteristische Funktion zugeordnet - die jedes Element in der Teilmenge auf 1 und jedes andere auf 0 abbildet.
Das ist "offensichtlich" bijektiv und man ist fertig.
Musst dafür natürlich nur wissen, daß die Potenzmenge von N überabzählbar ist, aber das sollte bekannt sein. Ansonsten gibt es da auch kurze Wege das zu zeigen...