Frage von Lumpi101, 57

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?

Expertenantwort
von PWolff, Community-Experte für Mathematik, 37

Es sind nur abzählbar viele i zugelassen.

Und die Vereinigung von abzählbar vielen abzählbaren Mengen ist wiederum nur abzählbar.

Kommentar von FataMorgana2010 ,

Die einzelnen Mengen sind sogar S^i sind sogar nur endlich, und davon nur abzählbar viele. Noch schöner :-)))

Antwort
von Roach5, 17

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

Antwort
von FataMorgana2010, 57

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. 

Kommentar von FataMorgana2010 ,

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.  

Kommentar von Lumpi101 ,

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...)

Kommentar von FataMorgana2010 ,

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. 

Kommentar von Lumpi101 ,

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?

Kommentar von FataMorgana2010 ,

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. 

Kommentar von Lumpi101 ,

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.)

Kommentar von FataMorgana2010 ,

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. 

Kommentar von Lumpi101 ,

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 =)

Keine passende Antwort gefunden?

Fragen Sie die Community