Potenzmenge der Primzahlen == Nat?

[Alexander]

hi,

es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen. wenn mich
nicht täusche gibt es einen satz, der besagt, dass die Potenzmenge
einer unendlichen menge stehts mächtiger ist, als die menge selbst.
das würde jedoch bedeuten, dass die menge der Primzahlen zwar
unendlich aber weniger mächtig ist als die menge der natürlichen
zahlen. d.h. hat eine geringere kardinalszahl (?) als N.

[Pether Hubert]

Post by Alexander
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.

Wieso ist das offensichtlich? Das sehe ich nicht so. Die Menge der
Primzahlen ist gleichmächtig zur Menge der natürlichen Zahlen, und
somit sind auch die Potenzmengen gleichmächtig. Wenn das, was Du
behauptest, so offensichtlich ist, mußt Du doch in der Lage sein, eine
Bijektion anzugeben. Die würde ich gerne mal sehen.

Ciao,

Pether

[David Kastrup]

Post by Pether Hubert

Post by Alexander
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.

Wieso ist das offensichtlich? Das sehe ich nicht so. Die Menge der
Primzahlen ist gleichmächtig zur Menge der natürlichen Zahlen, und
somit sind auch die Potenzmengen gleichmächtig. Wenn das, was Du
behauptest, so offensichtlich ist, mußt Du doch in der Lage sein, eine
Bijektion anzugeben. Die würde ich gerne mal sehen.

Eine Bijektion der Potenzmenge der Primzahlen zur Menge der
quadratfreien natürlichen Zahlen ist einfach: jede quadratfreie
natürliche Zahl ist durch die Menge ihrer Primfaktoren eineindeutig
bestimmt.

[Markus Keppeler]

Post by David Kastrup
Eine Bijektion der Potenzmenge der Primzahlen zur Menge der
quadratfreien natürlichen Zahlen ist einfach: jede quadratfreie
natürliche Zahl ist durch die Menge ihrer Primfaktoren eineindeutig
bestimmt.

Auch wenn ich net weiss, was eine quadratfreie natürliche Zahl ist:
Was machst du mit den unendlichen Mengen in der Potenzmenge der
Primzahlen? Welche natürliche Zahl willst du denen zuordnen?

[David Kastrup]

Post by Pether Hubert

Post by Alexander
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.

Wieso ist das offensichtlich? Das sehe ich nicht so. Die Menge der
Primzahlen ist gleichmächtig zur Menge der natürlichen Zahlen, und
somit sind auch die Potenzmengen gleichmächtig. Wenn das, was Du
behauptest, so offensichtlich ist, mußt Du doch in der Lage sein, eine
Bijektion anzugeben. Die würde ich gerne mal sehen.

/Eine Bijektion der Potenzmenge der Primzahlen zur Menge der
/quadratfreien natürlichen Zahlen ist einfach: jede quadratfreie
/natürliche Zahl ist durch die Menge ihrer Primfaktoren eineindeutig
/bestimmt.

Äh, Kommando zurück. Das sind natürlich nur die Elemente endlicher
Mächtigkeit aus der Potenzmenge der Primzahlen, die zu den
quadratfreien Zahlen korrelieren.

[Markus Pfeiffer]

Post by Alexander
hi,
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.

Ist das so? Ich würde eher sagen, dass | |N | = | |P |.

Markus

[Markus Keppeler]

Post by Alexander
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.

Ist es? Wieso? Ich find eher offensichtlich, das die Menge der
Primzahlen gleichmächtig zu |N ist, und dann ist nach dem von dir
genannten Satz die Potenzmenge mächtiger als |N.

cu,
Markus

[Jan Fricke]

Post by Alexander
hi,
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen. wenn mich

Hm, kann das sein, daß Du Dir nur die endlichen Teilmengen (anstatt
/aller/ Teilmengen) ansiehst? Diese ist offensichtlich gleichmächtig zur
Menge der natürlichen Zahlen.

Viele Grüße Jan

[Thomas Heye]

Hallo Jan,
sei P die Menge aller Primzahlen. Hab ich das richtig verstanden: Die Menge
aller endlichen Teilmengen von P ist gleichmächtig zur Menge der natürlichen
Zahlen? Dann müßte es eine bijektive Abbildung zwischen ihnen geben. Aber es
gibt doch sicher mehr als eine k-elementige Teilmenge von Primzahlen
(k>1)...

Gruß
Thomas

Post by Jan Fricke

Post by Alexander
hi,
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen. wenn mich

