TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 154
{{Beispiel|1= Angabetext }}
oder
{{Beispiel| Angabetext }}
zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)
{{Beispiel|status=solved|1= Angabetext }}
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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 >
Lösungsvorschlag von banal_trivial[Bearbeiten | Quelltext bearbeiten]
Eine Menge ist überabzählbar, wenn sich keine Projektion (oder ein sogenanntes "Mapping") auf die Natürlichen Zahlen erstellen lässt (wodurch z.B. bewiesen wurde, dass = = gilt).
Versuchen wir nun die Menge aller unendlichen Wörter bestehend aus Buchstaben des Alphabets {a, b} zu projezieren:
Die Anzahl an "b" in dem jeweiligen Wort wird einer natürlichen Zahl zugeordnet:
0*b: aaaaaaaaa... 0
1*b: baaaaaaaa... 1
2*b: bbaaaaaaa... 2
3*b: bbbaaaaaa... 3
.... ...
Wenn sich die Buchstaben "b" immer nur am Anfang befinden, kann man die Wörter auf projezieren.
Da in Wörten jedoch die Reihenfolge der Buchstaben sehr wohl relevant ist, gibt es 2^ Mögliche Kombinationen.
Somit muss abaaaaaaa... einer anderen Zahl als 1, abbaaaaaa... einer anderen Zahl als 2, ... zugeordnet werden. Da bereits 0 bis nur durch Wörter wo "b" ausschließlich am Anfang der Buchstabensequenz vorkommen abgedeckt wurden, muss die Menge aller unendlichen Wörter aus {a, b} überabzählbar sein.