Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach

From Studia Informatyczne

Spis treści

1 Wstęp
2 Podstawowe definicje
3 Aksjomat zbioru pustego
4 Aksjomat Pary
5 Aksjomat Sumy
6 Schemat aksjomatu wyróżniania
7 Aksjomat Nieskończoności
8 Aksjomat Zbioru Potęgowego
9 Schemat Aksjomatu Zastępowania
10 Aksjomat Regularności
11 Aksjomat Wyboru
12 Podsumowanie

Wstęp

Aksjomatyczna teoria mnogości powstała jako odpowiedź na paradoksy powstające w teorii naiwnej. Jest ona oparta o uzupełniony aksjomatami rachunek predykatów. Aksjomaty to formuły, o których zakładamy, że są prawdziwe. Słowo $\alpha \xi \iota \omega \mu \alpha$ , z którego wywodzi się aksjomat, oznaczało wśród filozofów greckich tezę, która jest oczywista i nie potrzebuje dowodu. Aksjomaty teorii mnogości to formuły, które definiują podstawowe własności zbiorów - przyjmujemy je bez dowodów i w oparciu o nie wyprowadzamy bardziej skomplikowane własności. Dlatego właśnie niezwykle istotne jest, aby aksjomaty były możliwie najprostsze w formie i aby ich "prawdziwość" była oczywista. Przyjęcie złej aksjomatyki może doprowadzić do sytuacji, w której udaje się poprawnie dowodzić twierdzenia zupełnie sprzeczne z intuicją. Aksjomaty to podstawy naszej teorii -- jeśli podstawy są nieodpowiednie, stworzona na nich teoria może być zupełnie nieprzydatna.

Istnieje wiele różnych aksjomatyzacji teorii mnogości. Aksjomatyka, którą przedstawiamy w tym wykładzie, została zaproponowana, w podstawowej wersji, przez Ernsta Zermelo i uzupełniona później przez Adolfa Abrahama Halevi Fraenkela. Stąd też pochodzi jej nazwa ZF (aksjomatyka Zermelo-Fraenkla). Jeden spośród aksjomatów prezentowanych w tym wykładzie zasługuje na szczególną uwagę, jest to aksjomat wyboru. Ten pozornie oczywisty aksjomat pociąga za sobą konsekwencje sprzeczne z intuicją. Aksjomat ten często wyróżniany jest z podstawowego zestawu i aksjomatyka bez niego oznaczana jest przez ZF, a z nim przez ZFC (gdzie ostatnia litera pochodzi od nazwy dodatkowego aksjomatu: Axiom of Choice).

[Edytuj]

Podstawowe definicje

Aksjomatyczna teoria mnogości jest oparta o rachunek predykatów posługujący się jedynym symbolem predykatowym. Symbol ten jest dwuargumentowy i oznaczamy go przez

$\in$

Predykat ten jest najczęściej interpretowany w modelu jako symbol przynależności do zbioru. Zbiór, który jest wartością zmiennej po lewej stronie symbolu jest elementem zbioru, który jest wartością zmiennej występującej po prawej.

Dla ułatwienia posługiwania się formalizmem związanym z aksjomatyczną teorią mnogości używamy wielu skrótów pozwalających na bardziej zwięzłe zapisywanie formuł. Często używany symbol $\notin$ jest skrótem mówiącym, że dwa elementy nie są ze sobą w relacji $\in$ , to znaczy

$x \notin y \stackrel{\textrm{def}}{\equiv} \lnot x\in y.$

Kolejny skrót oznaczamy przez $=$ i definiujemy go w następujący sposób,

$x = y \stackrel{\textrm{def}}{\equiv} \forall z \left( z\in x\iff z\in y\right).$

Zgodnie z intuicją wyniesioną z naiwnej teorii zbiorów skrót ten definiuje dwa zbiory jako równe, jeśli dla każdego wartościowania zmiennej $z$ element jest w zbiorze $x$ wtedy i tylko wtedy, kiedy jest w zbiorze $y$ . Nieformalnie, dwa zbiory są równe jeśli posiadają dokładnie te same elementy. W naszym języku nie mamy możliwości zdefiniowania pojedynczego bytu w modelu, gdyż nie mamy wpływu na to, jak interpretowane są predykaty. Będziemy mówić, że zbiór posiadający daną cechę jest unikalny, jeśli wszystkie zbiory posiadające tą cechę są równe.

