Ist Sigmastern abzählbar?
wenn ein Alphabet Sigma endlich ist , was bedeutet das für die Mächtigkeit von Sigma Stern
Meine vermutung ist , dass Sigma Stern dann abzählbar unendlich ist aber wie kann man das beweisen und stimmt die Vermutung überhaupt?
Danke
2 Antworten
![](https://images.gutefrage.net/media/user/MagicalGrill/1548472380616_nmmslarge__260_60_1080_1080_9461c4b490096d30204b9d24434abaa7.png?v=1548472381000)
Betrachte für jede natürliche Zahl n die Menge Σ^n, i.e. die Menge aller Wörter über Σ der Länge n. Zeige, dass diese Mengen endlich sind.
Nun ist Σ* die Vereinigung aller Σ^n. Aber eine abzählbare Vereinigung endlicher Mengen ist abzählbar.
![](https://images.gutefrage.net/media/user/ralphdieter/1444750340_nmmslarge.jpg?v=1444750340000)
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik
Die Vermutung stimmt. Ordne jedem Element aus Σ eine Ziffer zur Basis |Σ|+1 zu (ohne die 0).
Dann stellt jedes Wort aus Σ* eine eindeutige Zahl dar. Also |Σ*|≤|ℕ|