Zapoznanie się z podstawowymi pojęciami i narzędziami matematyki. Wprowadzenie fundamentalnych obiektów matematycznych i opis ich własności.
Czy zbiór bocianów jest elementem zbioru wszystkich ptaków?
Oznaczmy powyższe zdania przez \( p,q,r \) (w takiej właśnie kolejności). Używając symboli, które zwyczajowo odpowiadają potocznemu rozumieniu spójników jeśli [..] to, lub oraz powyższych oznaczeń, otrzymamy formułę
\( p \Rightarrow (q \vee r). \)
Jeśli powyższą formułę uznamy za prawdziwą, to może nam ona posłużyć do otrzymania nowych wniosków. Na przykład, jeśli o jakiejś liczbie \( \mathrm {n} \) będziemy wiedzieć, że jest liczbą pierwszą oraz że nie jest nieparzysta, to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt, że liczba \(\mathrm {n} \) jest równa 2. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:
to zgodnie z klasycznym rachunkiem zdań powinniśmy uznać za prawdziwe zdanie \( \mathrm {r} \), czyli \( \mathrm {n} \) jest równe 2. Powyższy schemat wnioskowania można również opisać formułą
\( ((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q))\Rightarrow q. \)
W powyższej formule symbol \( \wedge \) odpowiada spójnikowi \( \mathrm {i} \) (oraz).
Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy wnioskowania i zdania złożone oraz oceniać ich prawdziwość.
Wielu matematyków zgadza się dzisiaj co do tego, że zdania pasujące do poniższych schematów powinny być uznane za prawdziwe:
Definicja 3.1 Aksjomaty klasycznego rachunku zdań
Zdania pasujące do powyższych schematów to wszystkie zdania, które można otrzymać, podstawiając w miejsce \( \phi, \nu, \psi \) dowolne formuły.
Przyglądnijmy się teraz jak posługujemy się implikacją we wnioskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:
jeśli \( {\phi} \) to \( {\psi} \).
W takim przypadku, jeśli akceptujemy powyższą implikacjię jako zdanie prawdziwe oraz jeśli zdanie \( {\phi} \) jako prawdziwe, to powinniśmy także zaakceptować \( {\psi} \). Przedstawiony sposób wnioskowania nosi nazwę reguły Modus Ponens (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób
\( \frac{\phi \Rightarrow \psi, \phi} {\psi}. \)
Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów o ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych aksjomatów, definiujemy poniżej pojęcie dowodu.
Definicja 3.2
Ciąg formuł \( \phi_0, \dots ,\phi_n \) jest dowodem formuły \( {\psi} \) wtedy i tylko wtedy, gdy:
W drugim punkcie powyższej definicji, jeśli formuła \( \phi_i \) nie jest aksjomatem (a więc powstaje przez zastosowanie MP), to formuły \( \phi_j,\phi_k \) muszą pasować do przesłanek reguły MP, a więc \( \phi_j \) musi być postaci \( \phi_k \Rightarrow \phi_i \) lub \( \phi_k \) postaci \( \phi_j \Rightarrow \phi_i \).
Definicja 3.3
Formułę nazywamy twierdzeniem klasycznego rachunku zdań jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań 3.1
Zastanówmy się na formułą postaci \( \phi \Rightarrow \phi \). Intuicja podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów, użyliśmy nawiasów kwadratowych dla nawiasów, które pochodzą ze schematów.
Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za prawdziwe, zdefiniowaliśmy, wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły Modus Ponens. Warto zwrócić uwagę, że pomimo tego, iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.
Uwaga 3.4
Warto przyglądnąć się przyjętym aksjomatom i zastanowić się jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni uznać je za prawdziwe. Pomocne może być interpretowanie formuł postaci \( \phi \Rightarrow (\nu \Rightarrow \psi) \) jako „jeśli prawdziwe jest \( {\phi} \) i prawdziwe jest \( \nu \) to prawdziwe jest \( {\psi} \)”. W kolejnych rozdziałach przekonamy się, że taka interpretacja jest uzasadniona.
Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie
Jeśli \( \mathrm {n} \) jest liczbą pierwszą to \( \mathrm {n} \) jest liczbą nieparzystą lub \( \mathrm {n} \) jest równe 2.
Opisaliśmy je wtedy formułą
\( p \Rightarrow (q \vee r). \)
w której \( p,q,r \) odpowiadały odpowiednio zdaniom
Podstawiając zamiast zdania \(\mathrm {n} \) jest liczbą pierwszą zmienną zdaniową \( \mathrm {p} \) ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie \( \mathrm {n} \), co więcej zdania \( {p,q} \) i \( \mathrm {r} \) dotyczą tej samej liczby \( \mathrm {n} \). Zapiszmy więc \( p(n) \) zamiast \( {p} \) aby podkreślić fakt że prawdziwość \( {p} \) zależy od tego jaką konkretną wartość przypiszemy zmiennej \( \mathrm {n} \). Zdanie \( p(n) \) będzie prawdziwe jeśli za \( \mathrm {n} \) podstawimy jakąś liczbę pierwszą i fałszywe w przeciwnym przypadku. Zgodnie z tą konwencją nasze zdanie przyjmie postać
\( p(n) \Rightarrow (q(n) \vee r(n)). \)
Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania \( \mathrm {p} \) dopóki nie podstawimy w miejsce \( \mathrm {n} \) jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce \( \mathrm {n} \) zdanie będzie prawdziwe. Możemy więc przeformułować je jako
Dla każdej liczby naturalnej \( \mathrm {n} \), jeśli \( \mathrm {n} \) jest liczbą pierwszą to \( \mathrm {n} \) jest liczbą nieparzystą lub \( \mathrm {n} \) jest równe 2.
Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy kwantyfikator \( \forall \) który będzie oznaczał ,,dla każdego" oraz \( \exists \) który będzie oznaczał ,,istnieje". Każde wystąpienie kwantyfikatora będzie dotyczyło pewnej zmiennej. W naszym przykładzie napiszemy
\( \forall_n p(n) \Rightarrow (q(n) \vee r(n)). \quad \mbox{(1.1)} \)
Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa w zbiorze liczb naturalnych, gdzie \( p(n),q(n),r(n) \) będą oznaczać odpowiednio \(\mathrm {n} \) jest liczbą pierwszą, \( \mathrm {n} \) jest liczbą nieparzystą, \( \mathrm {n} \) jest równe 2.
Przy tej samej interpretacji \( p(n),q(n) \) moglibyśmy wyrazić zdanie
Istnieje parzysta liczba pierwsza.
jako
\( \exists_n p(n) \wedge \neg q(n) \quad \mbox{(1.2)} \)
Rachunek predykatów podobnie jak klasyczny rachunek zdań może być wprowadzony aksjomatycznie. Pierwsza grupa aksjomatów to aksjomaty klasycznego rachunku zdań. Druga dotyczy kwantyfikatora \( \forall \) oraz jego interakcji z implikacją. Przypomnijmy, że kwantyfikator \( \exists \) traktujemy jako pewien skrót zapisu.
Definicja 3.1. Schematy aksjomatów rachunku predykatów
Poza tym do aksjomatów dorzucamy również wszystkie generalizacje formuł pasujących do powyższych schematów. Generalizacja formuły jest to ta sama formuła poprzedzona blokiem kwantyfikatorów ogólnych - dla dowolej formuły \( \phi \) oraz dowolnych zmiennych \( x_1,\dots,x_k \) formuła \( \forall_{x_1} \dots \forall_{x_k} \phi \) jest generalizacją \( \phi \).
Podobnie jak w rachunku zdań dowodem formuły \( {\phi} \) nazwiemy ciąg formuł \( \phi_0, \dots, \phi_n \) taki, że \( \phi_n \) jest tym samym napisem co \( {\phi} \) a każda formuła \( \phi_i \) dla \( i < n \) jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły Modus Ponens z Wykładu 2.
Definicja 3.2.
Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.
Przykład 3.3.
Formalne dowody twierdzeń rachunku predykatów są zwykle skomplikowane. Dlatego w rozważanym przykładzie poczynimy kilka uproszczeń. Będziemy się zajmować formułą \( \displaystyle p(t) \Rightarrow \exists_x p(x). \)
Zamiast dowodzić dokładnie powyższą formułę, dowiedziemy podobny fakt, a mianowicie, że jeśli dołączymy do zbioru aksjomatów formułę \( \displaystyle p(t) \), to będziemy w stanie udowodnić \( \displaystyle \exists_x p(x) \). Twierdzenie o dedukcji, które można znaleźć w wykładzie Logika dla informatyków, mówi, że te podejścia są równoważne.
W poniższym dowodzie pominiemy również dowód formuły \( \displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x) \). Formuła ta pasuje do schematu \( \displaystyle \neg \neg \phi \Rightarrow \phi \). Łatwo więc sprawdzić, że formuła \( \displaystyle \neg \neg \phi \Rightarrow \phi \) jest tautologią klasycznego rachunku zdań, a więc -- w myśl twierdzenia Posta (patrz Wykład 2, Twierdzenie 4.4) -- ma dowód. Po zastąpieniu w tym dowodzie zmiennej \( \displaystyle \phi \) formułą \( \displaystyle \forall_x \neg p(x) \), otrzymamy dowód formuły \( \displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow \forall_x \neg p(x) \).
Przestawiamy uproszczony dowód formuły \( \displaystyle p(t) \Rightarrow \exists_x p(x) \):
Ostatnia formuła to dokładnie \( \displaystyle \exists_x p(x) \) po rozpisaniu skrótu \( \displaystyle \exists \).
W oparciu o logikę predykatów możemy budować nowe teorie, dokładając inne, tzw. pozalogiczne aksjomaty. W językach wielu teorii pojawia się symbol predykatywny \( =^2 \), mający symbolizować równość. Ponieważ zwykle wymagamy aby te same własności były spełnione dla \( =^2 \), zostały wyodrębnione specjalne aksjomaty dla równości. Aksjomaty, te to wszystkie formuły oraz ich generalizacje odpowiadające poniższym schematom:
Rozważmy język, w którym mamy jeden binarny symbol predykatywny \( =^2 \), jeden symbol stałej \( 0 \) oraz symbole funkcyjne \( s^1, +^2, \times^2 \). Zgodnie z przyjętą konwencją termy i formuły będziemy zapisywać infixowo. Do aksjomatów logicznych, oraz aksjomatów dla równości, dokładamy następujące aksjomaty:
Teorią Q nazwiemy wszystkie formuły w ustalonym języku które da się udowodnić z aksjomatów logiki predykatów z dołączonymi aksjomatami równości oraz 1-7. Nietrudno się przekonać, że wszystkie twierdzenia teorii Q są prawdziwe w liczbach naturalnych, przy naturalnej interpretacji występujących symboli (\( s(x) \) interpretujemy jako \( x+1 \)). W następnym wykładzie (patrz Wykład 4) przedstawiamy aksjomatyczną teorię w rachunku predykatów nazywaną teorią mnogości ZFC.
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).
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 ( z\in x\iff z\in y). \)
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 ( z\in x \Longrightarrow z\in y). \)
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 ( x = y \iff x\subset y \land y\subset x). \)
Dowód
Zastępując skróty przez odpowiadające im napisy, otrzymujemy:
\( \forall x \forall y [ \forall z ( z\in x\iff z\in y) \iff \forall z ( z\in x \Longrightarrow z\in y)\land \forall z ( z\in y \Longrightarrow z\in x)]. \)
Używając podstawowych własności rachunku predykatów, otrzymujemy:
\( \forall x \forall y [\forall z ( z\in x\iff z\in y) \iff \forall z ( (z\in x \Longrightarrow z\in y)\land ( z\in y \Longrightarrow z\in x))] \)
i dalej
\( \forall x \forall y [\forall z ( z\in x\iff z\in y) \iff \forall z (z\in x\iff z\in y)], \)
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 ) \Longrightarrow x\subset z. \)
Czyli, że zawieranie zbiorów zdefiniowane w rachunku predykatów jest przechodnie.
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 \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow x=y. \)
Dowód
Niewątpliwie
\( \forall x\forall y \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow (\forall z\,(z\notin x\land z\notin y )) \)
skąd możemy wnioskować, że
\( \forall x\forall y \;(\forall z\,z\notin x\land \forall z \,z\notin y ) \Longrightarrow (\forall z\,z\in x\iff z\in y ) \)
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.
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\; (\emptyset\in x \land (\forall y\; y\in x\Longrightarrow y\cup\{y\}\in x )). \)
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.
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 \Longrightarrow u=v) \Longrightarrow (\forall x \exists y\forall v\; (v\in y \iff \exists w\; w\in x \land \varphi)) \)
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 Zermelo. Został 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.
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\; (x\neq\emptyset \Longrightarrow \exists y\; (y\in x \land y\cap x = \emptyset )). \)
(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.
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\ ( \emptyset\notin x\land \forall y\forall z\ (z\in x\land y\in x) \Longrightarrow (z=y \lor z\cap y = \emptyset))\Longrightarrow \exists w \forall v\ (v \in x \Longrightarrow \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ą.
W definicji iloczynu kartezjańskiego (patrz Wykład 5: "Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów" Definicja 2.1) jest pewna nieścisłość. Konstrukcja iloczynu kartezjańskiego odwołuje się do aksjomatu wyróżniania w wersji nieuprawomocnionej. Konstrukcja, którą zobaczą państwo w tym rozdziale, usuwa tę poprzednią niedogodność.
Twierdzenie 5.1.
Dla dowolnych dwóch zbiorów \( \displaystyle x \) i \( \displaystyle y \) istnieje zbiór \( \displaystyle x\times y \) zawierający wszystkie pary postaci \( \displaystyle (w,z) \), gdzie \( \displaystyle w\in x \) i \( \displaystyle z\in y \).
Dowód
Ustalmy dwa dowolne zbiory \( \displaystyle x \) i \( \displaystyle y \). Jeśli \( \displaystyle x=\emptyset \) lub \( \displaystyle y=\emptyset \), to \( \displaystyle x\times y = \emptyset \) istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku \( \displaystyle x\cup y \) jest zbiorem jednoelementowym \( \displaystyle \{z\} \), to \( \displaystyle x\times y=\{\{\{z\}\}\} \) istnieje na podstawie aksjomatu pary. W dalszej części dowodu zakładamy, że zbiory \( \displaystyle x \) i \( \displaystyle y \) są niepuste i że \( \displaystyle x\cup y \) ma więcej niż jeden element. Na podstawie aksjomatu zbioru potęgowego, aksjomatu unii i aksjomatu wycinania następujące zbiory istnieją:
\( \displaystyle \begin{align*} A & =\{z\in\mathcal{P}(x)\,|\, \exists w\; z =\{w\}\}, \\ B & =\{z\in\mathcal{P}(x\cup y)\,|\, \exists w \exists v\; (w \neq v \land z=\{v,w\})\}, \\ C & =\{z\in\mathcal{P}(\mathcal{P}(y))\,|\, \exists v\; z=\{\{v\}\}=(v,v)\}. \end{align*} \)
Nasze założenia gwarantują, że żaden z powyższych zbiorów nie jest pusty. Kontynuując, możemy stworzyć:
\( \displaystyle \begin{align*} D_0 & =\{z\in\mathcal{P}(A\cup B)\,|\, \exists w \exists v\; w\neq v \land z=\{\{w\},\{w,v\}\}=(w,v)\}, \end{align*} \)
w którym to zbiorze mamy pewność, że \( \displaystyle w \) jest elementem \( \displaystyle x \). Kontynuujemy, definiując:
\( \displaystyle \begin{align*} D_0' & =\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(v,v)\}\}, \end{align*} \)
gdzie mamy pewność, że \( \displaystyle w \) jest elementem \( \displaystyle x \), a \( \displaystyle v \) elementem \( \displaystyle y \) oraz:
\( \displaystyle \begin{align*} D_0'' & =\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(w,w )\}\}, \end{align*} \)
gdzie mamy pewność, że \( \displaystyle w\in A\cap B \). Kończąc:
\( \displaystyle \begin{align*} x\times y & =\{z\in\bigcup D_0' \,|\, \exists w \exists v\; w\neq v \land z=(w,v)\}\cup \{z\in\bigcup D_0'' \,|\, \exists w\; z=(w,w)\}. \end{align*} \)
Twierdzenie 5.2.
Jeśli \( \displaystyle x,y \) i \( \displaystyle z \) są zbiorami i \( \displaystyle z\subseteq x\times y \), to zbiorem jest również ogół \( \displaystyle v \) takich, że istnieje \( \displaystyle w \) spełniające \( \displaystyle (v,w)\in z \). Zbiór takich \( \displaystyle v \) oznaczamy przez \( \displaystyle \pi_1(z) \) i nazywamy projekcją na pierwszą współrzędną.
Dowód
Zbiór \( \displaystyle \pi_1(z) \) istnieje na podstawie aksjomatów ZF i jest równy:
\( \displaystyle \pi_1(z) = \bigcup\{w\in\bigcup z\,|\, \exists u\; w=\{u\}\}. \)
W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykładzie 4 (patrz Wykład 4: "Teoria mnogości ZFC. Operacje na zbiorach"). Dla dowolnej formuły \( \displaystyle \varphi' \) nieposiadającej zmiennych wolnych innych niż \( \displaystyle z' \) i \( \displaystyle x_1' \), następująca formuła jest prawdą:
\( \displaystyle \forall x_1' \forall x' \exists y' \forall z'\; z'\in y' \iff (z'\in x' \land \varphi'). \)
Aby dowieść tę własność, ustalmy dowolną formułę \( \displaystyle \varphi' \) i dowolny zbiór \( \displaystyle x_1' \). Stosujemy aksjomat wyróżniania do \( \displaystyle x=x\times \{x_1'\} \) (który istnieje na mocy Twierdzenia 5.1 i do formuły
\( \displaystyle \exists z' \exists x_1'\; z=(z',x_1')\land\varphi', \)
otrzymując zbiór \( \displaystyle y \). Wymagany zbiór \( \displaystyle y' \) istnieje na mocy Twierdzenia 5.2 i jest równy \( \displaystyle \pi_1(y) \).
Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji z iloczynu kartezjańskiego. Aby otrzymać \( \displaystyle \pi_2(z) \), stosujemy powyższe twierdzenie do \( \displaystyle x_1'=z \), \( \displaystyle x=\bigcup\bigcup{z} \) i wyrażenia \( \displaystyle \varphi' \) mówiącego \( \displaystyle \exists w\; (w,z')\in x_1' \).
Warto wspomnieć, że rozważa się również teorie, w których pierwotnymi pojęciami są właśnie funkcje i składanie funkcji. Okazuje się, że bardzo wiele twierdzeń klasycznej matematyki (opartej na teorii zbiorów) da się udowodnić na ich gruncie. Takiemu właśnie podejściu poświęcony jest wykład Teoria kategorii dla informatyków.
Twierdzenie Knastra-Tarskiego posłuży nam do udowodnienia lematu
Banacha, który z kolei wykorzystamy w wykładzie "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum" dotyczącym teorii mocy.
Twierdzenie 7.8.
Dla dowolnych zbiorów \( X,Y \) oraz funkcji \( f:X \rightarrow Y \) i \( g:Y \rightarrow X \) istnieją zbiory \( A_1,A_2 \subset X \) oraz \( B_1,B_2 \subset Y \) takie, że:
Dowód
Rozważmy funkcję \( F:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \) zdefiniowaną następująco. Dla dowolnego \( A\subset X \) niech
\( F(A)= X\setminus \vec{g}(Y\setminus \vec{f}(A)). \)
Pokażemy najpierw, że \( F \) jest monotoniczna. Weźmy dowolne zbiory \( C_1,C_2 \subset X \) takie, że \( C_1 \subset C_2 \). Wtedy
\( \vec{f}(C_1) \subset \vec{f}(C_2), \)
więc
\( Y \setminus \vec{f}(C_1) \supset Y\setminus \vec{f}(C_2) \)
\( \vec{g}( Y \setminus \vec{f}(C_1)) \supset \vec{g}(Y\setminus \vec{f}(C_2)) \)
\( X \setminus \vec{g}( Y \setminus \vec{f}(C_1)) \subset X \setminus \vec{g}(Y\setminus \vec{f}(C_2)), \)
a więc \( F(C_1) \subset F(C_2) \).
Skoro \( F \) jest monotoniczna, to na mocy twierdzenia 7.6 Knastra-Tarskiego posiada najmniejszy punkt stały. Oznaczmy go przez \( A_1 \). Zdefiniujemy teraz pozostałe zbiory z tezy twierdzenia. Niech:
\( A_2\stackrel{\textrm{def}}{\equiv} X \setminus A_1, \)
\( B_1 \stackrel{\textrm{def}}{\equiv} \vec{f}(A_1), \)
\( B_2 \stackrel{\textrm{def}}{\equiv} Y \setminus B_1. \)
Z definicji zbiorów \( A_1,A_2,B_1,B_2 \) natychmiast wynika, że zbiory \( \{A_1,A_2\} \) oraz \( \{B_1,B_2\} \) tworzą odpowiednio podziały zbiorów \( X \) i \( Y \). Również z definicji spełniony jest punkt trzeci tezy (czyli \( B_1 \stackrel{\textrm{def}}{\equiv} \vec{f}(A_1) \)). Pozostaje pokazać, że zachodzi punkt czwarty. Skoro \( A_1 \) jest punktem stałym funkcji \( F \), to
\( A_1= X\setminus \vec{g}(Y\setminus \vec{f}(A_1)). \)
Podstawiając kolejno w powyższym wzorze zdefiniowane zbiory, otrzymujemy:
\( A_1= X\setminus \vec{g}(Y\setminus B_1), \)
\( A_1= X\setminus \vec{g}( B_2). \)
Odejmując obie strony od \( X \), otrzymamy:
\( X \setminus A_1 = \vec{g}( B_2). \)
Ponieważ jednak lewa strona w powyższej równości jest z definicji równa \( A_2 \), to otrzymujemy: \( A_2 = \vec{g}( B_2). \)
W teorii mnogości liczby naturalne, podobnie jak wszystkie inne byty, muszą być zbiorami. Od aksjomatyki teorii mnogości niewątpliwie należy wymagać, aby gwarantowała ich istnienie. W aksjomatyce ZF opisanej w wykładzie "Teoria mnogości ZFC. Operacje na zbiorach" jako liczby naturalne przyjmuje się zbiory, do których istnienia niezbędny jest aksjomat zbioru pustego, aksjomat pary i aksjomat sumy. Konstrukcja liczb naturalnych przedstawiona w dalszej części wykładu została zaproponowanych przez Johna von Neumanna jak specyficzny przypadek liczb porządkowych, które będą dokładniej przedstawione w wykładzie "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady".
Liczby naturalne definiujemy następująco. Liczbą naturalną zero jest zbiór pusty \( \emptyset \). Każdą następną liczbę naturalną otrzymujemy z poprzedniej w prosty sposób:
jeśli \( n \) jest liczbą naturalną, to następną po niej liczbą jest \( n'\stackrel{\textrm{def}}{\equiv} \{n\} \cup n \)
Początkowe liczby naturalne to:
\( \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} \)
Liczby naturalne to zbiory, których istnienie jest zagwarantowane przez aksjomaty ZF. Intuicyjnie, patrząc na nie widzimy, że posiadają tyle elementów jaka jest "wartość" liczby. Zero, to zbiór pusty, jeden, to zbiór którego jedynym elementem jest \( \emptyset \) i tak dalej.
Zakładamy, że następująca formuła, zwana aksjomatem nieskończoności, jest prawdą:
\( \exists x\; (\emptyset\in x \land (\forall y\; y\in x \Longrightarrow y\cup\{y\}\in x )). \) Każdy zbiór \( x \) spełniający warunek występujący w aksjomacie nieskończoności nazywamy zbiorem induktywnym. Aksjomat nieskończoności nie nakłada żadnych ograniczeń górnych na zbiory induktywne -- mogą być one dowolnie wielkie. Zbiorem liczb naturalnych będziemy nazywać najmniejszy ze zbiorów induktywnych. Wcześniej jednak musimy udowodnić, że zbiór taki istnieje. Następujące fakty pozwolą nam go zdefiniować.
Lemat 2.1.
Jeśli \( x \) jest niepustym zbiorem zbiorów induktywnych to \( \bigcap x \) jest również zbiorem induktywnym.
Dowód
Aby wykazać, że \( \bigcap x \) jest zbiorem induktywnym, musimy wykazać, że:
oraz że
Ponieważ każdy z elementów \( x \) jest zbiorem induktywnym, to \( \forall z\; z\in x\Longrightarrow \emptyset\in z \), czyli zbiór pusty jest w każdym z elementów \( x \). Jeśli jakiś zbiór jest w każdym elemencie zbioru, to jest również w jego przecięciu, czyli \( \emptyset \in \bigcap x \). Pozostaje wykazać drugi fakt, weźmy dowolny \( y\in\bigcap x \). Natychmiastową konsekwencją jest, że dla każdego \( z \), elementu \( x \) mamy \( y\in z \). Skoro każdy element \( x \) jest zbiorem induktywnym, to dla każdego \( z \) w \( x \) mamy \( y\cup\{y\}\in z \) i, z definicji przecięcia, \( y\cup \{y\}\in\bigcap x \). W ten sposób udowodniliśmy oba warunki i równocześnie lemat.
Przechodzimy do dowodu głównego twierdzenia. Mówi ono, że istnieje zbiór induktywny będący podzbiorem wszystkich zbiorów induktywnych.
Twierdzenie 2.2.
Istnieje najmniejszy, pod względem inkluzji, zbiór induktywny.
Dowód
Na mocy aksjomatu nieskończoności istnieje co najmniej jeden zbiór induktywny -- oznaczmy go przez \( x \). Rozważmy wszystkie podzbiory \( \mathcal{P}(x) \) tego zbioru i wybierzmy z nich, na mocy aksjomatu wyróżniania, zbiory induktywne -- powstały w ten sposób podzbiór \( \mathcal{P}(x) \) nazwijmy \( y \). Zbiór \( y \) jest niepusty, ponieważ \( x\in y \) jest zagwarantowane przez fakt, że \( x\subset x \) i założenie mówiące, że \( x \) jest zbiorem induktywnym. Wnioskujemy, że zbiór \( y \) spełnia założenia Lematu 2.1 i w związku z tym \( \bigcap y \) jest zbiorem induktywnym.
Postulujemy, że zbiór \( \bigcap y \) jest najmniejszym zbiorem induktywnym. Aby to wykazać, pokażemy, że dla dowolnego zbioru induktywnego \( z \) mamy \( \bigcap y\subset z \). Ustalmy dowolny zbiór induktywny \( z \), na mocy Lematu 2.1, zastosowanego do zbioru \( \{x,z\} \) otrzymujemy, że \( x\cap z \) jest zbiorem induktywnym. W związku z tym \( x\cap z \in y \) i dalej \( \bigcap y\subset x\cap z \subset z \). To dowodzi, że zbiór \( \bigcap y \) jest podzbiorem każdego zbioru induktywnego, czyli najmniejszym pod względem inkluzji zbiorem induktywnym.
Natychmiastowym wnioskiem jest, że zbiór taki jest jedyny.
Wniosek 2.3.
Istnieje unikalny, najmniejszy pod względem inkluzji, zbiór induktywny.
Dowód
Ustalmy dwa dowolne, najmniejsze pod względem inkluzji zbiory induktywne \( x \) i \( y \). Wtedy \( x\subset y \) i \( y\subset x \), skąd wnioskujemy, że \( x=y \), co należało wykazać.
Tak skonstruowany zbiór nazywamy zbiorem liczb naturalnych.
Definicja 2.4.
Najmniejszy pod względem inkluzji zbiór induktywny nazywamy zbiorem liczb naturalnych i oznaczamy, przez \( \mathbb{N} \). Elementy tego zbioru nazywamy liczbami naturalnymi.
Skonstruowaliśmy, przy pomocy aksjomatów ZF zbiór posiadający pewne własności i nazwaliśmy go zbiorem liczb naturalnych. Zbiór ten niewątpliwie zawiera liczbę zero, zdefiniowaną wcześniej jako zbiór pusty. Zawiera również liczbę jeden \( 1=0'=\{\emptyset\} \), ponieważ zawiera \( 0 \) i dla każdego elementu zawiera również jego następnik. Każda, z intuicyjnie oczywistych własności liczb naturalnych, musi być wykazana na gruncie aksjomatów ZF zanim uznamy ją za prawdziwą. Pozostała część tego wykładu poświęcona jest dowodzeniu podstawowych faktów dotyczących liczb naturalnych.
Podstawową metodą dowodzenia twierdzeń o liczbach naturalnych jest zasada indukcji matematycznej. Używając aksjomatów, możemy wykazać, że indukcja matematyczna działa. Formalnie, dla dowolnej własności, którą chcemy dowodzić przez indukcję, definiujemy zbiór elementów, które ją spełniają. Jeśli zbiór ten spełnia wymagane własności, jest on równy zbiorowi liczb naturalnych, czyli własność jest prawdą dla wszystkich liczb naturalnych. W formalny sposób przedstawia to poniższe twierdzenie.
Twierdzenie 3.1. [o indukcji matematycznej]
Dla dowolnego zbioru \( P \) jeśli \( P\subset\mathbb{N} \)
oraz
to \( P=\mathbb{N} \).
Dowód
Ustalmy dowolny zbiór \( P \) spełniający założenia twierdzenia. Zbiór \( P \) jest zbiorem induktywnym, a więc, na mocy definicji zbioru liczb naturalnych, \( \mathbb{N}\subset P \). Równocześnie założyliśmy, że \( P\subset\mathbb{N} \) i w związku z tym \( P=\mathbb{N} \), co dowodzi twierdzenia.
Twierdzenie 6.1. [o definiowaniu przez indukcję]
Niech \( A \) i \( B \) będą zbiorami, a \( f: A \rightarrow B \) i \( g:B\times \mathbb{N}\times A \rightarrow B \) funkcjami. Istnieje unikalna funkcja \( h:\mathbb{N}\times A \rightarrow B \) taka, że:
\( h(0, a) = f(a), \mbox{ dla każdego }a \in A, \)
\( h(n', a) = g(h(n, a), n, a), \mbox{ dla każdego }a \in A \mbox{ i }n \in \mathbb{N}. \)
Dowód
Dowód istnienia funkcji \( h \) będzie się opierał na analizie elementów następującego zbioru:
\( H = \{e\,:\, \exists m\; m\in\mathbb{N} \land e:m'\times A \rightarrow B \land \mbox{(*)} \}, \)
gdzie
\( e(0, a) = f(a), \mbox{ dla każdego }a \in A, \)
\( e(g(n, a), n, a), \mbox{ dla każdego }a \in A \mbox{ i }n \in m \quad \mbox{(*)} \)
Zbiór \( H \) jest to zbiór funkcji, które częściowo rozwiązują nasz problem -- funkcje ze zbioru \( H \) działają dla liczb naturalnych mniejszych niż pewne, ustalone \( m \). Funkcja \( h \), której istnienia dowodzimy, powinna działać dla wszystkich liczb naturalnych.
W pierwszej części dowiedziemy, że zbiór \( H \) jest niepusty i, co więcej, zawiera przynajmniej jedną funkcję \( e:m'\times A \rightarrow B \) dla każdej liczby naturalnej \( m \). Dowód jest indukcyjny -- zdefiniujmy zbiór \( P \) jako zbiór tych liczb, dla których istnieją odpowiednie funkcje w \( H \):
\( P = \{m\in\mathbb{N}\,:\, \exists e\; e:m'\times A \rightarrow B \land e\in H\}. \)
Dowiedziemy indukcyjnie, że \( P=\mathbb{N} \):
zdefiniowana jako:
\( e'(n, a) = \begin{cases} e(n, a), & \mbox{jeśli } n \in m', \\ g(e(n, a), n, a), & \mbox{jeśli} n = m', \end{cases} \)
przeprowadza \( m''\times A \) w \( B \) i należy do \( H \), gwarantując, że \( m'\in P \).
Na podstawie twierdzenia o indukcji istnieje funkcja \( e:m'\times A \rightarrow B \) należąca do \( H \), dla każdego \( m\in\mathbb{N} \).
Kolejną rzeczą jako wykażemy jest to, że dowolne funkcje \( e\in H \) i \( e'\in H \) dla tych samych argumentów zwracają takie same wyniki (oczywiście zakładając, że argumenty należą do przecięcia dziedzin tych funkcji). Nasz dowód przebiega niewprost. Załóżmy że funkcje \( e,e'\in H \) są takie, że istnieje \( n\in\mathbb{N} \) i \( a\in A \) spełniające \( e(n,a)\neq e'(n,a) \). Zastosujmy Twierdzenie 5.2. do zbioru tych wszystkich \( n \), dla których istnieje \( a\in A \) spełniające \( e(n,a)\neq e'(n,a) \) (na mocy naszego założenia zbiór ten jest niepusty). Otrzymujemy najmniejszą liczbę naturalną \( n \) taką, że \( e(n,a)\neq e'(n,a) \). Liczba \( n \) nie może być równa \( 0 \), bo wtedy \( e(0,a) = f(a) = e'(0,a) \), więc, na mocy Faktu 4.2. \( n=k' \), dla pewnego \( k \). Ponieważ \( k < n \), więc \( e(k,a)=e'(k,a) \) i otrzymujemy sprzeczność dzięki:
\( e(n,a) = e(k',a)=g(e(k,a),k,a) = g(e'(k,a),k,a) = e'(k',a) = e'(n,a). \)
Dowód twierdzenia kończymy, definiując \( h = \bigcup H \). Na mocy wcześniejszego faktu \( h \) jest funkcją, a na mocy faktu, który dowodziliśmy indukcyjnie dziedziną \( h \) jest zbiór liczb naturalnych. Warunki stawiane \( h \) są spełnione w sposób oczywisty dzięki definicji zbioru \( H \).
Aby wykazać unikalność funkcji \( h \) załóżmy, że istnieje funkcja \( h'\neq h \) spełniająca tezę twierdzenia. Wnioskujemy, że istnieje \( n\in\mathbb{N} \) i \( a\in A \) takie, że \( h(n,a)\neq h'(n,a) \). Wtedy jednak \( h' \) zawężone do \( n' \) jest elementem zbioru \( H \), co stoi w sprzeczności z faktem wykazanym o \( H \).
Poniższy wykład poświęcony jest konsekwencjom aksjomatu wyboru. Aksjomat wyboru jest niewątpliwie najbardziej kontrowersyjnym z aksjomatów ZFC. Wielu znanych matematyków poddawało go w wątpliwość. W chwili obecnej znakomita większość uważa, że aksjomat wyboru jest prawdziwy, nawet jeśli niektóre z jego konsekwencji są sprzeczne z intuicją.
W tym wykładzie przedstawiamy szereg twierdzeń, które są równoważne lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi tych faktów, wprowadzimy jeszcze jeden koncept.
Definicja dobrego porządku nie zależy od aksjomatu wyboru. W aksjomatyce ZF istnieje wiele zbiorów dobrze uporządkowanych. Jednak w obecności aksjomatu wyboru zbiory dobrze uporządkowane nabierają zupełnie nowego znaczenia.
Definicja 2.1.
Częściowy porządek \( (A,\sqsubseteq) \) jest dobrym porządkiem, jeśli
Mówimy wtedy, że zbiór \( A \) jest dobrze uporządkowany przez \( \sqsubseteq \).
Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w wykładzie 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje" zbiór liczb naturalnych jest dobrze uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć, że również każda liczba naturalna \( n \) wraz z relacją inkluzji jest zbiorem dobrze uporządkowanym. Ogólnie, następujący fakt jest prawdziwy
Fakt 2.2.
Dla dowolnego dobrego porządku \( (A,\sqsubseteq) \) i dla dowolnego zbioru \( B\subset A \) zbiór ten jest dobrze uporządkowany przez relację \( \sqsubseteq\cap B\times B \).
Dowód
Relacja \( \sqsubseteq\cap B\times B \) to relacja \( \sqsubseteq \) zawężona do elementów zbioru \( B \). Mamy dla każdego \( a,b\in B \)
\( a\sqsubseteq b \iff a (\sqsubseteq\cap B\times B) b. \)
Oczywistym wnioskiem jest, że zbiór \( B \) jest uporządkowany liniowo przez \( \sqsubseteq\cap B\times B \). Pozostaje wykazać, że każdy podzbiór zbioru \( B \) ma element najmniejszy. Ustalmy dowolne \( C\subset B \), ponieważ \( B\subset A \) zbiór \( C \) jest również podzbiorem \( A \) i z definicji zbioru dobrze uporządkowanego wynika, że \( C \) posiada element najmniejszy względem \( \sqsubseteq \). Ponieważ \( C\subset B \), to ten sam element jest elementem najmniejszym w \( C \) względem \( \sqsubseteq\cap B\times B \), co kończy dowód faktu.
Dokładnej analizie własności zbiorów dobrze uporządkowanych jest poświęcony wykład 12 "Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną". W dalszej części wykładu ograniczamy się do własności tych porządków bezpośrednio powiązanych z aksjomatem wyboru.
Wiele twierdzeń wymaga aksjomatu wyboru, choć założenie ich prawdziwości w ZF nie implikuje prawdziwości tego aksjomatu. W tej części wykładu przedstawimy kilka tego typu twierdzeń. Zwróćmy uwagę, że żadna z dostępnych w tej chwili technik dowodowych nie nadaje się do udowodnienia, że jakiś fakt jest słabszy od aksjomatu wyboru. Możemy pokazać, że jeśli aksjomat wyboru jest prawdą, to dane twierdzenie jest prawdziwe, ale nie możemy pokazać, że jeśli założymy dane twierdzenie, to aksjomat wyboru nie musi być prawdą. Nie jesteśmy w stanie zdecydować, czy aksjomat wyboru jest niezbędny do udowodnienia danego twierdzenia - tego typu dowody wykraczają poza zakres tego kursu i nie będą prezentowane.
Pierwszy z faktów, które będziemy dowodzić brzmi następująco:
Twierdzenie 4.1.
Dla dowolnego zbioru nieskończonego istnieje iniekcja ze zbioru liczb naturalnych w ten zbiór.
Dowód 1
Co możemy dowieść bez aksjomatu wyboru. Ustalmy dowolny zbiór nieskończony \( A \). Na mocy definicji z wykładu "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum" wiemy, że nie istnieje bijekcja między \( A \) a żadną liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej \( n \) istnieje iniekcja z \( n \) do \( A \). Dowód przeprowadzamy przez indukcję na \( n \).
\( \displaystyle f'(m)=\left\{\begin{array}{ll} f(m), & \quad \textrm{jeśli } m \in n, \\ a , & \quad \textrm{jeśli } m=n. \end {array} \right. \)
Funkcja \( f' \) jest iniekcją, co kończy dowód indukcyjny.
Wykazaliśmy jedynie, że dla każdej liczby naturalnej istnieje iniekcja z niej w \( A \). Nie udało nam się wykazać istnienia jednej funkcji dla całego zbioru \( \mathbb{N} \).
Dowód 2
Dowód przy użyciu aksjomatu wyboru. Aby udowodnić istnienie iniekcji z \( \mathbb{N} \) w \( A \), skorzystamy z Twierdzenia twierdzenie 3.1. równoważnego aksjomatowi wyboru. Zastosujmy je do zbioru \( \mathcal{P}(A)\setminus \{\emptyset\} \), dostając funkcję \( e:\mathcal{P}(A)\setminus \{\emptyset\} \rightarrow A \) taką, że \( e(B)\in B \) dla każdego \( B \), jeśli tylko \( \emptyset \neq B \subset A \). Aby udowodnić istnienie żądanej funkcji, zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy funkcję \( h: \mathbb{N}\times\{\emptyset\} \rightarrow
\mathcal{P}(A) \) taką, że
\( h(0, \emptyset) = \{e(A)\} \)
oraz
\( h(n',\emptyset) = h(n,\emptyset)\cup \{e(A\setminus h(n))\}. \)
Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje zbiór o jeden element większy niż przyporządkowany poprzedniej liczbie naturalnej. Aby otrzymać żądaną iniekcję wystarczy zdefiniować:
\( f(n) = x \iff h(n',\emptyset)\setminus h(n,\emptyset) = \{x\}. \)
Funkcja \( f \) jest dobrze zdefiniowana, ponieważ dla każdego \( n \) zbiór \( h(n',\emptyset)\setminus h(n',\emptyset) \) jest jednoelementowy (co gwarantuje definicja funkcji \( e \)). A jest iniekcją, ponieważ \( h(m,\emptyset)\subset h(n,\emptyset) \), jeśli tylko \( m\leq n \).
Kolejną konsekwencję podajemy w formie ćwiczenia.
Ćwiczenie 4.1
Rozważmy przedział \( [-1,3] \) w zbiorze liczb rzeczywistych. Niech funkcja \( f:\mathcal{P}([-1,3]) \rightarrow \mathbb{R} \) będzie "miłą miarą zbiorów", jeśli:
\( f(\bigcup_i A_i) =\sum_i f(A_i), \)
to znaczy, że sumowanie zbiorów rozłącznych zachowuje miarę.
Wykaż, że nie istnieje miła miara zbiorów.
Podpowiedź
Połóż dwie liczby w relacji ze sobą jeśli ich różnica jest wymierna.
Podpowiedź
Wybierz po jednym reprezentancie z każdej klasy równoważności i przesuń go o wektor.
Rozwiązanie
Załóżmy, niewprost, że istnieje miła miara \( f \). Zdefiniujmy relację równoważności \( \,\rho\, \) na zbiorze \( [0,1] \) w następujący sposób
\( x\,\rho\, y \iff x-y\in\mathbb{Q}. \)
Niewątpliwie relacja \( \,\rho\, \) jest relacją równoważności:
W związku z tym zbiór \( [0,1] \) podzielony jest na klasy równoważności i, na mocy aksjomatu wyboru, możemy wybrać zbiór \( C \) posiadający po jednym elemencie z każdej klasy równoważności. Rozważmy przeliczalną rodzinę zbiorów \( \{C_r\} \), gdzie \( r \) jest liczbą wymierną z przedziału \( [-1,1] \), a zbiór \( C_r \) jest translacją zbioru \( C \) o liczbę \( r \)
\( C_r=\{c+r\,:\, c\in C\}. \)
Ponieważ każdy element zbioru \( [0,1] \) jest odległy o liczbę wymierną od jakiegoś elementu \( C \) (ponieważ jest z nim w tej samej klasie równoważności) i ponieważ ta odległość nie może być większa niż \( 1 \), to
\( [0,1] \subset \bigcup_r C_r \subset [-1,2], \)
czyli miara zbioru \( \bigcup_r C_r \) musi być pomiędzy \( f([0,1])=1 \), a \( f([-1,2])\leq 3 \). Ale, z założenia o mierze \( f \) mamy \( f(C) = f(C_r) \) dla każdego \( r \). Oraz
\( f(\bigcup_r C_r) = \sum_r f(C_r) = \sum_r f(C), \)
skąd wnioskujemy, że \( f(\bigcup_r C_r) \) musi być równe zero (w przeciwnym przypadku suma po prawej stronie równości byłaby nieskończona) i w związku z tym również \( \sum_r f(C_r) = 0 \), czyli zbiór \( C \) ma miarę \( 0 \), co jest żądaną sprzecznością. Skonstruowany przez nas zbiór \( C \) nazywa się, od nazwiska pomysłodawcy, zbiorem Vitaliego.
Z drugiej strony, wiele intuicyjnych faktów wymaga aksjomatu wyboru lub jednej z jego słabszych wersji. Twierdzenie, że jeśli zbiór jest nieskończony, to istnieje iniekcja liczb naturalnych w ten zbiór, jest intuicyjnym faktem. Bertrand Russell powiedział o aksjomacie wyboru:
The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes (Aksjomat wyboru jest niezbędny, aby wybrać zbiór z nieskończonej ilości skarpet, ale nie z nieskończonej ilości butów).
Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po jednym bucie z nieskończonego zbioru par mówiąc "wybierzmy buty lewe". Nie jesteśmy w stanie przeprowadzić tego rozumowania, jeśli byty występujące w zbiorach są identyczne.