1. Wprowadzenie do teorii zbiorów
Podobnie jak w teorii Euklidesa, poniżej przedstawimy zestaw postulatów, przy pomocy których będziemy dowodzić twierdzeń o zbiorach. Tak jak punkty, proste i okręgi w teorii Euklidesa, zbiory w teorii zbiorów maja charakter obiektów pierwotnych, którym nie przypisujemy materialnej interpretacji. Przyjęte sa jednak pewne wygodne konwencje oznaczeniowe, którymi będziemy się posługiwali przez cały wykład Wstępu do Matematyki:
- Zbiór pusty będziemy oznaczać
.
- Elementy zbioru skończonego
będziemy wypisywać jako
; zważywszy, że w teorii zbiorów jedynym obiektem pierwotnym są zbiory, elementy
są także zbiorami.
- Sumę dwóch zbiorów skończonych
i
oznaczamy jako
i możemy wypisać jako
(1) - Kolejność, w jakiej wypisujemy elementy nie ma znaczenia.
Przypominam te oznaczenia dla podkreślenia, że poniższy formalny opis teorii zbiorów jest tylko nieco bardziej precyzyjnym ujęciem tego, z czym mieli już Państwo styczność w szkole średniej.
2. Zbiory skończone i nieskończone
Pochodząca z początku dwudziestego wieku aksjomatyzacja Zermelo i Fraenkla teorii zbiorów stanowi dziś standard, jeśli chodzi o precyzyjne ujęcie własności zbiorów skończonych i nieskończonych. Zważywszy jednak, że operowanie zbiorami nieskończonymi wywołuje szereg poważniejszych trudności, najpierw przedysktujemy wersję teorii zbiorów, która skoncentrowana jest na zbiorach skończonych. Mając na uwadze to, że elementami zbiorów są również zbiory, jeśli istotnie chcemy nie dyskutować tymczasem zbiorów nieskończonych, musimy nie tylko ograniczyć się do zbiorów skończonych, ale także dodatkowo żądać, żeby elementy zbioru także były skończone. Takie zbiory nazywamy dziedzicznie skończonymi. Bardziej ogólne ujęcie teorii zbiorów, uwzględniajce zbiory nieskończone, pojawi się w dalszej części semestru. Zaproponowana poniżej formalizacja wywodzi się z książki A. Tarskiego i S. Givanta “A Formalization of Set Theory without Variables”, a mówiąc dokładniej z wersji tej formalizacji rozpatrywanej w pracy S. Świerczkowskiego “Finite sets and Gödel's incompleteness theorems”. W języku teorii zbiorów mamy do dyspozycji symbole na zbiory , symbole
,
oraz
, których znaczenie jest doprecyzowane przez poniższe trzy aksjomaty (DS1)-(DS3). W teorii Euklidesa nie nalegaliśmy na to, żeby dowodzone zdania były wypisane w sformalizowanym języku matematycznym - zadowoliliśmy się tym, że mają one w miarę precyzyjny sens matematyczny. Tymczasem także nie będziemy wymagali pełnej precyzji odnośnie zdań teorii zbiorów. To znaczy przyjemiemy, że legalnym zdaniem
teorii zbiorów jest każde rozsądne, ścisłe zdanie o zbiorach używające typowych dla matematyki konstrukcji językowych jak spójniki logiczne“lub”,“i”, sformułowań“dla każdego”,“istnieje”,“nie”,“implikuje”. W tym sensie przykładem zdania teorii zbiorów jest zatem
Natomiast zdanie
nie jest zdaniem teorii zbiorów mimo, że występuje w nim słowo “zbiory”. Posługując się typową notacją na kwantyfikatory“dla każdego”,“istnieje” i spójniki“lub” i“wtedy i tylko wtedy” pierwsze z powyższych zdań możemy równoważnie zapisać jako
2.1. Aksjomaty teorii zbiorów dziedzicznie skończonych
Podajemy poniżej aksjomaty zbiorów dziedzicznie skończonych zaproponowane przez S. Świerczkowskiego w pracy “Finite sets and Gödel's incompleteness theorems”.
Aksjomat (DS1) podaje definiująca własność zbioru pustego: jest to zbiór bez elementów.
Aksjomat (DS2) mówi w szczególności, że jeśli , to
. Zatem
oznacza zbiór
, do którego dodano element
.
Aksjomat (DS3) trzeba zastosować do każdego zdania , które opisuje własność zbiorów.
Aksjomat ten oznacza, że jeśli własność zachodzi dla zbioru pustego, oraz własność
z
przenosi się na
, to musi zachodzić dla wszystkich zbiorów.
2.2. Przykłady twierdzeń o zbiorach
Przykłady są zaczerpnięte z dodatku do pracy S. Świerczkowskiego “Finite sets and Gödel's incompleteness theorems”, strona 41 i następne.
Twierdzenie 1. (zasada ekstensjonalności) Dla każdych zbiorów zachodzi
wtedy i tylko wtedy, gdy
Dowód. Niech będzie powyższą formułą (
jest ustalone), to znaczy
Wykorzystujemy aksjomat (DS3) dla wykazania, że zdanie zachodzi dla wszystkich zbiorów. Zauważmy najpierw, że warta dowodzenia jest jedynie implikacja
gdyż druga implikacja jest oczywista.
Podstawa indukcji. Dla formuła
przyjmuje postać
Pozostaje zatem wykazać, że
Na mocy (DS1) wiemy, że dla każdego zachodzi
. Z założenia wnioskujemy, że dla każdego
zachodzi
. Zatem ponownie korzystając z (DS1) wnioskujemy, że
.
Krok indukcyjny. Wiemy już, że zachodzi oraz
. Chcemy wykazać, że zachodzi
, czyli
Jest to natychmiastowy wniosek z aksjomatu (DS2).
Twierdzenie 2. (istnienie sumy dwóch zbiorów) Dla każdych dwóch zbiorów istnieje zbiór
o tej własności, że dla każdego
zachodzi
Dowód. Niech mówi, że istnieje zbiór
o tej własności, że
.
Podstawa indukcji. Zachodzi , gdyż jako
można wziąć zbiór
.
Krok indukcyjny. Ustalmy zbiory i
. Zakładamy, że zachodzi
, to znaczy istnieje zbiór
taki, że
. Wtedy
jest sumą
i
.
Twierdzenie 3. (zasada wyróżniania) Dla każdego zbioru i każdej formuły
istnieje zbiór
taki, że
Twierdzenie 4. (zasada zastępowania) Dla każdego zbioru i formuły
załóżmy, że dla każdego
istnieje dokładnie jeden
taki, że zachodzi
. Wtedy istnieje zbiór
taki, że
Twierdzenie 5. (zasada zbioru potęgowego) Dla każdego zbioru istnieje zbiór
taki dla każdego zbioru
zachodzi
Uwaga. Aksjomaty (DS1)-(DS3) można użyć do dowodu podstawowych własności zbiorów. Można też przyjąć inny punkt widzenia - treści powyższych twierdzeń można przyjąć jako aksjomaty teorii zbiorów (ta lista nie wyczerpuje listy aksjomatów ZF). Odnośnie zbiorów skończonych obydwa podejścia prowadzą do podobnych konkluzji, gdyż zbiory skończone realizują aksjomaty teorii ZF bez aksjomatu nieskonczoności. Aksjomaty (DS1)-(DS3) nie uogólniają się na zbiory nieskończone. Inaczej przedstawia się sprawa zasad w twierdzeniach 1-5. Przykładowo, jako aksjomat zbioru potęgowego w teorii ZF wymagamy, żeby dla każdego zbioru istniał zbiór
taki, że dla każdego zbioru
zachodzi
. O ile dla konkretnego zbioru skończonego zbiór potęgowy można skonstruować (przykłady na ćwiczeniach), to jeśli założymy istnienie zbiorów nieskończonych, aksjomat zbioru potęgowego prowadzi do coraz większych zbiorów (uściślenie tego stwierdzenia stanowi treść twierdzenia Cantora, o którym będziemy mówić później na tym wykładzie), o których namacalnym istnieniu nie można się przekonać.
Zadanie z * na ćwiczenia. Udowodnić wybrany akjomat ZF posługując się metodami z książki S. Świerczkowskiego (“Finite sets and Gödel's incompleteness theorems”, strona 41 i następne.
2.3. Odwzorowanie W. Ackermanna
W. Ackermann w pracy z 1937 roku pod tytułem “Die Widerspruchsfreiheit der allgemeinen Mengenlehre” wskazał1 interesujące odwzorowanie zdefiniowane na zbiorach dziedzicznie skończonych, prowadzące w liczby naturalne. Mianowicie, na zbiorze pustym definiujemy
Załóżmy, że i
są już zdefiniowane i
. Definiujemy
Daje to asumpt do następujcej definicji , prowadzącej z liczb naturalnych w zbiory dziedzicznie skończone. Zadajemy
. Jeśli po zapisaniu binarnym liczby
dostajemy
dla pewnych liczb
, to definiujemy
Twierdzenie 6. Odwzorowania i
są wzajemnie odwrotne, to znaczy dla każdego zbioru dziedzicznie skończonego
zachodzi
oraz dla każdej liczby naturalnej
zachodzi
.
Dowód. Przedstawimy tutaj tylko jedną cześć rozumowania, mianowicie tą, że dla każdego zbioru dziedzicznie skończonego zachodzi
.
Zauważmy, że dla równość
wynika z przyjętych definicji funkcji
i
. Załóżmy teraz, że dla
i
już wiemy, że
Naszym zadaniem jest wykazać, że jeśli , to
Z definicji wiemy, że
Niech . W rozwinięciu dwójkowym
nie ma
, gdyż w przeciwnym razie otrzymalibyśmy
, wbrew przypuszczeniu, że
.
Z powyższego wnosimy, że skoro , nie występuje w rozwinięciu
, to w rozwinięciu
musi wystąpić
. Poza tym występują
- dokładnie te potęgi
, co w
. Zatem z definicji
Zadanie. Jak wyrazić i
w terminach
i
?
3. Dygresja na temat grafu Rado
Graf Rado to graf nieskończony, którego wierzchołkami są zbiory skończone. W grafie Rado dwa różne zbiory skończone ,
są połączone krawędzią wtedy i tylko wtedy, gdy
. Ten dość trudny do wyobrażenia graf ma szereg intersujących własności, między innymi zachodzi dla niego
Twierdzenie o rozszerzaniu. Jeśli i
to dwa rozłączne skończone zbiory wierzchołków, to istnieje wierzchołek
, który jest połączony z każdym elementem
i nie jest połączony z żadnym elementem
.
Okazuje się, że z dokładnością do izomorfizmu grafów istnieje tylko jeden graf, którego wierzchołkami są zbiory skończone i który spełnia twierdzenie o rozszerzaniu - wynika to z faktu, że korzystając z tego twierdzenia możemy krok po kroku rozszerzyć izomorfizm ze zbiorów skończonych na cały graf (jest to sensowne zadanie do przemyślenia niekoniecznie w tej chwili, ale w granicach tego kursu). Graf Rado nazywany jest także grafem losowym, gdyż po ustaleniu odpowiedniego pojęcia prawdopobieństwa, prawie każdy graf, którego zbiorem wierzchołków jest rodzina wszystkich zbiorów skończonych, jest izomorficzny z grafem Rado.
4. Dygresja na temat twierdzenia Gödla o niezupełności
Aksjomaty (DS1)-(DS3) postulują pewne własności zbiorów. Można się zastanawiać, czy wraz z żądaniami odnośnie równości zbiorów charakteryzują one rodzinę zbiorów dziedzicznie skończonych. Można tu postawić dwa pytania:
- czy każde zdanie udowodnione przy pomocy aksjomatów (DS1)-(DS3) jest prawdziwe dla zbiorów dziedzicznie skończonych?
- czy jeśli zdanie
zachodzi dla zbiorów dziedzicznie skończonych, to można je wyprowadzić z aksjomatów (DS1)-(DS3)?
W powyższym sformułowaniu żadne z tych pytań nie jest do końca precyzyjne. Na pierwsze pytanie można udzielić odpowiedzi pozytywnej, jeśli za zbiory dziedzicznie skończone uznać zbiór pusty i zbiory możliwe do uzyskania przy pomocy2 operacji
. Intuicja stojąca za tym stwierdzeniem jest taka, że tak zdefiniowana rodzina zbiorów spełnia również aksjomat (DS3), a zatem posługując się aksjomatami (DS1)-(DS3) nie możemy udowodnić żadnej własności, która by nie zachodziła dla tak zdefiniowanej rodziny zbiorów.
Na drugie pytanie negatywną odpowiedź można uzyskać posługując się twierdzeniem K. Gödla o niezupełności oraz powyższym kodowaniem W. Ackermanna. Odpowiedź wymaga pewnych umów, które można streścić w następujący sposób. Z twierdzenia o niezupełności wynika, że o ile dana teoria, w tym wypadku złożona ze zdań prawdziwych dla zbiorów dziedzicznie skończonych, wyraża w sobię arytmetykę liczb naturalnych z dodawaniem i mnożeniem, to żadna prosta lista aksjomatów typu (DS1)-(DS3) nie może w pełni aksjomatyzować tej teorii, to znaczy pozostaną zdania prawdziwe dla zbiorów dziedzicznie skończonych, których nie da się udowodnić z tychże aksjomatów. Będą też istniały inne, niestandardowe struktury matematyczne, realizujące te aksjomaty. Bardziej precyzyjne potraktowanie powyższych tematów ma miejsce na kursie logiki matematycznej.
5. Dygresja na temat formalizacji twierdzenia o niezupełności
Tak jak w przypadku formalizacji geometrii Euklidesowej we współczesnych terminach aksjomatycznych (patrzy poprzedni wykład), podobnie można sformalizować teorię zbiorów dziedzicznie skończonych. Mając na oku kodowanie Ackermanna, o zbiorach dziedzicznie skończonych możemy myśleć jako o liczbach naturalnych. L.C. Paulson w pracach A machine-assisted proof of Gödel's incompleteness theorems for the theory of hereditarly finite sets i A Mechanised Proof of Gödel’s Incompleteness Theorems using Nominal Isabelle nie tylko podaje komputerową formalizację zbiorów dziedzicznie skończonych, ale także wykorzystuje ją do dowodu wersji twierdzenia Gödla o niezupełności. Inną formalizację tego twierdzenia (w wersji wychodzącej od arytmetyki Peano) można znaleźć w rozprawie doktorskiej doktorskiej R. O'Connora Incompleteness & Completeness : Formalizing Logic and Analysis in Type Theory i w pracy tego samego autora Essential Incompleteness of Arithmetic Verified by Coq.
1.Niemiecki tytuł “Die Widerspruchsfreiheit der allgemeinen Mengenlehre” przykłada się na “Niesprzeczność ogólnej teorii zbiorów”. Chodzi tu o teorię zbiorów dziedzicznie skończonych, a niesprzeczność polega na tym, że Ackermann wyraził teorię zbiorów skończonych w terminach dodawania i mnożenia na liczbach naturalnych. ↩
2.konstrukcja nowych zbiorów z przy pomocy operacji
będzie w szczegółach dyskutowana na ćwiczeniach. ↩