Zeichenkette aus Nullen und Einsen

Question

Problem:

Ich mache gerade eine Übungsaufgabe und bei der ist die Aufgabenstellung so lang, dass ich nicht verstehe was da ganz genau gemacht werden soll. Wenn mir jemand mal kurz erklären könnte was da gemacht werden soll würde ich mich sehr freuen.

Aufgabe:

Unter einer Zeichenkette aus Nullen und Einsen verstehen wir ein endliches
(ggbf. leeres) Tupel a mit an ∈ {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 uberabzählbar? Beweisen oder widerlegen Sie.

Comments

Vom Duplikat:

Titel: Zeichenketten beweisen

Stichworte: beweis

Aufgabe:

  Unter einer Zeichenkette aus Nullen und Einsen verstehen wir ein endliches (ggbf. leeres) Tupel a mit an ∈ {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 fur 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

Problem/Ansatz

ich verstehe die frage nicht genau und weiß ich nicht wie kann man das lösen

könnten Sie bitte die Frage lösen und bisschen erklären

Answer 1

Die Menge ist abzählbar.

Eine mögliche Abzählung  f (also eine bijektive Abbildung von ℕ nach M ) wäre wie

folgt zu definieren.

f(2^n) = Zeichenkette der Länge n, die aus lauter 0en besteht.

(Für n=0 also die leere Zeichenkette)

Diese kann man ja auch interpretieren als Binärdarstellung der Zahl 2^n,

bei der man die erste Ziffer gestrichen hat.

Und dann kann man jeder nat. Zahl x , die größer als 2^n und kleiner

als 2^(n+1) die Zeichenkette zuordnen, die durch Weglassen der

führenden 1 in der Binärdarstellung von x entsteht.

Das ist dann immer eine Zeichenkette der Länge n.

Umgekehrt wird jede Zeichenkette der Länge n dabei erreicht

und da verschiedenen natürliche Zahlen auch verschiedenen

Binärdarstellungen haben, ist die Abbildung also bijektiv.

Comments

"Zwei Zeichenketten heißen gleich, wenn sie gleich lang...sind." bedeutet in meinen Augen zum Beispiel 0 ≠ 00 wobei beides der dezimaldarstellung der natürlichen Zahl 0 entspricht. Bedeutet nun deine Funktion/Abzählung trifft nicht alle Zeichenketten, oder irre ich mich?

---

bitte könnten noch mir erklären mit Rechnung

So ich habe bisschen verstanden  danke

Answer 2

Es soll angegeben werden ob die Menge aller Zeichenketten aus den Zeichen 0 und 1 abzählbar oder überabzählbar ist. Außerdem soll bewiesen werden, warum die Menge abzählbar bzw. überabzählbar ist.

Answer 3

Jede beschriebene Zeichenkette ist die Darstellung einer natürlichen Zahl im binären Zahlensystem. Verschiedene Zeichenketten sind Darstellungen verschiedener Zahlen. Die Menge der natürlichen Zahlen ist abzählbar. Also ist auch die Anzahl der Zeichenketten abzählbar.

Answer 4

Falls sie abzählbar ist und du dies nachweisen sollst, müsstest du eine Bijektion zwischen diesen Zeichenketten und der Menge der natürlichen Zahlen herstellen können.