Logika i teoria mnogości/Wykład 1: Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost

"Naiwna" teoria mnogości

wyszczególnionych w preambule Teoria zbiorów, zwana również teorią mnogości, została stworzona około połowy XIX wieku, przez niemieckiego matematyka Georg Cantor. Teoria mnogości to gałąź matematyki zajmująca się zbiorami - kolekcja obiektów. Skończone zbiory można definiować wypisując kolejno wszystkie ich elementy. Georg Cantor był pierwszą osobą która podjęła się przeniesienia na ścisły grunt matematyczny pojęcia zbioru nieskończonego. Według Georg Cantor zbiór może być dowolną kolekcją obiektów zwanych elementami. Według tego podejścia zbiór jest pojęciem podstawowym i niedefiniowalnym. Niestety podejście do teorii zbiorów w ten sposób rodzi paradoksy i dlatego teoria mnogości prezentowana w ten sposób jest często nazywana "naiwną" teorią mnogości.

Teoria matematyczna nie może dopuszczać istnienia paradoksów i dlatego na początku XX wieku zmieniono podejście do teorii mnogości. Zaproponowana przez Ernst Zermelo i uzupełniony przez Adolf Abraham Halevi Fraenkel system aksjomatów wyklucza paradoksy które spowodowały że naiwna teoria zbiorów musiała zostać porzucona. Aksjomaty te nakładają pewne ograniczenia na konstrukcje zaproponowane przez Georg Cantor. W większości przypadków jednak intuicje związanej z naiwna teorią mnogości sprawdzają się również w aksjomatycznej teorii zbiorów. Zaprezentowane poniżej, skrótowe przedstawienie "naiwnej teorii mnogości" ma na celu wyrobienie intuicji niezbędnych przy dalszej pracy formalną wersją tych teorii. Aksjomatyczna teoria zbiorów zostanie przedstawiona w Wykład 4.

W podejściu zaproponowanym przez Georg Cantor zbiory skończone można łatwo wskazywać poprzez wyliczenie ich elementów. Definiowanie zbiorów nieskończonych wymaga bardziej rozwiniętego języka, niemniej jednak, według Georg Cantor, każda kolekcja obiektów jest zbiorem. Podstawowym symbolem używanym przy definiowaniu i opisywaniu zbiorów jest

$\in$

oznaczający, że dany byt jest "elementem" pewnego zbioru. Napis

"Kraków" $\in$ "zbiór wszystkich miast Polski"

ilustruje zastosowanie tego symbolu.

Aby zdefiniować zbiór należy określić definitywny sposób na rozpoznawania czy dany byt jest elementem zbioru, czy nie. Najczęściej używanym symbolem przy definiowaniu zbioru są nawiasy klamrowe. Definicja skończonego zbioru może być bardzo łatwa. Zbiór

$\{2,3,$ Kraków $\}$

posiada trzy elementy. Liczba 2 jest elementem tego zbioru $2\in \{2,3,$ Kraków $\}$, ale również
Kraków $\in \{2,3,$ Kraków$\}$.

Dwa zbiory są sobie równe (takie same) jeśli posiadają dokładnie te same elementy. Jedynymi elementami zbioru $\{2,3\}$ są liczby naturalne 2 i 3 - ten sam fakt jest prawdziwy dla zbioru $\{2,2,3\}$, a więc

$\{2,3\}=\{2,3,3\}.$

Podobnie $\{2,3\}=\{3,2\}$ i

$\{2,3\}=$ "zbiór liczb naturalnych ściśle pomiędzy 1 a

4".

W definicji zbioru nie ma znaczenia kolejność w jakiej wymienione są jego elementy, ani krotność w jakiej dany element pojawia się w zbiorze.

