Induktion die dritte

19.04.2014, 20:27

Van Thom

Induktion die dritte

Ich soll folgendes per Induktion beweisen: Die Anzahl $\begin{eqnarray*} A_n \end{eqnarray*}$ aller Teilmengen einer n-elementigen Menge ist gegeben durch $\begin{eqnarray*} A_n=2^n \end{eqnarray*}$ .

So wie ich es verstanden habe soll ich zeigen das die Mächtigkeit der Potenzmenge gleich $\begin{eqnarray*} 2^n \end{eqnarray*}$ ist. Also formal ausgedrückt $\begin{eqnarray*} |P(A_n)|=2^n \end{eqnarray*}$ .

I.A.: $\begin{eqnarray*} n=1 \end{eqnarray*}$

zu zeigen: $\begin{eqnarray*} |P(A_n)|=2^n \end{eqnarray*}$

Beweis: $\begin{eqnarray*} A_1=\{a_1\} \end{eqnarray*}$ also $\begin{eqnarray*} P(A_1)=\{\{a_1\},\emptyset\} \end{eqnarray*}$ demnach ist $\begin{eqnarray*} |P(A_1)|=2^1=2 \end{eqnarray*}$

I.S.: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

Voraussetzung: $\begin{eqnarray*} |P(A_n)|=2^n \end{eqnarray*}$

zu zeigen: $\begin{eqnarray*} |P(A_{n+1})|=2^{n+1} \end{eqnarray*}$

Beweis:

$\begin{eqnarray*} P(A)=P(\{a_1,a_2,...,a_{n+1}\})=\{\{a_1,...,a_n\}\cup\{\emptyset\}\cup\{a_1\}\cup\{a_{n+1}\}\} \end{eqnarray*}$

Nun weiß ich nicht mehr weiter. Kann mir jemand helfen?

20.04.2014, 10:04

bijektion

Auf diesen Beitrag antworten »

Zitat:

zu zeigen: $\begin{eqnarray*} |P(A_n)|=2^n \end{eqnarray*}$

Rein formal ist zu zeigen, dass $\begin{eqnarray*} \mathcal{P}(A)=2^n \end{eqnarray*}$ gilt, falls $\begin{eqnarray*} A \end{eqnarray*}$ eine n-elementige Menge ist, also auch $\begin{eqnarray*} |A_n|=2^n \end{eqnarray*}$ .

Beachte beim Induktionsschritt die Tatsache, dass jede Teilmenge von $\begin{eqnarray*} A=\left\{a_1, \dots ,a_n,a_{n+1}\right\} \end{eqnarray*}$ das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält. Über Teilmengen, die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ nicht enthalten, weißt du ja etwas; wieviele gibt es davon? Und wieviele Teilmengen gibt es, die das Element enthalten?

20.04.2014, 10:24

Van Thom

Auf diesen Beitrag antworten »

Wie meinst du das?

Zitat:

Beachte beim Induktionsschritt die Tatsache, dass jede Teilmenge von $\begin{eqnarray*} A=\left\{a_1, \dots ,a_n,a_{n+1}\right\} \end{eqnarray*}$ das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält. Über Teilmengen, die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ nicht enthalten, weißt du ja etwas;

Du schreibst ja einmal das jede Teilmenge von $\begin{eqnarray*} A \end{eqnarray*}$ das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält und einmal gibt es Teilmengen die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ nicht enthalten?

Wenn jede Teilmenge von $\begin{eqnarray*} A \end{eqnarray*}$ das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält würde es folgendermaßen aussehen:

$\begin{eqnarray*} P(A)=(\{a_1,a_2,...,a_{n+1}\})=\{\{a_1,...,a_{n+1}\},\{\emptyset ,a_{n+1}\},\{a_1,a_{n+1}\},\{a_{n+1}\}\} \end{eqnarray*}$

20.04.2014, 10:41

bijektion

Auf diesen Beitrag antworten »

Zitat:

Oh, da hab ich den Satz zu früh beendet Hammer

