Zeigen Sie mittels Diagonalisierung, dass M nicht abzählbar unendlich ist.

Question

Aufgabe:

Sei M ={f Sf ∶N→{0,1}}. Zeigen Sie mittels Diagonalisierung, dass M nicht abzählbar unendlich ist.

Problem/Ansatz:

Kann mir bitte einer Helfen ich verstehe dieses Thema überhaupt nicht Ich weiss nur das ich mir mit der diagonalisierung eine komplett neue Funktion konstruieren kann sie sich zu jeder funktion in der Aufzählung unterscheiden soll. Zb

g(1)=f1(1)+1

Für n>1 definieren wir uns

g(n)={g(n)-1 falls f(n)=/g(n-1)

        {g(n-1)+1 sonst

Comments

vgl:

https://de.wikipedia.org/wiki/Cantors_zweites_Diagonalargument

Answer 1

Deine Funktion g ist aber wohl nicht in M; denn wenn du f1(1)+1 bildest,

kann das ja den Wert 2 haben.

Aber so geht es wohl : Falls (f_i )_i∈ℕ eine Aufzählung von M ist

Betrachte g : ℕ→{0,1} mit

          g(n) =  0  , falls f_n(n)=1 und

         g(n) =  1  , falls f_n(n)=0.

Dann ist g zwar in M, kommt aber in der Aufzählung nicht vor,

weil g sich an der Stelle n von jedem f_n unterscheidet.

Comments

Dankeeeeeeee

Answer 2

Ich weiss nur das ich mir mit der diagonalisierung eine komplett neue Funktion konstruieren kann sie sich zu jeder funktion in der Aufzählung unterscheiden soll.

Sei \(\left(f_i\right)_{i\in \mathbb{N}}\) eine solche Aufzählung.

Ferner sei \(g: \mathbb{N}\to\{0,1\}\) mit

• \(g(1) = \dots\), also ist \(g \neq f_1\)
  
• \(g(2) = \dots\), also ist \(g \neq f_2\)
• \(g(3) = \dots\), also ist \(g \neq f_3\)
  
• \(\vdots\)
• \(g(n) = \dots\), also ist \(g \neq f_n\) für alle \(n\in\mathbb{n}\).