Колико елемената је у сету напајања?

Тхе сет снаге сета А је збирка свих подскупова А. Кад радите са коначним комплет са н елемената, једно питање које бисмо могли поставити је: „Колико елемената има у скупу снаге А? " Видећемо да је одговор на то питање 2^н и математички доказати зашто је то тачно.

Потражићемо образац посматрајући број елемената у скупу снаге А, где А је н елементи:

• Ако А = {} (празан сет), тада А али нема елемената али П (А) = {{}}, скуп са једним елементом.
• Ако А = {а}, дакле А има један елемент и П (А) = {{}, {а}}, сет са два елемента.
• Ако А = {а, б}, тада А има два елемента и П (А) = {{}, {а}, {б}, {а, б}}, сет са два елемента.

У свим овим ситуацијама је једноставно тражити сетови са малим бројем елемената који, уколико постоји коначан број н елементи у А, а затим постављена снага П (А) има 2н елементи. Али да ли се овај образац наставља? Само зато што важи образац н = 0, 1 и 2 не значи нужно да је узорак истинит за веће вредности од н.

Али овај образац се и даље наставља. Да бисмо показали да је заиста тако, користићемо доказ индукцијом.

Доказивање индукцијом је корисно за доказивање изјава које се тичу свих природних бројева. То постижемо у два корака. За први корак ускладимо свој доказ показујући истиниту изјаву за прву вредност н које желимо да размотримо. Други корак нашег доказа је претпоставка да изјава стоји н = к, и емисију која подразумева да изјава држи н = к + 1.

Да бисмо помогли у нашем доказу, требат ће нам друго запажање. Из горњих примера видимо да је П ({а}) подскуп П ({а, б}). Подскупови {а} формирају тачно половину подскупова {а, б}. Све подскупове од {а, б} можемо добити додавањем елемента б у сваку од подскупова {а}. Ово додавање се врши помоћу задате операције спајања:

• Празан сет У {б} = {б}
• {а} У {б} = {а, б}

Ово су два нова елемента у П ({а, б}) који нису били елементи П ({а}).

Видимо сличну појаву за П ({а, б, ц}). Почињемо са четири скупа П ({а, б}), а сваком од њих додамо елемент ц:

• Празан сет У {ц} = {ц}
• {а} У {ц} = {а, ц}
• {б} У {ц} = {б, ц}
• {а, б} У {ц} = {а, б, ц}

И тако завршимо са укупно осам елемената у П ({а, б, ц}).

Сада смо спремни да докажемо тврдњу, „Ако је скуп А садржи н елемената, затим постављена снага П (А) има 2^н елементи. "

Започињемо са напоменом да је доказ индукцијом већ усидрен за случајеве н = 0, 1, 2 и 3. Претпостављамо да је индукција за коју се изјава односи к. Сада пустите сет А садржати н + 1 елемента. Можемо писати А = Б У {к} и размислите како да формирате подскупове од А.

Узимамо све елементе П (Б)и по индуктивној хипотези постоје 2^н ових. Затим додамо елемент к сваком од тих подскупина Б, што резултира још 2^н подскупови Б. Ово исцрпљује листу подскупова Б, и тако је укупно 2^н + 2^н = 2(2^н) = 2^{н + 1} елементи скупа снаге А.