0-1 - Folge

Wissenschaft Physik
#1

Eine 0-1 - Folge ist eine Abbildung f : N -> {0,1}. Zeigen Sie, dass die Menge aller 0-1 - Folgen überabzählbar ist.

Eigener Kommentar:

Bei dieser Aufgabe spielt die Mächtigkeit eine wichtige Rolle.
Ansatz mit Widerstandsbeweis:
Es existiert eine (bijektive) Abbildung phi: N -> {0,1}_N (0-1 - Folgen) daraus folgt ein Widerspruch.
Prinzip anhand von einem Beispiel für 0-1 Folgen:
0,0,1,1,0
0,0,0,1,1
1,1,1,0,1
0,0,1,1,1
0,0,0,1,1
Konstruiert man eine Folge von der Diagonalen von unten links beginnend (also Rückwärts) so erhält man eine Folge (hier: 1,1,1,0,0), die nicht mehr abzählbar ist, da sie an n-ter Stelle unterschiedlich zu allen anderen Folgen ist, da sie nicht mehr surjektiv ist.

#2

Hi Christoph!

Bei dieser Aufgabe spielt die Mächtigkeit eine wichtige Rolle.
Ansatz mit Widerstandsbeweis:

*g* Ich nehm’ mal an, du meinst einen Beweis durch Widerspruch.

Konstruiert man eine Folge von der Diagonalen von unten links
beginnend (also Rückwärts) so erhält man eine Folge (hier:
1,1,1,0,0), die nicht mehr abzählbar ist, da sie an n-ter
Stelle unterschiedlich zu allen anderen Folgen ist, da sie
nicht mehr surjektiv ist.

Äh… Das ist nicht so evident, daß diese Diagonalfolge nicht zufällig doch in den alten Folgen enthalten ist!

Warum machst du das nicht wie in den Lehrbüchern und nimmst die Negation der Diagonalfolge?

Das wäre bei

Folge a_0: 0 1 0 0 1 1 0 0 1 1 1 1 0 0 1…
Folge a_1: 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1…
Folge a_2: 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1…
…

Du nimmst dann die Folge (d_n) mit d_i = 1 - (a_i)_i, wobei (a_i)_i das i-te Element der i-ten FOlge ist.

Dann gilt: Egal, was für Folgen du aufgeschrieben hast, die Diagonalfolge ist von allen verschieden nach Konstruktion.

Chris

#3

Hallo Christoph,

eine alternative Überlegung findest Du hier:

http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…

Gruß,
Martin

P.S. Beachte, dass in dem obigen Archivartikel (a_n) die ganze Folge meint, während a_n, das n-te Glied dieser Folge bezeichnen soll. Für eine Abbildung f in die Menge der Folgen hinein ist dann ein Bild"punkt" f(m) ebenfalls eine ganze Folge und f(m)_k entsprechend das k-te Glied hiervon.