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

Answer 1

[MagicalGrill]

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.

Answer 2

[ralphdieter]

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