Wstęp do Matematyki

 

Nieco rozszerzony wykład ze Wstępu do Matematyki z naciskiem na zagadnienia obliczeniowe i interakcję z komputerem. Autorem tej koncepcji wykładu jest Henryk Michalewski. Elementy klikalne nie działają na stronie dydmat i ogólnie dość słabo działa formatowanie - wersję tego wykładu bez defektów można znaleźć na portalu wdm. Program wykładu jest obliczony na około 15 tygodni i obejmuje następujące tematy:

  1. przykłady dowodów w matematyce; na kolejnych wykładach pojawią się przykładowe dowody z“Elementów” Euklidesa, dowody arytmetyczne, dowody w rachunku zdań i dowody teoriomnogościowe.
  2. operacje na zbiorach skończonych: dodawanie, sumy, wyróżnanie, zbiór potęgowy.
  3. sumaproduktkategorii zbiorów,
  4. pojęcie mocy zbioru, tw. Cantoratw. Cantora-Schrödera-Bernsteina,
  5. relacje równoważności,
  6. relacje porządku,
  7. dobre porządki.
Created with Madoko.net.

01. Podstawy matematyki według Euklidesa

 

1. Zmieniające się postrzeganie podstaw matematyki

Wspólnym mianownikiem aktywności matematycznej jest pisanie dowodów, czyli rozumowań, które wychodzą od zbioru ustalonych przesłanek i doprowadzają do twierdzeń, czyli wniosków wypływajacych z tych przesłanek. Tym matematyka różni się od księgowości, informatyki, fizyki albo nauk inżynierskich. Obecność dowodów i koncentracja na procesie dowodzenia wyróżnia tekst matematyczny. “Elementy” Euklidesa można uznać za pierwszy “Wstęp do Matematyki”, gdyż ten napisany około 2300 lat temu 13-to ksiąg składa się z dowodów twierdzeń wyprowadzonych z ustalonych definicji, postulatów i aksjomatów. Przykładowo, w pierwszym tomie Euklides podaje 23 definicje, 5 postulatów i 9 aksjomatów odnoszących się do geometrii płaszczyzny.

Rysuje się zatem fundamentalna w matematyce wątpliwość, kiedy możemy być usatysfakcjonowani dowodem matmatycznym. W XIX wieku i wcześniej matematykom na ogół wystarczało, że ich nowe dowody były dostatecznie podobne do dowodów Euklidesa i dowodów prezentowanych przez innych znanych matematyków na przestrzeni dziejów. Zatem dowód matematyczny to była wyspecjalizowana konstrukcja językowa, dzięki której matematycy komunikowali się między sobą i upewniali się, że ich argumentacja jest rozumiana i akceptowana przez innych matematyków. Ta konstrukcja językowa podlega podobnym ograniczeniom, jak na przykład język przyjęty w przewodach sądowych, lub też mieszanka łaciny i języka polskiego używana w medycynie z tym, że specyficzną cechą dowodu matematycznego ma być niezawodność rozumiana w ten sposób, że wnioski są prawdziwe przy założeniu prawdziwości przesłanek.

W czasach współczesnych dowody matematyczne mogą służyć także innym celom niż tylko komunikacja między matematykami. W niektórych sferach aktywności ludzkiej chcielibyśmy mieć możliwie daleko posunięta pewność, że wszystko przebiega zgodnie z planem. Odnosi się to do obronności, kryptografii, finansów, aeronautyki, gdyż tam pomyłki mogą być bardzo kosztowne.

W powyższych przykładach matematyka może pomóc w uzyskaniu takiej pewności, gdyż chcemy w nich weryfikować, że dane urządzenie lub program komputerowy pracują dokładnie zgodnie ze specyfikacją, a to podlega opisowi matematycznemu i może być przedmiotem matematycznych dowodów.