Hm, kann das sein, daß Du Dir nur die endlichen Teilmengen (anstatt
/aller/ Teilmengen) ansiehst? Diese ist offensichtlich gleichmächtig zur
Menge der natürlichen Zahlen.
Viele Grüße Jan

[Jan Fricke]

Post by Thomas Heye
Hallo Jan,
sei P die Menge aller Primzahlen. Hab ich das richtig verstanden: Die Menge
aller endlichen Teilmengen von P ist gleichmächtig zur Menge der natürlichen
Zahlen? Dann müßte es eine bijektive Abbildung zwischen ihnen geben. Aber es
gibt doch sicher mehr als eine k-elementige Teilmenge von Primzahlen
(k>1)...

Das hast Du richtig verstanden. Kurz gesagt:
- Die Menge aller Primzahlen ist abzählbar.
- Die Menge der Worte über einem abzählbaren Alphabet ist abzählbar.
- Die Menge aller endlichen Teilmengen ist höchstens so mächtig wie die
Menge der Worte.
==> Die Menge der endlichen Teilmengen einer abzählbaren Menge ist
höchstens abzählbar. (Daß sie nicht endlich ist, ist aber auch klar.)

Im konkreten Beispiel läßt sich die Bijektion (fast) direkt angeben:
Jeder endlichen Teilmenge von Primzahlen ordne ich ihr Produkt zu. Das
wird eine injektive Abbildung von der Menge der endlichen Teilmengen in
die Menge der natürlichen Zahlen.
{} |--> 1,
{2} |--> 2,
{3} |--> 3,
{5} |--> 5,
{2,3} |--> 6,
{7} |--> 7,
{2,5} |--> 10,
usw.
Jetzt werden die Zahlen auf der rechten Seite durchnummeriert, z.B.
a_1 = 1,
a_2 = 2,
a_3 = 3,
a_4 = 5,
a_5 = 6,
a_6 = 7,
a_7 = 10,
usw. (Sloane's A005117:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005117
)
Nun setzt man aus diesen beiden Abbildungen eine Bijektion zusammen.

Zu Deinem Einwand mit den k-elementigen Teilmengen: Die Anzahl der
k-elementigen Teilmengen einer abzählbaren Menge ist wieder abzählbar.
Nun ist aber die Menge aller endlichen Teilmengen aber gerade die
Vereinigung dieser (abzählbar vielen) Mengen von k-elementigen
Teilmengen. Aber: Die Vereinigung abzählbar vieler abzählbarer Mengen
ist wieder abzählbar.

Schau Dir mal irgendwo "Hilberts Hotel" an. (Ich fand es in Wilenkin:
"Unterhaltsame Mengenlehre" sehr gut und ausführlich erklärt.)

Viele Grüße Jan

[Torsten Metzner]

Post by Thomas Heye
sei P die Menge aller Primzahlen. Hab ich das richtig verstanden: Die Menge
aller endlichen Teilmengen von P ist gleichmächtig zur Menge der natürlichen
Zahlen? Dann müßte es eine bijektive Abbildung zwischen ihnen geben. Aber es
gibt doch sicher mehr als eine k-elementige Teilmenge von Primzahlen
(k>1)...

Hi Thomas,
den Schluß den Du hier machen willst klappt nicht. Es gibt
doch auch mehr als einen (gekürzten) Bruch mit k im Zähler
oder Nenner, aber die natürlichen und die rationalen sind trotzdem
gleichmächtig.

Gruß,
Torsten

[Marc Olschok]

Post by Alexander
hi,
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen.[...]

Das stimmt nicht. Kann es sein, dass Du in der Eile
"Potenzmenge" mit "Menge der Potenzprodukte" verwechselt hast?

Marc

[Thomas Heye]

Hallo Alexander,
"offensichtlich"? Wie könnte denn die bijektive Abbildung zwischen der
Potenzmenge der Primzahlen und den nat. Zahlen aussehen?

Gruß

Thomas

Post by Alexander
hi,
es ist offensichtlich, dass die Potenzmenge der Menge der Primzahlen
gleich mächtig ist mit der Menge der natürlichen Zahlen. wenn mich
nicht täusche gibt es einen satz, der besagt, dass die Potenzmenge
einer unendlichen menge stehts mächtiger ist, als die menge selbst.
das würde jedoch bedeuten, dass die menge der Primzahlen zwar
unendlich aber weniger mächtig ist als die menge der natürlichen
zahlen. d.h. hat eine geringere kardinalszahl (?) als N.

