Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Potenzmenge 2^n beweisen

Potenzmenge 2^n beweisen

Universität / Fachhochschule

Komplexe Analysis

Tags: Analysis, Potenzmenge

anonymous

19:40 Uhr, 10.01.2010

Hallo!

Ich versuche mich gerade an folgender Aufgabe:
Mittels vollständiger Induktion zu beweisen ist, wenn
Menge

A = n,

dann folgt
Potenzmenge

P (A) = 2^{n}

Induktionsanfang ist klar:

n = 0

ergibt

2^{0} = 1

(Nullelement),

n = 1

ergibt

2^{1} = 2

(Nullelement und

z

. B.

{a})

Nun muss ich ja beweisen, dass die Annahme auch für

n + 1

gilt.
In anderen Foren/Beiträgen habe ich jetzt gelesen, dass man dazu die Potenzmenge in 2 Teile teilt, wobei eine ein bestimmtes Element enthält (mit den dazugehörigen Teilmengen, die dieses Element beinhalten) und eine, die dieses nicht enthält.

Ich habe mir das jetzt mit einem >kleinen< Beispiel erklärt:

A = {1,2,3}

P (A) = 1,2,3,12,13,23,123,0 \Rightarrow 2^{3}

(Klammern fehlen, ich weiß)
geteilt:

P 1 (A) = 0,1,2,12

P 2 (A) = 3,13,23,123

Was ich nicht verstehe:
Sind also immer beide Mengen gleichgroß wenn ich nach einem Element trenne?!
Und wieso habe ich dann trotzdem bei beiden Mengen

2^{n}

Auswahlmöglichkeiten, was dann zusammenaddiert die gewünschen

2^{n + 1}

ergibt?
Die Mengen sind doch um die Hälfte kleiner geworden..? Habe absolut keinen Überblick bzw keinen Ansatz wie man das jetzt richtig begründet?

: - (

Wäre über Hilfe sehr dankbar!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DK2ZA aktiv_icon

19:55 Uhr, 10.01.2010

Ich packe das von der anderen Seite an:

Die Potenzmenge von

{1,2,3}

ist

{{}, {1}, {2}, {3}, {12}, {13}, {23}, {123}}

mit

2^{3}

Elementen.

Nun füge ich ein viertes Element hinzu:

{1,2,3,4}

Die Potenzmenge dieser Menge enthält

{}, {1}, {2}, {3}, {12}, {13}, {23}, {123}

und dazu noch alle diese Mengen mit der zusätzlichen 4:

{4}, {14}, {24}, {34}, {124}, {134}, {234}, {1234}

Dabei hat sich die Zahl der Elemente dieser Potenzmenge gerade verdoppelt auf

2^{3 + 1}

.

GRUSS, DK2ZA

anonymous

20:40 Uhr, 10.01.2010

So wirklich habe ich das noch nicht verstanden.. Das ist doch jetzt noch kein Beweis, nur weil ich mir denke wie es ist? Wie schreibt man das denn jetzt formell richtig auf?

michaL aktiv_icon

21:42 Uhr, 10.01.2010

Hallo Miri,

hinter unklarer Schreibweise stecken auch immer unklare Gedanken. Deshalb sollst du an einem (recht) einfachen Beispiel zeigen, dass du sowolh zu klaren Gedanken wie auch zu klarer Schreibweise in der Lage bist.

Induktionsanfang ist wohl klar.

Induktionsvoraussetzung: Für alle Mengen

M

mit

∣ M ∣ \leq n

gilt:

∣ ℙ (M) ∣ = 2^{∣ M ∣}

Induktionsschluss: Jetzt gelte

∣ M ∣ = n + 1

. Sei

x \in M

. Definieren wir uns die Menge

A := M \ {x}

B := ℙ (A)

und

C := ℙ (M) \ B

.

Zunächst ist wohl klar, dass

∣ A ∣ = n

, infolge dessen gilt

∣ B ∣ = ∣ ℙ (A) ∣ = 2^{n}

.

Nun wollen wir zeigen, dass

B

und

C

gleich viele Elemente haben, d.h.

∣ B ∣ = ∣ C ∣

gilt. Dazu definieren wir eine Abbildung

φ : B \to C

X \mapsto X \overset{•}{\cup} {x}

. "

\overset{•}{}

" heißt, dass die zu vereinigenden Mengen disjunkt sind. Das wiederum heißt, dass

x

nicht schon in der Menge

X

liegt.

Wir müssen beweisen, dass die Abbildung bijektiv ist. Dann haben nämlich

B

und

C

gleich viele Elemente (die Elemente von

B

bzw.

C

sind selbst wieder Mengen).

Also los: injektiv: Wenn

f (X) = f (Y)

gilt, d.h.

X \overset{•}{\cup} {x} = Y \overset{•}{\cup} {x}

, dann gilt also

X \subseteq Y \overset{•}{\cup} {x}

. Weil aber

X

und

{x}

disjunkt sind, gilt also schon

X \subseteq Y

.
Analog beweist man

Y \subseteq X

. Also folgt

X = Y

, woraus folgt, dass

f

injektiv ist.

surjektiv: Sei

Y \in C

, d.h.

Y

ist irgendeine Teilmenge von

M

, die

X

enthält. (Enthielte sie

x

nicht, so wäre sie nach Definition in

B

und NICHT in

C

.)
Dann ist

X := Y \ {x}

eine Menge, die

X

NICHT enthält, d.h. es gilt

X \in B

.
Sicher kannst du leicht nachvollziehen, dass

X \overset{•}{\cup} {x} = Y

d.h.

f (X) = Y

ist. Damit ist

f

auch surjektiv.

Da

f

surjektiv und injektiv ist, heißt das,

f

ist bijektiv. Zwei Mengen, zwischen denen eine Bijektion angegeben werden kann, haben insbesondere gleich viele Elemente, d.h. es gilt

∣ C ∣ = ∣ B ∣ = 2^{n}

.

Nun gilt noch:

ℙ (M) = B \overset{•}{\cup} C

, woraus

∣ ℙ (M) ∣ = ∣ B ∣ + ∣ C ∣ = 2^{n} + 2^{n} = 2 \cdot 2^{n} = 2^{n + 1}

folgt.

Mfg Michael

anonymous

14:16 Uhr, 11.01.2010

Danke Michael - Kann das Verfahren nun nachvollziehen!

706758

706398

	Status: nicht eingeloggt	Noch nicht registriert?