Wie kann ich die Abzählbarkeit Beweisen?

... komplette Frage anzeigen

5 Antworten

Die Aussage, eine Menge X sei abzählbar, ist gleichbedeutend damit, dass X gleich mächtig oder von gleicher Kardinalität ist wie die Menge ℕ der Natürlichen Zahlen bzw. ℕ₀, wenn eindeutig die 0 dazugehören soll, geschrieben

(1.1) card(X) = card(ℕ)

oder auch

(1.2) |X| = |ℕ| =: ℵ₀.

Die Mächtigkeit oder Kardinalität ist eine Art Verallgemeinerung der Anzahl der Elemente einer Menge. Letztere, bei endlichen Mengen, ist natürlich eine natürliche Zahl.

Falls zwei Mengen X und Y unendlich viele Elemente enthalten, kann man natürlich nicht einfach durchzählen, um festzustellen, welche der beiden größer ist, doch hier gibt es einen »Trick«, der immer funktioniert (natürlich auch bei endlichen Mengen):

Man versucht, eine 1:1-Abbildung, eine Bijektion zwischen X und Y zu finden. Natürlich gelingt dies nur, wenn die Mächtigkeit gleich ist. Was es immer gibt, ist eine Abbildung

(2.1) f: X → Y; x ↦ y

und es gilt

(2.2) ∀x∈X ∃!(y∈Y): f(x) = y

Für alle x∈X gibt es genau ein y∈Y, sodass f(x) = y ist.

Bijektiv ist f dann, wenn diese Aussage auch umgekehrt gilt. Die Kardinalitäten lassen sich wie folgt vergleichen:

(3.1) |X| < |Y|    ⇔    ∄ f: X→Y und f surjektiv
(3.2) |X| > |Y|    ⇔    ∄ f: X→Y und f injektiv.

Sind |X| und |Y| endlich, sind alle Injektionen auch surjektiv und alle Surjektionen auch injektiv, sind sie es nicht, ist das nicht der Fall.

Um zu beweisen, dass

X = {x ∈ ℝ: 2x ∈ ℤ}

abzählbar ist, musst Du nur eine Bijektion X→ℕ bzw. ℕ₀ oder auch eine Bijektion ℕ₀ bzw. ℕ→X finden, eine Folge.

Die Folge

(a[n∈ℕ₀]) = 0, –½, +½, –1, +1, –1½, +1½, –2, +2, –2½, –2½,…

lässt ganz offensichtlich kein x∈X aus und zählt auch keine doppelt, Du kannst für x∈X immer ein n finden, sodass a[n] = x ist.

Antwort bewerten Vielen Dank für Deine Bewertung

Das ist die Menge aller Halben, also aller x so dass 2x ganzzahlig ist, also:

... -3/2, -2/2, -1/2, 0/2, 1/2, 2/2, 3/2, ...

Abzählbar bedeutet, dass es eine bijektive Abbildung zwischen dieser Menge und den natürlichen Zahlen gibt.

Das zeigst du genauso wie die Abzählbarkeit von Z

Antwort bewerten Vielen Dank für Deine Bewertung

Du gibst eine Bijektive Abbildung von den Natürlichen Zahlen in diese Menge an.

Antwort bewerten Vielen Dank für Deine Bewertung

Danke für die Antworten.

Das Prinzip habe ich verstanden... ich kann auch die Bijektiviät (Surjektivität und Injektivität) von Z beweisen. Ich verstehe nur diese Aufgabe nicht... kann mir jemand das Schritt für Schritt erklären? Danke :)

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von SlowPhil
03.08.2016, 18:04

Nicht eine Menge wie ℤ¹⁾ ist bijektiv, sondern eine Funktion

f: M → ℤ bzw. f: M → ℕ,

wobei M irgendeine Menge ist, deren Abzählbarkeit Du überprüfen möchtest.

--

¹⁾Um ℤ zu schreiben, schreib »&Zopf;« in eine Textdatei, kopiere sie und füge sie hier ein; in Chromium oder Google Chrome brauchst Du nur in die Maske zu schreiben, mit STRG+C kopieren und mit SHIFT+STRG+V statt nur STRG+V nur Inhalte einfügen.

0

Dies sind Parameter. Die sagen dass es Reelle Zahlen sind. Alle mögliche negative und Positve "unendlich lange" komma und nicht kommazahlen sind.

Also hängt deine Frage von deiner Definition von Abzählen ab

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von YStoll
02.08.2016, 17:39

Der Begriff der Abzählbarkeit ist klar definiert.

Was sind hier Parmeter? Hier ist eine Menge.
Und jedes Element dieser Menge hat im Dezimalsystem maximal eine Nachkommastelle, nicht beliebig viele.

1

Was möchtest Du wissen?