Wie zeige ich, dass eine Menge überabzählbar ist?

 - (Mathematik, menge, Abzählbarkeit)

3 Antworten

Angenommen, es gebe eine surjektive Abbildung g : IN —> 2^|N
Sei diag : |N —> 2 definiert durch diag(n) = 1–g(n)(n).
Da g surjektiv ist, existiert ein n* in IN, so dass g(n*) = diag.
Aber dann gilt diag(n*) = g(n*)(n*). Das widerspricht der Definition von diag.

Darum existiert keine Surjektion und somit, da wir ja wissen dass #IN <= #(2^IN), gilt #IN < #(2^IN) strikt. Das heißt 2^|N ist überabzählbar.

Bemerkung: auf diese Weise können für JEDE Kardinalität zeigen:
|X| < 2^|X|
Es gibt nicht nur diese zwei Kardinalitäten (abzählbar unendlich und kontinuum).

Sowas macht man üblicherweise durch einen Widerspruchsbeweis.

Nimm an, sie sei abzählbar und leite daraus einen Widerspruch her.

Was möchtest Du wissen?