Vollständige Induktion

Aufrufe: 360     Aktiv: 03.11.2022 um 11:51
0
Ich soll zeigen dass die Menge Sigma hoch n eine abzählbare Menge ist für n Element der natürlichen Zahlen (bei uns ist die 0 dabei) und Sigma als endliches Alphabet.
Der Induktionsanfang ist ja kein Problem da Sigma 0 ja nur ein Element enthält nämlich das Leere Wort.
Aber wie zeige ich jetzt mit dem Induktionsschritt das es für alle n gilt? Bisher habe ich die vollständige Induktion nur bei Summen verwendet und nicht bei Mengen, ich brauche einen kleinen Denkanstoß.
Diese Frage melden
gefragt

Punkte: 12

 
Kommentar schreiben
1 Antwort
0
Schreibe erstmal Induktionanfang, etc. auf. Und dann musst du dir überlegen, wie du im Induktionsschritt von $n$ auf $n+1$ schließen kannst. Wie kommst du also von der Menge $\Sigma^n$ zur Menge $\Sigma^{n+1}$ und warum ist letztere abzählbar?
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 30.55K

 
Also mein Induktionsanfang lautet wie folgt: Sigma0 = {leeres Wort}
Also ist für n = 0 Sigma n abzählbar.
Aber wie schreibe ich jetzt den Induktionsschritt auf, ich kann ja schlecht alle Elemente hinschreiben. Vielleicht sowas wie |Sigma|hoch n um zu zeigen, dass es endlich ist?   ─   user6c9741 03.11.2022 um 11:32
1
Hast du meine Antwort richtig gelesen? Da steht ja, du sollst dir überlegen, was von $\Sigma^n$ zu $\Sigma^{n+1}$ passiert, um dann die Induktionsvoraussetzung anzuwenden, die du übrigens auch noch aufschreiben musst.   ─   cauchy 03.11.2022 um 11:51

Kommentar schreiben