Abzählbar/Überabzählbar

30.10.2008, 21:12

Svenja1986

Abzählbar/Überabzählbar

Aufgabe:
Ist die Menge der abbrechenden Folgen von Ziffern 1 und 2 abzählbar oder überabzählbar? Bitte begründen Sie Ihre Antwort in Form eines Beweises!

Meine Überlegung:
Die Folgen an sich sind abzählbar, weil abbrechend, also endlich.
Aber die Mengen der Folgen sind überabzählbar, weil man ja eigentlich unendlich viele Folgen bilden kann.

Stimmt das?
Und wie könnte man das beweisen?

Danke für Hilfe Tanzen

30.10.2008, 21:24

Zizou66

Auf diesen Beitrag antworten »

Zitat:

Original von Svenja1986
Die Folgen an sich sind abzählbar, weil abbrechend, also endlich.
Aber die Mengen der Folgen sind überabzählbar, weil man ja eigentlich unendlich viele Folgen bilden kann.

Nach dieser Aussage glaube ich, dass du die Begriffe nicht genau kennst. Wann ist eine Menge abzählbar und wann überabzählbar?

30.10.2008, 21:35

Svenja1986

Auf diesen Beitrag antworten »

Hm...

Überabzählbar, wenn man die Elemente der Menge nicht durchnummerieren kann.

Ok. Ja, dann hab ich vorhin irgendwie Schwachsinn geschrieben.

Aber ich würde trotzdem sagen, dass die Mengen der Folgen überabzählbar sind, weil man ja nicht jeder 1 und 2 eine natürliche Zahl zuordnen kann, da sie ja öfter vorkommen... (?)

30.10.2008, 21:43

WebFritzi

Auf diesen Beitrag antworten »

Ist die Menge der rationalen Zahlen Q abzählbar? Kannst du eine injektive Abbildung von der vorliegenden Menge in die rationalen Zahlen angeben?

30.10.2008, 21:50

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von WebFritzi
Ist die Menge der rationalen Zahlen Q abzählbar?

Ja eigentlichen schon. Mit dieser Cantor-Diagonalisierung...

Zitat:

Original von WebFritzi
Kannst du eine injektive Abbildung von der vorliegenden Menge in die rationalen Zahlen angeben?

Steh grad aufm Schlauch unglücklich

30.10.2008, 21:59

tmo

Auf diesen Beitrag antworten »

Die Vereinigung abzählbar vieler abzählbarer (hier sind sie sogar endlich) Mengen ist wieder abzählbar.

Selbst wenn du diesen Satz nicht kennst/nicht benutzen darfst, weißt du damit immerhin schonmal was du überhaupt beweisen musst.

31.10.2008, 20:00

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Die Vereinigung abzählbar vieler abzählbarer (hier sind sie sogar endlich) Mengen ist wieder abzählbar.

Selbst wenn du diesen Satz nicht kennst/nicht benutzen darfst, weißt du damit immerhin schonmal was du überhaupt beweisen musst.

Hm und wie geh ich an diesen Beweis ran? verwirrt

01.11.2008, 14:19

tmo

Auf diesen Beitrag antworten »

Ich hätte da einen Ansatz zu bieten:

Die Menge, die betrachtet wird ist: $\begin{eqnarray*} \bigcup_{n \in \mathbb N} \{1,2\}^n \end{eqnarray*}$

Es ist $\begin{eqnarray*} |\{1,2\}^n| = 2^n \end{eqnarray*}$ , also ist für jedes n die Menge $\begin{eqnarray*} \{1,2\}^n \end{eqnarray*}$ endlich. Nun listest du für jedes n die Menge $\begin{eqnarray*} \{1,2\}^n \end{eqnarray*}$ einfach auf, sodass die einzelnen Elemente dieser Menge eine Ordnung haben. Die ist dann einfach durch die Reihenfolge der Auflistung gegeben.

Nun zeigst du, dass die Abbildung $\begin{eqnarray*} f:\bigcup_{n \in \mathbb N} \{1,2\}^n \mapsto \mathbb N \end{eqnarray*}$ , die dem k-ten Element ( $\begin{eqnarray*} 1 \leq k \leq 2^n \end{eqnarray*}$ ) von $\begin{eqnarray*} \{1,2\}^n \end{eqnarray*}$ die natürliche Zahl $\begin{eqnarray*} 2^n+k-2 \end{eqnarray*}$ zuordnet, bijektiv ist.

01.11.2008, 16:31

WebFritzi

Auf diesen Beitrag antworten »

Oder so: Sei M die Menge deiner Folgen. Zeige, dass die Abbildung

$\begin{eqnarray*} \phi : M \to \mathbb N,\quad \phi((a_n)_{n\in\mathbb N}) := \sum_{n=0}^\infty (a_{n+1} - 1)\cdot 2^n \end{eqnarray*}$

bijektiv ist.

01.11.2008, 17:04

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von WebFritzi
Oder so: Sei M die Menge deiner Folgen. Zeige, dass die Abbildung

$\begin{eqnarray*} \phi : M \to \mathbb N,\quad \phi((a_n)_{n\in\mathbb N}) := \sum_{n=0}^\infty (a_{n+1} - 1)\cdot 2^n \end{eqnarray*}$

bijektiv ist.

Kannst du mir das vll mal etwas genauer erklären?
Komme nicht so ganz dahinter verwirrt

01.11.2008, 19:59

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Svenja1986
Kannst du mir das vll mal etwas genauer erklären?

Nein, das kann ich leider nicht, wenn du mir nicht sagst, wo deine Probleme liegen.

01.11.2008, 20:35

Svenja1986

Auf diesen Beitrag antworten »

Hm... Einfach, wie du auf diesen Ansatz gekommen bist... Ist mir irgendwie nicht klar... Hammer

02.11.2008, 16:14

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Nun listest du für jedes n die Menge $\begin{eqnarray*} \{1,2\}^n \end{eqnarray*}$ einfach auf, sodass die einzelnen Elemente dieser Menge eine Ordnung haben. Die ist dann einfach durch die Reihenfolge der Auflistung gegeben.

Also so: $\begin{eqnarray*} \{1,2,4,8,16,32,...,2^n\} \end{eqnarray*}$ ?

Zitat:

Original von tmo
Nun zeigst du, dass die Abbildung $\begin{eqnarray*} f:\bigcup_{n \in \mathbb N} \{1,2\}^n \mapsto \mathbb N \end{eqnarray*}$ , die dem k-ten Element ( $\begin{eqnarray*} 1 \leq k \leq 2^n \end{eqnarray*}$ ) von $\begin{eqnarray*} \{1,2\}^n \end{eqnarray*}$ die natürliche Zahl $\begin{eqnarray*} 2^n+k-2 \end{eqnarray*}$ zuordnet, bijektiv ist.

Wie mach ich das?

Neue Frage »

Antworten »

Abzählbar/Überabzählbar

Verwandte Themen