Podobnie do równości jesteśmy w stanie zdefiniować zawieranie, czyli inkluzji zbiorów

$x \subset y \stackrel{\textrm{def}}{\equiv} \forall z \left( z\in x\implies z\in y\right).$

Inkluzja ta spełnia własności, które pochodzą z naiwnej teorii mnogości. Przede wszystkim, dwa zbiory są sobie równe wtedy i tylko wtedy, kiedy jeden jest podzbiorem drugiego, a drugi pierwszego.

Fakt 2.1.

Następująca formuła jest prawdziwa w aksjomatycznej teorii mnogości

$\forall x \forall y \left( x = y \iff x\subset y \land y\subset x\right).$

Dowód

Zastępując skróty przez odpowiadające im napisy, otrzymujemy:

$\forall x \forall y \left[ \forall z \left( z\in x\iff z\in y\right) \iff \forall z \left( z\in x\implies z\in y\right)\land \forall z \left( z\in y\implies z\in x\right)\right].$

Używając podstawowych własności rachunku predykatów, otrzymujemy:

$\forall x \forall y \left[\forall z \left( z\in x\iff z\in y\right) \iff \forall z \left( (z\in x\implies z\in y)\land ( z\in y\implies z\in x)\right)\right]$

i dalej

$\forall x \forall y \left[\forall z \left( z\in x\iff z\in y\right) \iff \forall z (z\in x\iff z\in y)\right],$

co jest tautologią rachunku predykatów.

W bardzo podobny sposób możemy pokazać, że

$\forall x \forall y \forall z (x\subset y \land y\subset z )\implies x\subset z.$

Czyli, że zawieranie zbiorów zdefiniowane w rachunku predykatów jest przechodnie.

[Edytuj]

Aksjomat zbioru pustego

Formuły, które daje się udowodnić wyłącznie na gruncie rachunku predykatów nie są interesujące. Aby na gruncie aksjomatycznej teorii mnogości udało się udowodnić nawet podstawowe fakty, potrzebujemy aksjomatów. Pierwszy aksjomat gwarantuje, oczywiste w naiwnej teorii mnogości, istnienie zbioru pustego.

Aksjomat zbioru pustego Zakładamy, że następująca formuła, zwana aksjomatem zbioru pustego, jest prawdą

$\exists x \forall y\; y\notin x,$

a zbiór $x$ spełniający ten warunek nazywamy zbiorem pustym i oznaczamy przez $\emptyset$ .

Aksjomat zbioru pustego mówi, że istnieje zbiór nieposiadający elementów. Dokładnie, definiująca go formuła mówi, że każdy $y$ nie należy do $\emptyset$ . Symbol $\emptyset$ oznacza dokładnie jeden zbiór, czego dowodzą poniższe fakty.

W następującym fakcie pokażemy, że istnieje nie więcej niż jeden zbiór pusty. Aksjomat zbioru pustego gwarantuje nam istnienie przynajmniej jednego zbioru pustego i w związku z tym zbiór pusty jest dokładnie jeden.

Fakt 3.1.

Istnieje co najwyżej jeden zbiór pusty, czyli następująca formuła jest prawdziwa

$\forall x\forall y \;\left(\forall z\,z\notin x\land \forall z \,z\notin y \right)\implies x=y.$

Dowód

Niewątpliwie

$\forall x\forall y \;\left(\forall z\,z\notin x\land \forall z \,z\notin y \right)\implies \left(\forall z\,(z\notin x\land z\notin y \right))$

skąd możemy wnioskować, że

$\forall x\forall y \;\left(\forall z\,z\notin x\land \forall z \,z\notin y \right)\implies \left(\forall z\,z\in x\iff z\in y \right)$

gdzie prawa strona implikacji jest definicją równości zbiorów. Intuicyjnie dowód przebiega następująco. Dwa zbiory są sobie równe, jeśli każdy element albo należy do obu z nich równocześnie, albo do żadnego. Weźmy dwa zbiory puste i dowolny element. Element ten nie należy do żadnego z tych zbiorów. Wnioskujemy, że zbiory te muszą być sobie równe.

