Sind unendliche Mengen gleich mächtig?

[weiss_nics]

Ich habe jetzt kapiert, dass endlich Mengen gleich mächtig sein können oder eben auch nicht.

Aber was ist mit unendlich großen Mengen (also z.B. die Menge der natürlichen Zahlen, die Menge der ganzen Zahlen etc.)? Sind die alle gleich mächtig?

Ist dann auch die Menge der natürlichen Zahlen genauso mächtig wie die Menge aller ungeraden natürlichen Zahlen? Und auch genauso mächtig wie die Menge aller reelen Zahlen? In meinem Matheduden stehen sie alle als unendliche Mengen drin.

Oder ist das vielleicht eine Verabredung, dass man sagt, alle unendlichen Mengen seien gleich mächtig? Kann mir jemand sagen, wie man sich das vorstellen kann?

Vielen Dank!

[Micro]

Hi,

man unterscheidet zwischen abzählbar (unendlich) und überabzählbar (unendlich). Abzählbar sind zum Beispiel die natürlichen Zahlen und die gebrochenrationalen Zahlen. Überabzählbar sind zum Beispiel die rellen Zahlen. Ganz allgemein sind zwei Mengen A und B gleichmächtig, wenn es zwischen diesen eine bijektive Abbildung gibt. So kannst Du zum Beispiel jeder natürlichen Zahl eindeutig einen Bruch zuordnen. Oder anders, eine Menge ist abzählbar, wenn Du jedem Element eine Nummer geben kannst.
Die Menge der rationalen Zahlen ist dagegen nicht „durchnummerierbar“. Genauso wie die Menge der stetigen Funktionen auf dem Intervall. (Man nehme die konstanten Funktionen f(x) = c für alle c aus R. Diese Menge ist ja schon überabzählbar. Alle Funktionen sind dann natürlich noch viel mehr.)

Noch ein interessantes Beispiel zum Abschluss: Du nimmst die Menge der Punkte einer Geraden mit Länge 1. Dann teilst Du diese Strecke in 3 gleichlange Teile ein und entfernst das mittlere Stück. Dann bleiben also 2/3 der Strecke über. Das ganze machst du mit jedem Teilstück, wieder und wieder, bis Du ganz viele kleine „Strecken“ hast, die im unedlichen „Punkte“ werden. Das überraschende: Die Strecke am Anfang hat genausviele Punkte wie der „Staub“ am Ende. Sog. Cantormenge (Cantorstaub).

Fazit also: Unendlich ist nicht gleich unendlich.

Micro

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

[Enno_Sandner_66c4aa]

Hallo,
nein. Du kannst zu jeder Menge A (auch einer unendlichen) eine mächtigere finden (d.h. es gibt eine Injektion von A in Menge aber keine Bijektion zwischen A und der Menge), durch Potenzmengenbildung:

card(A)
Nr Zahl
0 0000000…
1 4987542…
2 3343343…
3 1111111…
4 4095829…
. .

darstellen (die Zahlen sind willkürlich gewählt). Es gäbe also eine erste reelle Zahl (aus [0,1)), eine zweite etc. Wenn wir nun die Zahl auf der Hauptdiagonalen dieser Tabelle betrachten (von oben-links in Richtung rechts unten), im Bsp. 09418… und jede Ziffer ändern (z.B. durch (x+1) mod 10) erhalten wir eine Zahl, die zu allen Zahlen in dieser Tabelle mind. an einer Stelle verschieden ist. Sie ist also nicht in der Abzählung enthalten und [0,1) damit nicht abzählbar.

Gruss
Enno

[Gandalf]

Hallo Enno,

was mich verwundert hat ist, daß die reelen Zahlen und die Komplexen Zahlen gleichmächtig sind.

Irgendwie will es mir nicht in den Kopf, daß eine „Fläche“ nicht mehr „Punkte“ hat als eine „Gerade“

Gandalf

[Enno_Sandner_66c4aa]

Hallo,
die analoge Situation ist doch bei den rationalen Zahlen und den natürlichen Zahlen oder noch direkter bei N x N und N. Letzteres sieht man leicht ein, wenn man

 0 1 2 3
0 (0,0) (0,1) (0,2) (0,3) ...
1 (1,0) (1,1) (1,2) (1,3) ...
2 (2,0) (2,1) (2,2) (2,3) ...
3 (3,0) (3,1) (3,2) (3,3) ...
. . . . .

z.B. in der Reihenfolge

(0,0) (x+y=0)
(1,0),(0,1) (x+y=1)
(2,0),(1,1),(0,2) (x+y=2)
(3,0),(2,1),(1,2),(0,3) (x+y=3)
 . . . .