Można sobie wyobrazić, że lekturą dowodu matematycznego pokazującego “poprawność rakiety”może zająć się generał albo zatrudniony przez niego matematyk. Scenariusz ten można posunąć jeszcze dalej, gdyż dowody matematyczne przedstawiane są w sformalizowanym i precyzyjnym języku, który można uczynić zrozumiałym dla komputera. Chodzi tu zatem o sytuację, w której dowód jest wymyślany przez człowieka, natomiast czytany i weryfikowany nie tylko przez innych ludzi, ale także przez komputer. Wysiłki związane z formalizacją całej matematyki sięgają początku dwudziestego wieku i nasz przedmiot je podsumowuje w skróconej formie. Ten proces formalizowania matematyki do pewnego stopnia można uznać za zamknięty w tym sensie, że udało się ustalić, co formalizacja może nam dać, a na co nie możemy liczyć. Najbardziej intersujące wnioski, jakie matematykom udało się osiągnąć przez ostatnie sto lat to tw. K. Gödla o niezupełnościtwierdzenie P. Cohena o niezależności pewnych zdań matematycznych od “reszty” matematyki, a także zainpirowanie infomatyki odnośnie poszukiwania własnych podstaw, czego pokłosiem jest hipoteza milejnijna P vs NP. Jedną z konsekwencji tw. Gödla o niezupełności jest konkluzja, że przy bardziej skomplikowanych dowodach komputer może co prawda zweryfikować poprawność naszej argumentacji, ale nie możemy liczyć na to, że znajdzie za nas dowód twierdzenia1.

2. Wybiórcze przedstawienie definicji, postulatów i aksjomatów Euklidesa

Przedstawiam poniżej wybrane definicje, postulaty i aksjomaty z pierwszej księgi “Elementów”Euklidesa, ograniczając się do tych, które będą potrzebne w podanych niżej przykładach. Szerszy zakres definicji, postulatów i aksjomatów może się przydać na ćwiczeniach i podczas odrabiania pracy domowej.

Postulat 1. Niech będzie wymagane, aby: poprowadzić prostą od każdego punktu do każdego punktu.

Postulat 2. Niech będzie wymagane, aby: skończoną prostą przedłużyć w sposób ciągły po prostej.

Postulat 3. Niech będzie wymagane, aby: narysować koło o dowolnym środku i promieniu.

Definicja 15. Kołem jest figura płaska zawarta w obrębie jednej linii zwanej okręgiem, takiej, że wszystkie proste spadające na nią z jednego spośród punktów wewnątrz figury są sobie równe.

Definicja 20. Wśród figur trójbocznych, równobocznym jest trójkąt mający trzy równe boki, równoramiennym – mający jedynie dwa równe boki, a nierównoramiennym – mający trzy nierówne boki.

Aksjomat 1. Rzeczy równe temu samemu są też sobie równe.

Aksjomat 3. Jeśli od rzeczy równych odjąć równe, części pozostałe będą równe.

Poza zależnościami od aksjomatów, w “Elementach”pojawiają się także zależności od poprzednich wyników udowodnionych przez Euklidesa. Uzyskujemy w ten sposób dość skomplikowane drzewo zależności.

3. Przykłady dowodów

3.1. Przykład 1

Jako pierwszy przykład dowodu aksjomatycznego przestudiujemy Zagadnienie 1 z “Elementów” Euklidesa 2. Zagadnienie to w polskim tłumaczeniu L.A. Kołodziejczyka i R. Szczepkowskiego mówi, żeby

Na danej prostej skończonej skonstruować trójkąt równoboczny.

W nieco bardziej współczesnym języku

Zagadnienie 1. Dla danych punktów $A,B$ można skonstruować trójkąt równoboczny, którego bokiem jest odcinek z $A$ do $B$.

stw1


Figure 1. Ilustracja konstrukcji w dowodzie Zagadnienia 1.

Oryginalny dowód przedstawia się następująco

Niech daną prostą skończoną będzie AB. Na prostej AB należy teraz skonstruować trójkąt równoboczny. Narysujmy koło BCD o środku A i promieniu AB. Dalej, narysujmy koło ACE o środku B i promieniu BA. Z punktu C, w którym przecinają się te koła, pociągnijmy proste CA, CB do punktów A, B. Ponieważ punkt A jest środkiem koła CDB, prosta AC jest równa AB. Dalej, ponieważ punkt B jest środkiem koła CAE, prosta BC jest równa BA. Wykazaliśmy jednak, że również CA jest równe AB. Obie proste CA, CB są więc równe AB. Rzeczy równe zaś temu samemu są też sobie równe. Również CA jest więc równe CB. Wszystkie trzy proste CA, AB, BC są więc sobie równe. Trójkąt ABC jest więc równoboczny i został skonstruowany na danej prostej skończonej AB. Na danej prostej AB skonstruowaliśmy więc trójkąt równoboczny. Co należało wykonać