[Edytuj]

Aksjomat Pary

Aby aksjomatyczna teoria mnogości była podobna do naiwnej teorii, którą chcemy naśladować, powinna gwarantować istnienie więcej niż jednego zbioru. Niestety, aksjomat zbioru pustego gwarantuje istnienie tylko jednego zbioru. Jednoelementowy model $\{a\}$ , gdzie $a\notin a$ , spełnia aksjomat zbioru pustego. Wprowadzenie następnego aksjomatu gwarantuje istnienie "nieskończonej ilości" zbiorów. Jest to aksjomat mówiący, że dla dowolnych dwóch bytów możemy stworzyć zbiór zawierający je i żadnych innych elementów. Stwierdzenie to jest prawdziwe w naiwnej teorii mnogości i zgodne z intuicją.

Zakładamy, że następująca formuła, zwana aksjomatem pary, jest prawdą

$\forall x \forall y \exists z \forall w\;\ w\in z \iff (w = x\lor w =y).$

Zbiór $z$ którego istnienie gwarantuje ten aksjomat jest oznaczany przez $\{x,y\}$ . W przypadku kiedy $x=y$ stosujemy skrót $\{x,x\} = \{x\}$ .

Podobnie jak dowodziliśmy unikalności zbioru pustego, możemy wykazać, że dla ustalonych zbiorów $x$ i $y$ istnieje dokładnie jeden zbiór $\{x,y\}$ . Weźmy dwa zbiory $z_1$ i $z_2$ takie, że dla każdego $w$ mamy $w\in z_1 \iff (w=x\lor w = y)$ i $w\in z_2 \iff (w=z\lor w=y)$ . Natychmiast otrzymujemy $w\in z_1 \iff w\in z_2$ , co dowodzi, że $z_1=z_2$ i że dla dowolnych dwóch zbiorów istnieje dokładnie jeden zbiór zawierający wyłącznie te zbiory jako elementy.

Aksjomat pary razem z aksjomatem zbioru pustego gwarantują, że modele dla aksjomatycznej teorii mnogości zawierają nieskończenie wiele zbiorów. Każdy model zawiera, na mocy aksjomatu zbioru pustego, zbiór pusty oznaczony przez $\emptyset$ . Na mocy aksjomatu pary w modelu istnieje również zbiór $\{\emptyset\}$ różny od zbioru pustego. Używając aksjomatu pary, jeszcze raz możemy skonstruować następny, różny od poprzednich zbiór $\{\{\emptyset\}\}$ . Tą procedurę możemy powtarzać dowolną ilość razy, konstruując za każdym razem nowy zbiór. Aksjomat pary nie gwarantuje istnienia zbiorów więcej niż dwuelementowych. Na podstawie aksjomatu zbioru pustego posiadamy zbiór zeroelementowy, aksjomat pary gwarantuje istnienie zbiorów jedno- i dwuelementowych.

Ćwiczenie 4.1

Skonstruuj model dla dwu pierwszych aksjomatów posiadający wyłącznie zbiory zero, jedno oraz dwuelementowe.

Podpowiedź

Użyj w tym celu drzew binarnych.

Rozwiązanie

Aby skonstruować model dla dwóch pierwszych aksjomatów, posłużymy się drzewami binarnymi. Oznaczymy jako $\bullet$ drzewo składające się z jednego liścia. Oznaczmy, dla dwu drzew binarnych $r$ i $s$ , drzewo powstałe z nich przez dodanie korzenia i połączenia go z tymi drzewami jako $r\,{}^{\land} s$ . Zaniedbujemy orientację w drzewach, a więc zawsze $r\,{}^{\land} s$ jest tym samym drzewem co $s\,{}^{\land} r$ . Rozważmy teraz wszystkie drzewa binarne tego typu i zdefiniujmy dla dwóch drzew $s$ i $t$

$s\in t$ , jeśli istnieje jakieś drzewo $r$ takie, że drzewo $t$ jest równe $s\,{}^{\land} r$ .

Sprawdźmy, czy w tym modelu aksjomat zbioru pustego i aksjomat pary są spełnione.

Aksjomat zbioru pustego mówi, że istnieje drzewo $t$ , dla którego nie ma drzew $s$ spełniających $s\in t$ . Oczywiście w naszym modelu jest to drzewo $\bullet$ .

