Wie beweise ich das die Menge aller Wörter über einem Alphabet abzählbar?
Frage steht oben ... ich weiß leider wirklich nicht wie man so einen beweis macht ... wäre sehr lieb wenn mir jemand ein paar ansätze geben könnte.
4 Antworten
"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.
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.
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.
Ein Alphabet ist eine endliche nicht leere Menge. Wörter sind ebenfalls endlich. Daraus folgt, dass jede Sprache abzählbar ist
Da täuschst du dich.
Kann es sein, dass du „abzählbar“ mit „endlich“ verwechselst?