Question

Aufgabe 8 Studieren Sie den folgenden Beweis:
Wir wollen die folgende Behauptung beweisen: Die Potenzmenge P(M) einer Menge
M ist machtiger als die Menge selbst. M kann eine endliche oder eine unendliche Menge
sein.
Wir fuhren einen Beweis durch Widerspruch. Es ist klar, dass die Potenzmenge von M
nicht weniger machtig ist als die Menge M , denn die Abbildung
f : M → P(M)
x → {x}
ist injektiv. Unsere Annahme lautet also:
Annahme: M und P(M) sind gleichmachtig.

Answer 1

wenn zwei Mengen gleichmächtig sind, dann gibt es eine Bijektion zwischen diesen. Ordnen wir nun (o.B.d.A) jedem Element x von M die Teilmenge in P(M) zu, die nur x enthält (dies ist die gegebene Abbildung f).

Die Abbildung f ist folglich nicht surjektiv, falls M mehr als ein Element enthält: Wir können für zwei Elemente x1 und x2 aus M nicht auf die Menge K = {x1, x2} in P(M) abbilden, da f schlicht kein Element in M auf K abbildet.

Die Klausel "o.B.d.A" heißt übrigens ohne Beschränkung der Allgemeinheit und bedeutet hier, dass wir (für die Abbildung f) aus P(M) die einfachsten Mengen auswählen können, ohne die Allgemeinheit des übrigen Beweises einzuschränken.

Angenommen, wir würden jetzt auf K statt auf eine Menge in P(M), die nur ein x enthält, abbilden. Dann müssten wir auf diese Menge, die nur x enthält, verzichten und die Gültigkeit des Beweises bliebe erhalten. Sprich Permutationen im Bildraum verändern nicht die Tatsache, dass M weniger Elemente als P(M) enthält.

Schließlich kann man sagen: In P(M) lassen sich mehr als |M| Elemente finden, sofern |M| > 1 gilt, sprich |P(M)| > |M|.

MfG

Mister

Comments

Dein Beweis funktioniert so nur für endliches \(M\). Ansonsten würde man mit einer ähnlichen Argumentation zeigen können, dass \(\mathbb Z\) mächtiger als \(\mathbb N\) ist.

---

Dies bedeutet nur eine Einschränkung an die Wahl der Bijektion.

---

Inwiefern soll das jetzt deinen Beweis rechtfertigen? Du hast nirgends gezeigt, dass es keine Bijektion zwischen \(M\) und \(P(M)\) (für unendliches \(M\)) gibt.

---

Eine "nicht surjektive" Abbildung ist keine Bijektion.

---

Ja, und du hast gezeigt, dass es eine Abbildung von \(M\) nach \(P(M)\) gibt, die nicht surjektiv ist, nämlich \(x\mapsto\{x\}\). Wieso kann es nicht irgendeine andere bijektive Abbildung geben?

---

Vertauschungen im Bildraum lassen die Aussage invariant. Die injektive Abbildung f : x ↦ {x} ist bis auf Isomorphie äquivalent zu allen anderen injektiven Abbildungen von M auf P(M), was die Gleichheit der Anzahl der Elemente im Bild- und Urbildraum angeht.

---

Ja und wieso gibt es keine Vertauschung im Bildraum, welche die Mengen der Form \(\{x\}\) auf ganz \(P(M)\) abbildet?

---

Die Menge aller {x} ist echte Teilemenge von P(M).

---

Ja und? Die natürlichen Zahlen bilden auch eine echte Teilmenge der ganzen Zahlen. Trotzdem gibt es zwischen diesen Mengen eine Bijektion.

---

Ich zitiere mich nun selbst: "Dies bedeutet nur eine Einschränkung an die Wahl der Bijektion."

---

Was wiederum keinerlei Sinn ergibt. Wodurch wird die Wahl welcher Bijektion wie eingeschränkt?

---

Versuch es dir einfach mal vorzustellen. Deine Angabe von Z und N ist kein echtes Gegenbeispiel für diesen Beweis.

---

Ich sehe keinen Beweis. Du hast nur gezeigt, dass die Abbildung \(x\mapsto\{x\}\) nicht die gesamte Potenzmenge als Bild hat.

Dann hast du noch behauptet, dass es keine Bijektion zwischen \(\Bigl\{\{x\}:x\in M\Bigr\}\) und \(P(M)\) gibt, das aber nicht bewiesen.

---

Besagte Abbildung f: x ↦ {x} ist aber injektiv. Vertauschungen im Bildraum erhalten diese Eigenschaft, oben anhand der Menge K erklärt. Die Möglichkeit an sich, Bildelemente austauschen zu können, impliziert die Nicht-Surjektivität.

f ist nur ein sehr anschaulicher Repräsentant einer Äquivalenzklassen von auf M injektiven Funktionen, die nicht surjektiv sind. Da alle auf M injektiven Funktionen zu dieser Äquivalenzklasse gehören, gibt es keine zugleich injektive und surjektive Funktion, die von M auf P(M) abbildet.

---

