Matematik
Induktionsbevis indenfor mængder
Er der nogen der kan løse denne opgave ved hjælp af et induktionsbevis. Opgaven formulerer jeg ordret efter min bog på engelsk. Den kommer herunder.
Show that for any finite set S, the power set 2^S has 2|^S| elements (that is, there are 2^|S| distinct subsets of S).
Her kommer min halve løsning til opgaven:
Basis:
n = antal elementer i mængde S = 1
En mængde S med et element:
S = {a}
Denne mængde S med et element har følgende delmængder:
1) S er en delmængde S
2) Denne tomme mængde Ø er en delmængde af S
Dvs. Mængden S med et elemen har 2 delmængder. Det stemmer overens med at 2^|S| = 2^|1| = 2.
Dvs. basis er OK.
Induktionsskridt:
Antager at sætningen er sand for n = en mængde med et element. Jeg skal nu bevise at det også er sand for n+1 element.
Ja, jeg ved ikke hvordan jeg skal komme videre med opgaven.
Svar #1
16. juni 2008 af tal-pædagog (Slettet)
Svar #3
16. juni 2008 af datmat (Slettet)
Svar #4
16. juni 2008 af The Master (Slettet)
Svar #5
16. juni 2008 af tal-pædagog (Slettet)
A=S U {q}
Hvor q altså er det nye element. Nu danner vi mængden af alle delmængder af A på følgende måde:
2^A = 2^S U {B U {q}|B tilhører 2^S}
hvoraf det ses, at 2^A er en disjunkt forening af alle delmængder af S og alle delmængder af S med elementet q tilføjet.
Svar #6
16. juni 2008 af tal-pædagog (Slettet)
Antallet af elementer i den nye mængde 2^A, er, da foreningen er disjunkt, lig summen af antallet af elementer i 2^S og antallet af elementer i {B U {q}|B tilhører 2^S}. Sidstnævnte har ligeså mange elementer som 2^S, da hvert element er dannet fra et B, der tilhører 2^S og da ingen elementer er ens.
Svar #7
16. juni 2008 af tal-pædagog (Slettet)
Skriv et svar til: Induktionsbevis indenfor mængder
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.