Zeige, dass die Menge aller unendlich langer Bitfolgen, überabzählbar ist

Question

Eine unendlich lange Bitfolge ist eine Funktion f_Bit : ℕ → {0, 1}. Zeige, dass M = {f_Bit}, die Menge aller unendlich langer Bitfolgen, überabzählbar ist.

Wie geht das?

Comments

Per Widerspruchsbeweis.

Nimm an es gibt eine Abzählung und konstruiere dann eine Folge die nicht in dieser Abzählung liegen kann.

Hier gibt es die Lösung (bzw. einen Tipp):

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

Answer 1

Du musst nur zeigen, dass eine bijektive Abbildung g:ℕ → M nicht möglich ist.

Idee ist: Angenommen man hat eine solche Abb. g  ,

dann wird zu jedem n ∈ ℕ eine unendlich lange Bitfolge zugeordnet.

Betrachte nun die Bitfolge a  , die an der Stelle 1 einen anderen Wert hat als g(1),

also a(1) = 0  falls g(1) an der Stelle 1 eine 1 hat und

      a(1) = 1  falls g(1) an der Stelle 1 eine 0 hat .

Entsprechend an der 2. Stelle

  a(2) = 0  falls g(2) an der Stelle 2 eine 1 hat und
      a(2) = 1  falls g(2) an der Stelle 2 eine 0 hat ..

Dann stimmt a mit keiner Bitfolgen in M überein; denn a hat an der n-ten

Stelle immer einen anderen Wert als g(n).

Also ist g nicht surjektiv.

Kannst ja mal googeln:

"Cantorsches Diagonalverfahren"