Menge aller endlichen Strings

Question

Aufgabe:

Sei A∗ die (unendliche) Menge aller endlichen Strings, welche aus den Dezimalziffern A =
{0, 1, 2, . . . , 9} gebildet werden können; formal ¨ A∗ = {ϵ, 0, 1, 2, . . . , 9, 00, 01, 02, . . . , 09, . . . }.
a) Zeigen Sie, dass A∗
abzählbar ist.
b) Benutzen Sie Teilaufgabe a), um zu zeigen, dass die Menge Q der rationalen Zahlen
abzahlbar ist. Nutzen Sie dafür aus, dass ¨ Q = {a/b |a ∈ Z ∧ b ∈ N≥1}.

Problem/Ansatz:

… wie zeige ich das A* abzählbar ist ?

Answer 1

… wie zeige ich das A* abzählbar ist ?

Es gibt 10 einstellige Strings. Die bekommen die Nummern 1 bis 10.

Es gibt 100 zweistellige String (00 bis 99), die erhalten die nächsten 100 Nummern.

Es gibt 1000 dreistellige String (000 bis 999), die erhalten die nächsten 1000 Nummern.

...

Nenne mir einen String, der  nach diesem Prinzip keine Nummer erhält ...

Comments

(Wenn ich die Aufgabenstellung richtig deute, soll auch der leere String möglich sein, der braucht noch eine Nummer.)