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
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.
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 |Σ*|≤|ℕ|