Wie zeige ich das die Potenzmenge genau 2^n Elemente enthält?

Question

1. Zeigen Sie: Für jedes n ∈ N enthält die Potenzmenge P({1,...,n}) genau 2n Elemente, das heißt, zeigen Sie die Gleichung

   #P({1,...,n}) = 2n 

Answer 1

 

das zeigt man mit vollständiger Induktion:

Basis n=0:   {  }  hat  2⁰ = 1 Teilmenge, nämlich sich selbst.

Induktionsschluss:

Nimmt man aus einer Menge M  mit  n+1 Elementen ein Element e heraus, hat die Restmenge R nach Induktionsvoraussetzung  2ⁿ  Teilmengen.

Alle weiteren Telmengen von M ergeben sich durch Hinzufügen von e zu den Teilmengen von R.

Insgesamt hat M dann also  2 • 2ⁿ  =  2ⁿ⁺¹  Teilmengen

Gruß Wolfgang