Informatyka MIMUW

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$.