Es muss heißen: Beachte beim Induktionsschritt die Tatsache, dass jede Teilmenge von $\begin{eqnarray*} A=\left\{a_1, \dots ,a_n,a_{n+1}\right\} \end{eqnarray*}$ das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält oder eben nicht.

20.04.2014, 10:54

Van Thom

Auf diesen Beitrag antworten »

Also wenn ich es bis hierhin korrekt gemacht habe steht erstmal folgendes hier:
$\begin{eqnarray*} P(A)=P(\{a_1,a_2,...,a_{n+1}\})=\{\{a_1,...,a_n\}\cup\{\emptyset\}\cup\{a_1\}\cup\{a_{n+1}\}\}=\{\{a_1,...,a_n\}\cup\underbrace{\{\emptyset\}\cup\{a_1\}}_{\text{Nach Voraussetzung}}\cup\{a_{n+1}\}\} \end{eqnarray*}$ . Demnach gibt es noch eine Teilmenge die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthält und eine Teilmenge die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ nicht enthält. Ja?

20.04.2014, 11:13

bijektion

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} P(A)=P(\{a_1,a_2,...,a_{n+1}\})=\{\{a_1,...,a_n\}\cup\{\emptyset\}\cup\{a_1\}\cup\{a_{n+1}\}\}=\{\{a_1,...,a_n\}\cup\underbrace{\{\emptyset\}\cup\{a_1\}}_{\text{Nach Voraussetzung}}\cup\{a_{n+1}\}\} \end{eqnarray*}$

Ich verstehe nicht wie du das meinst. Warum vereinigst du $\begin{eqnarray*} \left\{a_1, \dots,a_n\right\} \end{eqnarray*}$ mit $\begin{eqnarray*} \left\{a_1\right\} \end{eqnarray*}$ ? Außerdem hätte diese Potenzmenge auch nur (n+1) Elemte.

Es ist doch zu zeigen, dass $\begin{eqnarray*} \mathcal{P}(A)=2^{n+1} \end{eqnarray*}$ gilt, wenn $\begin{eqnarray*} A=\left\{a_1, \dots ,a_n,a_{n+1}\right\} \end{eqnarray*}$ .

Offenbar sind in der Potenzmenge von A auch alle Teilmengen enthalten, die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ nicht enthalten, denn es ist $\begin{eqnarray*} \mathcal{P}(A \backslash \left\{a_{n+1}\right\}) \subseteq \mathcal{P}(A) \end{eqnarray*}$ .
Die Induktionsvoraussetzung sagt aber gerade etwas über n-elementige Mengen, denn es gilt doch nach nach Voraussetzung $\begin{eqnarray*} | \mathcal{P}(A \backslash \left\{a_{n+1}\right\})|=2^n \end{eqnarray*}$ .

Wieviele Teilmengen, die $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ enthalten, muss es nun geben, damit die Behauptung wahr ist?
Du musst nur noch abzählen, in wievielen Teilmengen von A das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ liegt, das ist aber leicht.

20.04.2014, 11:31

Van Thom

Auf diesen Beitrag antworten »

Wenn $\begin{eqnarray*} | \mathcal{P}(A \backslash \left\{a_{n+1}\right\})|=2^n \end{eqnarray*}$ gilt dann gibt es noch eine Teilmenge in der das Element $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ liegt? da $\begin{eqnarray*} |A\cup\{a_{n+1}\}|=|\mathcal{P}(\{a_1,...,a_{n+1}\})|=2^{n+1} \end{eqnarray*}$ ist? Langsam bin ich verwirrt ...

21.04.2014, 13:04

Van Thom

Auf diesen Beitrag antworten »

RE: Induktion die dritte
Kann mir noch jemand helfen?

21.04.2014, 13:31

Stevö

Auf diesen Beitrag antworten »

