Twierdzenia matematyczne z dowodami

Twierdzenie to zdanie udowodnione w danej teorii matematycznej. W tym dziale zbieramy twierdzenia wraz z pełnymi dowodami krok po kroku - od klasyków sprzed dwóch tysięcy lat po wyniki, które w XX wieku zmieniły sposób myślenia o samej matematyce. Każde hasło ma ten sam układ: treść, założenia, dowód (schowany pod przyciskiem, żeby dać sobie szansę na własne rozumowanie), przykłady, kontrprzykłady i zastosowania.

Teoria liczb

• Twierdzenie Euklidesa: liczb pierwszych jest nieskończenie wiele - klasyczny dowód nie wprost sprzed $2300$ lat i najczęstszy błąd w jego streszczeniach.
• Twierdzenie o liczbach pierwszych - ile jest liczb pierwszych do x: π(x) ≈ x/ln x; elementarny dowód oszacowania Czebyszewa i droga do hipotezy Riemanna.
• Podstawowe twierdzenie arytmetyki - każda liczba ma dokładnie jeden rozkład na czynniki pierwsze; z przykładem świata, w którym jednoznaczność zawodzi.
• Algorytm Euklidesa - NWD przez dzielenie z resztą, dowód poprawności, NWW i tożsamość Bézouta; najstarszy algorytm wciąż w powszechnym użyciu.
• Twierdzenia Fermata - przewodnik po trzech twierdzeniach o tym nazwisku (plus zasada, punkt i liczby Fermata), gdy nie wiadomo, o które chodzi.
• Małe twierdzenie Fermata - dowód indukcyjny, liczby Carmichaela i rola tego twierdzenia w szyfrowaniu RSA.
• Wielkie twierdzenie Fermata - dowód przypadku $n = 4$ metodą nieskończonego schodzenia, 358 lat poszukiwań i dowód Andrew Wilesa.
• Twierdzenie Wilsona - warunek równoważny pierwszości, oparty na silni; dowód przez parowanie liczb z ich odwrotnościami.

Kombinatoryka

• Zasada szufladkowa Dirichleta - najprostsze twierdzenie o najbardziej zaskakujących wnioskach: włosy mieszkańców Warszawy, punkty w kwadracie i reszty z dzielenia.
• Zasada włączeń i wyłączeń - jak liczyć sumę zbiorów, które się przecinają; problem szatniarki i wzór na funkcję Eulera.
• Twierdzenie Ramseya - wśród sześciu osób zawsze są trzy znające się nawzajem albo trzy wzajemnie obce; dlaczego R(5,5) pozostaje nieznane i kosmici Erdősa.
• Mosty królewieckie i twierdzenie Eulera o grafach - kiedy da się przejść po wszystkich krawędziach dokładnie raz; zagadka, od której zaczęła się teoria grafów.
• Twierdzenie o czterech barwach - każdą mapę pokolorują cztery kolory; pełny dowód wersji o sześciu barwach, słynny błąd z 1879 roku i pierwsze twierdzenie udowodnione komputerowo.

Rachunek prawdopodobieństwa

• Twierdzenie Bayesa - dlaczego dodatni wynik testu o czułości $99\%$ oznacza tylko około $17\%$ szans na chorobę.
• Paradoks urodzin - dlaczego już w grupie $23$ osób szansa na wspólne urodziny przekracza połowę.
• Problem Monty Halla - z symulatorem: zagraj sam albo puść tysiąc rozgrywek i sprawdź, że zmiana bramki podwaja szansę wygranej.
• Prawo wielkich liczb - z symulatorem rzutów monetą: częstość orłów zbiega do 50%, ale saldo niczego nie wyrównuje; pełny dowód przez nierówności Markowa i Czebyszewa.
• Centralne twierdzenie graniczne - z symulatorem histogramu: uśredniaj rzuty kostką, monetą albo rozkład skośny i patrz, jak każdy kształt zamienia się w dzwon Gaussa; szkic dowodu i reguła trzech sigm.

Geometria

