Aksjomat Sumy

Aby teoria mnogości mogła się rozwijać, potrzebujemy gwarancji istnienia zbiorów trzy-, cztero- i więcej elementowych. Tę i wiele innych własności gwarantuje aksjomat sumy. Aksjomat ten mówi, że jeśli posiadamy zbiór zbiorów, to można utworzyć nowy zbiór składający się z elementów tych zbiorów. Postać tego aksjomatu jest techniczna, ale w połączeniu z aksjomatem pary pozwala on między innymi stworzyć zbiór równoważny sumie zbiorów z naiwnej teorii mnogości.

Aksjomat sumy. Zakładamy, że następująca formuła, zwana aksjomatem sumy, jest prawdą
\( \forall x \exists y \forall z \; (z\in y) \iff (\exists w\; w\in x \land z\in w). \)

Zbiór \( y \), którego istnienie gwarantuje ten aksjomat oznaczamy przez \( \bigcup x \).

Aksjomat sumy oznacza, że dla dowolnego zbioru istnieje zbiór składający się dokładnie z elementów elementów tego zbioru. Podobnie jak powyżej bardzo proste rozumowanie gwarantuje, że zbiór \( \bigcup x \) jest unikalny dla każdego \( x \). Aksjomat sumy pozwala nam sumować zbiory w sposób nieco inny niż ten, który dawała naiwna teoria mnogości. Wykażemy kilka podstawowych własności dotyczących sum zbiorów.

Fakt 5.1.

Następująca formuła jest prawdą

\( \bigcup \emptyset = \emptyset. \)

Dowód

Dla dowolnego zbioru \( z \) na mocy definicji \( \bigcup\emptyset \) mamy \( z\in\bigcup\emptyset \) wtedy i tylko wtedy, kiedy \( \exists w\; w\in\emptyset \land z\in w \). Ponieważ nic nie należy do zbioru pustego, ten ostatni warunek nigdy nie jest spełniony, co dowodzi, że dla dowolnego \( z \) mamy \( z\notin\bigcup\emptyset \). Natychmiastowym wnioskiem z tego jest, że \( \bigcup\emptyset = \emptyset \), co należało pokazać.

Kolejny fakt jest nieco bardziej skomplikowany.

Fakt 5.2. Następująca formuła jest prawdą

\( \bigcup \{\emptyset\} = \emptyset. \)

Dowód

Dla dowolnego zbioru \( z \) na mocy definicji \( \bigcup\{\emptyset\} \) mamy \( z\in\bigcup\{\emptyset\} \) wtedy i tylko wtedy, kiedy \( \exists w\; w\in\{\emptyset\} \land z\in w \). Pierwsza część koniunkcji jest spełniona wtedy i tylko wtedy, kiedy \( w=\emptyset \), ale wtedy druga część koniunkcji \( z\in\emptyset \) jest nieprawdą. Wnioskujemy z tego, że każdego \( z \) mamy \( z\notin\bigcup\{\emptyset\} \) i \( \bigcup\{\emptyset\} = \emptyset \).

Jeśli jeden zbiór jest podzbiorem drugiego zbioru, to również ich sumy powinny pozostać w takiej samej zależności. Formalnie fakt ten przedstawia się następująco:

Fakt 5.3.

Następująca formuła jest prawdą

\( \forall x \forall y \;x\subset y \Longrightarrow \bigcup x\subset \bigcup y. \)

Dowód

Chcemy pokazać, że dla dowolnego \( z \), jeśli \( z\in\bigcup x \), to \( z\in\bigcup y \). Ustalmy dowolne \( z \) takie, że \( z\in\bigcup x \). To implikuje, że istnieje zbiór \( w \) spełniający \( w\in x \) i \( z\in w \). Na mocy założenia mówiącego, że \( x\subset y \) wnioskujemy, że \( w\in y \), a co za tym idzie \( \exists w\; w\in y \land z\in w \), czyli \( z\in\bigcup y \), co należało pokazać.

Kolejną własność podajemy w formie ćwiczenia.

Ćwiczenie 5.1

Wykaż, że dla dowolnego zbioru \( x \) mamy \( x=\bigcup\{x\} \).

Rozwiązanie

