Колко елемента има в мощност?

Най- мощност на комплект А е колекцията на всички подмножества на A. Когато работите с ограничен комплект с н елементи, един въпрос, който бихме могли да зададем, е: „Колко елементи има в мощностния набор А? " Ще видим, че отговорът на този въпрос е 2^н и докажете математически защо това е вярно.

Ще потърсим модел, като наблюдаваме броя на елементите в мощността на А, където А има н елемента:

• ако А = {} (празният набор), тогава А няма елементи, но P (A) = {{}}, набор с един елемент.
• ако А = {a}, тогава А има един елемент и P (A) = {{}, {a}}, набор с два елемента.
• ако А = {a, b}, тогава А има два елемента и P (A) = {{}, {a}, {b}, {a, b}}, набор с два елемента.

Във всички тези ситуации е направо да се търси комплекти с малък брой елементи, които ако има ограничен брой н елементи в А, след това мощността P (А) има 2н елементи. Но продължава ли този модел? Само защото модел е валиден за н = 0, 1 и 2 не означава непременно, че моделът е валиден за по-високи стойности на н.

Но този модел продължава. За да покажем, че това наистина е така, ще използваме доказателство чрез индукция.

Доказването чрез индукция е полезно за доказване на твърдения, отнасящи се до всички естествени числа. Ние постигаме това на две стъпки. За първата стъпка ние закрепваме доказателството си, като показваме вярно изявление за първата стойност на н които искаме да разгледаме. Втората стъпка от нашето доказателство е да приемем, че това твърдение е валидно н = ки шоуто, което означава, че това твърдение е валидно н = к + 1.

За да помогнем в нашето доказателство, ще ни трябва друго наблюдение. От горните примери можем да видим, че P ({a}) е подмножество на P ({a, b}). Подмножествата от {a} формират точно половината от подмножествата на {a, b}. Можем да получим всички подмножества на {a, b}, като добавим елемента b към всеки от подмножествата на {a}. Това комплектоване се осъществява чрез зададената операция на обединение:

• Празен набор U {b} = {b}
• {a} U {b} = {a, b}

Това са двата нови елемента в P ({a, b}), които не бяха елементи на P ({a}).

Виждаме подобно явление за P ({a, b, c}). Започваме с четирите множества на P ({a, b}) и към всеки от тях добавяме елемента c:

• Празен набор U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

И така завършваме с общо осем елемента в P ({a, b, c}).

Вече сме готови да докажем твърдението: „Ако е зададено А съдържа н елементи, след това мощността P (A) има 2^н елементи ".

Започваме с отбелязването, че доказателството чрез индукция вече е закотвено за случаите н = 0, 1, 2 и 3. Предполагаме чрез индукция, за която твърди изложението к. Сега оставете набора А съдържа н + 1 елемента. Можем да пишем А = B U {x} и помислете как да формирате подмножества на А.

Ние приемаме всички елементи на P (B), и по индуктивната хипотеза има 2^н от тях. След това добавяме елемента x към всеки от тези подмножества на B, което води до още 2^н подмножества на B. Това изчерпва списъка с подмножества на B, и така общият е 2^н + 2^н = 2(2^н) = 2^{н + 1} елементи на мощност на А.