Aksjomat pary mówi, że dla dowolnych dwóch drzew $r$ i $s$ istnieje drzewo $t$ takie, że $r\in t$ i $s\in t$ i relacja ta nie zachodzi dla żadnych innych zbiorów. W naszym modelu własność tę spełnia drzewo $r\,{}^{\land} s$ . Niewątpliwie $r\in r\,{}^{\land} s$ , ale ponieważ $r\,{}^{\land} s$ i $s\,{}^{\land} s$ są identyczne, to również $s\in r\,{}^{\land} s$ . Co więcej drzewo $r\,{}^{\land} s$ nie posiada żadnych innych poddrzew tego typu.

Wykazaliśmy, że nasz model spełnia aksjomat zbioru pustego i aksjomat pary. Pozostaje wykazać że, wszystkie zbiory są zero, jedno lub dwuelementowe. Zbiór $\bullet$ jest zeroelementowy. Każde drzewo postaci $t\,{}^{\land} t$ jest jednoelementowe, a każde drzewo postaci $r\,{}^{\land} s$ dla $r$ różnego od $s$ jest dwuelementowe (choć elementy tych zbiorów mogą być bardzo skomplikowane).

[Edytuj]

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 \implies \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.

[Edytuj]

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\implies 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\implies 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)$ .

Rozwiązanie

Ustalmy dowolne zbiory $x, y$ i $z$ .

1. Dla dowolnego zbioru $w$ mamy $w\in x\cap y$ jest równoważne $w\in x\land w\in y$ (na podstawie równania (+)). To z kolei jest równoważne $w\in y\land w\in x$ i $w\in y\cap x$ , co należało pokazać.

2. Dla dowolnego $w$ , prawdą jest $w\in x \land w\in y \implies w\in x$ czyli, na podstawie równania (+), $w\in x\cap y\implies w\in x$ , co należało dowieść.

3. Na podstawie dwóch poprzednich punktów $y\supset y\cap x$ i $y\cap x = x\cap y$ i ten przypadek jest dowiedziony.

4. Ten podpunkt w sposób trywialny wynika z równania (+), ponieważ dla dowolnego $w$ mamy $w\in x \iff w\in x \land w\in x$ .

5. W tym przypadku używamy równania (+) i otrzymujemy dla dowolnego $w$

$w\in \emptyset \iff \textrm{FAŁSZ} \land w\in x\iff w\in \emptyset \land w\in x,$

co należało dowieść.

6. Dla dowolnego $w$ mamy $w\in x\cap(y\cup z)$ wtedy i tylko wtedy, kiedy $w\in x \land (w\in y \lor w\in z)$ , co używając praw de'Morgana, jest równoważne $(w\in x \land w\in y)\lor (w\in x \land w\in z)$ , co oznacza, że $w\in (x\cap y)\cup(x\cap z)$ .

7. Podobnie jak w poprzednim przypadku używamy równania (+), aby otrzymać dla dowolnego $w$ :

$w \in x \cup (y \cap z) \iff w \in x \lor (w \in y \land w \in z) \iff$
$(w \in x \lor w \in y) \land (w \in x \lor w \in z) \iff w \in (x \cup y) \cap (x \cup z),$

co należało dowieść.

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 \implies \left( \forall y\; (\forall z\; z\in x \implies y\subset z)\implies y\subset \bigcap x\right)$

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 \implies 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) \implies \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 \implies \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 )\implies 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 \implies x=y$ .

Rozwiązanie

Ustalmy dowolne zbiory $x, y$ i $z$ .

