| Autor |
Beitrag |
    
Markus
| | Veröffentlicht am Montag, den 15. Oktober, 2001 - 21:25: | 
|
Hallo,
ich wende mich in meiner Verzweiflung an euch, da ich einfach nicht mehr weiter weiß!
folgendes Problem: Welche der folgenden Mengen sind abzählbar bzw. überabzählbar?
a.) 2^(E*) E definiert ein endliches nichtleeres Alphabet und E* bezeichnet die Menge aller Wörter über dem Alphabet E.
b.) A u B u C; A, B, C sind abzählbare Mengen
c.) A = {M| M Teilmenge der natürlichen Zahlen, |M| < unendlich}
bitte helft mir.
lg. Markus |
Armin Heise (Armin)
| | Veröffentlicht am Dienstag, den 16. Oktober, 2001 - 20:58: |
|
Hallo Markus
b) A und B und C ist abzählbar, denn die Vereinigung von abzählbar vielen abzählbaren Mengen ist abzählbar |
Markus
| | Veröffentlicht am Mittwoch, den 17. Oktober, 2001 - 08:52: |
|
Hallo nochmal
Danke Armin, dass ist mir mittlerweilen auch klar. Unklar ist mir eher a.) und c.), wobei ich bei c.) auch schon einen Ansatz habe.
zu c.)
die Menge der natürlichen Zahlen ist abzählbar unendlich (Beweis.: Cantor Diagonalmengenprinzip)
ein Teilmenge der natürlichen Zahlen ist somit mindestens abzählba unendlich, da aber |M| < unendlich, muss M endlich abzählbar sein.
Stimmt das soweit?
lg Markus |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 17. Oktober, 2001 - 09:19: |
|
Hallo Markus
Das Cantor'sche Diagonalverfahren kann man bei a) anwenden. Es besagt, dass ^2N und R überabzählbar sind, nun ist E* abzählbar unendlich, daher ist 2E* ünberabzählbar.
Dass die Menge der natürlichen Zahlen abzählbar ist, ist nicht Cantor, sondern die Definition der Abzählbarkeit. Die Elemente von A sind bei c auch nicht Zahlen, sondern Teilmengen der natürlichen Zahlen, es ist A={{},{1},{2},...,{1,2},{1,3},...,{2,3},{2,4},......}
A ist abzählbar, im Moment hab ich aber leider keine Zeit mehr.
viele Grüße
SpockGeiger |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 17. Oktober, 2001 - 14:40: |
|
Hallo Markus
Sorry wegen heute morgen, Busse warten leider nicht.
Zu a) ist noch Folgendes bekannt: Egal, welche Menge M man nimmt, 2M, also die Potenzmenge von M, hat immer größere Mächtigkeit als M. Hieraus folgt insbesondere, dass 2N überabzählbar ist, da ja es ja größere Mächtigkeit haben muss als N. Wenn Dich der Beweis interessiert, kann ich ihn mal rauskramen.
Zu c) müssen wir noch zeigen, dass A abzählbar ist. Dazu schreiben wir A=Un=0¥{B|B Teilmenge von N hat n Elemente}. In Worten: Wir zerlegen A in Klassen, wobei in jeder Klasse nur Mengen drin sind, die eine bestimmte Anzahl von Elementen haben. Da in A alle endliche Mengen liegen, ist A gerade diese Vereinigung. Was nutzt uns das? Eine abzählbare Vereinigung von abzählbaren Mengen ist wieder abzählbar. Unsere Vereinigung ist abzählbar, da wir von n=0 bis unendlich vereinigen. Nun müssen wir nur noch zeigen, dass jede dieser Mengen, die vereinigt werden, abzählbar ist. Das können wir mit Induktion machen.
n=0: Da gibt es nur die leere Menge, also eine, diese Anzahl ist abzählbar.
n-1->n: Nach Induktionsvoraussetzung gibt es abzählbar viele Mengen mit n-1 Elementen. Sei C1,C2,... eine Aufzählung. Um auf n Elemente zu kommen, haben wir bei jeder dieser Mengen nur abzählbar viele Möglichkeiten, eine Zahl dazuzunehmen, also ist wieder Un=1¥{D|D hat n Elemente und enthält Cn} eine abzählbare Vereinigung von abzählbaren Mengen, somit abzählbar. Man kann sich schnell überlegen, dass diese Vereinigung alle Mengen mit n Elementen enthält, somit ist der Beweis vollbracht.
viele Grüße
SpockGeiger |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 17. Oktober, 2001 - 14:45: |
|
Sorry, hab aus versehen die Variable n überladen. In der letzten Vereinigung muss es heißen: Uk=1¥{D|D hat n Elemente und enthält Ck}.
viele Grüße
SpockGeiger |
Markus
| | Veröffentlicht am Mittwoch, den 17. Oktober, 2001 - 19:18: |
|
hallo SpockGeiger
vielen Dank für Deine ausführlichen Erklärungen. Ich glaube ich hab jetzt verstanden wie das Problem zu lösen ist und Dank Dir werd ich vielleicht die Klausur auch bestehen.
lg
Markus |
|
