0 Daumen
789 Aufrufe

Sei A eine Menge. Die Potenzmenge  P(A)  wir definieren

induktiv, für alle k ≤ 1,

Pk(A) =   P(A) , falls k = 1,

                P(P k−1(A)) , sonst.

Wir definieren außerdem die Funktion g: ( ℕ \ {0})2 → ℕ induktiv 

durch g(1, n) = 2, für alle n ≥ 1,

und g(k, n) = 2g(k−1,n) , für alle n ≥ 1 und k ≥ 2.

Beweisen Sie per vollständiger Induktion.

Für alle k ≥ 1 gilt: |Pk(A)| = g(k, |A|).

Avatar von

1 Antwort

0 Daumen

Ind. anf. k=1  dann ist |P(A)| = 2^n wobei n=|A| ist; denn offenbar ist A eine endliche Menge,

Das fehlt zwar bei der Angabe der Voraussetzungen,

ansonsten wäre die ganze Sache unsinnig.

Und die Aussage: Die Potenzmenge einer n-elementigen Menge hat 2^n Elemente ist ja wohl bekannt.

Sei  nun k ≥ 1 und |Pk(A)| = g(k, |A|).  

Dann gilt Pk+1(A)= P(  Pk(A)) also ist die Elementezahl davon

= 2 Elementezahl von Pk(A) = 2 g(k, |A|)   und nach der Def. von g ist das

= g(k+1, |A|).  q.e.d.

Avatar von 289 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community