Aby uzasadnić

Niech daną prostą skończoną będzie AB. Na prostej AB należy teraz skonstruować trójkąt równoboczny. Narysujmy koło BCD o środku A i promieniu AB. Dalej, narysujmy koło ACE o środku B i promieniu BA.

dwukrotnie korzystamy z Postulatu 3. Następnie aby uzsadnić kolejny fragment dowodu

Z punktu C, w którym przecinają się te koła, pociągnijmy proste CA, CB do punktów A, B.

korzystamy z Postulatu 1. Następnie korzystamy z Definicji 15 aby uzasadnić, że

Dalej, ponieważ punkt B jest środkiem koła CAE, prosta BC jest równa BA. Wykazaliśmy jednak, że również CA jest równe AB. Obie proste CA, CB są więc równe AB.

Z Aksjomatu 1 wnioskujemy, że

Rzeczy równe zaś temu samemu są też sobie równe. Również CA jest więc równe CB. Wszystkie trzy proste CA, AB, BC są więc sobie równe.

Stąd na mocy Definicji 20 wnioskujemy, że trójkąt o wierzchołkach $A$, $B$, $C$ jest równoboczny.

3.2. Przykład 2

Jako drugi przykład dowodu aksjomatycznego przestudiujemy Zagadnienie 2 z “Elementów” Euklidesa. Zagadnienie to w polskim tłumaczeniu L.A. Kołodziejczyka i R. Szczepkowskiego mówi, że

W danym punkcie położyć prostą równą danej prostej.

W nieco bardziej współczesnym języku moglibyśmy to zagadnienie sformułować następująco

Zagadnienie 2. Dla danych punktów $A,B,C$ można skonstruować punkt $L$ taki, że odcinek z $B$ do $C$ jest równy odcinkowi z $A$ do $L$.

Oryginalny dowód Euklidesa przedstawia się następujco

Niech danym punktem będzie A, a daną prostą BC. Należy teraz położyć w punkcie A prostą równą danej prostej BC.

Pociągnijmy z punktu A do punktu B prostą AB i skonstruujmy na niej trójkąt równoboczny DAB.

W tym miejscu korzystamy z Zagadnienia 1. Zauważamy następnie, że z Postulatu 2 dopuszczalne jest

Przedłużmy DA, DB po prostej prostymi AE, BF.

Dwukrotnie wykorzystujemy Postulat 3 aby uzasadnić, że

Narysujmy koło CGH o środku B i promieniu BC. Dalej narysujmy koło GLK o środku D i promieniu DG.

Następnie korzystamy z Definicji 15:

Ponieważ punkt B jest środkiem koła CGH, prosta BC jest równa BG. Dalej, ponieważ punkt D jest środkiem koła GLK, prosta DL jest równa DG, z czego DA jest równe DB.

Wykorzstujemy Aksjomat 3 który pozwala na usunięcie z dwóch równych sobie odcinków innych równych sobie odcinków— po tej operacji usuwania ciagle mamy do dyspozycji dwa równe odcinki, w tym wypadku AL i BC.

Pozostałe AL jest więc równe pozostałemu BG. Wykazaliśmy jednak, że również BC jest równe BG.

Wykorzystujemy Aksjomat 1 aby uzsadnić, że

Obie proste AL, BC są więc równe BG. Rzeczy równe zaś temu samemu są też sobie równe. Również AL jest więc równe BC. W danym punkcie A położyliśmy więc prostą AL równą danej prostej BC. Co należało wykonać.

stw2


Figure 2. Ilustracja konstrukcji w dowodzie Zagadnienia 2.

4. Zadanie do przemyślenia, ewentualnie do zrobienia na ćwiczeniach

Rozłożyć na czynniki jedno z poniższych zagadnień:

Zagadnienie 3

Zagadnienie 4

pracy domowej pojawiają się zagadnienia 5 i 6.

5. Dygresja na temat aksjomatyzacji Tarskiego i Hilberta