\( y\in x \) wtedy niewątpliwie istnieje element w \( \{x\} \) taki, że \( y \) jest jego elementem -- \( y\in x\in\{x\} \), czyli \( x\subset \bigcup\{x\} \). Aby uzyskać inkluzję w drugą stronę, ustalmy dowolny \( y \) element z \( \bigcup\{x\} \). Fakt, że \( y\in\bigcup\{x\} \) implikuje, że \( y \) jest w którymś z elementów \( \{x\} \). Ponieważ zbiór \( \{x\} \) posiada dokładnie jeden element, otrzymujemy \( y\in x \), co dowodzi, że \( \bigcup\{x\}\subset x \). Te dwa fakty wspólnie dowodzą, że \( x=\bigcup\{x\} \), co należało wykazać.

Przy pomocy aksjomatu sumy, posiłkując się aksjomatem pary, możemy zdefiniować sumę zbiorów znaną z naiwnej teorii mnogości. Aby zsumować dwa zbiory \( x \) i \( y \), tworzymy zbiór \( \{x,y\} \), a następnie używamy w stosunku do niego aksjomatu sumy.

\( x\cup y \stackrel{\textrm{def}}{\equiv} \bigcup\{x,y\}. \) Suma ta posiada identyczne własności jak suma naiwna.

Fakt 5.4.

Element występuje w sumie dwóch zbiorów wtedy i tylko wtedy, kiedy występuje w którymś z nich. Formalnie, następująca formuła jest prawdą

\( \forall x\forall y\forall z \; z\in x\cup y \iff (z\in x \lor z\in y). \)

Dowód

Ustalmy dowolne \( x, y \) i \( z \). Dla dowodu implikacji w prawą stronę załóżmy, że \( z\in x\cup y \), to znaczy, że \( z\in \bigcup\{x,y\} \), czyli, że istnieje element \( \{x,y\} \) taki, że \( z \) do niego należy. Tym elementem może być \( x \) lub \( y \), więc \( z\in x \lor z\in y \) -- pokazaliśmy implikację w prawą stronę. Dla dowodu implikacji w drugą stronę zakładamy, że \( z\in x\lor z\in y \). Wtedy niewątpliwie istnieje element \( \{x,y\} \) zawierający w sobie \( z \) i \( z\in\bigcup\{x,y\}=x\cup y \). Dowodzi to implikacji w drugą stronę i równocześnie całego faktu.

Ćwiczenie 5.2

Udowodnij następujące własności dotyczące sumy zbiorów. Dla dowolnych zbiorów \( x \), \( y \):

1. \( x\cup y = y\cup x \),

2. \( x\subset x\cup y \),

3. \( y\subset x\cup y \),

4. \( x\cup x = x \),

5. \( x\cup \emptyset = x \).

Rozwiązanie

Ustalmy dwa dowolne zbiory \( x \) i \( y \)

1. Mamy \( x\cup y = \bigcup\{x,y\} \), ale ponieważ \( \{x,y\}=\{y,x\} \) natychmiast otrzymujemy:

\( x\cup y = \bigcup\{x,y\} = \bigcup\{y,x\} = y\cup x. \)

2. Na podstawie poprzedniego ćwiczenia mamy \( x=\bigcup\{x\} \) i na podstawie Faktu 5.3 (patrz fakt 5.3.) \( \bigcup\{x\}\subset \bigcup\{x,y\} \). Łącząc ze sobą te dwa fakty, otrzymujemy:

\( x=\bigcup\{x\}\subset\bigcup\{x,y\}=x\cup y, \)

co należało dowieść.

3. Na podstawie poprzedniego podpunktu otrzymujemy \( y\subset y\cup x \) i na podstawie pierwszego podpunktu \( y\cup x = x\cup y \), co należało wykazać.

4. Mamy \( x\cup x = \bigcup\{x,x\} = \bigcup\{x\}=x \), gdzie ostatnia równość pochodzi z poprzedniego ćwiczenia.

5. Dla dowolnego \( z \) mamy

\( z\in x \iff z\in x \lor \textrm{FAŁSZ} \iff z\in x \lor z\in\emptyset, \)

co, na mocy Faktu 5.4 (patrz fakt 5.4.), pokazuje, że \( x\cup\emptyset = x \).

