Dowód na niemożliwość

W matematyce dowód niemożliwości to dowód , który pokazuje, że określonego problemu nie można rozwiązać w sposób opisany w twierdzeniu lub że określonego zestawu problemów nie można rozwiązać w ogóle. Taki przypadek jest również znany jako dowód negatywny , dowód twierdzenia o niemożliwości lub wynik negatywny . Ponieważ pokazują, że czegoś nie da się zrobić, dowód niemożliwości często jest postanowieniem dziesięcioleci lub stuleci pracy w poszukiwaniu rozwiązania. Udowodnienie, że coś jest niemożliwe, jest zwykle znacznie trudniejsze niż zadanie odwrotne, ponieważ często konieczne jest opracowanie dowodu, który działa ogólnie, a nie tylko pokazanie konkretnego przykładu. Twierdzenia o niemożliwości można zwykle wyrazić jako negatywne twierdzenia egzystencjalne lub twierdzenia uniwersalne w logice.

Irracjonalność pierwiastka kwadratowego z 2 jest jednym z najstarszych dowodów na niemożliwość. Pokazuje, że nie da się wyrazić pierwiastka kwadratowego z 2 jako stosunku dwóch liczb całkowitych . Innym konsekwentnym dowodem niemożliwości był Ferdinanda von Lindemanna z 1882 r., który pokazał, że problemu kwadratury koła nie można rozwiązać, ponieważ liczba $π$ jest przestępna (tj. niealgebraiczna) i że można podać tylko podzbiór liczb algebraicznych zbudowany przez kompas i linijka . Dwa inne klasyczne problemy – potrojenie kąta ogólnego i podwojenie sześcianu – również okazały się w XIX wieku niemożliwe i wszystkie te problemy dały początek badaniom nad bardziej skomplikowanymi strukturami matematycznymi.

Problemem, który pojawił się w XVI wieku, było utworzenie ogólnego wzoru za pomocą pierwiastków do wyrażenia rozwiązania dowolnego równania wielomianowego o ustalonym stopniu k , gdzie k ≥ 5. W latach dwudziestych XIX wieku twierdzenie Abela – Ruffiniego (znane również jako twierdzenie Abela o niemożliwości ) wykazało, że jest to niemożliwe, używając pojęć takich jak rozwiązywalne grupy z teorii Galois – nowego poddziedziny algebry abstrakcyjnej .

Do najważniejszych dowodów niemożliwości znalezionych w XX wieku należały dowody związane z nierozstrzygalnością , które pokazały, że istnieją problemy, których w ogóle nie da się rozwiązać żadnym algorytmem , a jednym z najbardziej znanych był problem zatrzymania . Twierdzenia Gödla o niezupełności były kolejnymi przykładami, które odsłoniły fundamentalne ograniczenia w możliwości udowodnienia systemów formalnych.

W teorii złożoności obliczeniowej techniki takie jak relatywizacja (dodanie wyroczni ) pozwalają na „słabe” dowody niemożliwości, ponieważ techniki dowodowe, na które nie ma wpływu relatywizacja, nie mogą rozwiązać problemu P kontra NP . Inną techniką jest dowód kompletności klasy złożoności , który dostarcza dowodów na trudność problemów, pokazując, że są one tak samo trudne do rozwiązania, jak każdy inny problem w tej klasie. W szczególności kompletny problem jest nierozwiązywalny jeśli jednym z problemów w tej klasie jest.

Rodzaje dowodów

Przez sprzeczność

Jednym z powszechnie stosowanych rodzajów dowodu niemożliwości jest dowód przez sprzeczność . W tego rodzaju dowodzie wykazano, że jeśli zakłada się, że zachodzi twierdzenie, takie jak rozwiązanie określonej klasy równań, to poprzez dedukcję można wykazać, że obowiązują dwie wzajemnie sprzeczne rzeczy, na przykład liczba będąca obie parzyste i nieparzyste lub zarówno negatywne, jak i pozytywne. Skoro sprzeczność wynika z pierwotnego założenia, oznacza to, że przyjęte założenie musi być niemożliwe.

Z pochodzenia

