Satz von Cantor

[Pippen]

Ok, ich habs mal noch etwas umgangssprachlicher formuliert, wie klingt das:

1. Wir haben also eine Menge X mit x als deren Elemente.
2. Wir haben die Potenzmenge P(X) mit px als deren Elemente.
3. Wir haben die Menge F, bei der wir annehmen, dass sie folgende Elemente hat: jedes px zu mind. einem x zugeordnet, d.h. [x, px] (Surjektionsannahme).
4. Jetzt konstruieren wir eine Menge B, welche diejenigen x als Elemente hat, die in F sind (und damit mind. ein px als Partner haben, vgl. 3.), aber nicht in diesem px vorkommen. B ist Teilmenge von X - entweder weil sie leer ist oder weil irgendwelche x darin sind. Dadurch ist B auch Element von P(X).
5. B muss wegen der Surjektionsannahme in 3. auf jeden Fall nicht nur in F sein, sondern auch ein x als Partner haben, nennen wir dieses x zur besseren Unterscheidbarkeit x_B.

Ist 5. in Ordnung?

[Pippen]

Ok, weiter geht's.

Cantor's Theorem für Amateure:

1. Wir haben also eine Menge X mit x als deren Elemente.
2. Wir haben die Potenzmenge P(X) mit px als deren Elemente.
3. Wir haben die Menge F, bei der wir annehmen, dass sie folgende Elemente hat: jedes px zu mind. einem x zugeordnet, d.h. [x, px] (Surjektionsannahme).
4. Jetzt konstruieren wir eine Menge B, welche diejenigen x als Elemente hat, die in F sind (und damit mind. ein px als Partner haben, vgl. 3.), aber nicht in diesem px vorkommen. B ist Teilmenge von X - entweder weil sie leer ist oder weil irgendwelche x darin sind. Dadurch ist B auch Element von P(X).
5. B muss wegen der Surjektionsannahme in 3. auf jeden Fall nicht nur in F sein, sondern auch ein x als Partner haben, nennen wir dieses x zur besseren Unterscheidbarkeit x_B.

Ist 5. in Ordnung?

[breaker]

Ja.

[Pippen]

Ok, das Ende naht.

Cantor's Theorem für Mathe-Amateure:

1. Wir haben also eine Menge X mit x als deren Elemente.
2. Wir haben die Potenzmenge P(X) mit px als deren Elemente.
3. Wir haben die Menge F, bei der wir annehmen, dass sie folgende Elemente hat: jedes px zu mind. einem x zugeordnet, d.h. [x, px] (Surjektionsannahme).
4. Jetzt konstruieren wir eine Menge B, welche diejenigen x als Elemente hat, die in F sind (und damit mind. ein px als Partner haben, vgl. 3.), aber nicht in diesem px vorkommen. B ist Teilmenge von X - entweder weil sie leer ist oder weil irgendwelche x darin sind. Dadurch ist B auch Element von P(X).
5. B muss wegen der Surjektionsannahme in 3. auf jeden Fall nicht nur in F sein, sondern auch ein x als Partner haben, nennen wir dieses x zur besseren Unterscheidbarkeit x_B.
6. Wenn ein x_B in F der Menge B zugeordnet ist, dann muss gelten: entweder x_B € B oder x_B ~€ B.
a) Wenn x_B € B, dann gilt wegen der Definition von B, dass x_B nicht in B vorkommt, also x ~€ B. Das widerspricht der Annahme x € B und kann daher nicht der Fall sein.
b) Wenn x_B ~€ B, dann gilt wegen der Definition von B, dass x_B in B vorkommt, also x € B. Das widerspricht der Annahme x ~€ B und kann daher nicht der Fall sein.
7. Weil es nur die zwei Möglichkeiten von 6a) und 6b) gibt und beide zu Widersprüchen führen gilt bei 6. Kontraposition, d.h. x_B ist in F nicht B zugeordnet. Damit gibt es in F ein px, dem kein x zugeordnet werden kann, was der Surjektionsannahme aus 3. widerspricht, die damit falsch sein muss, d.h. wahr ist: Nicht jedem px ist in F ein x zugeordnet, d.h. X und P(X) sind nicht surjektiv.
8. Wir wissen, dass X und P(X) injektiv sind, d.h. jedem x kann ein px zugeordnet werden, weil jedes x ja in P(X) schlicht als {x} geschrieben werden kann. Wenn aber jedes x einem px, aber nicht jedes px einem x zugeordnet werden kann, dann gilt: P(X) ist mächtiger als X, weil man zwar mit px alle x abzählen könnte, aber nicht mit allen x alle px. q.e.d.

