Abzählbarkeit

Eine unendliche Menge M heißt abzählbar unendlich (kurz: abzählbar), wenn es
eine bijektive Abbildung f: IN-->M gibt (oder ? was gleichwertig ist ? wenn es eine
bijektive Abbildung g: M-->IN gibt). f nennt man Abzählung. Ist M unendlich, aber nicht
abzählbar, so heißt M überabzählbar.

Satz:
1) Jede unendliche Teilmenge einer abzählbaren Menge ist abzählbar.
2) Jede Obermenge einer überabzählbaren Menge ist überabzählbar.

Beweis:
s. Übungen.

Satz:
Die Menge aller Algorithmen ist abzählbar.

Beweis:
Die Menge aller Algorithmen ist eine Teilmenge von X*. Wegen o.g. Satz brauchen wir
also nur zu zeigen, dass die Menge aller endlich langen Texte X*, die man über dem
Alphabet X bilden kann, abzählbar ist.
Sei |X| die Anzahl der Elemente des Alphabets X. Die Elemente von X mögen irgendwie
angeordnet sein, z.B. so:

X={'a',...,'z','A',...,'Z','0',...,'9',',',':',...,'-','+','à'}.

Sei

p: X-->{1,2,...,|X|}

eine totale Funktion, die jedem Zeichen x

X die Stelle zuordnet, an der es im Alphabet
X auftritt. Zum Beispiel gilt p('a')=1, p('z')=26, p('7')=60 usw.
Sei nun w

X* ein beliebiges Wort. w hat eine endliche Länge |w|=n

IN, d.h.

w=x₁ x₂ x₃ ...x_n , x_iX für alle i{1,...,n}.

x₁ ,...,x_n sind die Zeichen, aus denen w aufgebaut ist. Dann definieren wir folgende
Funktion:

: X* -->IN durch

Speziell sei

(

)=0. Offensichtlich ordnet f jedem Wort aus X* genau eine Zahl zu.

ist
also eine totale Funktion. Wir behaupten:

ist injektiv. Hierzu beachte man dass stets

gilt. Man betrachte nun zwei beliebige Wörter v,w

X* . Wenn diese zwei Wörter v und w
verschiedene Länge besitzen, dann gilt wegen obiger Ungleichung sicher

(w)

(v). Sei daher |w|=|v|, also w=x₁ x₂ x₃ ...x_n und v=y₁ y₂ y₃ ...y_n für ein n>= 0. Weiterhin gelte

(w)=(v), d.h.:

folglich:

Dies kann aber nur zutreffen, wenn p(x_i )-p(y_i )=0 für alle i gilt. Da p bijektiv ist, müssen
also alle x_i gleich den y_i sein. Wir haben somit gezeigt, daß für beliebige Wörter v und w
die Gleichheit

(w) =

(v) nur gelten kann, wenn v=w ist. Folglich ist

injektiv.
Wir betrachten nun

(X* ). Da X* eine unendliche Menge und

eine injektive Funktion ist, muß auch

(X* ) eine unendliche Menge sein. Nach o.g. Satz ist jede unendliche Teilmenge von IN abzählbar unendlich, also auch

(X* ). Da

(X* ) gleichmächtig zur Menge X* ist, folgt hieraus die Abzählbarkeit von X*. Somit ist auch die Menge aller Algorithmen als unendliche Teilmenge von X* abzählbar. •