Suche Home Einstellungen Anmelden Hilfe  

1. 3 Weiteres zu Mengen - Beweise

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:
1) Sei M eine abzählbare Menge und M'M eine unendliche Teilmenge. Sei
f: IN-->M.eine Abzählung von M. Seien k0, k1, k2, k3, ...IN diejenigen natürlichen Zahlen, für die f(ki )M' gilt. Eine Abzählung f' von M' erhält man dann durch die Definition:
f': IN-->M' mit f'(i)=f(ki ) für alle iIN. •

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 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 , xi X für alle i{1,...,n}.
x 1 ,...,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,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. •

Übersicht: Sprachklassen

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: