Frage bezüglich der Menge
-
Hallo,
ich muss die folgende Aufgabe lösen:Σ - endliche Menge, wobei Σ:={x1,x2,...xn}.
Σ+ - Die unendliche Menge aller Wörter, wobei die Operation Nacheinanderbindung (Konkatenation) ist, d.h. w1,w2→w1w2.
Σ*=Σ+υε, wobei ε das Leerwort ist. Σ* ist auch unendlich.
Zu beweisen ist: Σ* ist abzählbar?
Hinweis: Was wäre wenn es eine bijektive Relation zwischen den natürlichen Zahlen und dieser Menge gibt? Finden sie eine injektive Abbildung, so dass Σ*→N existiert.
-
Um Abzählbarkeit zu kriegen brauchste ne injektive Abbildung von Deiner Menge nach N. Du willst sozusagen jedem Element ne Nummer zuordnen. Wichtig dabei ist, daß Du jedem Wort eine andere Nummer geben kannst.
Mein Tipp wäre: bezeichne mal Deine Buchstaben aus dem Alphabet mit 0...n-1 und schreib das ganze dann im Zahlensystem zur Basis n auf. Jede Zahl in dieser Basis beschreibt jetzt genau ein Wort aus Deiner Sprache. Wer will kann das ja dann noch ins Dezimalsystem umrechnen.
-
Hallo, Jester,
erstens, danke sehr für die Antwort. Ich versuche etwas selbst zu schreiben.
Also x1, x2 usw sind Buchstaben. Wenn man sie konkateniert, dann bekommt man Wörter. Es gibt unendlich viele Wörter, die man bilden kann. Um man eine Abzählbarkeit zu zeigen, muss man beweisen, dass jedem Wort genau eine feste Nummer aus der Menge der natürlichen Zahlen zugeordnet werden kann. Warum das? Tja, eigentlich sind die natürlichen Zahlen abzählbar, infolge der bijektive Relation zwischen den beiden Mengen kann man auch behaupten, dass die Menge der Wörter vereinigt mit dem Leersymbol auch abzählbar ist. Habe ich bishier Recht?
Dann wie soll ich die Buchstaben nomerieren?
Z.B. Das Leereszeichen = 0
a = 1
b = 2
... usw
Wie bestimme ich die Nummer der Wörter, so dass sie eindeutig dadurch bestimmt sind?
-
Nehmen wir mal an, Du hättest nur 10 Buchstaben, nennen wir sie mal 0,1,2,3,4,5,6,7,8,9. Siehste jetzt ne eindeutige Abbildung von den Worten in die Zahlen? Was ist die Zahl, die zum Wort "1089" gehört?
Okay, Problem ist noch sowas wie "019", das ist keine wirkliche Zahl. Wenn wir aber zum Beispiel nur 9 Buchstaben zulassen (also die 0 wegnehmen) dann klappt es.
Wenn Du jetzt mehr oder weniger Buchstaben hast, dann nimmst Du halt nicht das Dezimalsystem, sondern das System mit Basis Anzahl Elemente des Alphabets (möglicherweise +1 wegen der 0).
Zahlen sind halt auch nur Symbole
Endlich viele Sachen dazunehmen geht immer einfach (in Deinem Fall ja nur das leere Wort), wenn man schon ne Funktion f hat, die's für die unendlich vielen tut, dann definiert man einfach
g(w) = { f(w)+1 für w nicht leeres Wort
{ 0 sonstdas ist natürlich auch noch eindeutig. Indem man das wiederholt anwendet kann man endlich viele Sachen noch dazunehmen.
MfG Jester