Jednym z rodzajów dowodu przez sprzeczność jest dowód przez zejście, który najpierw zakłada, że coś jest możliwe, na przykład rozwiązanie klasy równań w postaci dodatniej liczby całkowitej i że w związku z tym musi istnieć najmniejsze rozwiązanie (zgodnie z zasadą dobrego uporządkowania ) . Z rzekomego najmniejszego rozwiązania pokazano następnie, że można znaleźć mniejsze rozwiązanie, co zaprzecza założeniu, że poprzednie rozwiązanie było najmniejsze z możliwych - pokazując w ten sposób, że pierwotne założenie, że rozwiązanie istnieje, musi być fałszywe.

Rodzaje zaprzeczeń

Istnieją dwie alternatywne metody obalenia przypuszczenia, że coś jest niemożliwe: poprzez kontrprzykład ( dowód konstruktywny ) i sprzeczność logiczną ( dowód niekonstruktywny ).

Oczywistym sposobem obalenia hipotezy o niemożliwości jest podanie jednego kontrprzykładu. Na przykład Euler zaproponował , że aby zsumować do jeszcze jednej n- ^{tej potęgi, konieczne jest} co najmniej n różnych n- ^{tych potęg} . Przypuszczenie zostało obalone w 1966 r., Kontrprzykładem obejmującym zliczenie tylko czterech różnych potęg piątych, co dało kolejną potęgę piątą:

27 ⁵ + 84 ⁵ + 110 ⁵ + 133 ⁵ = 144 ⁵ .

Dowód przez kontrprzykład jest dowodem konstruktywnym , polegającym na przedstawieniu przedmiotu obalającego twierdzenie. W przeciwieństwie do tego, niekonstruktywny dowód twierdzenia o niemożliwości przebiegałby poprzez wykazanie, że jest to logicznie sprzeczne, aby wszystkie możliwe kontrprzykłady były nieważne: co najmniej jedna pozycja na liście możliwych kontrprzykładów musi w rzeczywistości być ważnym kontrprzykładem dla hipotezy o niemożności . Na przykład obalone zostało przypuszczenie , że nie jest możliwe, aby irracjonalna władza podniesiona do irracjonalnej władzy była racjonalna , pokazując, że jeden z dwóch możliwych kontrprzykładów musi być ważnym kontrprzykładem, bez wskazywania, który to jest.

Pitagorejski dowód na istnienie liczb niewymiernych

Dowód Pitagorasa (lub, co bardziej prawdopodobne, jednego z jego uczniów ^{[ według kogo? ]} ) około 500 roku p.n.e. wywarł głęboki wpływ na matematykę. Pokazuje, że pierwiastka kwadratowego z 2 nie można wyrazić jako stosunku dwóch liczb całkowitych. Dowód podzielił „liczby” na dwa niezachodzące na siebie zbiory - liczby wymierne i liczby niewymierne . To rozwidlenie zostało wykorzystane przez Cantora w jego metodzie diagonalnej , którą z kolei wykorzystał Turing w swoim dowodzie, że Entscheidungsproblem , problem decyzyjny Hilberta , jest nierozstrzygalny .

Nie wiadomo, kiedy i przez kogo odkryto „twierdzenie Pitagorasa”. Odkrycia tego raczej nie dokonał sam Pitagoras, ale z pewnością dokonano go w jego szkole. Pitagoras żył około 570–490 p.n.e. Demokryt, urodzony około 470 roku p.n.e., pisał na irracjonalnych liniach i bryłach …

— Heath, ^{[ potrzebne źródło ]}

Następnie przeprowadzono dowody dla różnych pierwiastków kwadratowych z liczb pierwszych aż do 17.

Teajtecie Platona znajdujemy słynny fragment, w którym stwierdza się, że Teodor (nauczyciel Platona) udowodnił irracjonalność

${\ Displaystyle {\ sqrt {3}}, {\ sqrt {5}}, ...,}$

biorąc wszystkie oddzielne przypadki aż do pierwiastka z 17 stóp kwadratowych... .

Istnieje obecnie bardziej ogólny dowód, że:

M - ty pierwiastek z liczby całkowitej N jest niewymierny, chyba że N jest m- tą potęgą liczby całkowitej n .

Oznacza to, że niemożliwe jest wyrażenie m- tego pierwiastka z liczby całkowitej N jako stosunku a ⁄ b dwóch liczb całkowitych aib , które nie mają wspólnego czynnika pierwszego, z wyjątkiem przypadków, w których b = 1.