1. Niech $w$ będzie dowolnym zbiorem w $x\setminus(x\setminus y)$ . Wtedy $w\in x \land \lnot (w\in x \land w\notin y)$ , co jest równoważne $w\in x \land (w\notin x \lor w\in y)$ i dalej (używając praw de'Morgana) $(w\in x\land w\notin x)\lor (w\in x \land w\in y)$ . Ponieważ pierwsza część alternatywy jest zawsze fałszem, otrzymujemy $w\in x\land w\in y$ , czyli $w\in x\cap y$ . Wszystkie zastosowane przejścia były równoważnościami, co dowodzi również inkluzji w drugą stronę.

2. Ustalmy $w$ jako dowolny element $x\setminus (y\cap z)$ . Wtedy $w\in x\land \lnot (w\in y \land w\in z)$ , czyli $w\in x \land (w\notin y \lor w\notin z)$ i dalej $(w\in x \land w\notin y)\lor (w\in x\land w\notin z)$ . Co jest równoważne $w\in (x\setminus y)\cup (x\setminus z)$ .

3. Tę tezę dowiedziemy niewprost. Załóżmy, że istnieje $w$ takie, że $w\in x$ i $w\notin y$ . Wtedy $w\in x\setminus y$ i $w\notin y\setminus x$ , co jest sprzecznością z założeniem. Ze względu na symetrię zmiennych teza jest prawdą.

[Edytuj]

Aksjomat Nieskończoności

Następujący aksjomat gwarantuje istnienie zbiorów nieskończonych. Działanie tego aksjomatu jest podobne do działania indukcji matematycznej omawianej wcześniej. Intuicyjnie aksjomat ten gwarantuje nam istnienie przynajmniej jednego zbioru zawierającego wszystkie liczby naturalne. Zbiór taki musi być nieskończony.

Aksjomat Nieskończoności Zakładamy, że następująca formuła, zwana aksjomatem nieskończoności, jest prawdą:

$\exists x\; \left(\emptyset\in x \land (\forall y\; y\in x\implies y\cup\{y\}\in x )\right).$

Rozważmy zbiór $x$ , którego istnienie jest gwarantowane przez aksjomat nieskończoności. Niewątpliwie $\emptyset\in x$ . Na podstawie drugiej części definicji wnioskujemy, że $\emptyset\cup \{\emptyset\}=\{\emptyset\}\in x$ . Stosując drugą część definicji raz jeszcze, otrzymujemy dalej $\{\emptyset\}\cup\{\{\emptyset\}\}=\{\emptyset,\{\emptyset\}\}\in x$ . Powtarzając tę operację za każdym razem, otrzymujemy nowy element zbioru $x$ . Intuicyjnie, wymagania stawiane zbiorowi $x$ w definicji gwarantują, że, na zasadzie podobnej do zasady indukcji matematycznej, będzie on posiadał "nieskończenie" wiele elementów. Zbiór ten może posiadać inne elementy niż te, które udają się skonstruować za pomocą procedury wymienionej powyżej.

Zbiór, którego istnienie gwarantuje aksjomat nieskończoności, jest używany do konstruowania liczb naturalnych. W konstrukcji liczb naturalnych opartej na liczbach porządkowych wprowadzonych po raz pierwszy przez Johna von Neumanna wyżej wymienione zbiory to kolejne liczby naturalne.

$\begin{array} {ll} \text{liczba naturalna zero to zbiór }&\emptyset \\ \text{liczba naturalna jeden to zbiór }&\{\emptyset\} \\ \text{liczba naturalna dwa to zbiór }&\{\emptyset,\{\emptyset\}\} \\ \text{liczba naturalna trzy to zbiór }&\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \\ \text{i tak dalej\dots}&\text{ } \end{array}$

W powyższej konstrukcji liczba naturalna to bardzo konkretny zbiór. Zbiór będący liczbą naturalną ma, intuicyjnie mówiąc, tyle elementów, jaka jest wartość tej liczby, choć nie każdy zbiór posiadający tyle elementów jest liczbą naturalną. Wykład 7 jest w całości poświęcony konsekwencjom tego aksjomatu; uzyskany tam zbiór liczb naturalnych jest najmniejszym $x$ spełniającym warunki aksjomatu nieskończoności.

[Edytuj]

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 9, 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\implies \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$ .

[Edytuj]

Schemat Aksjomatu Zastępowania

Kolejnym aksjomatem lub raczej schematem aksjomatu jest aksjomat zastępowania. Aksjomat ten, wraz z aksjomatem zbioru pustego, implikuje aksjomat wyróżniania i dlatego aksjomat wyróżniania jest często omijany w liście aksjomatów. Intuicyjna interpretacja tego aksjomatu jest następująca. Jeśli pewna własność, opisana formułą, ma cechy funkcji, to obrazem każdego zbioru, względem tej własności, jest również zbiór.

Aksjomat Zastępowania Dla dowolnej formuły $\varphi$ nieposiadającej zmiennych wolnych innych niż $w$ i $v$ następująca formuła jest prawdą:

$(\forall w \exists u \forall v\; \varphi \implies u=v)\implies \left(\forall x \exists y\forall v\; (v\in y \iff \exists w\; w\in x \land \varphi)\right)$

Aksjomat zastępowania posiada specyficzną formę. Istnienie zbioru $y$ jest zagwarantowane pod warunkiem, że formuła $\varphi$ spełnia wymaganą własność. Formuła $\varphi$ musi działać jak "funkcja częściowa", to znaczy, że jeśli jest spełniona dla zbiorów $w,v$ , to nie może być prawdą dla żadnych innych zbiorów $w,v'$ . Nieformalnie, formuła $\varphi$ przyporządkowuje jednoznacznie pewnym zbiorom inne zbiory. Pod tym warunkiem istnieje zbiór bytów przyporządkowany bytom z danego zbioru $x$ . Zupełnie nieformalnie możemy stwierdzić, że dla zdefiniowanej formułą częściowej funkcji, jeśli jako dziedzinę weźmiemy dowolny zbiór $x$ , to przeciwdziedzina tej funkcji również jest zbiorem.

Aksjomat zastępowania nie był jednym z aksjomatów zaproponowanych przez Ernsta ZermeloZostał on dodany później przez Adolfa Abrahama Halevi Fraenkela i jest stosowany obecnie jako część aksjomatyki, którą nazywamy potocznie ZF. Pokażemy teraz, że aksjomat zastępowania implikuje aksjomat wyróżniania.

Rozpoczynając dowód, ustalamy $x$ i $\varphi$ , do których chcielibyśmy zastosować aksjomat wyróżniania. Jedyną zmienną wolną w $\varphi$ jest $z$ i aksjomat wyróżniania gwarantuje istnienie zbioru $y$ będącego podzbiorem $x$ i składającego się dokładnie z tych elementów, dla których $\varphi$ jest prawdą. Aby istnienie zbioru $y$ zostało zagwarantowane przez aksjomat zastępowania, musimy zmienić formułę $\varphi$ . Nowa formuła $\varphi'$ wygląda następująco

$\exists z\; \varphi \land z=w=v.$

Formuła $\varphi'$ posiada dwie zmienne wolne $w$ i $v$ i spełnia warunek jednoznaczności, gdyż jeśli jest prawdą dla $w$ i $v$ , to niewątpliwie $w=v$ . Co więcej formuła jest prawdą dla wyłącznie tych $w=v$ , dla których $\varphi$ jest prawdą przy założeniu, że $z=w=v$ . Stosując aksjomat zastępowania dla tego samego $x$ , dla którego chcielibyśmy stosować aksjomat wyróżniania, otrzymujemy zbiór tych $v$ , dla których $\varphi'$ jest prawdą dla pewnego $w\in x$ . Ale skoro tak, to $w=z=v$ i $\varphi$ jest prawdą dla $z$ , co dowodzi, że otrzymaliśmy dokładnie ten sam zbiór. Dowiedliśmy, że aksjomat zastępowania implikuje aksjomat wyróżniania.

[Edytuj]

Aksjomat Regularności

W skład zestawu aksjomatów zaproponowanych przez Ernsta Zermelo i uzupełnionych później przez Adolfa Abrahama Halevi Fraenkela wchodzą dodatkowe dwa aksjomaty. Pierwszym z nich jest aksjomat regularności.

Aksjomat Regularności Zakładamy, że następująca formuła, zwana aksjomatem regularności, jest prawdą:

$\forall x\; \left(x\neq\emptyset \implies \exists y\; (y\in x \land y\cap x = \emptyset )\right).$

(Zwróćmy uwagę, że występujący w formule napis $y\cap x =\emptyset$ , można zastąpić równoważnym napisem $\neg \exists z\; z \in y \wedge z \in x$ , unikając tym samym symbolu $\cap$ . ) Aksjomat regularności nazywamy czasem aksjomatem ufundowania. Gwarantuje on, że zbiory budowane są zgodnie z intuicją. Mówi, że każdy zbiór posiada element przecinający się pusto z nim samym. W szczególności, używając aksjomatu regularności możemy pokazać, że żaden zbiór nie zawiera samego siebie.

Fakt 10.1.

Żaden zbiór nie jest swoim własnym elementem, równoważnie, następująca formuła jest prawdziwa:

$\forall x\; x\notin x.$

Dowód

Dla dowodu niewprost załóżmy, że nasz fakt jest nieprawdziwy i ustalmy $x$ takie, że $x\in x$ . Na podstawie aksjomatu pary możemy stworzyć zbiór $\{x\}$ . Istnienie takiego zbioru przeczy jednak aksjomatowi regularności, ponieważ jedynym elementem $\{x\}$ jest $x$ i $\{x\}\cap x \neq \emptyset$ , ponieważ $x\in \{x\}\cap x$ . Sprzeczność z aksjomatem w dowodzie niewprost gwarantuje, że fakt jest prawdziwy.

[Edytuj]

Aksjomat Wyboru

Ostatnim aksjomatem jest aksjomat wyboru. Jest to aksjomat, który wywołał dużą liczbę kontrowersji. Wielu znakomitych matematyków początku XX wieku uważało, że nie należy go dopuścić do zestawu podstawowych aksjomatów. W chwili obecnej większość matematyków uważa, że aksjomat wyboru jest prawdziwy, nawet jeśli jego konsekwencje są bardzo nieintuicyjne. System aksjomatów przedstawionych powyżej oznaczamy przez ZF -- skrót pochodzący od pierwszych liter nazwisk jego twórców. Zestaw aksjomatów z przedstawionym poniżej aksjomatem wyboru oznaczamy przez ZFC, gdzie C jest symbolicznym zapisem dodatkowego aksjomatu (Axiom of Choice). Prezentujemy poniżej jedną z wielu równoważnych postaci aksjomatu.

Aksjomat Wyboru. Następująca formuła jest prawdziwa:

$\forall x\ \left( \emptyset\notin x\land \forall y\forall z\ (z\in x\land y\in x) \implies (z=y \lor z\cap y = \emptyset)\right)\implies \exists w \forall v\ (v \in x \implies \exists u\ v\cap w=\{u\})$

Aksjomat wyboru mówi, że jeśli $x$ jest zbiorem nie zawierającym zbioru pustego oraz takim, że każde dwa jego elementy są rozłączne, to istnieje zbiór $w$ , który z każdym z elementów $x$ ma dokładnie jeden element wspólny. Intuicyjnie znaczy to, że mając rodzinę rozłącznych zbiorów, możemy stworzyć zbiór, wybierając po jednym elemencie z każdego zbioru.

Własność gwarantowana przez aksjomat wyboru może wydawać się intuicyjnie oczywista. Niestety konsekwencje, jakie pociąga za sobą przyjęcie tego aksjomatu, zniechęciły wielu matematyków. Jedną z konsekwencji aksjomatu wyboru jest twierdzenie znane jako Paradoks Banacha-Tarskiego - nie jest to sprzeczność logiczna jak paradoks Bertrandta Russella, a jedynie bardzo nieintuicyjny fakt. Twierdzenie to mówi, że trójwymiarową kulę można podzielić na sześć części, z których, za pomocą obrotów i translacji, da się skonstruować dwie kule identyczne z tą pierwszą.

[Edytuj]

Podsumowanie

Wszystkie dowody pojawiające się w kolejnych wykładach bazują na aksjomatyce ZF lub ZFC. Część dowodów przedstawionych podczas pozostałych wykładów nie korzysta z aksjomatu wyboru. Z kontekstu, w jakim są prezentowane, jest oczywiste, czy dany dowód wymaga, czy też nie wymaga tego aksjomatu.

Źródło: "http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_4:_Teoria_mnogo%C5%9Bci_ZFC._Operacje_na_zbiorach"

Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach

From Studia Informatyczne

Spis treści

Wstęp

Podstawowe definicje

Aksjomat zbioru pustego

Aksjomat Pary

Aksjomat Sumy

Schemat aksjomatu wyróżniania

Aksjomat Nieskończoności

Aksjomat Zbioru Potęgowego

Schemat Aksjomatu Zastępowania

Aksjomat Regularności

Aksjomat Wyboru

Podsumowanie

Nawigacja

Szukaj

Napisz do nas