matematikk.net

Trenger litt hjelp til et bevis her:

For any set A, we denote by [tex]\mathscr{P}(A)[/tex] the collection of all subsets of A.
Let A be a finite set, and let [tex]|A|=s[/tex]. Prove that [tex]|\mathscr{P}(A)| = 2^s[/tex].

Noen hint?

Prøv induksjon på s.

Takk!

er også greit å regne ut direkte:

Du har s elementer i A og for å lage et subsett må du bare gå gjennom hvert enkelt element og velge om du vil ha det med eller ikke i subsettet. Altså 2 valg for hvert element eller [tex]2^s[/tex] muligheter til sammen.

La A = {[tex]x_1, x_2, x_3, ..., x_s[/tex]}

Anta at vi ønsker å velge ut et subsett B av A.

Vi ser på hvert element i A. Det er to muligheter for [tex]x_1[/tex], [tex]x_1 \in B[/tex] eller [tex]x_1 \notin B[/tex]. Fortsetter vi på denne måten med [tex]x_2, x_3, x_4, ..., x_s[/tex] ser vi at det totale antallet muligheter er 2*2*...*2 (s ganger), som er [tex]2^s[/tex] ganger.

Delmengde er vel å foretrekke som norsk oversettelse!

Joda

Fordervet av engelske mattebøker