beweis potenzmenge

29.07.2005, 01:25

glocke

beweis potenzmenge

hi zusammen.

ich habe folgenden beweis für die anzahl der elemente einer potenzmenge, aber leider gleichzeitig ein verständnisproblem.
hier ist er:

satz:
sei M eine n-elementige menge. sei P=P(M) die menge aller teilmengen von M. dann besteht die potenzmenge P von M aus 2^n elementen.

beweis:
induktionsanfang: n = 0.
M hat kein element. also ist M = {...}. P(M)={{...}}. somit gibt es 2^0 = 1 elemente in P.

induktionsannahme: jede (n-1)-elementige menge habe genau 2^(n-1) verschiedene teilmengen.

induktionsbehauptung: ins M eine menge mit n elementen, so besteht P(M) aus 2^n elementen.

dazu sei M = {a_1,...,a_n}. dann hat P(M´) für M´={a_1, ... , a_(n-1)} nach induktionsannahme genau 2^(n-1) elemente. ist $\begin{eqnarray*} A \in P(M) \end{eqnarray*}$ , dann ist entweder $\begin{eqnarray*} a_n \in A \end{eqnarray*}$ oder $\begin{eqnarray*} a_n \notin A \end{eqnarray*}$ . im zweiten fall gehört A zu P(M´), und im ersten fall ist A´= A \ {a_n} $\begin{eqnarray*} \in \end{eqnarray*}$ P(M´).

und jetzt kommt der abschluß, und den verstehe ich leider nicht.

also besitz P(M) 2^(n-1) + 2^(n-1) = 2*2^(n-1) = 2^n elemente

um es etwas zu präzisieren:
aus dem ersten fall: $\begin{eqnarray*} a_n \in A \end{eqnarray*}$ wird gefolgert, daß A`= A\{a_n} ist. und daraus entsteht dann das zweite 2^(n-1)...aber wie ???

viele grüße
simon

29.07.2005, 02:10

Poff

Auf diesen Beitrag antworten »

RE: beweis potenzmenge

Zitat:

Original von glocke

dazu sei M = {a_1,...,a_n}. dann hat P(M´) für M´={a_1, ... , a_(n-1)} nach induktionsannahme genau 2^(n-1) elemente. ist $\begin{eqnarray*} A \in P(M) \end{eqnarray*}$ , dann ist entweder $\begin{eqnarray*} a_n \in A \end{eqnarray*}$ oder $\begin{eqnarray*} a_n \notin A \end{eqnarray*}$ . im zweiten fall gehört A zu P(M´), und im ersten fall ist A´= A \ {a_n} $\begin{eqnarray*} \in \end{eqnarray*}$ P(M´).

und jetzt kommt der abschluß, und den verstehe ich leider nicht.

also besitz P(M) 2^(n-1) + 2^(n-1) = 2*2^(n-1) = 2^n elemente

das will nichts anderes, als auf verdreht verquerte Weise aussagen,
dass es AUCH 2^(n-1) verschiedene A mit dem Element {a_n} gibt.
Zusammen mit den schon 2^(n-1) Fällen ohne das Element {a_n} ergibt
das dann diese 2 * 2^(n-1) Elemente

29.07.2005, 12:07

glocke

Auf diesen Beitrag antworten »

dankeschön

gut, kann ich (teilweise) nachvollziehen, für eine kleine menge (zb. mit 4 elementen) kann ich mir das auch notieren. aber mit der argumentation an besagter stelle komm ich immer noch nicht zurecht.

hier fängt es an

A´ = A \ {a_n} $\begin{eqnarray*} \in \end{eqnarray*}$ P(M´)

wozu wird das A´ benötigt ?

und wie bekomme ich den bogen zu der aussage, daß es in P(M) ausser den 2^(n-1) elementen aus P(M´) noch 2^(n-1) weitere gibt, die das a_n enthalten ?

es wäre schön, wenn du das etwas "aufdröseln" könntest

Neue Frage »

Antworten »

beweis potenzmenge

Verwandte Themen