Kiek elementų yra maitinimo bloke?

galios rinkinys rinkinio A yra visų A pogrupių kolekcija. Kai dirbate su baigtiniu rinkinys su n elementai, vienas klausimas, kurį mes galime užduoti, yra „Kiek elementų yra galios rinkinyje A? “ Pamatysime, kad atsakymas į šį klausimą yra 2ⁿ ir matematiškai įrodyk, kodėl tai tiesa.

Mes ieškosime modelio stebėdami elementų skaičių galios rinkinyje A, kur A turi n elementai:

• Jei A = {} (tuščias rinkinys), tada A neturi elementų, bet P (A) = {{}}, rinkinys su vienu elementu.
• Jei A = {a}, tada A turi vieną elementą ir P (A) = {{}, {a}}, rinkinys su dviem elementais.
• Jei A = {a, b}, tada A turi du elementus ir P (A) = {{}, {a}, {b}, {a, b}}, rinkinys, sudarytas iš dviejų elementų.

Visose šiose situacijose tai nesunku pastebėti rinkiniai su nedideliu skaičiumi elementų, kurie, jei yra baigtinis skaičius n elementai A, tada nustatytą galią P (A) turi 2n elementai. Bet ar šis modelis tęsiasi? Tiesiog todėl, kad modelis yra teisingas n = 0, 1 ir 2 nebūtinai reiškia, kad modelis yra teisingas didesnėms reikšmėms n.

Tačiau šis modelis tęsiasi. Norėdami parodyti, kad taip iš tikrųjų yra, mes naudosime įrodymus indukcijos būdu.

Įvedimas indukcija yra naudingas norint įrodyti teiginius, susijusius su visais natūraliaisiais skaičiais. Tai pasiekiame dviem etapais. Pirmame žingsnyje mes įtvirtiname savo įrodymą, parodydami teisingą teiginį, kad pirmoji vertė yra n kad mes norime apsvarstyti. Antrasis mūsų įrodymų žingsnis yra manyti, kad teiginys galioja n = k, ir parodymas, kad tai reiškia, teiginys galioja n = k + 1.

Norėdami padėti mums įrodyti, mums reikės dar vieno pastebėjimo. Iš aukščiau pateiktų pavyzdžių matome, kad P ({a}) yra P ({a, b}) pogrupis. {A} pogrupiai sudaro tiksliai pusę {a, b} pogrupių. Visus {a, b} pogrupius galime gauti pridėję elementą b prie kiekvieno {a} pogrupio. Šis rinkinio papildymas atliekamas naudojant nustatytą sąjungos veikimą:

• Tuščias rinkinys U {b} = {b}
• {a} U {b} = {a, b}

Tai yra du nauji elementai P ({a, b}), kurie nebuvo P ({a}) elementai.

Panašų įvykį matome ir P ({a, b, c}). Mes pradedame nuo keturių P ({a, b}) rinkinių ir prie kiekvieno iš jų pridedame elementą c:

• Tuščias rinkinys U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Taigi iš viso aštuoni elementai yra P ({a, b, c}).

Dabar esame pasirengę įrodyti teiginį: „Jei rinkinys A yra n elementai, tada galios rinkinys P (A) turi 2ⁿ elementai. “

Pirmiausia pažymime, kad įvadinis įrodymas jau buvo įtvirtintas bylomis n = 0, 1, 2 ir 3. Mes manome, kad indukcija, kuria šis teiginys galioja k. Dabar leisk rinkinį A talpinti n +1 elementai. Mes galime rašyti A = B U {x} ir pagalvokite, kaip sudaryti A.

Mes imame visus elementus P (B), o pagal indukcinę hipotezę yra 2ⁿ iš jų. Tada pridedame elementą x prie kiekvieno iš šių pogrupių B, gaunant dar 2ⁿ pogrupiai B. Tai išnaudoja B, taigi iš viso yra 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} galios rinkinio elementai A.