02. Teoria zbiorów skończonych | Portal Dydaktyczny dla Matematyków

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ć $\emptyset$ .
Elementy zbioru skończonego $A$ będziemy wypisywać jako $A = \{ A_1,\ldots,A_n\}$ ; zważywszy, że w teorii zbiorów jedynym obiektem pierwotnym są zbiory, elementy $A_1,\ldots,A_n$ są także zbiorami.
Sumę dwóch zbiorów skończonych $A = \{ A_1,\ldots, A_n\}$ i $B = \{ B_1,\ldots, B_m \}$ oznaczamy jako $A\cup B$ i możemy wypisać jako
(1)
$A\cup B = \{ A_1,\ldots, A_n, B_1,\ldots, B_m\}$
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 $A,B,C,\ldots,a,b,c,\ldots$ , symbole $\emptyset$ , $A\in B$ oraz $A\lhd B$ , 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 $\phi$ 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

(2)

\begin{split} \texttt{Dla każdych zbiorów } A, B \texttt{ istnieje zbiór } C,\\ \texttt{który zawiera dokładnie elementy } A \texttt{ i } B. \end{split}

Natomiast zdanie

(3)

\centering \begin{split} \texttt{Dzięki umiarkowanym opadom i dość wysokim temperaturom} \\ \texttt{zbiory buraka cukrowego zapowiadają się bardzo dobrze,} \end{split}

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

(4)

\forall_{A,B}\ \exists_C\ \forall_D\ (D\in A \vee D\in B)\ \iff\ D\in C.

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

(DS1)

A = \emptyset \text{ wtedy i tylko wtedy, gdy }\ \forall_{B}\ B\not\in A

Aksjomat (DS1) podaje definiująca własność zbioru pustego: jest to zbiór bez elementów.

(DS2)

\forall_{A,B}\ \forall_C\ \bigg\{ (C = A \lhd B) \iff\ (\forall_D\ D\in C \iff\ D\in A\ \vee\ D=B)\bigg\}.

Aksjomat (DS2) mówi w szczególności, że jeśli $A = \{ A_1,\ldots, A_n\}$ , to $A\lhd B = \{ A_1,\ldots, A_n, B \}$ . Zatem $A\lhd B$ oznacza zbiór $A$ , do którego dodano element $B$ .

Aksjomat (DS3) trzeba zastosować do każdego zdania $\phi(x)$ , które opisuje własność zbiorów.

(DS3)

(\phi(\emptyset)\ \wedge\ \forall_{A,B}\ \phi(A)\ \wedge \phi(B)\to \phi(A\lhd B)) \to \forall_A \phi(A).

Aksjomat ten oznacza, że jeśli własność $\phi$ zachodzi dla zbioru pustego, oraz własność $\phi$ z $A,B$ przenosi się na $A\lhd B$ , 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 $A,B$ zachodzi $A=B$ wtedy i tylko wtedy, gdy

(11)

\forall_C\ C\in A\ \iff\ C\in B.

Dowód. Niech $\phi(A)$ będzie powyższą formułą ( $B$ jest ustalone), to znaczy

(12)

\phi(A)\ \equiv\ \bigg\{ (A = B)\ \iff \big( \forall_C\ C\in A\ \iff\ C\in B \big) \bigg\}.

Wykorzystujemy aksjomat (DS3) dla wykazania, że zdanie $\phi$ zachodzi dla wszystkich zbiorów. Zauważmy najpierw, że warta dowodzenia jest jedynie implikacja

(13)

(\forall_C\ C\in A\ \iff\ C\in B) \to (A = B),

gdyż druga implikacja jest oczywista.

Podstawa indukcji. Dla $\emptyset$ formuła $\phi(\emptyset)$ przyjmuje postać

(14)

\phi(\emptyset) \equiv \bigg\{ (\emptyset = B)\ \iff \big( \forall_C\ C\in \emptyset\ \iff\ C\in B \big) \bigg\}.

Pozostaje zatem wykazać, że

(15)

(\forall_C\ C\in \emptyset\ \iff\ C\in B)\to (\emptyset = B).

Na mocy (DS1) wiemy, że dla każdego $C$ zachodzi $C\not\in\emptyset$ . Z założenia wnioskujemy, że dla każdego $C$ zachodzi $C\not\in B$ . Zatem ponownie korzystając z (DS1) wnioskujemy, że $B=\emptyset$ .

Krok indukcyjny. Wiemy już, że zachodzi $\phi(A)$ oraz $\phi(D)$ . Chcemy wykazać, że zachodzi $\phi(A\lhd D)$ , czyli

(16)

(\forall_C\ C\in A\lhd D\ \iff\ C\in B) \to (A\lhd D = B).

Jest to natychmiastowy wniosek z aksjomatu (DS2). $\QEDA$

Twierdzenie 2. (istnienie sumy dwóch zbiorów) Dla każdych dwóch zbiorów $A,B$ istnieje zbiór $A\cup B$ o tej własności, że dla każdego $C$ zachodzi

(17)

C\in (A\cup B)\ \iff\ \big( C\in A\ \vee\ C\in B \big)

Dowód. Niech $\phi(A)$ mówi, że istnieje zbiór $A\cup B$ o tej własności, że $\forall_C C\in A\cup B\iff C\in A \vee C\in B$ .

Podstawa indukcji. Zachodzi $\phi(A)$ , gdyż jako $C$ można wziąć zbiór $A$ .

Krok indukcyjny. Ustalmy zbiory $A$ i $D$ . Zakładamy, że zachodzi $\phi(A)$ , to znaczy istnieje zbiór $C$ taki, że $\forall_E E\in C\iff (E\in A\vee E\in B)$ . Wtedy $C\lhd D$ jest sumą $A\lhd D$ i $B$ . $\QEDA$

