Menge der Partitionen aller natürlichen Zahlen - Abzählbarkeit

Neue Frage »

poljpocket Auf diesen Beitrag antworten »
Menge der Partitionen aller natürlichen Zahlen - Abzählbarkeit
Hallo alle,

folgendes Problem (es geht um Mengenlehre):

Wie viele Partitionen der Menge der natürlichen Zahlen N gibt es? Endlich, abzählbar unendlich oder überabzählbar viele? Beweise deine Antwort.

Ich habe mir dazu Folgendes überlegt, erstmal: Diese Menge (alle Partitionen von ) ist abzählbar unendlich, da ich sie wie folgt versucht habe, zu konstruieren:

Sei eine Partition von . Weiter sei ein Teil (abzählbar, wie man sieht) der gesamten gesuchten Menge P.

Weiter sei eine Partition von und damit ein weiterer Teil (wieder abzählbar) der gesamten gesuchten Menge P.

Nach diesem Schema kann man alle Partitionen der natürlichen Zahlen mit zwei Teilmengen erhalten. Die Vereinigung aller dieser Mengen ist wieder abzählbar (ist in meinem Skript bewiesen).

Dasselbe Schema wende man nun auf alle Partitionen mit 3 Teilmengen an, dann mit 4, ... und vereinige alle erhaltenen Resultate zu einer Menge, welche unsere gesuchte ist. Diese ist dann abzählbar unendlich.

Nun, bin ich mir aber nachdem ich das Ganze nocheinmal durchüberlegt habe ziemlich sicher, dass das so nicht stimmt, oder zumindest so kein plausibler Beweis ist und zwar aus folgendem Grund:

Oben definierte Mengen sind für mich schon überabzählbar, resp. ich finde keinen Beweis, dass diese abzählbar sein sollten.

Vielen Dank für jeden noch so kleinen Tipp in Hinsicht auf die Lösung dieser Aufgabe.

Gruss, Julian
ollie3 Auf diesen Beitrag antworten »
RE: Menge der Partitionen aller natürlichen Zahlen - Abzählbarkeit
hallo polipocket,
also erstmal, das ist eine superinteressante aufgabe, ich glaube, die ganze kiste
ist doch abzählbar, man kann nämlich folgenden trick anwenden: man könnte
jedem P_nk den wert 2^n mal 3^k zuordnen, und wegen der eindeutigkeit
der primzahlzerlegung ist das immer nur einmal möglich, damit wäre P_nk schonmal abzählbar, bei den dreiersachen P_nkl würde man das mit 2^n mal
3^k mal 5^l machen, und so weiter. Ich glaube damit ist die ganze aufgabe
schon erschlagen. smile
gruss ollie3
tmo Auf diesen Beitrag antworten »

Der Beweis der Abzählbarkeit wird leider zum Scheitern verurteilt sein.

sei die Menge aller Partitionen von und P die Potenzmenge von . Für die Überabzählbarkeit betrachtet man mal die Abbildung .

ist zwar nicht injektiv, aber induziert eine injektive Abbildung , wobei die durch gegebene Äquivalenzrelation ist.

Wegen würde die Abzählbarkeit von schon die Abzählbarkeit von P implizieren.


PS: Dein Beweis scheitert übrigens an mehreren Sachen:

1. Du kriegst damit keine Partitionen aus unendlich vielen Teilmengen

2. Du kriegst mit den 's (welche für sich gesehen abzählbar sind) nocht nicht mal alle Partitionen aus 2 Teilmengen. Du kriegst nur alle Partionen aus 2 Teilemengen, bei denen die eine Menge genau 2 Elemente enthält.
Dass man nach so einer starken Einschränkung Abzählbarkeit vorliegen hat, muss nicht mehr verwundern smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »