wie Löse ich diese Induktion?

...komplette Frage anzeigen

4 Antworten

Nehme eine n+1 elementige Menge, n>1. Dann betrachte zwei Mengen, einmal eine n elementige Teilmenge der oberen, nämlhcj ohne das erste Element, und eine Teilmenge ohne das zweite Element. Beide haben nach Induktionsvoraussetzung 2^n Teilmengen, also die Gesamtmenge demnach 2 • 2^n = 2^(n+1) Teilmengen.

Antwort bewerten Vielen Dank für Deine Bewertung
kreisfoermig 28.10.2016, 08:57

Das Argument ist Unsinn. 1. du misst die Kardinalität der Teilmengen statt der von Mengen von Teilmengen, und 2. auch wenn du dies tätest 2.1 die Vereinigung der zwei Mengen von Teilmengen ist nicht gleich der ganzen Potenzmenge (es gibt keine Teilmeng mit beiden Elementen) und 2.2 die zwei Mengen von Teilmengen sind nicht einmal disjunkt (es gibt eine Teilmenge ohne beide Elemente), sodass du die Kardinalität nicht einfach so addieren kannst.

0
lks72 28.10.2016, 13:24
@kreisfoermig

Hab auch nicht richtig nachgedacht, schludrig geschrieben. Wollte eigentlich schreiben, einmal nimmt man eine Teilmenge von dieser n+1 elementigen Menge mit dem ersten Element und einmal ohne das erste Element (das zweite Element tut ja hier nichts zur Sache), dann sind die beiden Teilmengenbereiche auch disjunkt. In beiden Fällen gibt es 2^n Teilmengen, einmal mit und einmal ohne das erste Element.

0

Bezeichne mit X⁽ⁿ⁾ die Menge {1; 2; …; n}.

Behauptung. |P(X⁽ⁿ⁾)| = 2ⁿ für alle n∈ℕ.

Beweis.

lA. n=Ø. Dann gilt X⁽⁰⁾ = Ø und damit P(X⁽⁰⁾)=P(Ø)={Ø}, daher |P(X⁽⁰⁾)| = 1 = 2⁰.

lV. Sei n≥0. Angenommen, |P(X⁽ⁿ⁾)| = 2ⁿ.

lS. Betrachte X⁽ⁿ⁺¹⁾ = X⁽ⁿ⁾ u {n+1}. Zunächst zerlegt man die Potenzmenge wie folgt

P(X⁽ⁿ⁺¹⁾) = {A | A∈P(X⁽ⁿ⁺¹⁾) & n+1∈A}
u {A | A∈P(X⁽ⁿ⁺¹⁾) & n+1∉A}
= S₀ u S₁,

wobei

S₀ := {A | A∈P(X⁽ⁿ⁺¹⁾) & n+1∉A}
= {A | A⊆X⁽ⁿ⁺¹⁾(=X⁽ⁿ⁾u{n+1}) & n+1∉A}
= {A | A⊆X⁽ⁿ⁾}
= P(X⁽ⁿ⁾)

und

S₁ := {A | A∈P(X⁽ⁿ⁺¹⁾) & n+1∈A}.

Per Induktion gilt also

|S₀| = |P(X⁽ⁿ⁾)| = 2ⁿ.

Per Konstruktion ist es klar, dass S₀ und S₁ disjunkt sind, sodass per Definition von Kardinaladdition

|S₀| + |S₁| = |S₀ ∪ S₁|.

Es bleibt, die Kardinalität von S₁ zu bestimmen. Man konstruiere hierfür

ƒ : P(X⁽ⁿ⁾) –—→ P(X⁽ⁿ⁺¹⁾)
: A ⟼ A u {n+1}.

Dies ist offensichtlich injektiv, denn g : B⟼BnX⁽ⁿ⁾ invertiert die Funktion nach links. Darum gilt per Definition von Kardinalität als bijektive Gleichmächtigkeit

|Bild ƒ| = |P(X⁽ⁿ⁾)| = 2ⁿ (per Induktion).

Nun gilt

Bild ƒ = {Au{n+1} | A∈P(X⁽ⁿ⁾)}
= {A | A∈P(X⁽ⁿ⁾u{n+1}) & n+1∈A}
= {A | A∈P(X⁽ⁿ⁺¹⁾) & n+1∈A}
= S₁

Darum

|P(X⁽ⁿ⁺¹⁾)| = |S₀ ∪ S₁|
= |S₀| + |S₁|
= |S₀| + |Bild ƒ|
= 2ⁿ+2ⁿ
= 2ⁿ⁺¹.

Also gilt die Behauptung per Induktion.                                                   QED.

Antwort bewerten Vielen Dank für Deine Bewertung

Für den Induktionsanfang musst du zeigen, dass die Menge {1} genau 2^1=2 Teilmengen hat, die kannst du sogar explizit hinschreiben.

Antwort bewerten Vielen Dank für Deine Bewertung

Induktion läuft über n. Induktionsanfang bei n=1, dann Induktionsschritt.

Antwort bewerten Vielen Dank für Deine Bewertung
Simonfragtjetzt 24.10.2016, 21:10

ja nur wie stelle ich die Gleichung auf, da liegt das Problem... Danke!

0

Was möchtest Du wissen?