Überabzählbarkeit von Mengen mit Funktionen?
Hallo,
wir haben eine Menge M={f : N -> N | f ist surjektiv} (N sind die natürlichen Zahlen).
Wie kann ich beweisen, dass die Menge überabzählbar ist? Also welche Funktion konstruiert man da, die sich von allen unterscheidet, aber trotzdem surjektiv ist?
Vielen Dank im Voraus!
2 Antworten
Auch wenn alaaf es im Grunde schon gut auf den Punkt bringt, hier nochmal ein bisschen mehr Intuition:
Eine Menge ist abzählbar, wenn sie entweder endlich ist, oder wenn sie abzählbar unendlich ist. Eine Menge ist abzählbar unendlich, wenn es eine Bijektion zwischen den natürlichen Zahlen und dieser Menge gibt.
Die Menge der ganzen Zahlen zum Beispiel ist abzählbar, weil ich dir die Funktion
f : N --> G, f(n)={n/2, falls n gerade, -(n+1)/2, sonst
angeben kann. (Von dieser Funktion müsste man jetzt theoretisch zeigen, dass sie bijektiv ist, und wir nehmen an, dass 0 in N, und 0 gerade).
Mit den reelen Zahlen sieht es anders aus. Das Diagonalargument von Cantor zeigt sehr elegant, dass es solch eine Bijektion nicht geben *kann*, weil wir immer wieder neue Werte im Bildbereich finden, auf die wir nicht abbilden. Vielleicht hast du dieses Argument schon einmal gesehen, ansonsten kann dir das das ein oder andere YouTube Video sicher anschaulicher erklären, als ich hier im Text.
Meine Behauptung ist nun die, dass wir das bei deiner Menge M genau so hinbekommen. Du versuchst, unter der Annahme der Bijektivität, eine Funktion aufzustellen, die alle Elemente der natürlichen Zahlen auf Elemente der Menge aus M mapt, und zeigst dann allgemein, dass es Elemente in M gibt, die dann (allgemein, wir nehmen die Bijektion an) nicht erfasst werden. Das steht dann im Widerspruch. Ob du das graphisch machst, oder ihr irgendwelchen logischen Kalküle definiert habt, mit denen ihr so etwas macht, weiß ich nicht.
Ich denke, man könnte versuchen, das zweite Cantorsche diagonalargument abändern.