Aksjomat sumy gwarantuje istnienie zbiorów więcej niż dwuelementowych w modelu. Skończone zbiory składające się z pewnej liczby elementów będziemy oznaczać, podobnie jak zbiory dwuelementowe, używając nawiasów klamrowych. Na przykład czteroelementowy zbiór składający się ze zbiorów \( x,y,z,w \) będzie oznaczany przez \( \{x,y,z,w\} \). Na podstawie aksjomatu zbioru pustego i aksjomatu pary możemy skonstruować zbiór \( \{\{\emptyset, \{\emptyset\}\},\{\{\{\emptyset\}\},\{\{\{\emptyset\}\}\}\}\} \) i otrzymać
\( \bigcup\{\{\emptyset, \{\emptyset\}\},\{\{\{\emptyset\}\},\{\{\{\emptyset\}\}\}\}\} = \{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\}\} \)

zbiór czteroelementowy. Rzeczą, której aksjomat sumy nie gwarantuje, jest istnienie zbiorów nieskończonych.

Ćwiczenie 5.3.

Skonstruuj model dla trzech pierwszych aksjomatów posiadający wyłącznie zbiory skończone.

Podpowiedź

Użyj w tym celu drzew. Skonstruuj model w taki sposób, aby dwa drzewa równe w sensie teorii mnogości musiały być identyczne.

Rozwiązanie

Aby skonstruować model dla pierwszych trzech aksjomatów, posłużymy się drzewami. Podobnie jak poprzednio najmniejsze drzewo składające się wyłącznie z jednego wierzchołka oznaczamy przez \( \bullet \). Aby jednak wprowadzić drzewa o dowolnej arności, potrzebujemy nowego zapisu. Dla drzew \( t_1,\dotsc,t_n \) możemy stworzyć nowe drzewo przez dodanie korzenia i podłączenie tych drzew bezpośrednio do niego -- takie drzewo oznaczymy przez \( \langle t_1,\dotsc, t_n \rangle \). W drzewach nie rozróżniamy kolejności występowania poddrzew ani krotności występowania danego poddrzewa, a więc drzewo \( \langle t_1,t_1,t_1,t_2,\dotsc,t_n \rangle \) jest identyczne z drzewem \( \langle t_1,\dotsc,t_n \rangle \). Podobnie drzewo \( \langle r,s,t \rangle \) jest identyczne z \( \langle s,t,r \rangle \). Podobnie jak dla drzew binarnych zdefiniujemy relację należenia -- dla dwóch drzew \( s \) i \( t \)
\( s\in t \), jeśli istnieją drzewa \( r_1,...., r_n \) takie, że drzewo \( t \) jest równe \( \langle s,r_1,...., r_n \rangle \).

Sprawdźmy teraz prawdziwość aksjomatów.

Podobnie jak w przypadku drzew binarnych \( \bullet \) jest zbiorem pustym. Dla aksjomatu pary, dla dwóch drzew \( r \) i \( s \), tworzymy, podobnie jak w przypadku binarnym drzewo \( \langle r,s \rangle \), którego jedynymi elementami są \( r \) i \( s \).

Aby sprawdzić prawdziwość aksjomatu unii, ustalmy drzewo \( t \), dla którego będziemy definiować \( \bigcup t \). Jeśli drzewo \( t \) jest równe \( \bullet \), to \( \bigcup t \) jest równe \( \bullet \). W przeciwnym przypadku \( t \) jest równe \( \langle t_1,\dotsc,t_n \rangle \) i każde \( t_i \) jest albo \( \bullet \), albo \( \langle t_i^1,\dotsc, t_i^{l_i} \rangle \). Jeśli \( i=1 \) i \( t_1 \) jest równe \( \bullet \), to \( \bigcup t \) równa się \( \bullet \), jeśli nie, to
\( \bigcup t \) jest równe \( \langle t_1^1,\dotsc,t_1^{l_1},\dotsc, t_n^1,\dotsc,t_n^{l_n} \rangle, \)
gdzie w wyrażeniu tworzącym drzewo występują indeksy, dla których \( t_i \) jest różne od \( \bullet \).

Jak wykazaliśmy, w tym modelu aksjomat zbioru pustego, aksjomat pary i aksjomat sumy są prawdziwe. Ilość elementów w zbiorze to ilość bezpośrednich następników korzenia w drzewie - liczba skończona.