Was hälst du von der Formulierung der Punkte 6.-8.? So formuliert, verstehe ich jedenfalls den Beweis und finde ihn sogar überzeugend. Vllt. gibt's ja trotzdem noch Ungenauigkeiten. Evtl. werde ich versuche, diesen Beweis bei wikipedia reinzustellen, damit auch Laien ihn besser verstehen können. Der Knackpunkt ist die raffinierte Konstruktion, die man leicht übersieht, wenn man sich in den Zeichen und Symbolen verliert. Der Beweis ist mE jedenfalls anspruchsvoller als zB die Russellsche Antinomie, oder?

[breaker]

Ja, ich finde ihn auch anspruchsvoller.

Zur Formulierung: So wie Du ihn jetzt aufgeschrieben hast, glaube ich, dass du überall das richtige meinst.
Ob er in dieser Form für andere Laien genau so verständlich ist, wage ich anzuzweifeln. Mindestens würde ich ein paar Ungenauigkeiten in der Formulierung anmahnen und die Notation so ändern, dass die Elemente von P(X) nicht mehr px heißen.


Verstehst Du jetzt eigentlich auch, warum dein einfacherer Beweis nicht funktioniert und man den komplizierten Weg von Cantor gehen muss?

[Pippen]

Zur Formulierung: So wie Du ihn jetzt aufgeschrieben hast, glaube ich, dass du überall das richtige meinst.
Ob er in dieser Form für andere Laien genau so verständlich ist, wage ich anzuzweifeln. Mindestens würde ich ein paar Ungenauigkeiten in der Formulierung anmahnen und die Notation so ändern, dass die Elemente von P(X) nicht mehr px heißen.

Du kannst ja - falls du Lust hast - meinen Vorschlag als Vorlage nehmen und die Symbole oder Wörter ändern, die deiner Meinung nach ungenau oder unklar sind, ich habe bisher in der Tat immer nur auf mich geschaut, dass ich verstehe, um was es geht. Wenn dann stelle ich es ohnein erstmal als Diskussion bei wikipedia rein, mal sehen, was die Leute dann so sagen....

Verstehst Du jetzt eigentlich auch, warum dein einfacherer Beweis nicht funktioniert und man den komplizierten Weg von Cantor gehen muss?

Ich versteh es insoweit, als in meiner Version kein Widerspruch bei x_B rauskommt, bei Cantor's Version aber sehr wohl. Da Cantor's Beweisführung tadellos ist, muss meine falsch sein^^.

In jedem Fall ein großes Dankeschön an dich!!! Es ist nicht selbstverständlich, dass sich jemand die Zeit nimmt und die Mühe gibt, so einen Beweis Schritt für Schritt zu erklären. Damit hast du mich wirklich glücklich gemacht, denn ich habe verstanden, was für mich noch vor ein paar Tagen unverständlich war!

[breaker]

OK, mal sehen. Ich würd's vielleicht so formulieren:

Cantor's Theorem für Mathe-Amateure:

