Schemat aksjomatu wyróżniania
Zanim przejdziemy do wprowadzenia aksjomatu gwarantującego istnienie zbiorów nieskończonych, wprowadzimy jeszcze jeden aksjomat. Zasada zwana Aksjomatem Wyróżniania nie jest, formalnie rzecz biorąc aksjomatem - jest schematem aksjomatu albo rodziną aksjomatów o bardzo podobnej strukturze. Aksjomat ten mówi, że z każdego zbioru możemy wybrać podzbiór elementów spełniających konkretną własność, jeśli tylko własność tę można zdefiniować w języku rachunku predykatów.
Aksjomat Wyróżniania Dla dowolnej formuły \( \varphi \) nieposiadającej zmiennych wolnych innych niż \( z \) następująca formuła jest prawdą
\( \forall x \exists y \forall z\; z\in y \iff (z\in x \land \varphi). \)
Zbiór, którego istnienie gwarantuje ta formuła, jest często oznaczany przez \( \{z\in x\,:\, \varphi\} \).
W powyższym aksjomacie formuła \( \varphi \) definiuje własność, na podstawie której kwalifikujemy elementy do podzbioru zbioru \( x \). Schemat aksjomatu wyróżniania będziemy nazywać w skrócie aksjomatem wyróżniania. Aksjomat ten jest bardzo ważnym i mocnym narzędziem. Zwróćmy uwagę, że aksjomat ten pozwala nam tworzyć wyłącznie zbiory mniejsze od tych, których istnienie jest wcześniej gwarantowane - oczywistym wnioskiem z definicji jest, że \( \{z\in x\,:\, \varphi\}\subset x \).
Aksjomat wyróżniania jest nieco kłopotliwy w użyciu w formie zaprezentowanej powyżej. Poniższa własność jest konsekwencją tego aksjomatu, a jest dużo prostsza w zastosowaniach. Dla dowolnej formuły \( \varphi \) nieposiadającej zmiennych wolnych innych niż \( z \) i \( x_1 \) następująca formuła jest prawdą:
\( \forall x_1 \forall x \exists y \forall z\; z\in y \iff (z\in x \land \varphi). \quad \mbox{(*)} \)
Powyższa własność wynika z aksjomatu wyróżniania. Dowód tego faktu korzysta z powyżej zdefiniowanych aksjomatów i aksjomatu zbioru potęgowego (który zostanie wprowadzony dalej w tym wykładzie) i jest przedstawiony w wykładzie Iloczyn kartezjański i aksjomat wyróżniania.
Rozważmy zbiór \( \bigcup x_1 \), którego istnienie, dla każdego zbioru \( x_1 \), gwarantuje aksjomat sumy. Jest to zbiór takich \( z \), że istnieje \( w \) spełniające \( z\in w\in x_1 \). Mówiąc prościej, jest to zbiór bytów występujących w którymkolwiek z elementów \( x_1 \). Naturalną konsekwencją wydaje się definicja zbioru elementów występujących w każdym z elementów \( x_1 \). Definicja takiego zbioru jest możliwa właśnie dzięki aksjomatowi wyróżniania. Zbiór taki oznaczamy przez \( \bigcap x_1 \) i definiujemy jako
\( \bigcap x_1 = \{y\in\bigcup x_1\,:\, \forall z\; z\in x_1\Longrightarrow y\in z\}. \)
Aby wykazać istnienie tego zbioru, korzystamy z konsekwencji aksjomatu wyróżniania \( \mbox{(*)} \) w następującej formie:
\( \forall x_1 \forall x \exists y \forall z\; z\in y \iff (z\in x \land (\forall w\; w\in x_1\Longrightarrow z\in w)). \)
Jeśli w powyższej formule zastosujemy \( \bigcup x_1 \) jako \( x \), to otrzymujemy dowód istnienia \( \bigcap x_1 \).
Naturalnie zbiór \( \bigcap x \) jest podzbiorem zbioru \( \bigcup x \) i co za tym idzie \( \bigcap\emptyset \subset \bigcup \emptyset = \emptyset \), czyli \( \bigcap \emptyset = \emptyset \). Co więcej konstrukcja ta pozwala nam zdefiniować kolejną, znaną z naiwnego podejścia do teorii mnogości, operację
\( x\cap y \stackrel{\textrm{def}}{\equiv} \bigcap\{x,y\}. \)
Przecięcie dwóch zbiorów to zbiór tych elementów, które występują w obu zbiorach równocześnie. Rozumując analogicznie do dowodu Faktu 5.4 (patrz fakt 5.4.), można pokazać, że, podobnie jak dla unii, przecięcie ma znaczenie identyczne z tym używanym w naiwnej teorii mnogości:
\( \forall x\forall y \forall z\; z\in x \cap y \iff (z\in x \land z\in y). \quad \mbox{(+)} \)
Ćwiczenie 6.1
Udowodnij następujące własności dotyczące przecięcia zbiorów. Dla dowolnych zbiorów \( x \), \( y \) i \( z \)
- 1. \( x\cap y = y\cap x \),
- 2. \( x\supset x\cap y \),
- 3. \( y\supset x\cap y \),
- 4. \( x\cap x = x \),
- 5. \( x\cap \emptyset = \emptyset \),
- 6. \( x\cap(y\cup z) = (x\cap y)\cup (x\cap z) \),
- 7. \( x\cup(y\cap z) = (x\cup y)\cap(x\cup z) \).
Dowiedziemy teraz prostego faktu dotyczącego przecięć zbiorów. Fakt ten wyrazimy najpierw intuicyjnie, a następnie jako formułę, która będzie prawdziwa w naszej aksjomatyce:
- Fakt 6.1.
Przecięcie niepustego zbioru \( x \) jest największym pod względem inkluzji zbiorem zawartym w każdym elemencie \( x \). To znaczy, że następująca formuła jest prawdą:
\( \forall x \; x\neq\emptyset \Longrightarrow ( \forall y\; (\forall z\; z\in x \Longrightarrow y\subset z)\Longrightarrow y\subset \bigcap x) \)
Dowód
Ustalmy niepusty zbiór \( x \) i zbiór \( y \) taki, że \( y \) jest podzbiorem każdego elementu \( x \). Weźmy dowolny element zbioru \( y \) i nazwijmy go \( z \). Ponieważ \( y \) jest podzbiorem każdego elementu \( x \), to prawdą jest, że \( \forall w\; w\in x \Longrightarrow z\in w \). Ponieważ zbiór \( x \) nie jest pusty otrzymujemy \( z\in \bigcup x \), a ponieważ \( z \) spełnia formułę powyżej \( z\in \bigcap x \). Pokazaliśmy, że każdy element \( y \) jest elementem \( \bigcap x \), czyli że \( y\subset \bigcap x \), czego należało dowieść.
Kolejny fakt dowodzi, że, zgodnie z intuicją, przecięcie większej rodziny zbiorów jest mniejsze.
Fakt 6.2.
Jeśli zbiór \( x \) jest niepustym podzbiorem zbioru \( y \), to \( \bigcap y \) jest podzbiorem \( \bigcap x \). Równoważnie następująca formuła jest prawdą
\( \forall x \forall y (x\subset y \land x\neq \emptyset) \Longrightarrow \bigcap y \subset \bigcap x. \)
Dowód
Ustalmy zbiór \( x\neq\emptyset \) i zbiór \( y \) spełniające \( x \subset y \). Z definicji zbioru zbioru \( \bigcap y \) wnioskujemy, że \( \bigcap y \) jest podzbiorem każdego elementu zbioru \( y \). Ponieważ \( x\subset y \) zbiór \( \bigcap y \) jest również podzbiorem każdego elementu zbioru \( x \). Stosując Fakt 6.1, natychmiast otrzymujemy, że \( \bigcap y\subset \bigcap x \) -- co należało pokazać.
Kolejny fakt ilustruje zależność pomiędzy elementami zbioru, jego unią i przecięciem.
Fakt 6.3.
Zbiór \( \bigcap x \) jest podzbiorem, a zbiór \( \bigcup x \) nadzbiorem każdego elementu zbioru \( x \). Równoważnie następująca formuła jest prawdziwa:
\( \forall x\forall y\; y\in x \Longrightarrow \bigcap x\subset y \subset \bigcup x. \)
Dowód
Ustalmy dowolne zbiory \( x \) i \( y \) takie, że \( y\in x \). Dla dowodu pierwszej inkluzji ustalmy dowolne \( z\in\bigcap x \). Definicja \( \bigcap x \) implikuje, że \( z \) jest elementem każdego z elementów \( x \), w szczególności \( z\in y \), czyli \( \bigcap x\subset y \).
Dla dowodu drugiej inkluzji ustalmy dowolne \( z\in y \). Ponieważ istnieje element \( x \), którego \( z \) jest elementem, to \( z\in\bigcup x \). To dowodzi, że \( y\subset \bigcup x \) i druga inkluzja jest dowiedziona.
Przy pomocy aksjomatu wyróżniania jesteśmy w stanie zdefiniować różnicę dwóch zbiorów. Dla zbiorów \( x \) i \( x_1 \) ich różnica to zbiór elementów, które występują w pierwszym i nie występują w drugim zbiorze. Istnienie zbioru będącego różnicą dwu zbiorów dowodzimy przy użyciu równania (*). Piszemy:
\( x\setminus x_1 \stackrel{\textrm{def}}{\equiv} \{z\in x\,:\, z\notin x_1\}. \)
W powyższym przykładzie formuła \( \varphi \) występująca w definicji aksjomatu wyróżniania to \( z\notin x_1 \). Aby umotywować zgodność z intuicją dotyczącą różnicy zbiorów, wykażemy następujący fakt.
Fakt 6.4.
Zbiór \( x\setminus y \) jest największym zbiorem zawartym w \( x \) i przecinającym się pusto z \( y \). Równoważnie, następująca formuła jest prawdą
\( \forall x\forall y \forall z\; (z\subset x \land z\cap y = \emptyset )\Longrightarrow z\subset x\setminus y. \)
Dowód
Ustalmy dowolne zbiory \( x,y,z \) takie, że \( z\subset x \land z\cap y = \emptyset \) i dowolne \( w\in z \). Wtedy \( w\in x \), ponieważ \( z\subset x \) i \( w\notin y \), ponieważ \( z\cap y = \emptyset \). To implikuje, że \( w\in x\setminus y \), co należało pokazać.
Ćwiczenie 6.2
Udowodnij następujące własności dotyczące różnicy zbiorów. Dla dowolnych zbiorów \( x, y \) i \( z \):
- 1. \( x\setminus(x\setminus y) = x\cap y \),
- 2. \( x\setminus (y\cap z) = (x\setminus y)\cup (x\setminus z) \),
- 3. \( x\setminus y = y \setminus x \Longrightarrow x=y \).