|
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:
Beweis:
Satz:
Beweis:
X={'a',...,'z','A',...,'Z','0',...,'9',',',':',...,'-','+','à'}.Sei p: X-->{1,2,...,|X|}eine totale Funktion, die jedem Zeichen xX 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 wX* ein beliebiges Wort. w hat eine endliche Länge |w|=nIN, d.h. w=x1 x2 x3 ...xn , xiX für alle i{1,...,n}.x1 ,...,xn sind die Zeichen, aus denen w aufgebaut ist. Dann definieren wir folgende Funktion: : X* -->IN durchSpeziell 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,wX* . 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=x1 x2 x3 ...xn und v=y1 y2 y3 ...yn für ein n>= 0. Weiterhin gelte (w)=(v), d.h.: folglich: Dies kann aber nur zutreffen, wenn p(xi )-p(yi )=0 für alle i gilt. Da p bijektiv ist, müssen also alle xi gleich den yi 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. • |
|