Niemożliwe konstrukcje, których szukali starożytni Grecy

Trzy słynne pytania z geometrii greckiej brzmiały: jak:

dokonać trisekcji dowolnego kąta za pomocą kompasu i linijki ,
skonstruować sześcian o objętości dwukrotnie większej od objętości danego sześcianu ,
skonstruować kwadrat o polu równym polu danego koła.

Przez ponad 2000 lat podejmowano bezskuteczne próby rozwiązania tych problemów; wreszcie w XIX wieku udowodniono, że pożądane konstrukcje są logicznie niemożliwe.

Czwartym problemem starożytnych Greków było zbudowanie wielokąta równobocznego o określonej liczbie n boków, poza podstawowymi przypadkami n = 3, 4, 5, 6, które umieli konstruować.

Wszystko to są problemy w konstrukcji euklidesowej , a konstrukcje euklidesowe można wykonać tylko wtedy, gdy uwzględniają tylko liczby euklidesowe (z definicji tej ostatniej). Liczby niewymierne mogą być euklidesowe. Dobrym przykładem jest pierwiastek kwadratowy z 2 (liczba niewymierna). Jest to po prostu długość przeciwprostokątnej trójkąta prostokątnego, którego ramiona mają po jednej jednostce długości i można ją skonstruować za pomocą linijki i kompasu. Jednak wieki po Euklidesie udowodniono, że na liczbach euklidesowych nie można wykonywać żadnych operacji poza dodawaniem, odejmowaniem, mnożeniem, dzieleniem i wyciąganiem pierwiastków kwadratowych.

Trisekcja kąta i podwojenie sześcianu

Zarówno trisekcja kąta ogólnego, jak i podwojenie sześcianu wymagają pierwiastków sześciennych , których nie można skonstruować za pomocą kompasu ani linijki.

Kwadratowanie koła

nie jest $liczbą$ euklidesową … i dlatego nie można skonstruować metodami euklidesowymi długości równej obwodowi koła o jednostkowej

Istnieje dowód wykazujący, że dowolna liczba euklidesowa jest liczbą algebraiczną — liczbą będącą rozwiązaniem jakiegoś równania wielomianowego . Dlatego też, ponieważ $roku$ udowodniono, że jest liczbą przestępną , a zatem z definicji nie jest liczbą algebraiczną, jest to liczba euklidesowa. Stąd konstrukcja długości $okręgu$ jednostkowego jest niemożliwa i koła nie można podnieść do kwadratu.

Konstruowanie równobocznego n -kątu

Gaussa -Wantzela wykazało w 1837 roku, że skonstruowanie równobocznego n -gonu jest niemożliwe dla większości wartości n .

Równoległy postulat Euklidesa

Postulat równoległy z Elementów Euklidesa jest równoważny stwierdzeniu , że mając linię prostą i punkt nie leżący na tej linii, przez ten punkt można poprowadzić tylko jedną równoległą do tej prostej. W odróżnieniu od pozostałych postulatów uznawano go za mniej oczywisty. Nagel i Newman argumentują, że może to wynikać z faktu, że postulat dotyczy „nieskończenie odległych” obszarów przestrzeni; w szczególności linie równoległe definiuje się jako niespełniające się nawet „w nieskończoności”, w przeciwieństwie do asymptot . Ten dostrzegalny brak oczywistości doprowadził do pytania, czy można to udowodnić na podstawie innych aksjomatów i postulatów euklidesowych. Dopiero w XIX wieku niemożność wydedukowania postulatu równoległego z innych została wykazana w pracach Gaussa , Bolyai , Łobaczewskiego i Riemanna . Prace te pokazały, że postulat równoległości można ponadto zastąpić alternatywami, prowadząc do geometrii nieeuklidesowych .

Nagel i Newman uważają kwestię podniesioną przez równoległy postulat za „...być może najbardziej znaczący rozwój w zakresie jego dalekosiężnych skutków dla późniejszej historii matematyki”. W szczególności uważają, że jego wynik ma „największe znaczenie intelektualne”, gdyż pokazał, że „ można dać dowód na niemożność udowodnienia pewnych twierdzeń [w tym przypadku postulatu równoległego] w ramach danego systemu [w tym przypadku pierwsze cztery postulaty Euklidesa]”.

Ostatnie twierdzenie Fermata

