Potenzmenge: Zeige: Ist M eine endliche Menge mit n Elementen, so ist P(M) eine endliche Menge mit 2^n Elementen

Question

(Potenzmenge)

Zeigen Sie: Ist M eine endliche Menge mit n Elementen, so ist P(M) eine endliche Menge mit 2ⁿ Elementen

Answer 1

Für n = 0 = |M| ist M = {}, P(M) = { {} } und |P(M)| = 1 = 2⁰.

Nehmen wir an, es gäbe ein n ∈ ℕ so, dass |M| = n und |P(M)| = 2ⁿ gilt.

Wird die Menge M nun um einzusätzliches Element m_n+1 ergänzt,
ergibt sich die Menge M ∪ { m_n+1 } mit m+1 Elementen. Ihre
Pozenzmenge P( M ∪ { m_n+1 } ) enthält neben den Elementen von P(M)
auch alle Elemente von P(M), die zusätzlich noch das Element m_n+1
beinhalten. Dadurch sind zwei gleichgroße und disjunkte Teilmengen
von P( M ∪ { m_n+1 } ) gegeben, so dass sie doppelt so viele Elemente
enthalten muss wie P(M). Es gilt also:

| P( M ∪ { m_n+1 } ) |   =   2 * | P(M) |   =   2 * 2ⁿ   =   2ⁿ⁺¹,   q.e.d.

Comments

Was bedeutet dieses q.e.d ganz am Ende ?

---

quod erat demonstradum

Wenn ich mich nicht irre, das ist lateinisch und heisst so viel wie: Was zu zeigen war.

---

quod erat demonstrandum

;)