[ Inhalt ] [ Index ]

Abzählbarkeit

   

Definition: (abzählbare Menge, überabzählbare Menge [9])
Es sei M eine Menge. Wir nennen M abzählbar, wenn sich M bijektiv   auf oder eine Teilmenge davon abbilden läßt.
Anderenfalls heißt M überabzählbar.

Beispiel:

Jede endliche Menge ist abzählbar.

Ist A ein Alphabet (d.h. endlich!), so ist abzählbar. Man betrachte ganz einfach die lexikographische Ordnung  .

Satz:
Es sei E ein Alphabet. Dann gibt es überabzählbar viele Funktionen , von denen nur abzählbar viele berechenbar sind.

Beweis:
Jeder Algorithmus ist ein Text endlicher Länge. Diese Texte kann man lexikographisch anordnen und bijektiv auf abbilden. Folglich gibt es nur abzählbar viele Algorithmen.

Dann kann es aber auch nur abzählbar viele Funktionen geben, für die ein Algorithmus existiert.

Nun gibt es aber überabzählbar viele Funktionen. Man betrachte z.B. die Funktionen . Wenn es denn nur abzählbar viele davon geben würde, könnten wir sie in einer Tabelle anordnen:

Betrachten wir nun die Funktion

Dann muß f einen Index z.B. j haben: . Nach Definition gilt aber: .
Damit haben wir einen Widerspruch, den wir nur auflösen können, wenn wir die Annahme fallen lassen, daß wir die Funktionen abzählen können.

Folglich gibt es überabzählbar viele Funktionen, aber nur abzählbar viele Algorithmen.