traversiert. Trickreicher und direkt übertragbar auf das reelle Intervall [0,1) ist es, den Übergang vom 2-Tupel zur natürlichen Zahl durch „shufflen“ zur erreichen. Die Idee dabei ist, die geraden Stellen der Zahl aus dem Zähler, die ungeraden aus dem Nenner zu beziehen (immer abwechselnd). Bsp 1234/5678 wird zu 15263748 übersetzt. Analog kann man bei einer reellen Zahl aus [0,1) durch Betrachtung der geraden Stellen als „x-Wert“ und ungeraden Stellen als „y-Wert“ die Gleichmächtigkeit der Fläche und Gerade gut ersehen. Die Gerade enthält sozusagen genügend Information, um die Fläche darzustellen.

Gruss
Enno

[Mars_6e42af]

Hallo,

Die Menge der rationalen Zahlen ist dagegen nicht
„durchnummerierbar“.

Das ist sie durchaus. Mit Hilfe eines Diagonalverfahrens (die Diagonale(n) in die andere Richung als im Cantorbeweis der Überabzählbarkeit der reellen Zahlen) kann die Abzählbarkeit der Menge der rationalen Zahlen gezeigt werden. Es gilt dann sogar, dass jedes endliche Kreuzprodukt NxNx…xN abzählbar ist.

Gruß,
Martin

[Enno_Sandner_66c4aa]

Hallo,
in der Tat ist sogar N^N abzählbar.

Gruss
Enno

[Mars_6e42af]

Hallo Enno,

in der Tat ist sogar N^N abzählbar.

ist nicht schon {0,1}^N überabzählbar?

Dabei:
N = Menge der natürl. Zahlen,
{0,1}^N = Menge der Folgen mit Werten 0 oder 1
(N^N wäre mit dieser Schreibweise die Menge der Folgen mit Werten in N).

Wenn {0,1}^N abzählbar wäre, gäbe es eine surjektive Abbildung f: N -> {0,1}^N. Wähle dann

a_n := 1-f(n)_n in {0,1}, damit wäre (a_n) ein Element aus {0,1}^N.

f surjektiv liefert die Existenz eines m mit f(m) = (a_n) (jede Folge mit Werten in {0,1} hat ein Urbild in N).

Damit wäre aber f(m)_m = a_m = 1 - f(m)_m, also
f(m)_m = 1/2, was nicht möglich ist.

Grüße,
Martin

[Enno_Sandner_66c4aa]

Hallo,

Die Idee dabei ist, die geraden Stellen der Zahl aus dem Zähler, die
ungeraden aus dem Nenner zu beziehen (immer abwechselnd).

sollte natürlich erste und zweite Stelle des Tupels (statt Zähler und Nenner) heißen. Für Q gilt es noch die dort vorhandene Äquivalenz (z.B. 1/2=2/4=6/12=…) zu verwursten.

Gruss
Enno

[Enno_Sandner_66c4aa]

Hallo,
Du hast völlig Recht. Was mir im Hinterkopf rumschwebte, war card(N)^card(N). Eine Menge mit Mächtigkeit läßt sich z.B. durch die Vereinigung aller N^k für natürliche k basteln. Für {0,1}^N ist Cantors Diagonalisierungsbeweis direkt anwendbar.

Gruss
Enno

[Mars_6e42af]

Ist dann auch die Menge der natürlichen Zahlen genauso mächtig
wie die Menge aller ungeraden natürlichen Zahlen? Und auch
genauso mächtig wie die Menge aller reelen Zahlen? In meinem
Matheduden stehen sie alle als unendliche Mengen drin.

Ein etwas anderer als der klassische von Enno aufgeschriebene Beweis, dass die reellen Zahlen „mehr“ sind als die naürlichen, ginge etwa so:

Annahme: Es gibt eine Abbildung f: N -> (0,1), surjektiv
(Wenn (0,1) abzählbar wäre, müsste es so etwas geben).

Wähle a_1, b_1 in (0,1) mit a_1 = m.

Monotonie und Beschränktheit der Folgen liefern Grenzwerte a und b:
a_n -> a, b_n -> b, die für alle m die Ungleichung
a_m

[Micro]

Hallo,

Die Menge der rationalen Zahlen ist dagegen nicht
„durchnummerierbar“.

Das ist sie durchaus.

Pardon, da hab ich das „ir“ vergessen… War schon spät

Micro

[Enno_Sandner_66c4aa]

Hallo,
gefällt mir. Kann man auch sehr gut als „Spiel“ auffassen im Western-Style - „f schießt“, [a_n,b_n] weicht aus *g*.

Gruss
Enno