Frage von Simonfragtjetzt, 39

wie Löse ich diese Induktion?

Hi, stehe grade voll auf dem Schlauch, wie Löse ich diese Induktion?

Beweisen Sie mittels des Prinzips der vollständigen Induktion für alle n ∈ N: Es gibt genau 2^n verschiedene Teilmengen von {1, . . . , n}...

vielen Dank!

sehe einfach nicht wie ich beginnen soll... der Anfang wäre schon super!

Danke!!!!!!!!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von lks72, 19

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.

Kommentar von kreisfoermig ,

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.

Kommentar von lks72 ,

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.

Antwort
von iokii, 27

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

Antwort
von kreisfoermig, 7

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
von hibiskus001, 27

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

Kommentar von Simonfragtjetzt ,

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

Kommentar von hibiskus001 ,

Du sollst nur beweisen, keine Gleichung aufstellen. Die ist schon vorgegeben.

Keine passende Antwort gefunden?

Fragen Sie die Community