Ostatnie twierdzenie Fermata zostało wysunięte przez Pierre'a de Fermata w XVII wieku i stwierdza niemożność znalezienia rozwiązań równania w dodatnich liczbach całkowitych. ${\ displaystyle x ^ {n} + y ^ {n} = z ^ {n}}$ z ${\ displaystyle n> 2}$ . Sam Fermat przedstawił dowód dla przypadku n = 4, stosując swoją technikę nieskończonego zejścia , a następnie udowodniono inne szczególne przypadki, ale ogólny przypadek został udowodniony dopiero w 1994 r. przez Andrew Wilesa .

Paradoks Richarda

Ten głęboki paradoks zaprezentowany przez Julesa Richarda w 1905 roku wpłynął na twórczość Kurta Gödla i Alana Turinga. Zwięzłą definicję można znaleźć w Principia Mathematica :

Paradoks Richarda... jest następujący. Rozważmy wszystkie ułamki dziesiętne, które można zdefiniować za pomocą skończonej liczby słów [„słowa” to symbole; dodano pogrubienie dla podkreślenia] ; niech E będzie klasą takich miejsc po przecinku. Wtedy E ma [nieskończoną liczbę $terminów$ ; stąd jego elementy można uporządkować jako 1., 2., 3., ... Niech X będzie liczbą zdefiniowaną w następujący sposób [Whitehead i Russell stosują teraz metodę przekątnej Cantora] . Jeśli nr -ta cyfra n -tego miejsca po przecinku to p , niech n -ta cyfra w X będzie p + 1 (lub 0, jeśli p = 9). Wtedy X jest różne od wszystkich elementów E , ponieważ niezależnie od skończonej wartości n , n -ta cyfra w X różni się od n -tej cyfry n -tego miejsca po przecinku tworzącego E i dlatego X jest różni się od n -ta część dziesiętna. Niemniej jednak zdefiniowaliśmy X w skończonej liczbie słów [tzn. tę samą definicję „słowa” powyżej.] i dlatego X powinien należeć do E . Zatem X zarówno jest, jak i nie jest członkiem E.

— Principia Mathematica , wyd. 2 1927, s. 23. 61

Kurt Gödel uznał swój dowód za „analogię” paradoksu Richarda, który nazwał „ antynomią Richarda ” (patrz niżej ) .

Alan Turing skonstruował ten paradoks za pomocą maszyny i udowodnił, że maszyna ta nie jest w stanie odpowiedzieć na proste pytanie: czy maszyna ta będzie w stanie określić, czy jakakolwiek maszyna (w tym ona sama) zostanie uwięziona w bezproduktywnej „nieskończonej pętli” ( tj . obliczenie liczby przekątnej).

Niekompletność systemów aksjomatycznych: dowód Gödla

Cytując Nagela i Newmana (s. 68): „Artykuł Gödla jest trudny. Przed osiągnięciem głównych wyników należy opanować czterdzieści sześć wstępnych definicji wraz z kilkoma ważnymi wstępnymi twierdzeniami”. W rzeczywistości Nagel i Newman potrzebowali 67-stronicowego wprowadzenia do swojego przedstawienia dowodu. Jeśli jednak czytelnik poczuje się na tyle silny, aby zmierzyć się z treścią artykułu, Martin Davis zauważa, że „Ta niezwykła praca jest nie tylko kamieniem milowym pod względem intelektualnym, ale jest napisana z jasnością i wigorem, dzięki czemu czytanie jej jest przyjemnością” (Davis w „Undecidable”, s. 4). ). Polecane jest ^{[ przez kogo? ]} że większość czytelników widzi najpierw Nagela i Newmana.

Gödel udowodnił własnymi słowami:

„Rozsądne jest… przypuszczenie, że… [aksjomaty] [z Principia Mathematica i Peano ] są… wystarczające do rozstrzygnięcia wszystkich kwestii matematycznych, które można formalnie wyrazić w danych systemach. Poniżej znajduje się następujący opis: zostanie pokazane, że tak nie jest, ale raczej, że... istnieją stosunkowo proste problemy teorii zwykłych liczb całkowitych, których nie można rozstrzygnąć na podstawie aksjomatów” (Gödel w Nierozstrzygalne, s. 4).

