Autor |
Beitrag |
martin
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 14. Mai, 2002 - 18:14: |
|
zeige, daß M überabzählbar ist, wobei M={f| f: |N ->{0,1}} danke |
orion (orion)
Erfahrenes Mitglied Benutzername: orion
Nummer des Beitrags: 210 Registriert: 11-2001
| Veröffentlicht am Dienstag, den 14. Mai, 2002 - 19:08: |
|
martin : Der Beweis wird mit dem sog. Cantor'schen Diagonalverfahren erbracht. Den Elementen von M entsprechen bijektiv die (0,1)-Folgen f = (f(1),f(2),...,f(n),...) mit f(n) in {0,1} für n in |N. Daher genügt es, die Menge 2^|N aller (0,1)-Folgen als überabzählbar nachzuweisen. Annahme : f_i = (f_i(1),f_i(2),...,f_i(n),...),i = 1,2,3,... sei eine Abzählung. Wir definieren eine Folge d = (d(1),d(2),...,d(n),...) durch die Festsetzung d(n):=0, wenn f_n(n) = 1 und d(n):=1,wenn f_n(n)=0 Die Folge d ist also von allen Folgen f_i in obiger Abzählung verschieden,letztere kann also nicht alle (0,1)-Folgen enthalten : Widerspruch. mfg Orion |
martin
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 14. Mai, 2002 - 19:17: |
|
erstmal vielen dank, aber geht das ganze nicht auch mit hilfe einer bijektion zwischen der menge m und der potenzmenge von |N ? (wobei schon bekannt ist, das diese überabzählbar ist) wenn das geht, würde mich auch interessieren wie. grüße martin |
ende (ende)
Mitglied Benutzername: ende
Nummer des Beitrags: 20 Registriert: 05-2002
| Veröffentlicht am Dienstag, den 14. Mai, 2002 - 20:02: |
|
Hallo, martin! Ja, klar eine solche Bijektion kannst Du auch benutzen. Das waere auch mein erster Ansatz gewesen. Allerdings konnte Orion ja nicht wissen, ob ihr die Ueberabzaehlbarkeit von Pot(IN) schon habt. Die Bijektion p von Pot(IN) auf M geht wie folgt: Fuer eine Teilmenge T von IN und fuer alle n aus IN sei definiert: p(T)(n) := 1, falls n aus T, und 0, falls n nicht aus T. Wir geben also die Funktion, auf die eine Teilmenge T von IN abgebildet wird dadurch an, dass wir fuer diese Funktion angeben, was sie mit Werten aus ihrem Definitionsbereich tun soll. Ich hoffe, dass Dich das nicht zu sehr verwirrt. Zur Not kannst Du Dir das auch so formulieren: Fuer T aus Pot(IN) sei definiert: p(T) := fT, wobei fT(n) := 1, falls n aus T, und 0, falls n nicht aus T. Dass p eine Bijektion ist, kannst Du leicht selbst nachrechnen. ;-) Ist sonst alles klargeworden? Gruss, E. |
epsilon
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 14. Mai, 2002 - 20:12: |
|
Ja geht auch: f entspricht dem Element aus P(N), bei dem gilt P(N) = {n Element N mit f(n) = 1} Noch eine weitere Möglichkeit: mit der Definition g(f) = Summe (n von 1 bis unendl.) f(n)/2^n interpretiert man f als eine Binärdarstellung einer reellen Zahl zwischen 0 und 1. Es wird jede reelle Zahl aus [0;1] erreicht (manche sogar doppelt), also ist M mindestens so mächtig wie [0;1] Ebenso konstruiert man h(f) = f(n)/3^n, das nicht alle Zahlen in [0;1] erreicht. Also ist M höchstens so mächtig wie [0;1] Zusammen: M ist mit [0;1] gleich mächtig, also überabzählbar! Gruß epsilon |
|