Question

Sei M eine Menge. Zeigen sie, dass die Potenzmenge \( P(M) \) von \( M \) strikt mächtiger ist als \( M \), d.h. \( |M|<|P(M)| \).

Answer 1

Zu zeigen  "kleiner oder gleich" ist ja erst mal einfach.

Es ist f : M --- P(M) mit  x --->  {x}

offenbar injektiv, also die Mächtigkeit von M

kleiner oder gleich der von P(M).

Aber es gibt keine surjektive Abb von M nach P(M),; denn:

Sei F eine solche, dann betracht die Teilmenge A von M

mit A = { x aus M | x nicht aus F(x) }

klar ?  F(x) ist ja eine Teilmenge von M, also kann x da drin sein

oder eben nicht.

Da F surjektiv ist, gibt es ein a aus M mit F(a) = A

Dann bleiben nur zwei Möglichkeiten:

1.  a aus A, dann ist das a so ein x, bei dem x aus F(x) gilt,

also ist a nicht aus A.  Widerspruch !

2. a nicht aus A, dann ist das a so ein x, bei dem x nicht aus F(x) gilt,

also muss in a in A sein.  Widerspruch !

Schöne Geschichte dazu:
Der Dorfbarbier (ein Mann) soll genau alle Männer im Dorf rasieren,
die sich nicht selbst rasieren. Was macht er mit sich selbst ?

Comments

Er kann eben nicht das tun, was er soll. Es sei denn, ihm wüchsen keinerlei Barthaare.

---

...Und sich einen Bart einfach stehen lassen, kommt nicht in die Tüte, weil jeder Bart  vom Barbier rasiert werden soll.

---

mathematisch dann lapidar Widerspruch genannt.

---

Ja, genau. Die Welt ist voller Widersprüche.

Answer 2

wenn |M| = n, dann ist ja |P(M)| = 2^n

also musst du im endlichen Fall zeigen, dass für alle n gilt

n < 2^n

Ist M abzählbar, so ist P(M) überabzählbar (habt ihr das schon gemacht?)

Gruß

Comments

Kann man das dann nicht einfach mit vollständiger induktion beweisen ?

---

Das mit dem endlichen Fall?
Definitiv

---

Wie erklärt man das mit abzählbar und überabzählbar...

---

Weil es keine surjektive Abbildung einer Menge auf ihre Potenzmenge gibt

Man kann dies durch einen Widerspruchsbeweis zeigen:

Zu Beginn:

Sei \(M\) eine abzählbare Menge und \( f: M \to P(M) \) eine surjektive Abbildung.

Betrachte die Menge

$$ G := \{ x \in M | x \notin f(x) \subset P(M) \} $$

Überlege dir warum \( G\) nicht leer sein kann. Dann benutze die Surjektivität um zu zeigen, dass es ein

\( y \in M \) geben muss so dass \( f(y) = G \). Jetzt kannst du dies aber auf den Widerspruch

\( y \in G \Leftrightarrow y \notin G \) führen.