1. Wir haben also eine Menge X, deren Elemente wir mit x bezeichnen.
2. Wir haben die Potenzmenge P(X), deren Elemente wir mit Großbuchstaben (M,N,...) bezeichnen.
3. Nun nehmen wir an, wir hätten eine Abbildung, die jedem x aus X genau ein M aus P(X) zuordnet und surjektiv ist, d.h. es ist sogar jedes M aus P(X) mindestens einem x aus X zugeordnet.
Es sei nun F die Menge aller Paare (x,M), sodass M x zugeordnet ist.
4. Jetzt konstruieren wir eine Menge B, welche diejenigen x als Elemente hat, die nicht Element der ihr zugeordneten Menge M sind. B ist Teilmenge von X - entweder weil sie leer ist oder weil irgendwelche x darin sind. Dadurch ist B auch Element von P(X).
5. Da wir unsere Abbildung als surjektiv angenommen haben, muss ein x in X existieren, sodass das Paar (x,B) in F liegt; nennen wir dieses x zur besseren Unterscheidbarkeit x_B.
6. Es gilt entweder x_B ∈ B oder x_B ∉ B.
a) Wenn x_B ∈ B, dann gilt wegen der Definition von B, dass x_B nicht in B vorkommt, also x ∉ B. Das widerspricht der Annahme x ∈ B und kann daher nicht der Fall sein.
b) Wenn x_B ∉ B, dann gilt wegen der Definition von B, dass x_B in B vorkommt, also x ∈ B. Das widerspricht der Annahme x ∉ B und kann daher nicht der Fall sein.
7. Wir erhalten also in jedem Fall einen Widerspruch, woraus folgt, dass unsere Annahme falsch gewesen sein muss. Also gibt es keine surjektive Abbildung von X nach P(X) und damit muss P(X) mächtiger sein als X. (unabhängig davon, ob es eine injektive Abbildung gibt)

[Pippen]

Aha, d.h. wenn eine Menge Y nicht surjektiv zu einer Menge X ist, dann ist Y immer mächtiger als X?

[breaker]

Ich habe gerade nochmal nachgeschaut, und tatsächlich hast Du recht, dass man üblicherweise noch die Existenz einer injektiven Funktion voraussetzt, d.h.
B heißt mächtiger als A, wenn es eine injektive Funktion von A nach B gibt, aber keine surjektive.

Meiner Meinung nach ist aber die Forderung nach der Existenz einer injektiven Funktion von A nach B überflüssig, d.h. ich denke, man könnte genau so gut definieren:
B heißt mächtiger als A, wenn es keine surjektive Funktion von A nach B gibt.


Wenn Du aber den Beweis so aufschreiben willst, dass er für andere Leute leicht verständlich ist, solltest du natürlich die in der Literatur übliche Definition verwenden, d.h. wir sollten doch erwähnen, dass es eine injektive Funktion von X nach P(X) gibt.


Noch eine Anmerkung:
Die Sprechweise "X ist surjektiv zu Y" ist nich gebräuchlich. Das Wort surjektiv ist keine Eigenschaft von Mengen, sondern von Abbildungen. Eine Abbildung kann surjektiv sein, eine Menge nicht. Man sollte also lieber sagen "Es gibt keine surjektive Abbildung von X nach Y"

[Skeltek]

Es gibt ja noch gewisse Abstufungen, z.B. ob eine bijektive Funktion existiert, die auch stetig ist.
z.B. hat eine Bijektion von ]0;1] auf [0;1] mindestens abzählbar viele Unstetigkeitsstellen.

Eine Überlegung, die diesen Schritt weiterführt wäre:
Kann man zwei Mengen mit einer zugehörigen bijektiven Funktion konstruieren, die zwar bijektiv ist aber überabzählbar viele Unstetigkeitsstellen besitzt?
Liegt ihre Mächtigkeit zwischen der von N und R?
Ist bei jeder Funktion entscheidbar, ob sie bijektiv ist oder nicht? <- sehr kniffelige Frage, die eher von der betrachteten Menge als von der Funktion abhängig ist.
z.B. wäre eine Zahlenmenge denkbar, die am linken Rand ausschließlich rationale Zahlen hat und em rechten Rank ausschließlich irrationale Zahlen. Leider ist so eine Menge mit numerischen Mitteln nicht konstruierbar.

