Aksjomat Zbioru Potęgowego

Aksjomat nieskończoności pozwala nam tworzyć zbiory nieskończone. Dzięki poniższemu aksjomatowi możemy tworzyć zbiory wszystkich podzbiorów danego zbioru. Jak będzie to przedstawione w wykładzie: "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum", tworzenie zbioru składającego się z wszystkich podzbiorów danego zbioru jest prostym sposobem na tworzenie jeszcze liczniejszych zbiorów. W wykładzie tym wykażemy, że nawet dla zbiorów nieskończonych zbiór wszystkich podzbiorów danego zbioru jest liczniejszy niż sam zbiór.

Aksjomat Zbioru Potęgowego Zakładamy, że następująca formuła, zwana aksjomatem zbioru potęgowego, jest prawdą:

\( \forall x \exists y \forall z \; z\in y \iff z\subset x. \)

Zbiór potęgowy \( y \), którego istnienie gwarantuje ten aksjomat, oznaczamy przez \( \mathcal{P}(x) \) lub przez \( 2^x \).

Aksjomat zbioru potęgowego gwarantuje, że dla każdego zbioru \( x \) istnieje zbiór \( \mathcal{P}(x) \) zawierający wyłącznie wszystkie podzbiory \( x \). Bardzo łatwo zauważyć, że dla dowolnego zbioru \( x \) mamy \( \emptyset\in\mathcal{P}(x) \) oraz \( x\in\mathcal{P}(x) \). Oznaczanie zbioru potęgowego przez \( 2^x \) ma głębsze znaczenie, które zostanie przedstawione w zbiór funkcji \( x^y \). Na razie możemy jedynie dla zbiorów skończonych odpowiedzieć na dwa pytania:

Ćwiczenie 8.1

Czy następujące fakty są prawdziwe:

1. Jeśli \( x \) jest skończonym, \( n \)-elementowym zbiorem, to \( \mathcal{P}(x) \) posiada dokładnie \( 2^n \) elementów?

2. Jeśli \( x \) jest zbiorem będącym liczbą naturalną (oznaczmy ją nieformalnie jako \( n \)), to zbiór \( \mathcal{P}(x) \) jest zbiorem będącym liczbą naturalną oznaczoną nieformalnie jako \( 2^n \)?

Podpowiedź

1. Użyj naiwnej indukcji.

2. Nie, ale dlaczego?

Odpowiedź

Dowody powyższych faktów:

1. Używamy naiwnej formy indukcji

Jeśli zbiór \( x \) jest zeroelementowy, to \( x=\emptyset \) i \( \mathcal{P}(\emptyset)=\{\emptyset\} \) posiada dokładnie \( 2^0=1 \) element.

Załóżmy, że twierdzenie jest prawdą dla zbiorów \( n \)-elementowych. Weźmy dowolny zbiór \( n+1 \)-elementowy \( x \) i wyróżnijmy w nim dowolny element \( y \). Łatwo zauważyć, że zbiór \( \mathcal{P}(x) \) można podzielić na dwie części: zbiory zawierające \( y \) i zbiory niezawierające \( y \). Każda z tych części ma tyle elementów, ile \( \mathcal{P}(x\setminus\{y\}) \), czyli \( 2^n \). Wnioskujemy, że \( \mathcal{P}(x) \) ma \( 2\cdot 2^n= 2^{n+1} \) elementów, co należało pokazać.

2. Dla liczby dwa równej \( \{\emptyset,\{\emptyset\}\} \) mamy

\( \mathcal{P}(\{\emptyset,\{\emptyset\}\})=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}, \)

co jest różne od liczby cztery.

Wykażemy kilka prostych faktów dotyczących zbiorów potęgowych.

Fakt 8.1.

Dla dowolnego zbioru \( x \) mamy \( x=\bigcup \mathcal{P}(x) \), ale istnieje taki zbiór, że \( \mathcal{P}(\bigcup x)\neq x \).

Dowód

Dla dowodu równości \( x=\bigcup\mathcal{P}(x) \), ustalmy dowolne \( z\in x \). Wnioskujemy, że \( z\in\{z\}\in\mathcal{P}(x) \) i w związku z tym \( z\in\bigcup\mathcal{P}(x) \), czyli \( x\subset\bigcup\mathcal{P}(x) \). Dla dowodu inkluzji w drugą stronę ustalamy \( z\in\bigcup\mathcal{P}(x) \). To oznacza, że istnieje \( y\in\mathcal{P}(x) \) takie, że \( z\in y \). To z kolei implikuje, że \( z\in y\subset x \), czyli \( z\in x \) i \( \bigcup\mathcal{P}(x)\subset x \). Oba te fakty razem dowodzą, że \( x=\bigcup\mathcal{P}(x) \), co dowodzi pierwszej części tezy. Zbiór \( x \), dla którego \( \mathcal{P}(\bigcup x)\neq x \), to zbiór \( \{\{\emptyset\}\} \). Zbiór

