Ile elementów znajduje się w zestawie mocy?

conceptdraw.com

The zestaw zasilający zestawu A jest zbiorem wszystkich podzbiorów A. Podczas pracy ze skończonym ustawić z n elementów, jedno pytanie, które możemy zadać, brzmi: Ile elementów jest w zbiorze potęgowym A ? Zobaczymy, że odpowiedź na to pytanie to 2 ⁿ i udowodnij matematycznie, dlaczego tak jest.

Obserwacja Wzorca

Poszukamy wzorca obserwując liczbę elementów w zbiorze potęgowym A , gdzie A ma n elementy:

• Jeśli A = { } (zbiór pusty), wtedy A nie ma elementów, ale P (A) = { { } }, zbiór z jednym elementem.
• Jeśli A = {a}, to A ma jeden element i P (A) = { { }, {a}}, zbiór z dwoma elementami.
• Jeśli A = {a, b}, wtedy A ma dwa elementy i P (A) = { { }, {a}, {b}, {a,b}}, zbiór z dwoma elementami.

We wszystkich tych sytuacjach nietrudno się domyślić zestawy z niewielką liczbą elementów, które jeśli istnieje skończona liczba n elementy w A , a następnie zestaw mocy P ( A ) ma 2 n elementy. Ale czy ten wzór się utrzymuje? Tylko dlatego, że wzór jest prawdziwy dla n = 0, 1 i 2 niekoniecznie oznacza, że ​​wzorzec jest prawdziwy dla wyższych wartości n .

Ale ten wzór trwa. Aby pokazać, że rzeczywiście tak jest, użyjemy dowodu przez indukcję.

Dowód przez indukcję

Dowód przez indukcję jest przydatny do dowodzenia twierdzeń dotyczących wszystkich liczb naturalnych. Osiągamy to w dwóch krokach. W pierwszym kroku zakotwiczamy nasz dowód, pokazując prawdziwe stwierdzenie dla pierwszej wartości n które chcemy rozważyć. Drugim krokiem naszego dowodu jest założenie, że stwierdzenie obowiązuje dla n = k , i pokazać, że to implikuje, że stwierdzenie obowiązuje dla n = k + 1.

Kolejna obserwacja

Aby pomóc w naszym dowodzie, będziemy potrzebować kolejnej obserwacji. Z powyższych przykładów widzimy, że P({a}) jest podzbiorem P({a, b}). Podzbiory {a} tworzą dokładnie połowę podzbiorów {a, b}. Możemy uzyskać wszystkie podzbiory {a, b}, dodając element b do każdego z podzbiorów {a}. To dodawanie zestawu odbywa się za pomocą zestawu operacji połączenia:

• Pusty zbiór U {b} = {b}
• {a} U {b} = {a, b}

Są to dwa nowe elementy w P({a, b}), które nie były elementami P({a}).

Widzimy podobne zdarzenie dla P({a, b, c}). Zaczynamy od czterech zbiorów P({a, b}) i do każdego z nich dodajemy element c:

• Pusty zbiór U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

I tak otrzymujemy w sumie osiem elementów w P({a, b, c}).

Dowód

Jesteśmy teraz gotowi, aby udowodnić stwierdzenie, jeśli zestaw A zawiera n elementy, a następnie zestaw mocy P(A) ma 2 ⁿ elementy.

Zaczynamy od zwrócenia uwagi, że dowód przez indukcję został już zakotwiczony w przypadkach n = 0, 1, 2 i 3. Przypuszczamy przez indukcję, że zdanie obowiązuje dla k . Teraz niech zestaw A zawierać n + 1 elementy. Możemy pisać A = B U {x} i zastanów się, jak utworzyć podzbiory A .

Zbieramy wszystkie elementy P(B) , a zgodnie z hipotezą indukcyjną istnieje 2 ⁿ tych. Następnie dodajemy element x do każdego z tych podzbiorów B , w wyniku czego kolejne 2 ⁿ podzbiory B . To wyczerpuje listę podzbiorów B , więc suma wynosi 2 ⁿ + 2 ⁿ = 2(2 ⁿ ) = 2 ^{n + 1}elementy układu zasilania A .