Gödel porównał swój dowód do „antynomii Richarda” („ antynomia ” jest sprzecznością lub paradoksem; więcej informacji można znaleźć w paradoksie Richarda ):

„Analogia tego wyniku z antynomią Richarda jest od razu widoczna; istnieje także ścisły związek [14] z Paradoksem Kłamcy (przypis 14 Gödla: Każda antynomia epistemologiczna może zostać użyta do podobnego dowodu nierozstrzygalności)… Zatem, możemy mamy przed sobą twierdzenie, które stwierdza swoją własną niedowodliwość [15] (Jego przypis 15: Wbrew pozorom takie twierdzenie nie jest okrężne, gdyż na początek stwierdza niedowodliwość całkiem określonej formuły)”.

Problem zatrzymania: pierwszy dowód Turinga

Entscheidungsproblem , problem decyzyjny , został po raz pierwszy rozwiązany przez Kościół w kwietniu 1935 roku i wyprzedził Turinga o ponad rok, gdy artykuł Turinga został przyjęty do publikacji w maju 1936 roku .
Dowód Turinga jest utrudniony ze względu na liczbę wymaganych definicji i jego subtelną naturę. Aby uzyskać szczegółowe informacje, zobacz maszynę Turinga i dowód Turinga .
Pierwszy dowód Turinga (z trzech) jest zgodny ze schematem paradoksu Richarda: maszyna licząca Turinga to algorytm reprezentowany przez ciąg siedmiu liter w „maszynie liczącej”. Jego „obliczenia” polegają na przetestowaniu wszystkich maszyn liczących (w tym siebie) pod kątem „okręgów” i utworzeniu liczby ukośnej na podstawie obliczeń niekołowych lub „udanych” maszyn liczących. Robi to, zaczynając od 1, konwertując liczby (o podstawie 8) na ciągi siedmiu liter w celu przetestowania. Kiedy osiągnie swój własny numer, tworzy własny ciąg liter. Decyduje, że jest to ciąg liter udanej maszyny, ale gdy próbuje wykonać obliczenia tej ( własnej ) maszyny, blokuje się w okręgu i nie może kontynuować. W ten sposób dotarliśmy do paradoksu Richarda. (Jeśli jesteś zdezorientowany, zobacz dowód Turinga, aby uzyskać więcej informacji).

Szereg podobnych dowodów nierozstrzygalności pojawiło się wkrótce przed i po dowodzie Turinga:

Kwiecień 1935: Dowód Kościoła Alonzo („Nierozwiązalny problem elementarnej teorii liczb”). Jego dowód polegał na „...zaproponowaniu definicji efektywnej obliczalności… i pokazaniu na przykładzie, że nie każdy problem tej klasy jest rozwiązalny” (Undecidable s. 90))
1946: Problem korespondencji pocztowej (por. Hopcroft i Ullman s. 193 i nast., s. 407 w celach informacyjnych)
Kwiecień 1947: Dowód Emila Posta ( Rekurencyjna nierozwiązywalność problemu Thue ) (Nierozstrzygalny s. 293). Od tego czasu stało się to znane jako „Problem słów Thue” lub „Problem słów Thue” ( Axel Thue zaproponował ten problem w artykule z 1914 r. (por. Odniesienia do artykułu Posta w Undecidable, s. 303)).
Twierdzenie Rice'a : uogólnione sformułowanie drugiego twierdzenia Turinga (por. Hopcroft i Ullman s. 185 i nast.)
Twierdzenie Greibacha : nierozstrzygalność w teorii języka (por. Hopcroft i Ullman s. 205 i nast. oraz odniesienie na s. 401 ibid: Greibach [1963] „The undecidability of the niejednoznaczność problemu dla minimalnych gramatyk liniowych”, Information and Control 6:2, 117–125 , także odniesienie na s. 402 ibid: Greibach [1968] „Uwaga o nierozstrzygalnych właściwościach języków formalnych”, Math Systems Theory 2:1, 1–6.)
płytek Penrose .
Pytanie o rozwiązania równań diofantyny i otrzymaną odpowiedź w Twierdzeniu MRDP; zobacz wpis poniżej.

Ściśliwość strun: dowód Chaitina

