 |
 |
 |
 |
 |
 |
Startseite » Forum » Die Menge aller endlichen Teilmengen von N
Die Menge aller endlichen Teilmengen von N
Universität / Fachhochschule
Sonstiges
Funktionentheorie
Tags: abzählbar, Beweis, Teilmengen, unendlich
 
|
  |
|---|
|
Aufgabe: Beweisen Sie, dass die Menge aller endlichen Teilmengen von abzählbar unendlich ist. Also (die Menge aller Teilmengen von ist überabzählbar, da die Funktion definiert durch nicht bijetiv ist, so stehts im Skript. Wie das ganze nun mit der Menge von ENDLICHEN Teilmengen aussieht, darauf komm ich nicht... Die Funktion müsste ja dann bijektiv sein, also dann dürfte ja auf jedes Element nur ein Element von also nur eine Teilmenge abgebildet werden? Vielen Dank schonmal im Voraus! Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.) |
| Hierzu passend bei OnlineMathe: |
|
 |
|
Versuche eine Folge von endl. Teilmengen von zu konstruieren, so dass alle endl. Teilmengen von in der Folge vorkommen. Dann ist eine bijektion von auf die endlichen Teilmengen von Wenn du nicht drauf kommst, frag einfach nochmal nach, dann geben wir dir einen Tipp wie es genau gehen könnte; versuche es jedoch zuerst selbst. |
|
|
|
Das mit steht im Skript falsch oder du hast es falsch gelesen. "M ist überabzählbar" heisst, dass keine Abbildung surjektiv ist. Dass eine bestimmte Abbildung nicht surjektiv ist (selbst wenn sie injektiv ist), reicht nicht aus. Sieh dir den Beweis von in deinem Skript nochmal genauer an. Für die Bijektion endlich schreibe doch mal eine beliebige natürlcihe Zahl im Zweiersystem. Kannst du dir denken, wie man aus den endlich vielen Ziffern 0 und 1 dieser Darstellung ein finden kann? (Du musst ja für jedes entscheiden, ob oder |
 |
|
Entschuldige, ist das nun Absicht, dass du 2 Indizes hast, also ? Wenn ja, wie darf ich das verstehen? |
|
|
|
Zu Schreibweise: ist das n-te Folgenglied ist einfach diese Folgenglied in Klammern bezeichnet die ganze Folge, also alle wenn alle Element in durchläuft. findet man auch manchmal. Hast du die Diskrepanz in deinem Skript aufklären können? |
|
|
|
Die Potenzmenge . . von (die Menge aller Teilmengen von ist nicht abzählbar. Sie ist unendlich, da die durch die Formel definierte Funktion → injektiv ist. Dass sie nicht abzählbar unendlich ist, folgt aus dem folgenden Lemma. etc. Hab das wohl falsch verstanden. Ok, danke für die Erklärung der Notation. Mein großes Problem ist es, das, was wir in den Vorlesungen erklärt bekommen, anzuwenden. Seh ich die Lösung für ein Problem, kann ich das nachvollziehn, aber auf die Idee zu kommen, fällt mir schwer. Ich hoffe, dass das daran liegt, dass ich noch nicht mit der Arbeitsweise zurecht komm bzw dass mir die Übung fehlt, bin Erstsemester. Und es tut mir auch leid, dass ich so plump fragen muss, aber ich komm nicht drauf. Wie ist denn der Tipp? |
|
|
|
Genau. Wie du beim Nachlesen bemerkt haben dürftest, dient die injektive Abbildung lediglich dazu, zu zeigen, dass mindestens so groß ist wie also unendlich. Insofern könnte aber noch abzählbar unendlich sein, wenn es eine andere Abbildung gäbe, die surjektiv wäre. Das Argument, dass dies tatsächlich nicht der Fall ist, dass also nicht nur unendlich, sondern überabzählbar unendlich ist, steht erst in dem Lemma. OK, zurück zum eigentlichen Problem: Schreibe im Zweiersystem: . Wir sind ja noirmalerweise sparsam und lassen die führenden MNullen weg, heute wollen wir aber nicht so knauserig sein: . Jetzt definiere zu die Menge anhand der Zifferndarstellung wie folgt: Wenn ganz rechts eine 1 steht, soll gelten; wenn bei der nächsten Stelle eine 1 steht, soll gelten; wenn danach eine kommt, usw. Insgesamt die (k+1)-te Stelle von rechts in der Darstellung von ist eine ist injektiv, weil verschiedene Zahlen verschiedene Ziffernfolgen haben. ist surjektiv, weil man eine gegebene endliche Menge umgekehrt leicht in eine endliche Ziffernfolge und damit eine Zahl umwandeln kann. |
|
|
|
Es gibt auch eine andere Möglichkeit wie man darauf kommen könnte (führt aber auf das gleiche): Wir wollen alle endlichen Mengen in abzählen. Die Idee ist, dass wir die endl. Mengen durch ihr grösstes Element klassifizieren, um sie später abzuzählen. Wir identifizieren nun also alle Mengen die als grösstes Element haben mit der Zahl ; oder - ein wenig mathematischer ausgedrückt, wir definieren die Menge: Wir haben also ein paar Beispiele: : : : Wenn wir nun noch die leere Menge betrachten: dann sehen wir, dass dadurch entsteht, dass wir und nehmen und die Mengen darin jeweils mit der erweitern: Also hat ein Element, 2 Elemente und hat Elemente. Da alle endlichen Mengen abzhählbar sind und die Menge aller auch abzählbar ist, ist die Vereinigung aller auch abzählbar; und dies sind genau alle endlichen Ungermengen von . Natürlich ist das oben noch kein richtiger Beweis; ich habe eher meinen Gedankengang niedergeschrieben als ich über die Aufgabe nachdachte. Die Grundidee ist, dass du erkennst wie man endliche Mengen induktiv klassifiziert: Durch ihr grösstes Element. Müsstest du die endl. Mengen von klassifizieren, würdest du den grössten Betrag eines Elements der Mengen nehmen und du würdest auf ein ähnliches Resultat kommen. Wenn du magst, kannst du für den Beweis auch ein Lemma beweisen, dass die Vereinigung endlicher Mengen abzählbar ist. Wenn du das hast, kannst du mit dem obigen Argument mehr oder weniger direkt Beweisen, dass die endl. Mengen von abzählbar sind. |
 |
|
Ok, vielen Dank für eure Hilfe, beide Lösungen waren gut :-) |
677005
676056