Surjektive Abbildung widerlegen. Abbildung von einer Menge zu der Potenzmenge.

Question

Aufgabe:

Es sei M eine nichtleere Menge. Zeigen Sie:

Es gibt keine surjektive Abbildung φ : M → P(M).

Problem/Ansatz:

Im folgenden steht mein Versuch die Aufgabe zu lösen, ich bin mir aber nicht sicher ob dies schon als Beweis reicht.

Die Definition für surjektivität ist in dem Fall, dass für alle y∈P(M) mindestens ein x∈M existiert mit f(x)=y.

In einer Aufgabe davor hat man gezeigt, dass für n viele Elemente in der Menge M es genau 2^n viele Teilmengen gibt.

Wenn wir davon ausgehen, dass es so eine surjektive Abbildung gibt, dann müsste M>P(M) sein, da wir aber wissen dass es nicht so ist (durch die Aufgabe davor) und es dadurch mindestens ein Element y gibt für das f(x)≠y gilt kann die Abbildung nicht surjektiv sein.

Danke fürs lesen und Grüße :)

Answer 1

Hallo,

dein Argument funktioniert nur für endliche Mengen; denn es gibt sehr wohl z.B. eine
surjektive Abbildung \(\mathbb{N}\rightarrow \mathbb{Z}\), obwohl die erste Menge
eine echte Teilmenge der zweiten ist.

Der Beweis der Behauptung gelingt am einfachsten mit einem "Trick", der an die
berühmte Antinomie von Russell erinnert:

Angenommen \(f:M\rightarrow P(M)\) ist surjektiv.

Man betrachte nun die Menge$$A=\{x\in M: \, x \notin f(x)\} \in P(M)$$
Da \(f\) surjektiv ist, gibt es ein \(a\in M\) mit \(f(a)=A\).

Jetzt haben wir folgende Situation:

1. \(a\notin f(a)\Rightarrow a\in A=f(a)\) nach Definition von \(A\), Widerspruch !

2. \(a\in f(a)=A\Rightarrow a\notin f(a)\) nach Definition von \(A\), Widerspruch !

Die Surjektivitätsannahme für \(f\) führt also auf einen grundsätzlichen Widerspruch.

Gruß ermanus