Na pierwszy rzut oka można stwierdzić, że o ile 23 definicji, 5 postulatów i 9 aksjomatów Euklidesa mogło nadawać ton badaniu geometrii płaskiej na przestrzeni ponad 2000 lat, o tyle sformułowania twierdzeń i rozumowania dowodowe wymagają dość sporej inwencji intepreretacyjnej, która objawiała się dopisywaniem brakujących słówek, czy nawet całych postulatów do systemu Euklidesa. Przeczytanie dowodów Euklidesa jest do dziś możliwe i same rozumowania są przekonujące dla matematyków, jednak jest jasne, że czytelnik o ograniczonych możliwościach interpretacyjnych może mieć z tym tekstem dość duży problem. W szczególności, bez gruntownego przepisania tekst ten będzie z całą pewnością niezrozumiały dla komputera, to znaczy komputer może mieć trudności z odgadnięciem, z jakich przesłanek korzysta dany krok dowodu (przyuczenie komputera do zgadywania odpowiednich aksjomatów w dowodach Euklidesa wydaje mi się dość interesującym eksperymentem z zakresu uczenia maszynowego/machine learning). W roku 1899 D. Hilbert w The Foundations of Geometry/Grundlagen der Geometrie (link do wersji angielskiej) zaproponował nową aksjomatyzację geometrii w przestrzeniach euklidesowych. Nieco inną formalizację zaproponował A. Tarski. Opis tej ostatniej formalizacji można znaleźć w książce W. Schwabhäusera, W. Szmielew i A. Tarskiego “Metamathematische Methoden in der Geometrie” oraz w artykule A. Tarskiego i S. Givanta “Tarski's System of Geometry” 3. Zarówno system Hilberta jak i Tarskiego podlega formalizacji komputerowej, w szczególności system Tarskiego został zaimplementowany w ramach projektu Geocoq.

Created with Madoko.net.

1.W każdym razie nie tego typu komputer, z którego możemy skorzystać współcześnie.

2.W odniesieniu do oryginalnego tekstu Euklidesa będę używał trochę nietypowego terminu “Zagadnienie” na określenie zarówno twierdzeń, jak i konstrukcji. Cytowane przeze mnie angielskie tłumaczenie “Elementów” posługuje się słowem “Proposition”.

3.Tarski opublikował w 1959 roku artykuł What is elementary geometry?; artykuł z S. Givantem ukazał się już po śmierci A. Tarskiego.

02. Teoria zbiorów skończonych

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ł1 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 pomocy2 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.

03. Rachunek zdań - gramatyka i przykłady

 

1. Rachunek zdań

Jedną z najprostszych logik jest rachunek zdań. O ile w systemie Euklidesa można mówić o punktach, prostych i okręgach, a w teorii zbiorów o zbiorach, o tyle w rachunku zdań atomowym pojęciem jest zdanie. Zatem w rachunku zdań można

  1. wyrazić pewne ogólne własności zdań,
  2. z prostszych zdań tworzyć bardziej złożone.

W języku rachunku zdań symbole $p,q,\ldots$ oznaczają zdania atomowe, w których wewnętrzną strukturę nie chcemy dalej wnikać. Zdefiniujemy teraz w sposób precyzyjny gramatykę rachunku zdań, czyli zasady tworzenia nowych formuł rachunku zdań z już istniejących.

  1. $p,q,\ldots$ są formułami rachunku zdań,
  2. jeśli $\phi,\psi$ są formułami rachunku zdań, to $(\phi\wedge \psi)$, $(\phi\vee \psi)$,$(\phi\to\psi)$ oraz $(\neg \phi)$ są formułami rachunku zdań.

2. Przykłady użycia rachunku zdań.

Na pierwszy rzut oka może się wydawać, że jest język rachunku zdań jest bardzo ograniczony. Okazuje się jednak, że w rachunku zdań da się wysłowić szereg fundamentalnych właściwości własności otaczającej nas rzeczywistości. W szczególności, można w nim wyrazić wewnątrzną strukturę urządzeń elektronicznych, w tym mikroprocesorów. Na potrzeby tych notatek skoncentrujemy się na prostych przykładach, które jednak dość łatwo się rozszerzają do całkiem nietrywialnych zagadnień.

2.1. Sudoku

W pierwszej kolejności pokażemy, jak w języku rachunku zdań wysłowić istnienie rozwiązań w Sudoku.

