Suche einen mathematischen Beweis (Aus der PE)

[Wastl]

Kann mir jemand den mathematischen Beweiß, dass die Anzahl der Teilmengen einer endlichen Menge von n Elementen gleich 2^n ist schreiben? Ich finde den leider nicht, er sollte am besten in Form einer vollständigen Induktion sein. Ich probiere gerade sie selbst aufzustellen schaffe es aber leider nicht.... bitte helft mir

[Sur-Taka]

also grundlegend sehe ich darin eher ein kombinatorisches problem... also, wie viele möglichkeiten gibt es, verschiedene elemente miteinander zu kombinieren? diese anzahl lässt sich recht einfach ermitteln, das wäre nämlich n!... in diesem fall hätte das ganze aber eine ordnung, was bei mengen ja im allgemeinen nicht der fall ist^^ also genau genommen beschreiben alle diese möglichkeiten den gleichen fall^^ also, vielleicht sollten wir uns lieber anschauen, wie viele möglichkeiten es gibt k elemente aus diesen n herauszusuchen... das macht man dann eben für k = 0,1,2...,n-1,n... im endeffekt wäre also das ergebnis (n über 0) + (n über 1) + (n über 2) + ... + (n über n-1) + (n über n)...
ähm... vielleicht hilft uns das ja weiter^^

also, nehmen wir mal den fall n = 1...
Behauptung:
Anzahl der Teilmengen ist 2^1 = 2
Überprufung:
Anzahl der Teilmengen:
(1 über 0) + (1 über 1) = 1! / (0! * 1!) + 1! / (1! * 0!) = 1 + 1 = 2
stimmt also für n = 1...
...
äh, ich hab keine ahnung wie ich jetzt weitermachen muss xD
der übliche weg der vollständigen induktion wäre ja jetzt, dass man das ganze für n+1 beweist... das problem ist hier eben, dass sich mit n+1 alle summanden verändern und nicht nur einer hinzukommt^^

[Heinzi]

Sei Beh wie in Aufgabenstellung (siehe Einleitungspost).

(IA) n=0

Dies ist die leere Menge - sie hat außer sich selbst keine anderen Teilmengen, also nur 2^0 = 1 Teilmengen.

(IV) Es gelte die Behauptung für ein beliebiges, aber festes n >= 0.

(IS) Zeige nun unter (IV), dass Beh dann auch für n+1 gilt.

Sei hierzu angenommen, dass die k-elementigen Mengen alle die Form {1,2,3,...,k} haben, dies kann OE angenommen werden, denn sonst überführe die Mengen per Bijektion in eine solche.

M:={1,2,3,...,n,n+1} hat auch alle Teilmengen von N:={1,2,3,...,n}, dies sind nämlich all ihre Teilmengen, die nicht das Element n+1 enthalten.
Somit haben nach (IV) M und N schonmal 2^n gemeinsame Teilmengen.

Das Element n+1 kann nun jeder dieser Teilmengen hinzugefügt werden und wir erhalten somit 2^n neue Teilmengen. Weitere Teilmengen gibt es nicht. Denn gäbe es eine, dann wäre sie durch entfernen des Elements n+1 auch Teilmenge von N -> Widerspruch.

Wir haben also 2^n + 2^n = 2^(n+1) Teilmengen von M => Beh.

q.e.d.

[Harald]

Sei M besagte Menge.
Vollst. Induktion über n=|M|:
n=1: |M_1|=1 => o.B.d.A. sei M={x} => P(M) = {{x}, ∅} => |P(M)| = 2 = 2^1 <-- passt (P(M) bezeichne die Potenzmenge von M)

Annahme sei für n bel, aber fest bewiesen.

n -> n+1

|M_(n+1)|= n+1.
Sei o.B.d.A. M_(n+1) = {x_1,...., x_n, x_(n+1)}
Nun gilt M_n = {x_1,...., x_n} ⊂ M_(n+1) und |M_n| = n
Somit |P(M_n)|=2^n und P(M_n) ⊂ P(M_(n+1))

Sei ausserdem oBdA P(M_n) = {X_1,..., X_(2^n)}
Dann gilt:
P(M_(n+1)) = {X_1,..., X_(2^n), {x_n+1} ∪ X_1,..., {x_n+1} ∪ X_(2^n)} = P(M) ∪ {{x_n+1} ∪ X_1,..., {x_n+1} ∪ X_(2^n)}

Offensichtlich: |{{x_n+1} ∪ X_1,..., {x_n+1} ∪ X_(2^n)}| = 2^n

Also folgt |P(M) ∪ {{x_n+1} ∪ X_1,..., {x_n+1} ∪ X_(2^n)}| = |P(M)| + |{{x_n+1} ∪ X_1,..., {x_n+1} ∪ X_(2^n)}| = 2^n + 2^n = 2*2^n = 2^(n+1)

q.e.d.

Hmmm, ehrlich gesagt kein schöner Beweis, irgendwie nich wirklich sauber mathematisch denke ich, da vieles halt scheinbar vom Himmel fällt... Is aber eigtl alles ziemlich logisch, keine Ahnung, ob das reicht...


Edit: Ok, ich denke, Heinzis Beweis ist etwas besser^^

[Sur-Taka]

Sei Beh wie in Aufgabenstellung (siehe Einleitungspost).

(IA) n=0

Dies ist die leere Menge - sie hat außer sich selbst keine anderen Teilmengen, also nur 2^0 = 1 Teilmengen.

(IV) Es gelte die Behauptung für ein beliebiges, aber festes n >= 0.

(IS) Zeige nun unter (IV), dass Beh dann auch für n+1 gilt.

Sei hierzu angenommen, dass die k-elementigen Mengen alle die Form {1,2,3,...,k} haben, dies kann OE angenommen werden, denn sonst überführe die Mengen per Bijektion in eine solche.

M:={1,2,3,...,n,n+1} hat auch alle Teilmengen von N:={1,2,3,...,n}, dies sind nämlich all ihre Teilmengen, die nicht das Element n+1 enthalten.
Somit haben nach (IV) M und N schonmal 2^n gemeinsame Teilmengen.

Das Element n+1 kann nun jeder dieser Teilmengen hinzugefügt werden und wir erhalten somit 2^n neue Teilmengen. Weitere Teilmengen gibt es nicht. Denn gäbe es eine, dann wäre sie durch entfernen des Elements n+1 auch Teilmenge von N -> Widerspruch.

Wir haben also 2^n + 2^n = 2^(n+1) Teilmengen von M => Beh.

q.e.d.
ach verdammt, wenn mans liest, ist es so einfach -.-