[Alexander]

ok,
habs uebersehen. dann also ist die potenzmenge der primzahlen mächtiger als N?

[Thomas Nordhaus]

Post by Alexander
ok,
habs uebersehen. dann also ist die potenzmenge der primzahlen mächtiger als N?

Du kannst ja die Primzahlen durchnummerieren: p1=2, p2=3,p3=5 usw.

[Alexander]

Post by Thomas Nordhaus
Du kannst ja die Primzahlen durchnummerieren: p1=2, p2=3,p3=5 usw.

ich war ja davon ausgegangen, dass die Menge der Primzahlen < Menge
der Natürlichen Zahlen. Da sie beide unendlich groß sind, kann man so
nicht argumentieren, oder? Sonst könnte ich eine vergleichbare
Abbildung der nat. Zahlen auf die reellen finden: 1= pi/1 , 2= pi/2
... und behaupten dass die mengen gleich mächtig sind.. ok, der
vergleich hinkt.. aber es wäre doch theoretisch eine unendliche menge
vorstellbar, die unterabzählbar ist.( < N ) Da sie unendlich groß
wäre, könnte man wahrscheinlich auch eine Abbildung finden: p1=a1,
p2=a2... Gibt es einen beweis, dass eine solche menge nicht
existiert?

[Thomas Nordhaus]

Post by Alexander

Post by Thomas Nordhaus
Du kannst ja die Primzahlen durchnummerieren: p1=2, p2=3,p3=5 usw.

(da bin wohl ich gemeint)

Post by Alexander
ich war ja davon ausgegangen, dass die Menge der Primzahlen < Menge
der Natürlichen Zahlen. Da sie beide unendlich groß sind, kann man so
nicht argumentieren, oder?

Sorry, da hatte ich verfrühter Weise die Sendetaste gedrückt. (War
eigentlich der Meinung, dass ich den Beitrag erfolgreich gecancelt
hätte...)

Thomas

[Horst Kraemer]

Post by Alexander

Post by Thomas Nordhaus
Du kannst ja die Primzahlen durchnummerieren: p1=2, p2=3,p3=5 usw.

ich war ja davon ausgegangen, dass die Menge der Primzahlen < Menge
der Natürlichen Zahlen. Da sie beide unendlich groß sind, kann man so
nicht argumentieren, oder? Sonst könnte ich eine vergleichbare
Abbildung der nat. Zahlen auf die reellen finden: 1= pi/1 , 2= pi/2
... und behaupten dass die mengen gleich mächtig sind.. ok, der
vergleich hinkt.. aber es wäre doch theoretisch eine unendliche menge
vorstellbar, die unterabzählbar ist.( < N ) Da sie unendlich groß
wäre, könnte man wahrscheinlich auch eine Abbildung finden: p1=a1,
p2=a2... Gibt es einen beweis, dass eine solche menge nicht
existiert?

Ja. Man kann zeigen, dass jede unendliche Menge M eine Teilmenge U der
Maechtigkeit von N besitzt. Da fuer eine Teilmenge U von M immer gilt
||U||<=||M||, kann es keine Menge M mit ||M|| < ||N|| geben.

Beweisskizze: Sei M unendlich. Zuerst zeigt man mittels des
Auswahlaxioms und vollstaendiger Induktion, dass es eine unendliche
Folge von Teilmengen von M gibt, so dass U_i genau i Elemente
enthaelt. Jetzt betrachtet man die Teilfolge (V_k) von (U_i) mit V_k =
U_2^k. Das Folgenelement V_k ist also jeweils eine Teilmenge von M mit
2^k Elementen. Wenn V_k 2^k Elemente, dann erhalten alle Vorgaenger
von V_k insgesamt hoechstens 2^0 + 2^1 + ... + 2^(k-1) = 2^k-1
Elemente. Damit ist fuer jedes k aus N die Menge

Z_k := V_k \ (Vereinigung aller Vorgaenger von V_k)

nichtleer und alle Z_k sind paarweise disjunkt. Zusammengefasst haben
wir eine unendliche Folge Z_k von paarweise disjunkten und nichtleeren
Teilmengen von M konstruiert. Jetzt nehmen wir eine nach dem
Auswahlaxiom existierende Funktion f daher mit der Eigenschaft f(Z_k)
\in Z_k. Damit ist die Abbildung

g: n -> f(Z_n)

eine injektive Abbildung von N in eine Teilmenge von M. Damit gilt
||M||<||M||.