Wie beweise ich das die Menge aller Wörter über einem Alphabet abzählbar?

4 Antworten

Da Wörter theoretisch beliebig lang sein können, halte ich es für unwahrscheinlich, dass es dafür ein Beweis gibt. Ich hoffe ich habe das richtig verstanden.

LG.

Da täuschst du dich.
Kann es sein, dass du „abzählbar“ mit „endlich“ verwechselst?

0

"Ordne" die Menge aller Wörter zuerst aufsteigend nach Länge. Jede Teilmenge zu einer bestimmten Wortlänge (zum Beispiel: Alle Wörter der Länge 2) ist endlich. Die Gesamtmenge ist also die Vereinigung abzählbar vieler endlicher Mengen, daraus folgt Abzählbarkeit.

Wie weit du das nun ausarbeiten musst, hängt von den Sätzen über Abzählbarleit ab, die du voraussetzen darfst.

Ein Alphabet ist eine endliche nicht leere Menge. Wörter sind ebenfalls endlich. Daraus folgt, dass jede Sprache abzählbar ist

Finde eine isomorphe (eineindeutige) Abbildung zur Menge der natürlichen Zahlen - auf deutsch eine eindeutige Nummerung.

Dann ist die Menge der Wörter gleichmächtig zur Menge der natürlichen Zahlen. Und diese ist abzählbar.

Die Antwort von Mianthril ist sehr hilfreich.

Was möchtest Du wissen?