Informacje na temat ekspozycji odpowiedniej dla niespecjalistów można znaleźć w Beltrami, s. 23. 108 i nast. Zobacz także Franzen, rozdział 8, s. 137–148 i Davis, s. 263–266. Dyskusja Franzéna jest znacznie bardziej skomplikowana niż dyskusja Beltramiego i zagłębia się w tak zwane „prawdopodobieństwo zatrzymania” Ω – Gregory’ego Chaitina . Starsze podejście Davisa podchodzi do tej kwestii z punktu widzenia maszyny Turinga . Chaitin napisał wiele książek o swoich wysiłkach i wynikających z nich konsekwencjach filozoficznych i matematycznych.

Ciąg nazywa się (algorytmicznie) losowym, jeśli nie można go wygenerować za pomocą żadnego krótszego programu komputerowego. Chociaż większość ciągów znaków jest losowa , nie można tego udowodnić w przypadku żadnego konkretnego, z wyjątkiem skończenie wielu krótkich ciągów:

„Parafrazą wyniku Chaitina jest to, że nie może być formalnego dowodu na to, że wystarczająco długi ciąg jest przypadkowy…”

Beltrami zauważa, że „dowód Chaitina jest powiązany z paradoksem postawionym przez bibliotekarza z Oksfordu G. Berry’ego na początku XX wieku, który wymagał podania „najmniejszej dodatniej liczby całkowitej, której nie można zdefiniować za pomocą angielskiego zdania zawierającego mniej niż 1000 znaków”. Wiadomo, że najkrótsza definicja tej liczby musi mieć co najmniej 1000 znaków. Natomiast zdanie ujęte w cudzysłów, które samo w sobie jest definicją rzekomej liczby, ma mniej niż 1000 znaków!”.

Całkowite rozwiązania równań diofantyny: dziesiąty problem Hilberta

Pytanie „Czy dowolne równanie diofantyny ma rozwiązanie w postaci całkowitej?” jest nierozstrzygalny . Oznacza to, że nie da się odpowiedzieć na pytanie we wszystkich przypadkach.

Franzén wprowadza dziesiąty problem Hilberta i twierdzenie MRDP (twierdzenie Matiyasewicza-Robinsona-Davisa-Putnama), które stwierdza, że „nie istnieje algorytm, który mógłby zdecydować, czy równanie diofantyny ma w ogóle rozwiązanie” . MRDP wykorzystuje dowód nierozstrzygalności Turinga: „... zbiór rozwiązywalnych równań diofantyny jest przykładem zbioru przeliczalnego, ale nie rozstrzygalnego, a zbiór nierozwiązywalnych równań diofantyny nie jest przeliczalny”.

W naukach społecznych

W naukach politycznych twierdzenie o niemożliwości Arrowa stwierdza , że niemożliwe jest opracowanie systemu głosowania , który spełniałby zestaw pięciu konkretnych aksjomatów. Twierdzenie to można udowodnić, pokazując, że cztery aksjomaty łącznie implikują przeciwieństwo piątego.

W ekonomii twierdzenie Holmströma jest twierdzeniem o niemożliwości udowadniającym, że żaden system motywacyjny dla zespołu agentów nie może spełnić wszystkich trzech pożądanych kryteriów.

W naukach przyrodniczych

W naukach przyrodniczych twierdzenia o niemożliwości (podobnie jak inne twierdzenia) są powszechnie akceptowane jako w przeważającej mierze prawdopodobne, a nie uważane za udowodnione do tego stopnia, że są niepodważalne. Podstawą tej zdecydowanej akceptacji jest połączenie obszernych dowodów na to, że coś nie zachodzi, w połączeniu z leżącą u ich podstaw teorią, bardzo skuteczną w przewidywaniu, której założenia prowadzą logicznie do wniosku, że coś jest niemożliwe.

Dwa przykłady powszechnie akceptowanych w fizyce niemożliwości to maszyny perpetuum mobile , które naruszają prawo zachowania energii oraz przekraczanie prędkości światła , co narusza implikacje szczególnej teorii względności . Inną jest zasada nieoznaczoności mechaniki kwantowej , która stwierdza niemożność jednoczesnego poznania zarówno położenia, jak i pędu cząstki. Istnieje również twierdzenie Bella : żadna fizyczna teoria lokalnych zmiennych ukrytych nie jest w stanie odtworzyć wszystkich przewidywań mechaniki kwantowej.