• Twierdzenie o kącie zewnętrznym trójkąta - kąt zewnętrzny równa się sumie dwóch kątów wewnętrznych nieprzyległych; dwa dowody, w tym wersja Euklidesa działająca bez postulatu równoległości.
• Odcinek łączący środki boków trójkąta - linia środkowa jest równoległa do trzeciego boku i ma połowę jego długości; trzy dowody, linia środkowa trapezu i twierdzenie Varignona.
• Twierdzenie Pitagorasa w czterech dowodach - układanka z kwadratów, podobieństwo trójkątów, rozcięcie Bhaskary i dowód prezydenta Garfielda.
• Twierdzenie cosinusów (Carnota) - uogólnienie twierdzenia Pitagorasa na dowolny trójkąt; dwa dowody i test na trójkąt rozwartokątny z samych boków.
• Twierdzenie sinusów - boki są proporcjonalne do sinusów przeciwległych kątów, a stała to średnica okręgu opisanego; przypadek z dwoma trójkątami.
• Twierdzenie Talesa o kącie wpisanym w półokrąg - kąt oparty na średnicy jest zawsze prosty; dowód, twierdzenie odwrotne i wyjaśnienie, dlaczego w Polsce twierdzeniem Talesa nazywa się co innego.
• Twierdzenie Picka - pole wielokąta na kratce policzone z samego przeliczania kropek.
• Wzór Eulera dla wielościanów - dlaczego zawsze wychodzi dwójka i dlaczego wielościanów foremnych jest dokładnie pięć.

Algebra i nierówności

• Nierówność między średnimi (AM-GM) - dowód algebraiczny i geometryczny oraz optymalizacja bez pochodnych.
• Twierdzenie Abela-Ruffiniego - dlaczego nie istnieje wzór na pierwiastki równania piątego stopnia, choć dla stopni 2, 3 i 4 istnieje.

Analiza matematyczna

• Twierdzenie o wartości pośredniej - funkcja ciągła nie przeskoczy żadnej wartości; dowód metodą bisekcji, chwiejący się stół i temperatura na antypodach.
• Twierdzenie Fermata o ekstremum - dlaczego w zadaniach optymalizacyjnych przyrównujemy pochodną do zera i dlaczego to dopiero połowa roboty; trzy kontrprzykłady.
• Twierdzenie Banacha o punkcie stałym - mapa Polski na stole, klawisz cosinus i zasada kontrakcji, która rankinguje internet; pełny dowód z oszacowaniem tempa zbieżności.

Podstawy matematyki

• Niewymierność pierwiastka z dwóch - dowód, który zburzył pitagorejski obraz świata; dwa różne rozumowania i uogólnienia.
• Twierdzenie Cantora i metoda przekątniowa - dlaczego liczb rzeczywistych jest „więcej” niż naturalnych i skąd bierze się wieża nieskończoności.
• Twierdzenia Cantora - wszystkie cztery twierdzenia noszące to nazwisko (w tym Cantora-Heinego) oraz zbiór Cantora: miara zero i moc continuum.
• Twierdzenia Gödla o niezupełności - co dokładnie mówią, jak działa zdanie „nie jestem dowodliwe” i czego te twierdzenia nie mówią.

Czym jest twierdzenie

Twierdzenie to zdanie udowodnione w danej teorii matematycznej. Każdy aksjomat teorii jest również jej twierdzeniem. Na ogół twierdzenia mają postać implikacji lub też implikacji poprzedzonej kwantyfikatorami ogólnymi. Poprzednik implikacji, która jest twierdzeniem, nazywa się założeniem twierdzenia, a jej następnik - tezą twierdzenia. Zdanie wynikające w prosty sposób z twierdzenia lub będące jego szczególnym przypadkiem nazywa się wnioskiem z twierdzenia.

Jeżeli implikacja $\alpha \Rightarrow \beta$ (gdzie $\alpha$ i $\beta$ są zdaniami lub funkcjami zdaniowymi) jest twierdzeniem, to $\alpha$ nazywa się również warunkiem wystarczającym lub warunkiem dostatecznym na to, aby była spełniona własność wyrażona przez $\beta$, a $\beta$ nazywa się warunkiem koniecznym tego, by była spełniona własność wyrażona przez $\alpha$.

Przykład. W twierdzeniu arytmetyki: „jeżeli liczba naturalna $m$ jest podzielna przez sześć, to jest ona podzielna przez trzy”, założeniem twierdzenia jest „$m$ jest podzielna przez sześć”, a tezą - „$m$ jest podzielna przez trzy”. Warunkiem wystarczającym na to, aby liczba $m$ była podzielna przez trzy, jest jej podzielność przez sześć; warunkiem koniecznym podzielności liczby $m$ przez sześć jest natomiast jej podzielność przez trzy.

Twierdzenie odwrotne