sudoku44


Figure 1. Przykładowy problem Sudoku do zakodownia w rachunku zdań.

Rozwiązanie tego problemu kodujemy w następujący sposób. Zmienna $p_{i,j,n}$ oznacza, ze na pozycji $(i,j)$ stoi liczba $n$. Warunek

(1)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{j\in\{1,2,3,4\}}\ \bigvee_{n\in\{1,2,3,4\}} p_{i,j,n}
\]

oznacza zatem, że na każdej pozycji $(i,j)$ stoi jedna z liczb z zakresu od $1$ do $4$.

Następnie chcemy wykluczyć, że dwie różne liczby $n$, $m$ stoją na tym samym polu

(2)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{j\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\  \bigwedge_{m\in\{1,2,3,4\},m\neq n}\ p_{i,j,n}\to \neg p_{i,j,m}
\]

Następnie chcemy zapewnić spełnienie warunków zwycięstwa w Sudoku. Po pierwsze, w każdym wierszu muszą stać wszystkie liczby od $1$ do $4$.

(3)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\ \bigvee_{j\in\{1,2,3,4\}}\  p_{i,j,n}.
\]

To samo odnosi się do kolumn

(4)
\[\bigwedge_{j\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\ \bigvee_{i\in\{1,2,3,4\}}\  p_{i,j,n}.
\]

Kolejne warunki kodują żadanie, żeby w kwadratach pojawiały się także cztery liczby. Zacznijmy od górnego lewego rogu:

(5)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{1,2\}}\ \bigvee_{j\in\{1,2\}}\  p_{i,j,n}.
\]

Następnie analogicznie zajmujemy się prawym górnym, lewym dolnym i prawym dolnym rogiem.

(6)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{3,4\}}\ \bigvee_{j\in\{1,2\}}\  p_{i,j,n}.
\]
(7)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{1,2\}}\ \bigvee_{j\in\{3,4\}}\  p_{i,j,n}.
\]
(8)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{3,4\}}\ \bigvee_{j\in\{3,4\}}\  p_{i,j,n}.
\]

Na koniec żadamy, żeby był spełniony warunek początkowy

(9)
\[p_{2,2,2}\wedge p_{1,3,4}\wedge p_{2,4,3}\wedge p_{3,1,2}\wedge p_{4,2,4}\wedge p_{4,4,1}
\]

Rachunek zdań ma tą wyróżniające cechę, że zdania w tym języku podlegają automatycznej analizie przez komputer, który umie stwierdzić, czy da się tak dobrać $p_{i,j,n}$, żeby wszystkie powyższe warunki były spełnione. My skorzystamy z solwera on-line SatRennesPa.

sudoku44_sol


Figure 2. Przykładowe rozwiązanie problemu w terminach rachunku zdań.

Po zaimplementowaniu tych wskazówek n.p. w programie Paint dodstajemy

sudoku44_sol_red


Figure 3. Przykładowy problem Sudoku do zakodownia w rachunku zdań.

2.2. Owca, wilk i kapusta

Odnośnie powyższej gry można sobie postawić co najmniej dwa interesujące pytania. Mianowicie, jak bezpiecznie przewieźć cały dobytek na drugą stronę oraz ile ruchów jest niezbędne, żeby operacja przewożenia się udała.

O ile na piewsze pytanie można uzyskać odpowiedź metodą eksperymentów, o tyle na drugie pytanie odpowiedź można otrzymać programując nasze zadanie w terminach rachunku zdań. Przekonamy się, że 7 ruchów wystarcza w tej grze, natomiast 6 jest jeszcze nie wystarczające.

Przez $w_{0},\ldots,w_{7}$ będziemy oznaczać, że wilk jest po prawej stronie w chwili $0$, w chwili $1$ i tak dalej. Podobnie przez $o_{0},\ldots,o_{7}$, $k_{0},\ldots,k_{7}$ i $l_{0},\ldots,l_{7}$ oznaczamy, że owca, kapusta i łodka są po prawej stronie w chwili od $0$ do $7$.

Przyjrzyjmy się liście wymagań. Po pierwsze, jeśli w chwili $i$ owca i wilk znajdują sie po prawej stronie, to także powinna być tam łódka.

(10)