Choć twierdzenia o niemożliwości w naukach przyrodniczych nigdy nie da się w pełni udowodnić, można je obalić poprzez obserwację pojedynczego kontrprzykładu . Taki kontrprzykład wymagałby ponownego zbadania założeń leżących u podstaw teorii, która implikowała niemożność.

Zobacz też

Lista nierozwiązanych problemów w matematyce – Wciąż poszukuje się rozwiązań tych problemów. Natomiast wiadomo , że powyższe problemy nie mają rozwiązania.
Paradoksy teorii mnogości

Uwagi i odniesienia

Bibliografia

GH Hardy i EM Wright , An Wprowadzenie do teorii liczb , wydanie piąte, Clarendon Press, Oxford England, 1979, przedruk 2000 z indeksem ogólnym (pierwsze wydanie: 1938). Dowody na to, że e i pi są transcendentalne, nie są trywialne, ale doświadczony matematycznie czytelnik będzie w stanie się przez nie przebrnąć.
Alfred North Whitehead i Bertrand Russell , Principia Mathematica to *56, Cambridge at the University Press, 1962, przedruk drugiego wydania 1927, pierwszego wydania 1913. Rozdz. 2.I. „Zasada błędnego koła” s. 13 37 i nast. oraz rozdz. 2.VIII. „Sprzeczności” s. 60ff.
Turing, AM (1936), „O liczbach obliczalnych, z zastosowaniem do Entscheidungsproblem”, Proceedings of the London Mathematical Society , 2 (opublikowane 1937), tom. 42, nie. 1, s. 230–65, doi : 10.1112/plms/s2-42.1.230 , S2CID 73712 (i Turing, AM (1938), „On Computable Numbers, with an Application to the Entscheidungsproblem: A Correcting”, Proceedings of the London Mathematical Society , 2 (opublikowane 1937), t. 43, nr 6, s. 544–6, doi : 10.1112/plms/s2-43.6.544 ). wersja internetowa Jest to epokowy artykuł, w którym Turing definiuje maszyny Turinga i pokazuje, że jest to (podobnie jak Entscheidungsproblem ) nierozwiązywalne.
Martin Davis , The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions , Raven Press, Nowy Jork, 1965. Artykuł Turinga zajmuje trzecie miejsce w tym tomie. Wśród artykułów znajdują się prace Godela, Churcha, Rossera, Kleene’a i Posta.
Rozdział Martina Davisa „Co to jest obliczenie” w Lynn Arthur Steen’s Mathematics Today , 1978, Vintage Books Edition, Nowy Jork, 1980. W jego rozdziale opisano maszyny Turinga w kategoriach prostszej maszyny Post-Turinga , a następnie kontynuowano opisy maszyn Turinga pierwszy dowód i wkład Chaitina.
Andrew Hodges , Alan Turing: Enigma , Simon and Schuster, Nowy Jork. Por. rozdział „Duch Prawdy”, aby poznać historię prowadzącą do jego dowodu i dyskusję na jego temat.
Hans Reichenbach , Elements of Symbolic Logic , Dover Publications Inc., Nowy Jork, 1947. Odniesienie często cytowane przez innych autorów.
Ernest Nagel i James Newman , Dowód Gödla , New York University Press, 1958.
Edward Beltrami, Co to jest losowość? Szansa i porządek w matematyce i życiu , Springer-Verlag New York, Inc., 1999.
Torkel Franzén , Twierdzenie Gödla, niekompletny przewodnik po jego użyciu i nadużyciach , AK Peters, Wellesley Mass, 2005. Niedawne podejście do twierdzeń Gödla i ich nadużyć. Nie jest to taka prosta lektura, jak sądzi autor. (Niewyraźne) omówienie trzeciego dowodu Turinga przez Franzéna jest przydatne ze względu na jego próby wyjaśnienia terminologii. Zawiera dyskusje na temat argumentów Freemana Dysona, Stephena Hawkinga, Rogera Penrose'a i Gregory'ego Chaitina (między innymi), które wykorzystują twierdzenia Gödla, a także użyteczną krytykę niektórych filozoficznych i metafizycznych bzdur inspirowanych Gödla, które znalazł w Internecie.
Pavel Pudlák, Logiczne podstawy matematyki i złożoność obliczeniowa. A Gentle Wprowadzenie , Springer 2013. (Patrz rozdział 4 „Dowody niemożliwości”).