[Pippen]

Für mich stellen sich im Anschluss noch folgende Fragen zur Mengenlehre, die ich hier einbinden will:

1. Kann man zwei gleiche überabzählbare Mengen überhaupt bijektiv abbilden, also zB IR -> IR? Die Überlegung von mir ist folgende: Nach Cantor's eigenem Beweis kann es keine vollständige Auflistung von reellen Zahlen geben. Wenn IR auf sich selbst abbildbar wäre, dann müsste es eine Funktionsmenge F geben können, die alle zugeordneten Paare (IR, IR) enthält. Das wäre aber nichts anderes als die Liste, die es aber nicht geben kann. Widerspruch.

2. (zu Cantor's Überabzählbarkeitsbeweis) Wenn Cantor eine Liste mit unendlich vielen reellen Zahlen annimmt, dann kann er schon deswegen nie sagen, es gäbe eine Zahl die nicht in der Liste ist, weil diese Liste nie endet. Was ist das für eine Logik? So wie ich jmd. widerlegen könnte, der eine größte natürliche Zahl n behauptet, in dem ich eine Zahl n+1 konstruiere, kann ich gegen jede angebliche Diagonalzahl von Cantor einwenden, dass sie nur für n-Listenabzählungen gilt, meine Liste aber n+1 hat und so beginnt ein Kampf von Unendlichkeit (Liste) vs. Unendlichkeit (Diagonalzahl), der einfach unentscheidbar ist. Es gibt keinen Grund, dass man einfach so tun kann, als ob die Diagonalzahl diesen Kampf gewinnt, denn wenn es nicht so ist, dann wäre der Beweis widersprüchlich, d.h. man müsste es entscheiden.

[breaker]

Zu 1.:

Nach Cantor's eigenem Beweis kann es keine vollständige Auflistung von reellen Zahlen geben.

Mit "Auflistung" ist dort gemeint, dass man reelle Zahlen durch natürliche Zahlen abzählt. Du müsstest also eine Menge F angeben können, die Paare der Form (n,x) enthält, wobei n eine natürliche Zahl ist und x eine reelle. Und das geht nicht.

Eine bijektive Abbildung von R nach R ist natürlich durch f(x)=x gegeben.

Zu 2.:
Dafür müsste man vielleicht einen neuen Thread aufmachen, aber als direkte Antwort:
Die Argumentation "Die Liste ist unendlich, deshalb kann man nicht wissen, dass eine bestimmte Zahl nicht in ihr vorkommt" ist jedenfalls falsch. Beispiel:
Nehmen wir die Menge der Zahlen
{0.1 , 0.01 , 0.001 , 0.0001 , 0.00001 , ...}
Diese Menge enthlt unendlich viele Elemente. Du wirst mir aber sicherlich zustimmen, dass die Zahl 2 nicht darin vorkommt, oder?

[Pippen]

Zu 1.:
Mit "Auflistung" ist dort gemeint, dass man reelle Zahlen durch natürliche Zahlen abzählt. Du müsstest also eine Menge F angeben können, die Paare der Form (n,x) enthält, wobei n eine natürliche Zahl ist und x eine reelle. Und das geht nicht.

Eine bijektive Abbildung von R nach R ist natürlich durch f(x)=x gegeben.

Kann man das beweisen?

Die Argumentation "Die Liste ist unendlich, deshalb kann man nicht wissen, dass eine bestimmte Zahl nicht in ihr vorkommt" ist jedenfalls falsch. Beispiel:
Nehmen wir die Menge der Zahlen
{0.1 , 0.01 , 0.001 , 0.0001 , 0.00001 , ...}
Diese Menge enthlt unendlich viele Elemente. Du wirst mir aber sicherlich zustimmen, dass die Zahl 2 nicht darin vorkommt, oder?

Ja, aber da vergleichst du mE Äpfel mit Birnen. Denn Cantor's Liste reeller Zahlen ist gerade nicht dergestalt begrenzt. Was Cantor macht ist doch folgendes: Er konstruiert eine Liste mit n-Zeilen und in jeder Zeile ist eine reelle Zahl. Dann konstruiert er eine n-stellige Zahl, die er so definiert, dass sie von den n Zahlen der Liste verschieden ist. Daraus ergibt sich eine Unentscheidbarkeit, weil n beliebige Werte annehmen kann. Wenn zB Cantor meint, seine n-stellige Zahl sei von der Liste verschieden, dann zeige ich, dass sie nicht die n'-stellige Liste erfasst, woraufhin natürlich Cantor seine Zahl auf n' beziehen könnte und so scheint ein Wettlauf der Unendlichkeiten zu beginnen, ganz so wie der Kampf zwischen dem unendlich starken Speer und der unendlich starken Rüstung - wer soll da gewinnen?

[Skeltek]

Guten Morgen

Was Cantor macht ist doch folgendes: Er konstruiert eine Liste mit n-Zeilen und in jeder Zeile ist eine reelle Zahl. Dann konstruiert er eine n-stellige Zahl, die er so definiert, dass sie von den n Zahlen der Liste verschieden ist. Daraus ergibt sich eine Unentscheidbarkeit, weil n beliebige Werte annehmen kann. Wenn zB Cantor meint, seine n-stellige Zahl sei von der Liste verschieden, dann zeige ich, dass sie nicht die n'-stellige Liste erfasst, woraufhin natürlich Cantor seine Zahl auf n' beziehen könnte und so scheint ein Wettlauf der Unendlichkeiten zu beginnen, ganz so wie der Kampf zwischen dem unendlich starken Speer und der unendlich starken Rüstung - wer soll da gewinnen?

Standpunkt der Konstruktivisten:

Die durch das Diagonalverfahren entdeckte Eigenschaft wird von konstruktiven Mathematikern als Offenheit oder als Indefinitheit (Paul Lorenzen, Christian Thiel) der Mengen reeller Zahlen angesehen und nicht als die Überabzählbarkeit einer Menge

Cantor hat lediglich gezeigt, daß die Länge der Konstruktionsvorschrift für eine Zahl beliebig groß werden kann. Deshalb kann kein Algorithmus alle diese Zahlen innerhalb einer endlichen Entfernung zum Listenanfang zu Papier bringen.
Egal wieviele Zahlen man bereits aufgezählt hat, bleiben Zahlen übrig, die eine längere Konstruktionsvorschrift benötigen.
...
Körper sind ... beliebig oft erweiterbar.
Das ist mit der Offenheit der Menge gemeint.

Ich finde den Vergleich mit "Wettlauf der Unendlichkeiten" gar nicht so schlecht.

Kleiner Tipp: Versuch mal die Potenzmenge von N zu bilden.
R = lim(n->unendlich) von N^n (das Gleichheitszeichen soll nur bedeuten, daß links und rechts gleich mächtig sind)
bzw
lim(n->unendlich) von 2^n müsste gleichmächtig zu R sein, wenn ich mir das jetzt so aus den Fingern saugen darf.(für die schreckliche Notation verdien ich bestimmt das Fegefeuer, aber was soll´s...)

Keine Zeit grade Editor auszupacken für die drittletzte Zeile, denke ihr wisst was ich meine.

[breaker]

Kann man das beweisen?

Klar kann man das. Der Beweis ist gewiddermaßen trivial:
Für Surjektivität muss es zu jedem x in R ein y in R geben, sodass f(y)=x gilt. Das ist natürlich für y=x der Fall.
Für injektivität muss gelten, dass die Gleichung f(x)=f(y) die Gleichung x=y impliziert, was direkt da steht, wenn man ausschreibt, dass f(x)=x ist.


Zum Rest: -> Neuer Thread.