Abzählbarkeit von Mengen



  • Hallo Forum,

    folgende Aufgabe und deren Lösung will mir leider nicht einleuchten:

    E(M) bezeichne die Menge aller endlichen Teilmengen von M und P(M) die Menge aller Teilmengen von M. Zeige nun für die natürlichen Zahlen

    a) E(N) ist abzählbar,
    b) P(N) ist nicht abzählbar.

    Den Lösungsweg zu b) verstehe ich, den zu a) allerdings nicht. Er lautet wie folgt:

    Bezeichne Nn = {1,2,3,...n} und bemerke P(Nn) ist abzählbar da |P(N)| = 2^n ist.
    Offenbar gilt : E(N) = U P(Nn).
    n€N

    [Hier steht orginal P(N), aber ich denke stark er meint ] E(N) ist also eine abzählbare Vereinigung endlicher Mengen und ist als solche selbst abzählbar.

    Verstehe ich irgendwie nich mehr 😕

    Das fühlt sich für mich alles so dahergezogen aus, wenn er das gleiche als Definition für P(N) hinschreiben würde wüsste ich nicht, wie ich ihm da widersprechen könnte.

    Versteht ihr, was ich meine? :p

    Mfg
    Newbie



  • Das n€N da sollte eigentlich unter das Vereinigungs-Symbol U, sorry!



  • Der beweis passt schon. Er schaut sich zuerst an, was P(Nn) ist, was die Potenzmenge einer endlichen Menge ist. Da merkt er, dass sie abzählbar ist, weil ebenfalls endlich.

    Und das gilt eben für alle P(Nn), also bildet er die Vereinigung - und die Vereinigung abzählbarer Mengen ist abzählbar.

    Der Unterschied zu P(N) ist, dass du dort auch unendlich große Teilmengen drin hast (alle geraden Zahlen, alle Ungeraden zahlen...) und solche Mengen kriegst du mit der Konstruktion nicht hin.



  • Hmmm okay, ich denke ich schluck das jetzt einfach mal so, finde ich zwar nicht so ganz nachvollziehbar aber das liegt am mir und nichts anderem :p

    Danke auf jeden Fall für deine Antwort 🙂

    Mfg



  • otze schrieb:

    - und die Vereinigung abzählbarer Mengen ist abzählbar.

    die *abzählbare* Vereinigung ...



  • otze schrieb:

    Der Unterschied zu P(N) ist, dass du dort auch unendlich große Teilmengen drin hast (alle geraden Zahlen, alle Ungeraden zahlen...) und solche Mengen kriegst du mit der Konstruktion nicht hin.

    Den Grund verstehe ich nicht. Die Vereinigung von abzählbar vielen Mengen A_i ist abzählbar, wenn alle A_i selbst abzählbar sind (beweisbar mit Diagonalverfahren). Das irgendwelche A_i unendlich groß sind, stört dabei nicht.

    Zu P(N): P(N) sieht so aus wie die Menge wie Dualzahlen.
    Schreiben wir zuerst Dualzahlen als

    b = 0 , b0 b1 b2 ... (sprich: Null Komma b0 b1 b2 ...)

    wobei b_i entweder 1 oder 0 sei.
    Jede Menge B € P(N) entspricht genau einer Dualzahl, wobei b_i = 1 ist, falls i€B und sonst b_i = 0.

    Jetzt muss man nur noch herausfinden, wie das mit den Dualzahlen geht 🙂 Wenn man möchte,



  • Mups schrieb:

    otze schrieb:

    Der Unterschied zu P(N) ist, dass du dort auch unendlich große Teilmengen drin hast (alle geraden Zahlen, alle Ungeraden zahlen...) und solche Mengen kriegst du mit der Konstruktion nicht hin.

    Den Grund verstehe ich nicht. Die Vereinigung von abzählbar vielen Mengen A_i ist abzählbar, wenn alle A_i selbst abzählbar sind (beweisbar mit Diagonalverfahren). Das irgendwelche A_i unendlich groß sind, stört dabei nicht.

    Zu P(N): P(N) sieht so aus wie die Menge wie Dualzahlen.
    Schreiben wir zuerst Dualzahlen als

    b = 0 , b0 b1 b2 ... (sprich: Null Komma b0 b1 b2 ...)

    wobei b_i entweder 1 oder 0 sei.
    Jede Menge B € P(N) entspricht genau einer Dualzahl, wobei b_i = 1 ist, falls i€B und sonst b_i = 0.

    Jetzt muss man nur noch herausfinden, wie das mit den Dualzahlen geht 🙂 Wenn man möchte,

    AnalysisRookie Ich weiß nicht ganz genau, was du damit jetzt sagen willst? :p Sorry!



  • Mups schrieb:

    otze schrieb:

    Der Unterschied zu P(N) ist, dass du dort auch unendlich große Teilmengen drin hast (alle geraden Zahlen, alle Ungeraden zahlen...) und solche Mengen kriegst du mit der Konstruktion nicht hin.

    Den Grund verstehe ich nicht. Die Vereinigung von abzählbar vielen Mengen A_i ist abzählbar, wenn alle A_i selbst abzählbar sind (beweisbar mit Diagonalverfahren). Das irgendwelche A_i unendlich groß sind, stört dabei nicht.

    Die Endlichkeit der Teilmengen liefert hier die Abzählbarkeit der Indexmenge. Das ist bei P(N) nicht gegeben, deshalb funktioniert das Verfahren dort nicht. Das sagt an sich noch nichts über die (Über-)abzählbarkeit von P(N) aus, das kann man dann so machen, wie du angedeutet hast.



  • Bashar schrieb:

    Mups schrieb:

    otze schrieb:

    Der Unterschied zu P(N) ist, dass du dort auch unendlich große Teilmengen drin hast (alle geraden Zahlen, alle Ungeraden zahlen...) und solche Mengen kriegst du mit der Konstruktion nicht hin.

    Den Grund verstehe ich nicht. Die Vereinigung von abzählbar vielen Mengen A_i ist abzählbar, wenn alle A_i selbst abzählbar sind (beweisbar mit Diagonalverfahren). Das irgendwelche A_i unendlich groß sind, stört dabei nicht.

    Die Endlichkeit der Teilmengen liefert hier die Abzählbarkeit der Indexmenge. Das ist bei P(N) nicht gegeben, deshalb funktioniert das Verfahren dort nicht. Das sagt an sich noch nichts über die (Über-)abzählbarkeit von P(N) aus, das kann man dann so machen, wie du angedeutet hast.

    Für P(N) führt er das so weit ich in Erinnerung habe auf ein Widerspruch unter der Verwendung der Menge A = { x€N | x nichtElement f(x) }, diese ist selber Element von P(N) und dann benutzt er die biijektivität der Funktion f: N -> P(N) um sagen zu können, dass es ein m geben muss, sodass f(m) = A ist.

    Dann führt er das auf ein Widerspruch zurück in den zwei fällen, dass entweder
    a) m nichtElement A ist, damit müsste es aber laut Definition von A in A liegen und das ist ein Widerspruch, oder
    b) m liegt in A, damit dürfte es aber nicht in f(m) liegen und ist somit wider ein Widerspruch.


Anmelden zum Antworten