Potenzmenge 2 hoch M

10.04.2009, 16:45

schmouk

Potenzmenge 2 hoch M

Hallo,

dass die Potenzmenge einer Mengen M P(M) immer $\begin{eqnarray*} 2^m, m=card(M) \end{eqnarray*}$ Elemente hat, weiß ich. Macht auch irgendwie Sinn. Aber den Sinn krieg ich nicht ausformuliert.

Deshalb: Wieso ist das denn so, dass immer $\begin{eqnarray*} card(P(M))=2^{card(M)} \end{eqnarray*}$ ?

Grüße,

Schmouky

10.04.2009, 16:47

kiste

Auf diesen Beitrag antworten »

Hallo,

die Frage nach dem Sinn verstehe ich nicht. Es ist eben so und es lässt sich auch sehr leicht(Induktion oder abzählen) beweisen. Was genau willst du den hören?

10.04.2009, 16:55

Mazze

Auf diesen Beitrag antworten »

Fang doch von vorne an. Betrachte eine Menge mit 2 Elementen

$\begin{eqnarray*} \{1,2\} \end{eqnarray*}$

die Potenzmenge P ist dann

$\begin{eqnarray*} P = \{\emptyset, \{1\}, \{2\},\{1,2\}\} \end{eqnarray*}$

Nimm nun eine Menge mit 3 Elementen, und die Potenzmenge P' davon, dann ist

$\begin{eqnarray*} P \subset P' \end{eqnarray*}$ und darüber hinaus musst Du die Mengen $\begin{eqnarray*} x \cup \{3\} ~ x \in P \end{eqnarray*}$ zu P' hinzufügen. Dies verdoppelt die Anzahl der Elemente von P. Man muss sich nur noch klar mache das man so alle Teilmengen erwischt. Das Ganze jetzt immer soweiter und man "erhält" die Formel. Das ist im wesentlichen auch die Beweisidee per vollständiger Induktion.

10.04.2009, 17:26

schmouk

Auf diesen Beitrag antworten »

Ah ja, das versteh ich.

Folgende Aufgabe habe ich hier:

Zitat:

Es sei M eine Menge und $\begin{eqnarray*} 2^M:=\{f:M\rightarrow\{0,1\}\} \end{eqnarray*}$ die Menge aller Abbildungen von M nach $\begin{eqnarray*} \{0,1\} \end{eqnarray*}$ . Zeigen Sie, dass die Potenzmenge P(M) und $\begin{eqnarray*} 2^M \end{eqnarray*}$ von gleicher Mächtigkeit sind, kurz $\begin{eqnarray*} P(M)\sim 2^M \end{eqnarray*}$ , d.h. es besteht eine Bijektion zwischen P(M) und $\begin{eqnarray*} 2^M \end{eqnarray*}$ .

Ich würde halt so ran gehen.
Sind beispielsweise im allg. zwei Mengen X,Y gleich mächtig, ist es möglich eine injektive Abbildung von X auf Y zu definieren. (Da der Satz f(x)=f(x') => x=x' für alle x in X gelten kann).

Für diese Abbildung würde dann auch f(X)=Y gelten und damit wäre sie surjektiv. Also bijektiv.

dass $\begin{eqnarray*} card(2^M) = 2^m, m=card(M) \end{eqnarray*}$ ist klar.

Bleibt nur noch z.z. dass $\begin{eqnarray*} card(P(M))=2^m \end{eqnarray*}$ .

oder?

10.04.2009, 19:32

Romaxx

Auf diesen Beitrag antworten »

Zitat:

Bleibt nur noch z.z. dass $\begin{eqnarray*} card(P(M))=2^m \end{eqnarray*}$ .

Was du zeigen sollst ist:

$\begin{eqnarray*} card(P(M))=card(2^M) \end{eqnarray*}$

Das geht am Besten per Induktion.

Gruß

11.04.2009, 13:19

schmouk

Auf diesen Beitrag antworten »

hachherrje

11.04.2009, 15:35

Elvis

Auf diesen Beitrag antworten »

Potenzmenge
Hallo, was wollt ihr denn immer mit vollständiger Induktion und Kardinalität ? Ist doch ganz simpel, wenn man die Aufgabe direkt angeht (so wie es im "Zitat" von schmouk vorgeschlagen wird). Voraussetzung: $\begin{eqnarray*} M \end{eqnarray*}$ sei eine endliche Menge.
1. Man nehme ein Element der Potenzmenge $\begin{eqnarray*} N\in P(M) \end{eqnarray*}$ , also eine Teilmenge $\begin{eqnarray*} N\subset M \end{eqnarray*}$ . Diesem Element ordnet man die charakteristische Funktion $\begin{eqnarray*} f_N: M\rightarrow \lbrace 0,1\rbrace \end{eqnarray*}$ zu, also $\begin{eqnarray*} \operatorname {f_N}(n)=\begin {cases}1 &n\in N\\0 &n\in M-N\end {cases} \end{eqnarray*}$
2. Umgekehrt gehört zu einer Funktion $\begin{eqnarray*} f: M\rightarrow \lbrace 0,1\rbrace \end{eqnarray*}$ eine wohldefinierte Teilmenge $\begin{eqnarray*} N_f:=\lbrace m\in M: f(m)=1\rbrace \end{eqnarray*}$
Damit haben wir die Bijktion zwischen $\begin{eqnarray*} P(M) \end{eqnarray*}$ und $\begin{eqnarray*} 2^M \end{eqnarray*}$ , und dass $\begin{eqnarray*} card(2^M)=2^{card(M)} \end{eqnarray*}$ ist, dürfte ja offensichtlich sein.

11.04.2009, 15:38

schmouk

Auf diesen Beitrag antworten »

Danke. Das versteh ich. Wink

11.04.2009, 15:57

Elvis

Auf diesen Beitrag antworten »

Potenzmenge
War mir ein Vergnügen smile

Übrigens meinte ich "Bijektion" und nicht "Bijktion" Augenzwinkern

11.04.2009, 20:09

Elvis

Auf diesen Beitrag antworten »

Potenzmenge
Habe ich irgendwo die Voraussetzung gebraucht, daß $\begin{eqnarray*} M \end{eqnarray*}$ eine endliche Menge ist ? verwirrt

11.04.2009, 22:35

papahuhn

Auf diesen Beitrag antworten »

RE: Potenzmenge
Ja, nur dann macht der Term $\begin{eqnarray*} 2^{card(M)} \end{eqnarray*}$ einen Sinn.

12.04.2009, 09:26

Elvis

Auf diesen Beitrag antworten »

Potenzmenge
GENAU, papahuhn.

Die Bijektion $\begin{eqnarray*} P(M) \leftrightarrow 2^M \end{eqnarray*}$ funktioniert auch für unendliche Mengen. Aber nur für $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ weiss man genau, wieviele Dualzahlen mit $\begin{eqnarray*} n \end{eqnarray*}$ Ziffern es gibt (nämlich genau $\begin{eqnarray*} 2^n \end{eqnarray*}$ ).

Neue Frage »

Antworten »

Potenzmenge 2 hoch M

Verwandte Themen