Mengen und bijektive Abbildungen

Question

Aufgabe:

Für eine Menge M bezeichne P(M) die Menge aller Teilmengen von M.

I) Sei |M|=n. Berechnen Sie die Anzahl der Elemente von P(M).

II) Zeigen Sie, dass keine bijektive Abbildung f:ℕ→P(ℕ) existiert.

Hinweis: Betrachten Sie die Menge A:={n ∈ ℕ|n ∉ f(n)}.

Problem/Ansatz:

Bin im ersten Semester, hatte meine erste Vorlesung und bin einfach total verwirrt.

Ich weiß, dass die Lösung für I) 2ⁿ ist aber keine Ahnung wie ich es Beweise.

Answer 1

Aloha :)

zu I) ohne vollständige Induktion

Wenn du eine \(n\)-elementige Menge \(M\) hast, kannst du daraus \(\binom{n}{0}\) leere Teilmengen auswählen (die leere Menge ist auch als eine Menge definiert), du kannst daraus \(\binom{n}{1}\) 1-elementige Teilmengen auswähen, du kannst daraus \(\binom{n}{2}\) 2-elementige Teilmengen auswählen und so weiter bis zu \(\binom{n}{n}\) n-elementigen Teilmengen. Die Gesamtzahl aller Teilmengen von \(M\) ist daher:

$$\left|P(M)\right|=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum\limits_{k=0}^{n}\binom{n}{k}=\sum\limits_{k=0}^{n}\binom{n}{k}\cdot1^{n-k}\cdot1^k$$$$\phantom{\left|P(M)\right|}=(1+1)^n=2^n$$Am Ende der Rechnung kam die allgemeine binomische Formel zum Einsatz:$$(a+b)^n=\sum\limits_{k=0}^n\binom{n}{k}a^{n-k}\cdot b^k$$

zu II)

siehe Vorschlag von oswald.

Answer 2

I) Ist M_n = {1, ..., n} und M_n+1 = {1, ..., n+1}, dann ist jede Teilmenge von M_n+1 entweder

• eine Teilmenge von M_n, oder
  
• eine Menge die man bekommt indem man zu einer Teilmenge von M_n das Element n+1 hinzufügt.

Das kann man als Grundlage für eine vollständige Induktion verwenden.

II) Angenommen es gibt ein solches f. Sei n = f^-1(A). Dann ist

(1)        f(n) = A

laut Definition von n. Außerdem ist

(2)        n ∉ f(n),

laut Definition von A. Wegen (1) und (2) ist also auch

(3)        n ∉ A.

Aus (3) folgt, dass n ∉ f(n) nicht sein kann (wäre n ∉ f(n), dann wäre n ∈ A). Also ist

(4)        n ∈ f(n).

(2) und (4) widersprechen sich.

Comments

Ich weiß nicht wie man eine vollständige Induktion durchführt.

---

Weißt du was eine vollständige Induktion ist?

---

Nicht wirklich. Zumindest kann ich in dem Zusammenhang nichts damit anfangen. Hatte letzte Woche erst meine erste Vorlesung.

---

Hilf mir bitte!

Answer 3

Für I gibt es einige Möglichkeiten, kennst du

"vollständige Induktion" ?

oder vielleicht hattet ihr was über die Binomialkoeffizienten.

Damit würde es so gehen:

Man betrachtet die Teilemengen nach ihrer Elementezahl

0 Elemente     eine               bzw.    ( n über 0 ) 
1 Element           n               bzw.    ( n über 1 )
 2 Elemente     n*(n-1) / 2     bzw.    ( n über 2 )

Also ist die Zahl aller Teilmenge

(n über 0 ) + (n über 1 ) + ( n über 2 ) + ….. + ( n über n )

und vielleicht hattet ihr schon, dass dies immer 2^n ist.

Den 2. Teil findest du dort:

https://www.mathe-online.at/mathint/mengen/i_bewPm.html

Comments

Wir haben zu dem Thema noch Garnichts wirklich behandelt .