Twierdzenie odwrotne do danego twierdzenia to twierdzenie $T_1$, którego założeniem jest teza danego twierdzenia $T$, a tezą - założenie twierdzenia $T$. Niech będzie dane twierdzenie $\alpha \Rightarrow \beta$; twierdzeniem odwrotnym jest zdanie $\beta \Rightarrow \alpha$. Twierdzenie odwrotne do danego nie musi być prawdziwe. Twierdzenie odwrotne jest równoważne twierdzeniu przeciwnemu.

Przykład 1. Twierdzeniem odwrotnym do twierdzenia „w każdym prostokącie przekątne są równe” jest zdanie „jeżeli przekątne czworokąta są równe, to jest on prostokątem” - zdanie fałszywe (bo np. w trapezie równoramiennym przekątne też są równe).

Przykład 2. Twierdzeniem odwrotnym do twierdzenia „jeżeli iloczyn dwóch liczb rzeczywistych jest równy zeru, to jedna z tych liczb jest równa zeru” jest zdanie „jeżeli jedna z liczb rzeczywistych jest równa zeru, to ich iloczyn jest równy zeru” - zdanie prawdziwe.

Przykład 3. Twierdzenie odwrotne do twierdzenia Pitagorasa jest prawdziwe: jeśli $a^2 + b^2 = c^2$, to trójkąt jest prostokątny. Za to twierdzenie odwrotne do małego twierdzenia Fermata jest fałszywe - świadczą o tym liczby Carmichaela.

Twierdzenie przeciwne

Twierdzenie przeciwne do danego twierdzenia to zdanie stwierdzające, że negacja założenia twierdzenia implikuje negację jego tezy. Twierdzeniem przeciwnym do twierdzenia $\alpha \Rightarrow \beta$ jest zdanie $\neg\alpha \Rightarrow \neg\beta$. Na mocy prawa transpozycji twierdzenie przeciwne jest równoważne twierdzeniu odwrotnemu i - podobnie jak ono - nie musi być prawdziwe.

Twierdzenie przeciwstawne

Twierdzenie przeciwstawne do danego twierdzenia to zdanie stwierdzające, że z negacji tezy twierdzenia wynika negacja jego założenia. Twierdzeniem przeciwstawnym do twierdzenia $\alpha \Rightarrow \beta$ jest zdanie $\neg\beta \Rightarrow \neg\alpha$. Na mocy prawa transpozycji (inaczej: prawa kontrapozycji) twierdzenie przeciwstawne jest równoważne danemu twierdzeniu - i właśnie dlatego wolno dowodzić go zamiast oryginału. Ten chwyt nosi nazwę dowodu przez kontrapozycję.

Terminu „twierdzenie” używa się też przy formułowaniu zdań fałszywych, w postaci: „następujące twierdzenie nie jest prawdziwe…”.

Najczęstsze pytania

Czym różni się twierdzenie od aksjomatu? Aksjomat przyjmujemy bez dowodu - to punkt wyjścia teorii. Twierdzenie wymaga dowodu, choć formalnie każdy aksjomat też jest twierdzeniem swojej teorii.

Czy twierdzenie odwrotne zawsze jest prawdziwe? Nie i to jedna z najczęstszych pomyłek. „Każdy kwadrat jest prostokątem” jest prawdą, ale zdanie odwrotne już nie. Prawdziwość twierdzenia odwrotnego trzeba udowodnić osobno.

Co to jest twierdzenie pomocnicze (lemat)? Twierdzenie pomocnicze, czyli lemat, to twierdzenie dowodzone po to, by wykorzystać je w innym dowodzie. Od „zwykłego” twierdzenia różni się tylko rolą, nie statusem. Niektóre lematy okazały się ważniejsze od twierdzeń, dla których powstały - np. lemat Zorna czy lemat Euklidesa. Z kolei wniosek to twierdzenie, które wynika z innego niemal od razu.

Co to jest dowód nie wprost? Zakładamy, że teza jest fałszywa, i doprowadzamy do sprzeczności. Skoro zaprzeczenie prowadzi do fałszu, teza musi być prawdziwa. Tak dowodzimy m.in. nieskończoności liczb pierwszych.

Czy każde prawdziwe zdanie da się udowodnić? Nie. To najbardziej zaskakujący wynik logiki XX wieku - twierdzenia Gödla o niezupełności mówią, że w każdym odpowiednio bogatym systemie istnieją zdania prawdziwe, lecz niedowodliwe.