"Die Möglichkeit an sich, Bildelemente austauschen zu können, impliziert die Nicht-Surjektivität."
Die Nicht-Surjektivität wovon? Und wieso wird die impliziert?

"Da alle auf M injektiven Funktionen zu dieser Äquivalenzklasse gehören"
Wieso ist das der Fall?

Und bisher könntest du eben doch alles auch für \(\mathbb N\) und \(\mathbb Z\) formulieren: Die Abbildung \(\mathbb N\to\mathbb Z\), \(n\mapsto n\) ist injektiv, aber nicht surjektiv. Dann hat man wieder Permutationen im Bildraum, redet irgendetwas über Vertauschungen von Bildelementen und hat angeblich bewiesen, dass keine bijektive Abbildung \(\mathbb N\to\mathbb Z\) existiert. An welcher Stelle würde dein "Beweis" denn hierfür nicht mehr funktionieren?

---

Die negativen Elemente von ℤ entstehen ja nicht aus Teilmengen von ℕ.

PS: Du musst dich klarer ausdrücken, worin dein Problem liegt.

---

Nein, nein, du musst den Beweis klarer formulieren.

Das mit den ganzen Zahlen war so gedacht: Die ganze "Argumentation" würde anscheinend genauso "funktionieren", wenn du \(\mathbb N\) statt \(M\), \(\mathbb Z\) statt \(P(M)\) und \(x\) statt \(\{x\}\) schreiben würdest.

Anscheinend möchtest du eine injektive Funktion \(M\to P(M)\) betrachten und sagst, dass ihr Bild bijektiv zu dem von \(x\mapsto\{x\}\) ist. Soweit ist das noch in Ordnung. Aber wieso kann das Bild einer injektiven Funktion \(M\to P(M)\) dann nicht ganz \(P(M)\) sein? Genau dieser Schritt fehlt dir.

---

Dieser Schritt ist jedoch oben beschrieben.

Für das Gegenbeispiel wäre die Wahl der Abbildung f: x ↦ {x} bereits nicht zielführend (falsch), daher sich auch die ganze Argumentation erübrigte und diese gar nicht für ein Gegenbeispiel herhalten kann.

---

"Dieser Schritt ist jedoch oben beschrieben."
Wo? Schreib die Argumentation am besten nochmal sauber und an einem Stück auf.

Der zweite Absatz ist wieder nicht nachzuvollziehen: Welches Gegenbeispiel? Das mit den natürlichen und ganzen Zahlen? Dort habe ich auch nie die Abbildung \(x\mapsto\{x\}\) gewählt, sondern betrachte stattdessen \(n\mapsto n\).

---

Die Wahl dieser Abbildung wäre ebenso, denn im gleichen Sinne, nicht zielführend (falsch).

---

Und du hast mir immer noch nicht deinen Beweis vollständig aufgeschrieben...

---

Du hast es ja selbst gesagt. Das Bild einer injektiven Funktion, die von M auf P(M) abbildet, ist bijektiv zu dem Bild von x ↦ {x}. Warum kann das Bild nicht ganz P(M) sein? Weil es Mengen in P(M) der Art {x1, x2} gibt. Auf diese ist durch x ↦ {x} nicht abgebildet. Folglich ist der Bildbereich von x ↦ {x} und aller Bijektionen dieses Bildbereiches echte Teilmenge von P(M) (die Mächtigkeit bleibt unter Bijektion erhalten). Da aber jede injektive Funktion isomorph zu x ↦ {x} ist und diese nicht surjektiv ist, gibt es keine bijektive Abbildung von M nach P(M).

---

"Weil es Mengen in P(M) der Art {x1, x2} gibt. Auf diese ist durch x ↦ {x} nicht abgebildet."
Ja, das Bild dieser Abbildung ist nicht ganz \(P(M)\).

"Folglich ist der Bildbereich von x ↦ {x} und aller Bijektionen dieses Bildbereiches echte Teilmenge von P(M) (die Mächtigkeit bleibt unter Bijektion erhalten)."
Hier liegt das Problem: Es ist zwar der Bildbereich von \(x\mapsto\{x\}\) eine echte Teilmenge von \(P(M)\), aber du hast nicht gezeigt, dass auch jede zu diesem Bildbereich bijektive Teilmenge eine echte ist.
Daher auch mein Beispiel mit den natürlichen Zahlen: Zwar ist \(\mathbb N\) eine echte Teilmenge von \(\mathbb Z\), aber bijektiv zu dieser Obermenge.

Wenn dein Argument sein sollte, dass die Mächtigkeit unter Bijektionen erhalten bleibt, musst du für deine Behauptung wissen, dass \(P(M)\) mächtiger als das Bild von \(x\mapsto\{x\}\) ist. Das zu zeigen ist aber eigentlich die Aufgabe.

"Da aber jede injektive Funktion isomorph zu x ↦ {x} ist"
Was meinst du hier eigentlich mit "isomorph"? Dass die Bilder bijektiv sind? Wenn ja, dann hast du diese Aussage noch nicht bewiesen.