TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 149

From VoWi
Jump to navigation Jump to search

Hilfreiches[edit]

Lexikographische Ordnung:
Ein Wort A ist kleiner als ein Wort B wenn:
1) das Zeichen a aus A mit dem niedrigsten Index i,in dem sich die beiden Zeichenketten unterscheiden, (echt) kleiner ist als das entsprechende Zeichen b (mit Index i) aus B.
2) A ein Anfang von B ist, nur kürzer.

Überabzählbarkeit:
Eine Menge A ist überabzählbar, wenn ihre Mächtigkeit größer ist, als die von
Zwei Mengen A und B sind gleich mächtig, wenn es eine bijektive Abbildung f: A B gibt.

Lösungsvorschlag von neo[edit]

Wenn eine Menge mindestens 2 Buchstaben hat, folgt daraus, dass es 2^ mögliche unendliche Wörter gibt.
Wir suchen also ein f: W, wobei W die Menge aller unendlichen Wörter bezeichnet.
Wenn man sich die lexikographische Ordnung von der Menge anschaut fällt auf:
a; aa; aaa; aaaa; aaa... es kommen unendlich viele 'a's bevor Wörter mit b drankommen.
Ich bezeichne nun mit w die Länge eines Wortes aus W. Aus der vorigen Beobachtung mit den 'a's lässt sich eine (potenzielle) bijektive Abbildung herauslesen mit f(w) = w * a. Daher f(1)=a, f(2)=aa usw.
Da f() = * a ist und die 'b's aber bis jetzt gar nicht vorgekommen sind ist W >