Zbiory można definiować na wiele sposobów. Najprostszym sposobem zdefiniowani zbioru jest wyliczenie jego elementów. Strategia ta zawodzi jednak w odniesieniu do zbiorów nieskończonych -- nie jesteśmy w stanie wypisać wszystkich liczb naturalnych. Zgodnie z postulatami Georg Cantor możemy przyjąć że istnieje zbiór wszystkich liczb naturalnych. Czasami, na określenie zbiorów nieskończonych używamy nieformalnego zapisu - zbiór wszystkich liczb naturalnych może być zapisany jako

$\{0,1,2,3,4,\dots \}.$

W podejściu zaproponowanym przez Georg Cantor równoważna definicja tego zbioru brzmi

"zbiór wszystkich liczb naturalnych"

Bardzo często tworzymy zbiory składające się z obiektów spełniających daną własność. Zbiór liczb parzystych możemy zdefiniować w sposób następujący

$\{x|x$ jest liczbą parzystą $\}.$

Bardziej ogólnie

$\{x|$ warunek $\}$

W skład powyżej zdefiniowanego zbioru wchodzą te elementy, które spełniają warunek występujący po znaku $|$. Żeby zakwalifikować element do powyższego zbioru wstawiamy go w miejsce $x$ w warunku występującym po $|$ i sprawdzamy czy jest on prawdziwy. Żeby pokazać, że

$2\in \{x|x$ jest liczbą parzystą $\}.$

musimy dowieść, że warunek "2 jest liczbą parzystą" jest prawdziwy.

Pomiędzy zbiorem liczb parzystych a zbiorem wszystkich liczb naturalnych występuje oczywista zależność. Każda liczba parzysta jest liczbą naturalną, co, ujęte w języku zbiorów oznacza że każdy element zbioru liczb parzystych jest elementem zbioru liczb naturalnych. Zbiór liczb parzystych jest podzbiorem zbioru liczb naturalnych (a zbiór liczb naturalnych nadzbiorem zbioru liczb parzystych). Zapisujemy to w następujący sposób

$\{x|x$ jest liczbą parzystą $\}\subseteq$ "zbiór liczb naturalnych" $.$

Ogólniej, jeśli każdy element zbioru $A$ jest elementem zbioru $B$ mówimy że zbiór $A$ jest podzbiorem zbioru $B$ i piszemy

$A\subseteq B.$

W takim przypadku mówimy, że pomiędzy zbiorami $A$ i $B$ zachodzi inkluzja.

W szczególności, dla dowolnego zbioru $A$ zachodzi $A\subseteq A$. Wspomnieliśmy wcześniej, że dwa zbiory są sobie równe wtedy i tylko wtedy kiedy posiadają dokładnie takie same elementy. Fakt ten możemy zapisać formalnie w następujący sposób

$A=B$ wtedy i tylko wtedy, kiedy $A\subseteq B$ i $B\subseteq A.$

Często zależy nam na określeniu znaczącym, że jeden zbiór jest podzbiorem drugiego i że zbiory te nie są sobie równe. Używamy wtedy symbolu $⊊$ w następujący sposób

Parser nie mógł rozpoznać (błąd składni): {\displaystyle A\varsubsetneq B \textrm{ wtedy i tylko wtedy, kiedy } ( A\subseteq B\textrm{ i nieprawda, że } A=B). }

Ćwiczenie 1.1

{{{3}}}

Obrazek 1.1 standardowy obrazek ilustrujący unię zbiorów

Podobnie definiujemy przecięcie zbiorów

$A\cap B=\{x|x\in A$ i $x\in B\}$

Obrazek 1.2 standardowy obrazek ilustrujący przecięcie zbiorów oraz różnicę zbiorów

$A\setminus B=\{x|x\in A$ i $x\notin B\}.$

Obrazek 1.3 standardowy obrazek ilustrujący różnicę zbiorów

Ćwiczenie 1.2

{{{3}}}

"Naiwna" indukcja

Zasada indukcji matematycznej jest o prawie trzysta lat starsza niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy Francesco Maurolico w 1575 roku. W pracy tej autor wykazał, że suma Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} pierwszych liczb nieparzystych równa się $n^2$.

