Konwersja Arka
"Naiwna" teoria mnogości
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
oznaczający, że dany byt jest "elementem" pewnego zbioru. Napis
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
posiada trzy elementy. Liczba
jest elementem tego zbioru Kraków , ale równieżKrakówKraków .
Dwa zbiory są sobie równe (takie same) jeśli posiadają dokładnie te same elementy. Jedynymi elementami zbioru
są liczby naturalne i -- ten sam fakt jest prawdziwy dla zbioru , a więcPodobnie
iW 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
W podejściu zaproponowanym przez Georg Cantor równoważna definicja tego zbioru brzmi
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
Bardziej ogólnie
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 w warunku występującym po i sprawdzamy czy jest on prawdziwy. Żeby pokazać, żemusimy dowieść, że warunek "
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
Ogólniej, jeśli każdy element zbioru
jest elementem zbioru mówimy że zbiór jest podzbiorem zbioru i piszemyW takim przypadku mówimy, że pomiędzy zbiorami
i zachodzi inkluzja.W szczególności, dla dowolnego zbioru
zachodzi . 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óbCzę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Ćwiczenie [Uzupelnij]
Dla każdej pary zbiorów poniżej określ czy są sobie równe, oraz czy jeden z nich jest nadzbiorem drugiego
- , dzieli liczbę
- "zbiór liczb naturalnych" , dzieli
- ,
- Solution.
- Rozwiązanie:
- Zarówno , jak i dzielą , a więc
dzieli liczbę . Liczba jest elementem lewego zbioru, a nie jest elementem prawego i dlatego zbiory te są od siebie różne. Odpowiedzią jest dzieli liczbę .
- Do zbioru liczb naturalnych należy , które nie należy do zbioru
dzieli (ponieważ nie dzieli ). Równocześnie do prawego zbioru należy liczba która nie jest liczbą naturalną. Żaden z wymienionych tu zbiorów nie jest podzbiorem drugiego.
- Lewy zbiór to, oczywiście zbiór , a prawy to
jednoelementowy zbiór
. W tym przypadku odpowiedzią jest .Najczęstszymi operacjami wykonywanymi na zbiorach są operacje "sumy","przecięcia" i "różnicy". Sumą dwóch zbiorów
i jest zbiór oznaczony przez w skład którego wchodzą wszystkie element zbioru , wszystkie elementy zbioru i żadne elementy spoza tych zbiorów.{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący unię zbiorów Podobnie definiujemy przecięcie zbiorów
{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący przecięcie zbiorów oraz różnicę zbiorów
{obra}{1}{Obrazek {section}.{obra}}standardowy obrazek ilustrujący różnicę zbiorów
Ćwiczenie [Uzupelnij]
Dla następujących par zbiorów ustal zawieranie, lub równość
- "zbiór liczb naturalnych" liczba nieparzysta, większa niż 2 dzieli i drugi zbiór gdzie jest liczbą naturalną ,
- liczba 2 dzieli liczba 3 dzieli i zbiór
liczba 6 dzieli .
- Solution.
- Rozwiązanie:
- Każda liczba postaci jest liczbą naturalną
niepodzielną przez żadną liczbę nieparzystą większą niż
, a więc . Każda liczba naturalna, która nie dzieli się przez żadną liczbę nieparzystą posiada tylko jeden dzielnik pierwszy . W związku z tym każda z liczb w występuje również w . W związku z tym .- Każda liczba która jest podzielna przez dzieli się
również przez
co dowodzi, że . Zawieranie w drugą stronę nie zachodzi ponieważ liczba i .Dla dowolnego zbioru
zachodzi i . Zbiór który otrzymujemy jako wynik operacji jest "zbiorem pustym". Na mocy definicji różnicy zbiorów elementami zbioru są wyłącznie te elementy , które nie należą do . Takie elementy nie istnieją -- żaden element ze zbioru nie należy do i żaden element spoza nie należy do tego zbioru. Zbiór pusty jest oznaczany przez . Odejmowanie zbiorów od samych siebie nie jest jedynym sposobem na otrzymanie zbioru pustego.Zbiór po lewej stronie nierówności jest równy zbiorowi po prawej stronie nierówności. Każdy element zbioru po prawej stronie jest również elementem zbioru po lewej stronie nierówności i vice versa dlatego, że żaden z tych zbiorów nie posiada elementów.
Niestety, podejście zaproponowane przez Georg Cantor i uściślone przez Friedrich Frege posiada błędy. Jedną z pierwszych osób które zwróciły uwagę na niedociągnięcia tej teorii jest Bertrandt Russell. Zgodnie z zasadami zaproponowanymi przez Georg Cantor można zdefiniować dowolny zbiór. Zdefiniujmy więc zbiór
Zbiór
składa się ze zbiorów, które nie są swoimi własnymi elementami. Paradoks zaproponowany przez Bertrandt Russell polega na tym, że pytanie czy jest swoim własnym elementem prowadzi do sprzeczności. Jeśli to, zgodnie z definicją zboru otrzymujemy co jest sprzecznością z założeniem. Jeśli , to spełnia warunek na przynależność do i w związku z tym co jest kolejną sprzecznością. Definicja zbioru zaproponowana przez Georg Cantor prowadzi do powstania logicznych paradoksów. Okazuje się że pytanie co jest zbiorem jest trudniejsze niż wydawało się matematykom końca XIX wieku.W dalszej części wykładu przedstawimy właściwe podejście do teorii mnogości. Podejście to jest oparte o część logiki zwaną rachunkiem predykatów. Podejście to zostało zaproponowane przez Ernst Zermelo na początku XX wieku i ma na celu dostarczenie spójnej teorii zbiorów o mocy podobnej to naiwnej teorii, przy równoczesnym uniknięciu paradoksów. Aksjomatyczna teoria mocy definiuje bardzo dokładnie które kolekcje obiektów są zbiorami. W szczególności paradoks zaproponowany przez Bertrandt Russell nie pojawia się w aksjomatycznej teorii zbiorów, ponieważ zbiór zdefiniowany powyżej jako
w niej nie istnieje."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
pierwszych liczb nieparzystych równa się .Aby zastosować zasadę indukcji matematycznej należy wykazać dwa fakty:
- hipoteza jest prawdziwa dla ;
- jeśli hipoteza jest prawdziwa dla to jest również prawdziwa dla
.
Drugi z powyższych punktów musi być prawdą dla wszystkich
. Jeśli oba fakty są prawdą to hipoteza jest prawdziwa dla wszystkich liczb naturalnych większych od . Rozumowanie które stoi za tym wnioskiem wygląda następująco:- hipoteza jest prawdziwa dla na podstawie podstawy indukcji,
- hipoteza jest prawdziwa dla , ponieważ jest prawdziwa dla i po zastosowaniu kroku indukcyjnego również dla ,
- hipoteza jest prawdziwa dla ; w poprzednim punkcie pokazaliśmy,
że jest prawdziwa dla
i na podstawie kroku indukcyjnego jest również prawdziwa- i tak dalej.
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. {obra}{1}{Obrazek {section}.{obra}}nieskończone domino ponumerowanych liczbami naturalnymi klocków w trakcie przewracania
Dowód indukcyjny przedstawiony przez Francesco Maurolico pokazuje, że suma pierwszych
liczb nieparzystych jest równa .- Jeśli to pierwsza liczba nieparzysta jest równa .
- Jeśli hipoteza jest prawdą dla , to znaczy że suma pierwszych
liczb nieparzystych równa się
. Bardziej formalnietak więc suma pierwszych
liczb nieparzystych , przy użyciu założenia powyżej może być zapisana jakoKrok indukcyjny został dowiedziony.
Ćwiczenie [Uzupelnij]
Wykaż, że suma pierwszych
liczb naturalnych jest równa .- Solution.
- Aby udowodnić wzór na sumę
- Dla mamy .
- Zakładamy, że wzór jest prawdziwy dla . W związku z tym do sumy
pierwszych liczb naturalnych posłużymy się indukcją.
stosujemy założenie indukcyjne
i po paru prostych przekształceniach otrzymujemy
co dowodzi kroku indukcyjnego.
Na zasadzie indukcji matematycznej dowiedliśmy wzór na sumę
pierwszych liczb naturalnych.Ćwiczenie [Uzupelnij]
Wykaż, że suma kwadratów pierwszych
liczb naturalnych jest równa .- Solution.
- Aby
wykazać prawdziwość wzoru powyżej postępujemy jak w poprzednim zadaniu.
- Dla mamy co dowodzi
podstawy indukcji.
- Zakładamy że wzór jest prawdziwy dla to jest, że
Korzystając z tego faktu przekształcamy
i dalej do
co dowodzi kroku indukcyjnego.
Podobnie jak w poprzednim przykładzie zasada indukcji matematycznej gwarantuje, że wzór jest prawdziwy dla wszystkich liczb naturalnych.
Ćwiczenie [Uzupelnij]
Wykaż, że dla
zachodzi .- Solution.
- Jak
poprzednio stosujemy zasadę indukcji matematycznej.
- Dla mamy jest podzielne przez .
- Zakładamy że podzielność zachodzi dla .
Pokażemy że
jest podzielne przez . Przekształcamywprowadzamy sztuczny czynnik
Zarówno
(na mocy założenia indukcyjnego) jak i są podzielne przez , a wiec ich różnica również. W ten sposób udowodniliśmy krok indukcyjny.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
, ale , lub dowolnej innej liczby naturalnej. W takim przypadku drugi krok indukcyjny nie musi działać dla wszystkich a wystarczy by działał dla 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
. Po pierwsze nierówność ta nie zachodzi dla , więc nie można rozpocząć kroku indukcyjnego od . Indukcja będzie wyglądać następująco.- Hipoteza jest prawdą dla , ponieważ .
- Jeśli hipoteza jest prawdą dla i jeśli to
gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a druga z faktu, że dowodzimy krok indukcyjny dla liczb większych niż
.Ćwiczenie [Uzupelnij]
W tym ćwiczeniu dowodzimy wariant nierówności Bernoulliego. Dla dowolnego
takiego, że i i dla dowolnego zachodzi .- Solution.
- Rozwiązanie:
- Nierówność ostra nie jest prawdą dla , ani dla
. Krok indukcyjny zaczniemy od . Wtedy , gdzie ostatnia nierówność bierze się z faktu, że .
- Zakładamy teraz, że nierówność jest prawdziwa dla , czyli, że dla dowolnego takiego, że mamy
Przekształcając nierówność dla
otrzymujemygdzie otrzymujemy ostrą nierówność dzięki założeniu indukcyjnemu i faktowi, że
. W ten sposób krok indukcyjny został udowodniony.Ćwiczenie [Uzupelnij]
Liczby Fibonacciego zdefiniowane są następująco
Udowodnij, że dla dowolnego
liczby i są względnie pierwsze.- Solution.
- Dowód przez indukcję matematyczną
- Twierdzenie jest prawdą dla ponieważ i są
względnie pierwsze.
- Zakładamy że twierdzenie jest prawdą dla . Rozpatrzmy wspólny
dzielnik liczb
i i oznaczmy go przez . Jeśli dzieli i równocześnie to . Korzystając z definicji liczb Fibbonaciego otrzymujemy . W związku z czym jest wspólnym dzielnikiem liczb i , więc na mocy założenia indukcyjnego mówiącego, że liczby te są względnie pierwsze, jest równy . Pokazaliśmy, że każdy wspólny dzielnik i jest równy , a więc liczby te są względnie pierwsze. Krok indukcyjny został pokazany.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ż
i dowodzimy, że jest również prawdziwa dla .Jako przykład udowodnimy, że każda liczba naturalna większa niż
jest produktem jednej, lub więcej liczb pierwszych.- Hipoteza jest prawdą dla ponieważ jest liczbą pierwszą.
- Zakładamy że hipoteza jest prawdziwa dla liczb od do
. Weźmy liczbę , jeśli jest liczbą pierwszą, to hipoteza jest udowodniona. Jeśli nie jest liczbą pierwszą, to gdzie . Założenie indukcyjne gwarantuje, że
gdzie
są liczbami pierwszymi. W związku z tymi krok indukcyjny jest udowodniony.
Ćwiczenie [Uzupelnij]
Udowodnij, że każda liczba naturalna większa niż
może być przedstawiona jako suma liczb Fibonacciego tak, że żadna liczba nie występuje w tej sumie więcej niż raz.- Solution.
- Przedstawimy dowód przez indukcję.
- Dla mamy .
- Zakładamy że każda liczba mniejsza lub równa może być
przedstawiona w sposób opisany powyżej. Jeśli liczba
jest liczbą Fibonacciego to krok indukcyjny jest już dowiedziony, jeśli nie to znajdujemy największą liczbę Fibonacciego mniejszą od -- oznaczmy tą liczbę . Liczba jest mniejsza niż więc, na mocy założenia indukcyjnego, posiada reprezentację jako suma liczb Fibonacciegotak, że każda z liczb w tej reprezentacji występuje co najwyżej raz. Oczywiście
i pozostaje wykazać, że
nie występuje pośród liczb . Skoro było największą liczbą Fibonacciego mniejszą niż to a więc . W związku z tym liczby są silnie mniejsze niż i żadna z nich nie może być równa . W ten sposób krok indukcyjny został dowiedziony.Ćwiczenie [Uzupelnij]
Znajdź błąd w poniższym dowodzie indukcyjnym. Dowodzimy indukcyjnie twierdzenia, że wszystkie liczby są parzyste.
- Twierdzenie jest prawdą dla ponieważ jest liczbą parzystą.
- Zakładamy, że twierdzenie jest prawdą dla wszystkich liczb
mniejszych lub równych
. Liczba jest niewątpliwie sumą dwóch liczb silnie mniejszych od siebie . Liczby i , na podstawie założenia indukcyjnego, są parzyste, zatem ich suma równa jest parzysta. Krok indukcyjny został dowiedziony.Na zasadzie indukcji matematycznej wszystkie liczby są parzyste.
- Solution.
- Dowód indukcyjny jest niepoprawny. Krok indukcyjny nie
działa dla wszystkich
większych lub równych od -- które jest podstawą indukcji. Jeśli , to i nie jesteśmy w stanie rozbić liczby na sumę dwóch liczb istotnie mniejszych od niej samej.Ćwiczenie [Uzupelnij]
W trójwymiarowej przestrzeni znajduje się
punktów. Ilość punktów w rzutowaniu na płaszczyznę oznaczamy przez . Podobnie ilość punktów w rzutowaniu na przez i ilość punktów w rzutowaniu na przez . Wykaż, że dla dowolnego rozkładu punktów w przestrzeni zachodzi nierówność{hint}{1}
- Hint .
- Użyj nierówności pomiędzy średnią geometryczną, a
średnią arytmetyczną
{hint}{1}
- Hint .
- Podziel punkty na dwie grupy płaszczyzną równoległą do
którejś z płaszczyzn
, lub .- Solution.
- Dowiedziemy nierówność przy użyciu indukcji.
- Jeśli to i nierówność jest prawdziwa.
- Zakładamy, że nierówność jest prawdziwa dla wszystkich liczb
naturalnych (dla dowolnego układu punktów) mniejszych niż
. Rozpoczynamy z dowolnym układem punktów w przestrzeni. Ponieważ wiemy, że istnieje płaszczyzna równoległa do którejś z płaszczyzn , lub i dzieląca punktów na dwie niepuste części posiadające odpowiednio i punktów. Ponieważ nasz układ jest bardzo symetryczny możemy założyć że nasza płaszczyzna jest równoległa do płaszczyzny . Stosując założenie indukcyjne do każdej z części otrzymujemyoraz
Co więcej, pomiędzy projekcjami zachodzą następujące zależności
Dla płaszczyzny
nie posiadamy podziału na część punktów należących do i i możemy jedynie wnioskować, żeZaczynamy przekształcenia mające udowodnić pożądaną nierówność
używając założenia indukcyjnego i nierówności pomiędzy projekcjami na płaszczyznę
. Kontynuujemy używając nierówności pomiędzy średnią algebraiczną i geometrycznąW ostatnim kroku wystarczy wykorzystać zależności pomiędzy projekcjami na pozostałe dwie współrzędne i
Krok indukcyjny został dowiedziony.
Na podstawie zasady indukcji matematycznej twierdzenie jest prawdziwe.
{obra}{1}{Obrazek {section}.{obra}}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 [Uzupelnij]
Istnieje nieskończenie wiele liczb pierwszych.
Dowód [Uzupelnij]
Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych
. Zdefiniujmy liczbęi rozważmy
. Liczba posiada dzielnik pierwszy, a ponieważ jedynymi pierwszymi liczbami są liczby wnioskujemy, że dzieli dla pewnego . Liczba dzieli również , a więc dzieli co jest sprzecznością.
Ćwiczenie [Uzupelnij]
Wykaż, że nie istnieje największa liczba naturalna.
- Solution.
- Załóżmy, niewprost, że istnieje największa liczba
naturalna i oznaczmy ją przez
. Niewątpliwie jest liczbą naturalną większą od , co jest sprzecznością z naszym założeniem.Ćwiczenie [Uzupelnij]
Wykaż, że
jest liczbą niewymierną.- Solution.
- Załóżmy,
niewprost, że
jest liczbą wymierną, czyli, że istnieją dwie naturalne, względnie pierwsze liczby i takie, że . Przekształcając ostatnie wyrażenie otrzymujemy . Skoro dzieli lewą stronę równości dzieli też i prawą, a ponieważ dwa jest liczbą pierwszą wnioskujemy, że dzieli . Jeśli dzieli to dzieli i na podstawie równości dzieli . Wnioskujemy stąd, że dzieli i, na podstawie pierwszości liczby , że dzieli . Udowodniliśmy, że dzieli zarówno jak i , co jest sprzecznością z założeniem, że liczby te są względnie pierwsze.Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie logiki, której poświęcony jest następny wykład.