| Autor |
Beitrag |
    
Alexander Duschau-Wicke (Alibaba)
| | Veröffentlicht am Mittwoch, den 27. Dezember, 2000 - 00:32: | 
|
Hallo, ich stehe bei folgender Aufgabe vor grösseren Problemen:
Beweisen oder widerlegen Sie:
a) Die Menge A = { f | f: Z -> Z, f total} ist abzählbar.
b) Die Menge A = { f | f: N_0 -> {0,1}, f total} ist abzählbar.
Zum Beweis soll eine konkrete Abzählung angegeben werden, zum Beweis der Überabzählbarkeit mit dem Cantorschen Diagonalisierungsverfahren ein Widerspruch herbeigeführt werden.
Meine Hauptprobleme dabei: Was genau bedeutet: Eine Funktion ist total? Wie wendet man man das Cantorsche Diagonalisierungsverfahren auf Mengen von Funktionen an? |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 27. Dezember, 2000 - 22:11: |
|
Hallo Alexander
Zunächst mal: eine Fuktion ist total, wenn es zu jedem Wert aus dem Definitionsbereich auch wirklich einen Funktionswert gibt, also im Prinzip einfach nur das, was man normalerweise von einer Fuktion oder einer Abbildung versteht. Auf der anderen Seite gibt es noch partielle Funktionen. Bei denen ist es erlaubt, dass es zu einigen Werten keinen Funktionswert gibt.
Nun zum Diagonalisierungsverfahren:
Wie oben angedeutet, nimmt man an, man könnte alle diese Funktionen auf/abzählen. Dazu benutze ich eine wirkürliche Aufzählung der ganzen Zahlen in den Spalten, wobei ich eine der natürlicheren genommen habe, und wir nehmen an, die Zeilen würden alle Funktionen mit ihren zugehörigen Werten aufzählen. Diese Tabelle muss man sich sowohl nach unten als auch nach rechts unendlich lang vorstellen.
Nun konstruieren wir aber eine Funktion, die garantiert noch nicht in der Liste steht. Und zwar, indem wir die Diagonalelemente (rot markiert) anschauen. Wir konstruieren eine Fuktion, die an der Stelle 0 einen anderen Wert hat als f1, an der Stelle -1 einen anderen Wert als f2, an der Stelle 1 einen anderen Wert als f3 usw...
Nun vergleichen wir die so konstruierte Funktion mit allen in der Liste. Sie ist nicht gleich f1, weil sie an der Stelle 0 einen anderen Wert hat, nicht gleich f2 wgen der Stelle -1, nicht gleich f3 usw. Insgesamt folgt also, dass die Funktion noch nicht in der Liste aufgetaucht ist. Also muss die Behauptung falsch sein, dass man alle Funktionen aufzählen kann.
Die zweite Menge ist übrigens auch überabzählbar. Der Beweis ist sogar ein bisschen einfacher. Versuch es mal selbst.
viele Gruesse
nachträglich frohe Weihnachten
und ein frohes Neues Jahrtausend
SpockGeiger |
|
