Beweisen Sie, dass die Menge M := {f : N → N} überabzählbar ist.
ist nicht M := {f : N → N | f monoton wachsend} gemeint?
Die Funktion ist definitiv überabzählbar
Was für eine Funktion? Du sollst zeigen, dass M überabzählbar ist.
E = Endzahl
?
Intervall zwischen 1 & E
???
Annahme:
M ist abzählbar (endlich)
das ist ein guter Ansatz
Cantors zweites Dialogargument
1. |4|51858
2. 4|3|6285
3. 84|5|683
4. 313|7|63
5. 2178|8|3
6. 21012|9|
| ...
v
758397
total unverständlich was gemeint ist.
M ist nicht endlich -> M ist über abzählbar
das ist keine richtige Implikation. Wenn M nicht endlich ist könnte M immer noch abzählbar sein und müsste nicht überabzählbar sein.
----
Beweisprototyp:
Angenommen M abzählbar, sei \( (f_i)_{i \in \mathbb N} \) eine Abzählung von M.
Dann gilt:
$$ f_1(1) \le f_1(2) \le f_1(3) \le f_1(4) \le \dotsm \le f_1(i) \le \dotsm \\f_2(1) \le f_2(2) \le f_2(3) \le f_2(4) \le \dotsm \le f_2(i) \le \dotsm \\f_3(1) \le f_3(2) \le f_3(3) \le f_3(4) \le \dotsm \le f_3(i) \le \dotsm \\ ...\\f_i(1) \le f_i(2) \le f_i(3) \le f_i(4) \le \dotsm \le f_i(i) \le \dotsm $$
Definiere die Abbildung \( g : \mathbb N \to \mathbb N \) durch
$$ g(n) := ... $$
dann ist g monton wachsend, da ... Insb ist g in M.
aber g liegt nicht in der Abzählung \( (f_i)_{i \in \mathbb N} \), denn ...
Widerspruch zur Annahme, also ist M überabzählbar.
Versuche jetzt mal die Lücken selbstständig auszufüllen.
Tipp: jede endliche Teilmenge der natürlichen Zahlen besitzt ein Maximum.