Aby zastosować zasadę indukcji matematycznej należy wykazać dwa fakty:

• hipoteza jest prawdziwa dla $n=1$;

• jeśli hipoteza jest prawdziwa dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} to jest również prawdziwa dla $n+1$.

Drugi z powyższych punktów musi być prawdą dla wszystkich $n\ge 1$. Jeśli oba fakty są prawdą to hipoteza jest prawdziwa dla wszystkich liczb naturalnych większych od 1. Rozumowanie które stoi za tym wnioskiem wygląda następująco:

1. hipoteza jest prawdziwa dla $n=1$ na podstawie podstawy indukcji,

2. hipoteza jest prawdziwa dla $n=2$, ponieważ jest prawdziwa dla 1 i po zastosowaniu kroku     indukcyjnego również dla 2,

3. hipoteza jest prawdziwa dla $n=3$; w poprzednim punkcie pokazaliśmy, że jest prawdziwa dla     2 i na podstawie kroku indukcyjnego jest również prawdziwa 3

4. i tak dalej.

Nieskonczone domino ponumerowanych liczbami naturalnymi klocków w trakcie przewracania

Zasadę indukcji matematycznej można porównać do domina. Aby mieć pewność że przewrócone zostaną wszystkie klocki wystarczy wykazać, że przewrócony zostanie pierwszy klocek i że każdy klocek pociąga za sobą następny.

Dowód indukcyjny przedstawiony przez Francesco Maurolico pokazuje, że suma pierwszych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} liczb nieparzystych jest równa $n^2$.

• Jeśli $n=1$ to pierwsza liczba nieparzysta 1 jest równa $1^2$.

• Jeśli hipoteza jest prawdą dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} , to znaczy że suma pierwszych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} liczb nieparzystych równa się $n^2$. Bardziej formalnie

$1+3+\cdots +(2n-1)=n^2.$

tak więc suma pierwszych $n+1$ liczb nieparzystych $1+3+\cdots +(2n-1)+(2(n+1)-1)$, przy użyciu założenia powyżej może być zapisana jako

$1+3+\cdots +(2n-1)+(2(n+1)-1)=n^2+(2(n+1)-1)=n^2+2n+1={(n+1)}^2.$

Krok indukcyjny został dowiedziony.

Ćwiczenie 2.1

{{{3}}}

Ćwiczenie 2.2

{{{3}}}

Ćwiczenie 2.3

{{{3}}}

Często bardzo niepraktyczne jest używanie indukcji w jej podstawowej formie. Używa się wtedy indukcji, która w pierwszym kroku nie zaczyna się od $n=1$, ale $n=0$, $n=2$ lub dowolnej innej liczby naturalnej. W takim przypadku drugi krok indukcyjny nie musi działać dla wszystkich Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} a wystarczy by działał dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} większych lub równych od liczby którą wybraliśmy w pierwszym kroku. Końcowy dowód indukcyjny pokaże, że dana hipoteza nie jest prawdziwa dla wszystkich liczb naturalnych, a jedynie dla liczb większych od tej wybranej na pierwszy krok indukcyjny.

Jako przykład pokażemy, że $n!>2^n$. Po pierwsze nierówność ta nie zachodzi dla $1,2,3$, więc nie można rozpocząć kroku indukcyjnego od $n=1$. Indukcja będzie wyglądać następująco.

• Hipoteza jest prawdą dla $n=4$, ponieważ $4!=24>16=2^4$.

• Jeśli hipoteza jest prawdą dla $n$ i jeśli $n\ge 4$ to

$(n+1)!=n!\cdot (n+1)>2^n\cdot (n+1)>2^{n+1}$

gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a druga z faktu, że dowodzimy krok indukcyjny dla liczb większych niż 4.

Ćwiczenie 2.4

{{{3}}}

Ćwiczenie 2.5

{{{3}}}