Twierdzenie 3. (zasada wyróżniania) Dla każdego zbioru $A$ i każdej formuły $\phi(B)$ istnieje zbiór $C$ taki, że

(18)

\forall_D D\in C \ \iff\ (D\in A\ \wedge \phi(D)).

Twierdzenie 4. (zasada zastępowania) Dla każdego zbioru $A$ i formuły $\phi(X_1,X_2)$ załóżmy, że dla każdego $B\in A$ istnieje dokładnie jeden $C$ taki, że zachodzi $\phi(B,C)$ . Wtedy istnieje zbiór $D$ taki, że

(19)

\forall_E E\in D \ \iff\ (\exists_B B\in A \wedge \phi(B,E)).

Twierdzenie 5. (zasada zbioru potęgowego) Dla każdego zbioru $A$ istnieje zbiór $C$ taki dla każdego zbioru $B$ zachodzi

(20)

B\subseteq A \text{ wtedy i tylko wtedy, gdy } B\in C.

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 $A$ istniał zbiór $C$ taki, że dla każdego zbioru $B$ zachodzi $B\subseteq A\ \iff\ B\in C$ . 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ł¹ interesujące odwzorowanie zdefiniowane na zbiorach dziedzicznie skończonych, prowadzące w liczby naturalne. Mianowicie, na zbiorze pustym definiujemy

(21)

Ack(\emptyset) = 0.

Załóżmy, że $Ack(A)$ i $Ack(B)$ są już zdefiniowane i $B\not\in A$ . Definiujemy

(22)

Ack(A\lhd B) = Ack(A) + 2^{Ack(B)}.

Daje to asumpt do następujcej definicji $Ack^{-1}$ , prowadzącej z liczb naturalnych w zbiory dziedzicznie skończone. Zadajemy $Ack^{-1}(0) = \emptyset$ . Jeśli po zapisaniu binarnym liczby $n$ dostajemy $n = 2^{i_1}+2^{i_2}+\ldots+2^{i_k}$ dla pewnych liczb $i_1<i_2<\ldots<i_k$ , to definiujemy

(23)

Ack^{-1}(n) = \{ Ack^{-1}(i_1),Ack^{-1}(i_2),\ldots, Ack^{-1}(i_k) \}

Twierdzenie 6. Odwzorowania $Ack$ i $Ack^{-1}$ są wzajemnie odwrotne, to znaczy dla każdego zbioru dziedzicznie skończonego $A$ zachodzi $Ack^{-1}(Ack(A)) = A$ oraz dla każdej liczby naturalnej $n$ zachodzi $Ack(Ack^{-1}(n)) = n$ .

Dowód. Przedstawimy tutaj tylko jedną cześć rozumowania, mianowicie tą, że dla każdego zbioru dziedzicznie skończonego $A$ zachodzi $Ack^{-1}(Ack(A)) = A$ .

Zauważmy, że dla $\emptyset$ równość $Ack^{-1}(Ack(\emptyset)) = \emptyset$ wynika z przyjętych definicji funkcji $Ack$ i $Ack^{-1}$ . Załóżmy teraz, że dla $A$ i $B$ już wiemy, że

(24)

\begin{aligned} Ack^{-1}(Ack(A)) = & A,\\ Ack^{-1}(Ack(B)) = & B. \end{aligned}

Naszym zadaniem jest wykazać, że jeśli $B\not\in A$ , to

(25)

Ack^{-1}(Ack(A\lhd B)) = A\lhd B.

Z definicji $Ack$ wiemy, że

(26)

Ack(A\lhd B) = Ack(A)+2^{Ack(B)}.

Niech $i_B = Ack(B)$ . W rozwinięciu dwójkowym $2^{Ack(A)}$ nie ma $2^{i_B}$ , gdyż w przeciwnym razie otrzymalibyśmy $\{\ldots,B,\ldots\} = \{\ldots,Ack^{-1}(i_B),\ldots\} = Ack^{-1}(Ack(A)) = A$ , wbrew przypuszczeniu, że $B\not\in A$ .

Z powyższego wnosimy, że skoro $2^{i_B}$ , nie występuje w rozwinięciu $Ack(A)$ , to w rozwinięciu $Ack(A)+2^{Ack(B)}$ musi wystąpić $2^{i_B}$ . Poza tym występują $2^{i_A^1}+\ldots+2^{i_A^k}\}$ - dokładnie te potęgi $2$ , co w $Ack(A)$ . Zatem z definicji $Ack^{-1}$

(27)

\begin{aligned} Ack^{-1}( Ack(A)+2^{Ack(B)} ) & = \{ Ack^{-1}(i_A^1),\ldots,Ack^{-1}(i_A^k) \} \cup \{ Ack^{-1}(i_B) \} \\ & = A\cup \{B\} \\ & = A \lhd B. \end{aligned}

$\QEDA$

Zadanie. Jak wyrazić $Ack^{-1}(n\cdot m)$ i $Ack^{-1}(n+m)$ w terminach $Ack^{-1}(n)$ i $Ack^{-1}(m)$ ?

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 $A$ , $B$ są połączone krawędzią wtedy i tylko wtedy, gdy $A\subseteq B$ . 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 $U$ i $V$ to dwa rozłączne skończone zbiory wierzchołków, to istnieje wierzchołek $A$ , który jest połączony z każdym elementem $U$ i nie jest połączony z żadnym elementem $V$ .

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 $\phi$ 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 $\emptyset$ i zbiory możliwe do uzyskania przy pomocy² operacji $\lhd$ . 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.

Created with Madoko.net.

^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 $\emptyset$ przy pomocy operacji $\lhd$ będzie w szczegółach dyskutowana na ćwiczeniach. ↩