hi,
du weisst, dass $\begin{eqnarray*} \mathcal |P(A_n)|=2^n \end{eqnarray*}$
Die Potenzmenge von $\begin{eqnarray*} A_{n+1} \end{eqnarray*}$ enthält ja die Potenzmenge von $\begin{eqnarray*} A_n \end{eqnarray*}$ , also $\begin{eqnarray*} \mathcal P(A_n)\subset \mathcal P(A_{n+1}) \end{eqnarray*}$ .
Man kann dann schreiben $\begin{eqnarray*} |\mathcal P(A_{n+1})|=|\mathcal P(A_n)|+|\{\{a_{n+1}\},\,\{\cdots\}\}| \end{eqnarray*}$
Du musst dir nur noch überlegen wie viele Elemente das $\begin{eqnarray*} \{\{a_{n+1}\},\,\{\cdots\}\} \end{eqnarray*}$ enthält
lg

21.04.2014, 13:48

Van Thom

Auf diesen Beitrag antworten »

Wenn ich das ganze etwas umschreibe und bei der Notation bleibe die ich am Anfang benutzt habe müsste es ja folgendermaßen aussehen:

$\begin{eqnarray*} P(A)=P(\{a_1,a_2,...,a_{n+1}\})=\{\{a_1,...,a_n\}\cup\{\emptyset\}\cup\{a_1\}\cup\{a_{n+1}\}\}=\{\{a_1,...,a_n\}\cup\underbrace{\{\emptyset\}\cup\{a_1\}}_{\text{Nach Voraussetzung}}\cup\{a_{n+1}\}\} \end{eqnarray*}$

Da die Menge $\begin{eqnarray*} \{\{a_1,...,a_n\}\cup\{a_{n+1}\}\} \end{eqnarray*}$ ebenfalls $\begin{eqnarray*} 2 \end{eqnarray*}$ Elemente enthält müsste es ja $\begin{eqnarray*} 2^n+2^n= 2\cdot 2^n=2^{n+1} \end{eqnarray*}$ . Damit wäre der Beweis erbracht?

21.04.2014, 14:07

Stevö

Auf diesen Beitrag antworten »

ein Tipp am Rande: Elemente einer Menge trennt man mit Beistrich, soll ja eine Aufzählung sein. Genauso zählt man Elemente einer Potenzmenge auf, also kein $\begin{eqnarray*} \cup \end{eqnarray*}$
$\begin{eqnarray*} \mathcal P(A_n) \end{eqnarray*}$ sieht doch so aus:
$\begin{eqnarray*} \{\{\emptyset\},\{a_1\},\cdots ,\{a_n\},\{a_1,a_2\}\},\cdots,\{a_1,a_n\},\cdots ,\{a_1,a_2,a_3\},\cdots ,\{a_1,a_2,\cdots ,a_n\}\} \end{eqnarray*}$

21.04.2014, 14:17

Van Thom

Auf diesen Beitrag antworten »

Ok, dann noch einmal. $\begin{eqnarray*} |\mathcal P(A_{n+1})|=|\mathcal P(A_n)|+|\{\{a_{n+1}\},\,\{\cdots\}\}|=\underbrace{|\mathcal P(A_n)|}_{\text{Nach Voraussetzung}}+\{\{a_{n+1}\},\,\{\cdots\}\}| \end{eqnarray*}$

Die Mächtigkeit der Menge $\begin{eqnarray*} \{\{a_{n+1}\},\,\{\cdots\}\} \end{eqnarray*}$ müsste dann $\begin{eqnarray*} 2^n \end{eqnarray*}$ sein also insgesamt $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ . Genau erklären kann ich mir das allerdings nicht wieso die Menge ebenfalls $\begin{eqnarray*} 2^n \end{eqnarray*}$ Elemente enthält.

21.04.2014, 23:27

Stevö

Auf diesen Beitrag antworten »

versuchs mal mit einem Beispiel, sie dir die Potenzmengen von konkreten Mengen an und vergleiche sie miteinander, zB
$\begin{eqnarray*} A_1=\{1\} \end{eqnarray*}$
$\begin{eqnarray*} A_2=\{1,2\} \end{eqnarray*}$
$\begin{eqnarray*} A_3=\{1,2,3\} \end{eqnarray*}$

Neue Frage »

Antworten »

Induktion die dritte

Verwandte Themen