Aber ist M abzählbar oder überabzählbar?

Question

Aufgabe:

abzählbar oder überabzählbar

Problem/Ansatz:

Unter einer Zeichenkette aus Nullen und Einsen verstehen wir ein endliches (ggf. leeres)
Tupel a mit a_n ∈ {0, 1} für alle n. Beispielsweise sind (0, 0, 1, 0, 1, 1, 0), (0, 0, 0, 0, 0) und
(1) Zeichenketten aus Nullen und Einsen. (Eine alternative Schreibweise für diese Zeichenketten ist 0010110, 00000 und 1.) Zwei Zeichenketten heißen gleich, wenn sie gleich
lang sind und an entsprechenden Positionen die gleichen Ziffern stehen – dies ist die Definition von Gleichheit, die man für Zeichenketten erwarten würde. Sei nun M die Menge aller Zeichenketten aus Nullen und Einsen, in allen (endlichen) Längen. Offenbar ist M unendlich groß. Aber ist M abzählbar oder überabzählbar? Beweisen oder widerlegen Sie.

Answer 1

Die geschilderten Zeichenketten kann man auch als binäre Schreibweisen natürlicher Zahlen interpretieren. Folglich ist M abzählbar.

Comments

Die Zahl 6 kommt aber unendlich oft vor, nämlich als 110 , 0110 , 00110 , 000110 , ...

---

Ich würde sagen: es gibt eine Bijektion zu jeder Kettenlänge in jeder Besetzung.

-> abzählbar unendlich

---

"Ich würde sagen" und "Es gibt eine Bijektion" (von wo nach wo eigentlich?) sind reine Sprechblasen.

Kannst du die Existenz einer Bijektion zwischen diesen Zeichenketten und der Menge der natürlichen Zahlen konkret beschreiben?

---

Ich kann jeder Kette/Tupel eine natürliche Zahl zuordnen.

Was soll das daran unklar sein? Man kann die Tupel abzählen.

Dann müssten alle Formulierungen in duesem Kontext, die man ständig liest, nur hohle Phrasen sein.

Für mich ist das vollkommen ausreichend und vorstellbar, ob Sie öffentlich zum Verspotten aufrufender Oberlehrer das glauben wollen oder nicht.

---

hj2166 hat recht. Jede natürliche Zahl kommt abzählbar unendlich oft vor. Das ändert aber nichts an der Abzählbarkeit.

---

Das ändert aber nichts an der Abzählbarkeit.

Das ist sowas von evident, dass es eigentlich keiner Diskussion bedarf.

Zahlenfolgen, nur aus Nullen und Einsen bestehend, sind abzählbar unendlich.

Das leuchtet auch einem Nicht-Profi sofort ein.

Ich kann jeder eine natürliche Zahl zuordnen.

---

Zahlenfolgen, nur aus Nullen und Einsen bestehend, sind abzählbar unendlich.
Du meinst wahrscheinlich die Anzahl aller nur aus Nullen und Einsen bestehenden Zahlenfolgen. Die ist übrigens überabzählbar.

Ich kann jeder eine natürliche Zahl zuordnen.
Man kann übrigens auch jeder reellen Zahl eine natürliche Zahl zuordnen, obwohl ℝ überabzählbar ist.