Kolejnym uogólnieniem zasady indukcji matematycznej jest indukcja, w której w drugi kroku indukcyjnym zakładamy, że hipoteza jest prawdą dla wszystkich liczb mniejszych niż Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} i dowodzimy, że jest również prawdziwa dla $n+1$.

Jako przykład udowodnimy, że każda liczba naturalna większa niż 2 jest produktem jednej, lub więcej liczb pierwszych.

• Hipoteza jest prawdą dla $n=2$ ponieważ 2 jest liczbą pierwszą.

• Zakładamy że hipoteza jest prawdziwa dla liczb od 2 do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} . Weźmy liczbę $n+1$, jeśli $n+1$ jest liczbą pierwszą, to hipoteza jest udowodniona. Jeśli $n+1$ nie jest liczbą pierwszą, to $n+1=k\cdot l$ gdzie $2\le k,l\le n$. Założenie indukcyjne gwarantuje, że

$k=p_1\cdot p_2\cdot \cdots \cdot p_i$ i $l=q_1\cdot q_2\cdot \cdots \cdot q_j$

gdzie $p_1,\dots ,p_i,q_1,\dots ,q_j$ są liczbami pierwszymi. W związku z tym

$n+1=p_1\cdot p_2\cdot \cdots \cdot p_i\cdot q_1\cdot q_2\cdot \cdots \cdot q_j$

i krok indukcyjny jest udowodniony.

Ćwiczenie 2.6

{{{3}}}

Ćwiczenie 2.7

{{{3}}}

Ćwiczenie 2.8

{{{3}}}

Obrazek 2.2 Obrazek do powyższego ćwiczenia według załączonego skanu

Zasada indukcji matematycznej jest bardzo potężnym narzędziem. Intuicyjnie wydaje się jasne, że dowody przeprowadzone przy jej pomocy są poprawne. Niemniej jednak, żeby uzasadnić poprawność samej zasady należy sięgnąć do teorii mnogości i definicji zbioru liczb naturalnych. Wiemy już, że "naiwna teoria mnogości" nie daje nam poprawnych zbiorów na których można oprzeć ścisłe rozumowanie. W dalszej części wykładu wyprowadzimy zasadę indukcji matematycznej w oparciu o aksjomaty i aksjomatycznie zdefiniowany zbiór liczb naturalnych. Takie podejście gwarantuje nam poprawność rozumowania -- podejście naiwne zapewnia intuicje niezbędne do budowania poprawnych teorii.

"Naiwne" dowody niewprost

Częstą metodą dowodzenia twierdzeń matematycznych jest dowodzenie niewprost. Dowód niewprost polega na założeniu zaprzeczenia twierdzenia, które chcemy udowodnić i doprowadzeniu do sprzeczności. Wykazujemy, że jeśli twierdzenie nasze jest nieprawdziwe, jesteśmy w stanie udowodnić jakąś tezę, która jest w sposób oczywisty fałszywa.

Jednym z najbardziej znanych dowodów niewprost jest dowód istnienia nieskończenie wielu liczb pierwszych. Dowód ten został zaproponowany przez Euclid of Alexandria a my prezentujemy go w wersji podanej przez Ernst'a Kummera.

Twierdzenie [Istnieje nieskończenie wiele liczb pierwszych]

Dowód

Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych $p_0,\dots ,p_n$. Zdefiniujmy liczbę

$k=p_0\cdot p_1\cdot \cdots \cdot p_n$

i rozważmy $k+1$. Liczba $k+1$ posiada dzielnik pierwszy, a ponieważ jedynymi pierwszymi liczbami są liczby $p_0,\dots ,p_n$ wnioskujemy, że $p_i$ dzieli $k+1$ dla pewnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{i}} . Liczba $p_i$ dzieli również $k$, a więc $p_i$ dzieli $(k+1)-k=1$ co jest sprzecznością.

Ćwiczenie 3.1

{{{3}}}

Ćwiczenie 3.2

{{{3}}}