Abzählbarkeit Aufgabe

08.12.2017, 16:50

Snexx_Math

Abzählbarkeit Aufgabe

Hallo zusammen,

folgende Aufgabe bereitet mir, obwohl ich denke Abzählbarkeit verstanden zu haben, direkt Startschwierigkeiten.

Sei M eine Menge. Zeigen Sie:

a) Ist M abzählbar, so ist die Menge aller endlichen Teilmengen von M abzählbar.

b) Ist M endlich, so ist P(M) endlich.

c) Ist M überabzählbar, so ist auch P(M) überabzählbar.

d) Die Menge aller Permutationen $\begin{eqnarray*} \bigcup_{n\geq1}S_n \end{eqnarray*}$ ist abzählbar.

Weiß überhaupt nicht wie ich anfangen soll ....

bei der a) denke ich, dass endliche Teilmengen abzählbar sind, da diese endlich sind. Nun müsste man nur iwie zeigen, dass Die Anzahl solcher endlicher Teilmengen wiederum abzählbar unendlich oder endlich ist. Nur wie ?=!

Bei der b) denke ich nur an die Formel $\begin{eqnarray*} |P(M)|= 2^{|M|} \end{eqnarray*}$ . Wenn nämlich M endlich ist dann kann man die Anzahl der Elemente von M und auch von P(M) bestimmen, somit sind diese Anzahlen endlich und somit abzählbar.

Bei der c) habe ich erst an einen Beweis durch Kontraposition gedacht aber scheint mir iwie nicht ganz so einleuchtend im Nachhinein.

Bei der d) würde ich behaupten, dass man die Mächtigkeit der Menge von jeder Symmetrischengruppe mit $\begin{eqnarray*} n! \end{eqnarray*}$ berechnen kann und da $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ abzählbar ist und es n Symmetrische Gruppen gibt mit Startwert $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ kann man den Satz anwenden: Die Vereinigung abzählbar vieler abzählbarer Mengen ist wieder abzählbar.

LG

Snexx_Math

08.12.2017, 18:18

sibelius84

Auf diesen Beitrag antworten »

Hallo snexx_math,

erstmal: (b) und (d) - sauber! Tanzen

Zu (a) könntest du dir - abweichend vom Standardweg - überlegen, dass sowohl jede abzählbare (=abzählbar-unendliche) Menge, als auch die Menge aller Teilmengen dieser Menge bijektiv abgebildet werden können auf die Menge der "Binärtupel"

$\begin{eqnarray*} \{(a_n)_{n\in\mathbb{N}}\subseteq\{0,1\}\,\mid\,a_n\neq 0 \text{ für höchstens endlich viele }n\in\mathbb{N}\} \end{eqnarray*}$ .

Beispiel für $\begin{eqnarray*} M=\mathbb{N} \end{eqnarray*}$ (kann man sowieso auch oBdA annehmen):

235 aus |N => Umrechnung in binär: $\begin{eqnarray*} 235 = 2^7 + 2^6 + 2^5 + 2^3 + 2^1 + 2^0 = (11101011)_2 \end{eqnarray*}$ . Dies bedeutet, von rechts nach links gelesen: 1, 2, 4, 6, 7, 8 werden 'angeknipst', also die zugehörige Teilmenge von |N ist {1, 2, 4, 6, 7, 8}.

{10,11,12} Teilmenge von |N => Binärtupel ist $\begin{eqnarray*} (111000000000)_2 = 2^{12}+2^{11}+2^{10} = 4096+2048+1024 = 7168\in\mathbb{N} \end{eqnarray*}$ .

Bei (c) würde ich viel einfacher ansetzen: P(M) enthält doch auf jeden Fall schon mal alle einelementigen Teilmengen der Form {m} von M.

LG
sibelius84

08.12.2017, 22:10

Snexx_Math

Auf diesen Beitrag antworten »

Erstmal danke für die nette und hilfreiche Antwort !!! smile

zu a mache ich mir morgen mal Gedanken.

Könnte ich b) und d) genauso aufschreiben ( also als Text ) oder bedarf es einer Formalisierung mit mathematischen Schreibweisen Augenzwinkern

???

und zur c)

Könnte man dann argumentieren : Wenn M bereits überabzählbar ist und wir wissen, dass die Menge solcher Elemente, welche elemente von M als Menge geschrieben, also $\begin{eqnarray*} \{m\} \end{eqnarray*}$ , eine Teilmenge von P(M) ist und wir diese nicht abzählen können, so folgt zwingend , dass wir auch P(M) nicht abzählen können. Denn $\begin{eqnarray*} M \subset P(M) \end{eqnarray*}$

LG

Snexx_Math

09.12.2017, 12:11

sibelius84

Auf diesen Beitrag antworten »

b) könntest du genau so aufschreiben, bei d) ist der Halbsatz "...dass es n symmetrische Gruppen gibt..." etwas merkwürdig. Dies klingt erstmal nach einem Missverständnis, denn zu einer symmetrischen Gruppe S_n gibt es ja n Elemente, die permutiert werden. Vielleicht eher:

"...dass es $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ viele symmetrische Gruppen gibt..." oder "...dass es zu jeder natürlichen Zahl n eine symmetrische Gruppe gibt...", oder so.

c) ist super bis auf die Behauptung $\begin{eqnarray*} M \subset P(M) \end{eqnarray*}$ , das stimmt genau genommen so nicht, da ja für $\begin{eqnarray*} m\in M \end{eqnarray*}$ nicht $\begin{eqnarray*} m\in P(M) \end{eqnarray*}$ , sondern $\begin{eqnarray*} \{m\}\in P(M) \end{eqnarray*}$ gilt. Da würde ich eher schreiben: $\begin{eqnarray*} \lvert M \rvert \leq \lvert P(M) \rvert \end{eqnarray*}$ . Genaue Begründung ist: ...da es mit $\begin{eqnarray*} m\mapsto \{m\} \end{eqnarray*}$ eine injektive Abbildung von M nach P(M) gibt.

09.12.2017, 15:18

Snexx_Math

Auf diesen Beitrag antworten »

Ok super vielen Dank nochmals.

Zitat:

"...dass es zu jeder natürlichen Zahl n eine symmetrische Gruppe gibt..."

klingt sehr gut ! smile

Ich meld mich gegebenfalls nochmal, wenn es mit der a) Probleme gibt.

Aber schonmal Danke für die tolle Hilfe Augenzwinkern

LG

Snexx_Math

11.12.2017, 16:19

Snexx_Math

Auf diesen Beitrag antworten »