\( \mathcal{P}(\bigcup\{\{\emptyset\}\})= \mathcal{P}(\{\emptyset\}) = \{\emptyset,\{\emptyset\}\}\neq \{\{\emptyset\}\}, \)

co potwierdza fakt, że istnieją zbiory, dla których \( \mathcal{P}(\bigcup x)\neq x \).

Kolejny fakt dowodzi, że inkluzja przenosi się na zbiory potęgowe.

Fakt 8.2.

Większe zbiory mają więcej podzbiorów, czyli następująca formuła jest prawdą:

\( \forall x\forall y\; x\subset y\Longrightarrow \mathcal{P}(x)\subset\mathcal{P}(y). \)

Dowód
Aby dowieść faktu, ustalamy dowolne \( x \), \( y \) takie, że \( x\subset y \) oraz dowolne \( z \) takie, że \( z\in\mathcal{P}(x) \). To implikuje, że \( z\subset x \) i korzystając z założenia, otrzymujemy \( z\subset x\subset y \), co oznacza, że \( z\in\mathcal{P}(y) \).

Następujące własności zbiorów potęgowych przedstawiamy w formie ćwiczeń

Ćwiczenie 8.2

Dla dowolnego zbioru \( x \) zachodzi \( x\subset \mathcal{P}(\bigcup x) \).

Rozwiązanie

Ustalmy dowolne \( z\in x \). Dla dowolnego \( w \), jeśli \( w\in z \) to \( w\in\bigcup x \). To implikuje, że \( z\subset \bigcup x \), czyli \( z\in\mathcal{P}(\bigcup x) \), co należało pokazać.

Ćwiczenie 8.3

Jakie implikacje zachodzą pomiędzy dwoma warunkami \( \bigcup x\subset x \) i \( x\subset \mathcal{P}(x) \).

Rozwiązanie

Te warunki są sobie równoważne. Jeśli \( \bigcup x\subset x \), to, na mocy Faktu 8.2 (patrz fakt 8.2.), otrzymujemy \( \mathcal{P}(\bigcup x)\subset \mathcal{P}(x) \). Poprzednie ćwiczenie implikuje, że \( x\subset \mathcal{P}(\bigcup x) \) i łącząc oba te fakty, wnioskujemy, że \( x\subset \mathcal{P}(x) \). Co dowodzi implikacji w jedną stronę.

Dla implikacji w drugą stronę załóżmy, że \( x\subset \mathcal{P}(x) \). Na mocy Faktu 5.3 (patrz fakt 5.3.) dostajemy \( \bigcup x\subset \bigcup\mathcal{P}(x) \).
Fakt 8.1 (patrz fakt 8.1.) mówi, że w takim przypadku \( \bigcup x\subset \bigcup\mathcal{P}(x) = x \), co dowodzi implikacji w drugą stronę.

Ćwiczenie 8.4

Czy następujące równości są prawdziwe dla dowolnych zbiorów \( x \) i \( y \)?

1. \( \mathcal{P}(\bigcup(x\cap y))= \mathcal{P}(\bigcup x)\cap\mathcal{P}(\bigcup y) \),

2. \( \bigcap\mathcal{P}(x\cap y) = \bigcap\mathcal{P}(x)\cap\bigcap\mathcal{P}(y) \).

Rozwiązanie

Rozwiązania są następujące:

1. Równość ta nie jest prawdą. Ustalmy dwa różne zbiory \( w \) i \( v \) i połóżmy \( x=\{\{w,v\}\} \) i \( y=\{\{w\}\} \). Wtedy \( x\cap y =\emptyset \) i lewa strona równości jest równa \( \{\emptyset\} \). Tymczasem \( \bigcup x = \{w,v\} \) i \( \bigcup y = \{w\} \), więc \( \{w\} \) jest elementem prawej strony, co dowodzi różności zbiorów.

2. Dla dowolnego zbioru \( x \) mamy \( \emptyset\in\mathcal{P}(x) \), a to implikuje, że \( \bigcap\mathcal{P}(x) \) jest zawsze równy \( \emptyset \). Równość jest zawsze spełniona i obie jej strony są równe \( \emptyset \) niezależnie od wyboru \( x \) i \( y \).