Warum ist die Kleene'sche Hülle nicht überabzählbar?
Im Buch Theoretische Informatik von Hoffmann ist die Kleene'sche Hülle über ein Alphabet (Sigma) definiert als:
(Sigma)* := Vereinigung von ((Sigma)^i) mit Index i=0 bis unendlich
(Leider gibt es hier keine LaTeX-Formatierung. Daher die etwas unschöne Formelschreibweise)
Meines Erachtens sind durch diese Definition auch unendliche Folgen inbegriffen, da eben der Index i bis unendlich zählt und damit unendliche Folgen (Sigma)^(unendlich) Elemente der Kleene'schen Hülle sind. Da die Menge aller unendlichen Folgen über (Sigma) m.E. überabzählbar ist (man korrigiere mich, wenn ich hier falsch liege), ist auch die Kleene'sche Hülle überabzählbar.
Nun lese ich jedoch überall, dass die Kleene'sche Hülle abzählbar unendlich ist mit dem Argument, dass alle Elemente endlich sind und man könne diese dann lexigrafisch ordnen. Wie allerdings oben aufgeführt, bin ich eher der Meinung, dass in der Kleene'schen Hülle auch unendlich lange Wörter enthalten sind und diese daher überabzählbar ist.
Wo liegt nun mein Fehler?
3 Antworten
Es sind nur abzählbar viele i zugelassen.
Und die Vereinigung von abzählbar vielen abzählbaren Mengen ist wiederum nur abzählbar.
Die einzelnen Mengen sind sogar S^i sind sogar nur endlich, und davon nur abzählbar viele. Noch schöner :-)))
Nein, die unendlichen Folgen sind eben nicht einbegriffen, da steckt dein Fehler.
Nimm mal ein Element s von Sigma*. Das liegt in der Vereinigungsmenge aller Sigma^i. D. h. es gibt ein i, so dass s in Sigma^i liegt.
Dieses eindeutig bestimmte i ist aber endlich - also ist auch jedes Wort endlich.
Meines Erachtens wäre die Vereinigung der N_i, i = 1 bis unendlich tatsächlich überabzählbar, aber eben auch nicht die Menge N der natürlichen Zahlen. Es gibt schließlich keine natürliche Zahl, die unendlich lang ist. (Wie zum Beispiel: man nehme alle Nachkommastellen von Wurzel 2 und füge sie zu einer Zahlenfolge zusammen. Das ist glaube ich keine natürliche Zahl...)
Der Fehler liegt darin, dass du glaubst, dass in Sigma* unendlich lange Wörter enthalten sind.
Ich versuch es mal andersherum: Angenommen, in Sigma* ist ein unendlich langes Wort w enthalten. Dann müsste es ein i geben, so dass w in Sigma^i liegt. In jedem Sigma^i liegen aber nur endliche Wörter.
Genauso, wie in jedem N^i nur endlich lange Zahlen liegen - insgesamt aber alle erfasst werden.
Ich glaube wir drehen uns im Kreis ^^
Angenommen, in Sigma* ist ein unendlich langes Wort w enthalten. Dann müsste es ein i geben, so dass w in Sigma^i liegt.
liegen in Sigma^unendlich (also i=unendlich) keine unendlich langen Wörter?
Ja, in Sigma^unendlich liegen unendlich lange Wörter.
Nein, Sigma^unendlich wird nicht mit vereinigt.
Du missverstehst die unendliche Vereinigung. Auch wenn da steht, i = 0 bis unendlich wird i eben nicht = unendlich.
Mein Problem ist, dass der Index i bis unendlich gezählt wird...
Ist denn (Sigma)^(unendlich) keine Menge von unendlich langen Wörtern?? Ich hätte das jedenfalls so interpretiert.
Wenn das nicht die Menge der unendlich langen Wörtern über Sigma ist, wie wird die Menge der unendlich langen Wörtern über Sigma dann gebildet? (Ich weiß, das hat irgendwas mit omega-Sprachen zu tun. Aber die müssen ja auch irgendwie formal definiert sein.)
Ja, i läuft bis unendlich. Das heißt aber nicht, dass i=unendlich in dern Summe vorkommt. Das ist wohl dein Irrtum.
Formal aufgeschrieben:
(S)^unendlich ist keine Teilmenge der Vereinigung S^i, i = 0 bis unendlich.
i = 0 bis unendlich ist nichts anderes als i Element von N (wenn ich die Null in N sehe).
Es gibt unendlich viele Zahlen in N - aber unendlich selber ist kein Element von N.
Achso ok, dann liegt hier tatsächlich mein Irrtum. Summiert man über alle natürlichen Zahlen (ohne unendlich), ist auch jedes Wort in der Kleene'schen Hülle endlich.
Danke für die Aufklärung =)
Wie allerdings oben aufgeführt, bin ich eher der Meinung, dass in der Kleene'schen Hülle auch unendlich lange Wörter enthalten sind[.]
Das ist leider falsch. Jedes Element s aus Sigma* ist Element eines Sigma^i [da diese Sigma* zerlegen]. Dann hat s Länge i.
Da wir jetzt wissen, dass wir nur endlich lange Wörter haben, ist der Beweis der Abzählbarkeit einfach. Ich mache mal den Fall, wenn Sigma endlich ist.
Wenn Sigma endlich ist, dann sei n die Kardinalität von Sigma. Wir bekommen eine Bijektion p: Sigma -> {0,...,n-1}
Sei nun s = {s0,...,sk} ein Wort in Sigma*, und wir schicken es auf p(s0) + p(s1)n + p(s2)n² + p(s3)n³ + ... + p(sk)n^k. Dies ist offensichtlich eine Injektion, da wir einfach nur eine n-adische Darstellung der natürlichen Zahlen mit Ziffernblock Sigma bekommen. Also ist Sigma* abzählbar.
Wenn Sigma nicht endlich, aber abzählbar ist, bekommst du auf ähnliche Art und weise eine Injektion in Z[X], den ganzzahligen Polynomring, der isomorph zu Z* ist, wenn du Z als Alphabet betrachtest. Da Sigma also unendlich und abzählbar ist, bekommst du eine Bijektion von Sigma nach Z, also eine Bijektion von Sigma* nach Z*, dessen Abzählbarkeit trivial ist.
LG
Nach deiner Logik wäre auch N überabzählbar. Bilde mal folgende Mengen:
N_i = Menge der Zahlen aus N mit i Ziffern (ohne führende Nullen).
Dann gilt
N = Vereinigung der N_i, i = 1 bis unendlich.