TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 154

Dieser Beispielseite fehlt die Angabe.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{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

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 $\mathbb {N}$
Zwei Mengen A und B sind gleich mächtig, wenn es eine bijektive Abbildung f: A $\to$ B gibt.

Lösungsvorschlag von neo

Wenn eine Menge mindestens 2 Buchstaben hat, folgt daraus, dass es 2^$\infty$ mögliche unendliche Wörter gibt.
Wir suchen also ein f: $\mathbb {N}$ $\to$ 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...$\infty$ $\to$ es kommen unendlich viele 'a's bevor Wörter mit b drankommen.
Ich bezeichne nun mit $\vert$w$\vert$ 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) = $\vert$w$\vert$ * a. Daher f(1)=a, f(2)=aa usw.
Da f($\infty$) = $\infty$ * a ist und die 'b's aber bis jetzt gar nicht vorgekommen sind ist $\vert$W$\vert$ > $\vert$$\mathbb {N}$$\vert$

Lösungsvorschlag von banal_trivial

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 $\vert$$\mathbb {N}$$\vert$ = $\vert$$\mathbb {Z}$$\vert$ = $\vert$$\mathbb {Q}$$\vert$ 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...$\longmapsto$ 0

1*b: baaaaaaaa...$\longmapsto$ 1

2*b: bbaaaaaaa...$\longmapsto$ 2

3*b: bbbaaaaaa...$\longmapsto$ 3

.... $\infty$ ...

Wenn sich die Buchstaben "b" immer nur am Anfang befinden, kann man die Wörter auf $\mathbb {N}$ projezieren.

Da in Wörten jedoch die Reihenfolge der Buchstaben sehr wohl relevant ist, gibt es 2^$\infty$ Mögliche Kombinationen.

Somit muss abaaaaaaa... einer anderen Zahl als 1, abbaaaaaa... einer anderen Zahl als 2, ... zugeordnet werden. Da bereits 0 bis $\infty$ 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.