+1 Daumen
6,6k Aufrufe

Ich weiß leider nicht wie ich dies beweisen soll, gerade beim beweisen stell ich mich immer etwas schwierig an. Ich bin sehr dankbar über jeden Tip.

Die Aufgabe:

Sei \( M = \{ f | f : N \rightarrow \{ 0 , I \} \} \)

N sind die natürlichen Zahlen, ich hab das Zeichen leider nicht gefunden. ;)

Beweisen Sie, dass M überabzählbar ist.

von

1 Antwort

+2 Daumen
 
Beste Antwort

Du kannst hier das Zweite Cantor'sche Diagonalargument nutzen:

Nimm das Gegenteil an, d.h.: sei die Menge abzählbar unendlich. Dann existiert einen Bijektion φ: ℕ→Μ und man kann eine Tabelle erstellen:

n φ(n)(1) φ(n)(2) φ(n)(3) ... 1 2 3 ...

a11 a12 a13 ...
a21 a22 a23 ...
a31 a32 a33 ...
... ... ... ...

Was bedeutet das jetzt?
Die Menge besteht aus allen Funktionen f, die jeder natürlichen Zahl einen Wert der Menge {0, 1} zuordnen, das heißt, ein mögliches f sieht so aus:

f(1) = 0, f(2)=0, f(3)=1, f(4)=0, f(5)=1, f(6)=1, ...

in beliebiger Kombination folgen also 0en und 1en aufeinander. Aus der Annahme, es gebe nur abzählbar endlich viele solcher Funktionen folgt, dass es eine Bijektion zu den natürlichen Zahlen gibt: das heißt, man kann diese Funktionen durchnummerieren, wie ist erstmal egal.

In der Tabelle steht nun in der ersten Zeile die erste Funktion, in der zweiten die Zweite usw. Und in den Spalten steht dann jeweils der Wert der ersten Funktion für die 1, für die 2 und so weiter.

Stünde etwa die Beispielfunktion in der ersten Zeile, dann wäre

a11 = 0, a12 = 0, a13 = 1, ...

Da es sich um eine Bijektion handelt, muss jede mögliche Funktion vorkommen - und zwar genau einmal.

Nun kann man aber mit dem Cantorschen Diagonalargument eine Funktion konstruieren, die in der Tabelle nicht vorkommt und zwar folgendermaßen:

Wähle eine neue Funktion und zwar folgendermaßen:

g(1) = ¬a11
g(2) = ¬a22
g(3) = ¬a33
...
g(k) = ¬akk

Wobei die Funktion ¬: {0, 1}→ {0, 1} folgendermaßen definiert sei:

¬0 = 1
¬1 = 0

Diese Funktion g hat nun die folgenden Eigenschaften:

1.) Sie ist auf ganz ℕ definiert.

2) Sie nimmt Werte in der Menge {0, 1} an.

Diese beiden Eigenschaften zeigen schonmal, dass sie eigentlich in der Tabelle vorkommen muss.

Aber die dritte Eigenschaft ist:

3.) Sie kommt nicht in der Tabelle vor.

Wie zeigt man die dritte Eigenschaft?
Ganz einfach: damit sie in der Tabelle vorkommt, muss eine Zeile existieren, mit der sie komplett identisch ist.

Aber: von jeder Zeile unterscheidet sie sich mindestens in der k-ten Spalte, denn da ist sie ja gerade als Gegenteil definiert worden. Mit anderen Worten (wenn man die Funktion der n-ten Zeile fn nennt:)

g(1) ≠ f1(1)
g(2) ≠ f2(2)
g(3) ≠ f3(3)
...

Also ist die Menge nicht abzählbar.

von 10 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
1 Antwort
Gefragt 3 Feb 2016 von Gast
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community