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

$x\cup y = y\cup x$ ,

$x\subset x\cup y$ ,

$y\subset x\cup y$ ,

$x\cup x = x$ ,

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