Warum ist die Kleene'sche Hülle nicht überabzählbar?

...komplette Frage anzeigen

3 Antworten

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 bewerten Vielen Dank für Deine Bewertung

Es sind nur abzählbar viele i zugelassen.

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

Antwort bewerten Vielen Dank für Deine Bewertung
FataMorgana2010 01.08.2016, 11:02

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

1

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. 

Antwort bewerten Vielen Dank für Deine Bewertung
FataMorgana2010 01.08.2016, 10:06

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.  

0
Lumpi101 01.08.2016, 10:32
@FataMorgana2010

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

0
FataMorgana2010 01.08.2016, 10:39
@Lumpi101

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. 

0
Lumpi101 01.08.2016, 10:49
@FataMorgana2010

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?

0
FataMorgana2010 01.08.2016, 10:57
@Lumpi101

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. 

0
Lumpi101 01.08.2016, 10:28

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

0
FataMorgana2010 01.08.2016, 10:41
@Lumpi101

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. 

1
Lumpi101 01.08.2016, 12:45
@FataMorgana2010

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

0

Was möchtest Du wissen?