0 Daumen
611 Aufrufe

Aufgabe:

Wir nennen eine Funktion f : N → N monoton wachsend, wenn für alle i ∈ N gilt, dass f(i) ≤ f(i + 1). Beweisen Sie, dass die Menge M := {f : N → N} überabzählbar ist.


Problem/Ansatz:

Die Funktion ist definitiv überabzählbar da sie ein immer weiter steigendes Wachstum hat (unendlich).

E = Endzahl

Intervall zwischen 1 & E

Annahme:

M ist abzählbar (endlich)



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


M ist nicht endlich -> M ist über abzählbar


ich nehme an, dass ich Syntax Fehler habe und es wahrscheinlich übersichtlicher schreiben könnte, würde mich freuen auch Tipps dahingehend zu bekommen.

Liebe Grüße.


Avatar von
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.

1 Antwort

0 Daumen

Cantors 2. Diagonalargument reicht doch z.B. schon

um zu zeigen, dass alle Abb'en von N nach {0,1}

eine überabzählbare Menge bilden. Das ist von deiner eine Teilmenge.

Avatar von 287 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community