Dowód niemożliwości - Proof of impossibility

W matematyce , a dowodem braku możliwości , znane również jako ujemną dowód , dowód na twierdzeniu niemożliwość lub ujemny wynik jest dowodem na wykazanie, że dany problem nie może być rozwiązany w sposób opisany w zastrzeżeniach, albo że dany zestaw problemu nie można rozwiązać ogólnie. Dowody niemożliwości często stawiają dziesięciolecia lub stulecia pracy, próbując znaleźć rozwiązanie, aby odpocząć. Udowodnienie, że coś jest niemożliwe, jest zwykle znacznie trudniejsze niż zadanie przeciwne, ponieważ często konieczne jest opracowanie teorii. Twierdzenia o niemożliwości są zwykle wyrażalne jako negatywne twierdzenia egzystencjalne lub uniwersalne twierdzenia w logice (więcej informacji można znaleźć w uniwersalnej kwantyfikacji ).

Być może jednym z najstarszych dowodów niemożliwości jest nieracjonalność pierwiastka kwadratowego z 2 , który pokazuje, że nie można wyrazić pierwiastka kwadratowego z 2 jako stosunku liczb całkowitych. Innym znanym dowodem niemożliwości był dowód Ferdinanda von Lindemanna z 1882 roku , pokazujący, że starożytny problem kwadratury koła nie może być rozwiązany, ponieważ liczba π jest przestępna (tzn. niealgebraiczna) i tylko podzbiór liczb algebraicznych może być skonstruowany przez kompas i linijkę. Dwa inne klasyczne problemy — przecięcie kąta ogólnego i podwojenie sześcianu — również okazały się niemożliwe w XIX wieku.

Problemem, który pojawił się w XVI wieku, było stworzenie ogólnej formuły za pomocą pierwiastków wyrażających rozwiązanie dowolnego równania wielomianowego o stałym stopniu k , gdzie k ≥ 5. W latach dwudziestych XIX wieku twierdzenie Abela-Ruffiniego (znane również jako twierdzenie o niemożliwości Abla) wykazali, że jest to niemożliwe, używając takich pojęć, jak rozwiązywalne grupy z teorii Galois — nowej poddziedziny algebry abstrakcyjnej .

Wśród najważniejszych dowodów niemożliwości XX wieku znalazły się te związane z nierozstrzygalnością , które pokazały, że istnieją problemy, których w ogóle nie da się rozwiązać za pomocą żadnego algorytmu, z których najsłynniejszym jest problem zatrzymania . Inne podobne odkrycia dotyczą twierdzeń o niezupełności Gödla , które ujawniają pewne fundamentalne ograniczenia w dowodliwości systemów formalnych.

W teorii złożoności obliczeniowej techniki takie jak relatywizacja (patrz maszyna Oracle ) dostarczają „słabych” dowodów niemożliwości, wyłączając niektóre techniki dowodowe. Inne techniki, takie jak dowody kompletności dla klasy złożoności , dostarczają dowodów na trudność problemów, pokazując, że są one tak samo trudne do rozwiązania, jak inne znane problemy, które okazały się niewykonalne .

Rodzaje dowodu niemożliwości

Dowód przez sprzeczność

Jednym z powszechnie stosowanych rodzajów dowodu niemożliwości jest dowód przez sprzeczność . W tego typu dowodzie pokazuje się, że gdyby coś, na przykład rozwiązanie określonej klasy równań, było możliwe, to prawdziwe byłyby dwie wzajemnie sprzeczne rzeczy, na przykład liczba jest zarówno parzysta, jak i nieparzysta. Sprzeczność oznacza, że ​​pierwotna przesłanka jest niemożliwa.

Dowód pochodzenia

Jednym z typów dowodu przez sprzeczność jest dowód dziedziczny, który opiera się najpierw na założeniu, że coś jest możliwe, na przykład rozwiązanie klasy równań w postaci liczby całkowitej dodatniej , a zatem musi istnieć rozwiązanie najmniejsze. Z rzekomego najmniejszego rozwiązania wynika następnie, że można znaleźć mniejsze rozwiązanie, co przeczy przesłance, że poprzednie rozwiązanie było najmniejsze z możliwych – pokazując tym samym, że pierwotna przesłanka (że rozwiązanie istnieje) musi być fałszywa.

Rodzaje obalania przypuszczeń o niemożliwości

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

Oczywisty sposób obalenia przypuszczenia o niemożliwości poprzez podanie jednego kontrprzykładu. Na przykład, Euler zaproponował , że co najmniej n inna n ^th uprawnień były konieczne, aby podsumować kolejny n ^-tego siły. Przypuszczenie zostało obalone w 1966 roku, z kontrprzykładem obejmującym liczbę tylko czterech różnych 5-tej potęgi, sumując się do innej piątej potęgi:

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

Dowód przez kontrprzykład jest dowodem konstruktywnym , w którym eksponowany jest obiekt obalający twierdzenie. W przeciwieństwie do tego, niekonstruktywny dowód twierdzenia o niemożliwości będzie postępował, pokazując, że jest logicznie sprzeczny, aby wszystkie możliwe kontrprzykłady były nieważne: co najmniej jeden z elementów na liście możliwych kontrprzykładów musi być w rzeczywistości prawidłowym kontrprzykładem dla przypuszczenia o niemożliwości . Na przykład przypuszczenie, że niemożliwe jest, aby siła irracjonalna podniesiona do potęgi irracjonalnej była racjonalna, zostało obalone , pokazując, że jeden z dwóch możliwych kontrprzykładów musi być słusznym kontrprzykładem, nie pokazując, który to jest.

Istnienie liczb niewymiernych: dowód pitagorejczyków

Dowód Pitagorasa (lub, co bardziej prawdopodobne, jednego z jego uczniów) około 500  p.n.e. wywarł głęboki wpływ na matematykę. Wynika z niego, że pierwiastek kwadratowy z 2 nie może być wyrażony jako stosunek dwóch liczb całkowitych (liczby liczące). Dowód podzielił „liczby” na dwa nienakładające się kolekcje — liczby wymierne i niewymierne . Ten rozwidlenie był używany przez Cantora w jego przekątnej metody , która z kolei została wykorzystana przez Turinga w jego dowód, że Entscheidungsproblem The Problem decyzja o Hilbert , jest nierozstrzygalny.

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

—  Heath,

Następnie pojawiły się dowody dla różnych pierwiastków kwadratowych liczb pierwszych do 17.

Jest słynny fragment Plato „s Theaetetus , w którym stwierdza się, że Teodorus (nauczyciel Platona) udowodnił irracjonalność

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

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

Obecnie istnieje bardziej ogólny dowód, że:

M p korzenia liczba całkowita N jest irracjonalna, o ile dotyczy to m do potęgi liczby całkowitej n ”.

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

Niemożliwe konstrukcje poszukiwane przez starożytnych Greków

Trzy słynne pytania greckiej geometrii dotyczyły tego, jak:

1. ... z kompasem i liniałem do trisekcji pod dowolnym kątem ,
2. skonstruować sześcian o objętości dwukrotnie większej od objętości danego sześcianu
3. skonstruować kwadrat o powierzchni równej powierzchni danego okręgu.

Przez ponad 2000 lat podejmowano nieudane 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 skonstruowanie wielokąta równobocznego o określonej liczbie n boków, poza podstawowymi przypadkami n  = 3, 4, 5, które umieli skonstruować.

Wszystko to są problemy w konstrukcji euklidesowej , a konstrukcje euklidesowe mogą być wykonane tylko wtedy, gdy dotyczą tylko liczb euklidesowych (z definicji tych ostatnich) (Hardy i Wright s. 159). Liczby niewymierne mogą być euklidesowe. Dobrym przykładem jest liczba niewymierna pierwiastek kwadratowy z 2. Jest to po prostu długość przeciwprostokątnej trójkąta prostokątnego z nogami o długości jednej jednostki i może być skonstruowana za pomocą liniału i cyrkla. Ale setki lat po Euklidesie udowodniono, że liczby euklidesowe nie mogą obejmować żadnych operacji poza dodawaniem, odejmowaniem, mnożeniem, dzieleniem i wyciąganiem pierwiastków kwadratowych.

Trisekcja kąta i podwojenie sześcianu

Zarówno pokrojenie kąta ogólnego, jak i podwojenie sześcianu, wymaga wzięcia pierwiastków sześciennych , które nie są liczbami konstruowanymi przez kompas i linijkę.

Kwadratura koła

${\displaystyle \pi}$nie jest liczbą euklidesową ... i dlatego nie można skonstruować metodami euklidesowymi długości równej obwodowi okręgu o jednostkowej średnicy

Istnieje dowód na to, że każda liczba euklidesowa jest liczbą algebraiczną — liczbą, która jest rozwiązaniem pewnego równania wielomianowego . Dlatego, ponieważ w 1882 roku udowodniono, że jest liczbą przestępną, a zatem z definicji nie jest liczbą algebraiczną, nie jest liczbą euklidesową. Stąd konstrukcja długości z okręgu jednostkowego jest niemożliwa, a okręg nie może być podniesiony do kwadratu. ${\displaystyle \pi}$${\displaystyle \pi}$

Konstruowanie równobocznego n -gon

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

Równoległy aksjomat Euklidesa

Nagel i Newman uważają, że pytanie podniesione przez równoległy postulat jest „...być może najbardziej znaczącym osiągnięciem w jego dalekosiężnych skutkach na późniejszą historię matematyczną” (s. 9).

Pytanie brzmi: czy aksjomat, że dwie równoległe linie „...nie spotkają się nawet 'w nieskończoności'” (przypis, tamże) można wyprowadzić z innych aksjomatów geometrii Euklidesa? Dopiero prace w XIX wieku autorstwa „…Gassa, Bolyai, Lobachevsky’ego i Riemanna wykazały niemożność wydedukowania paralelnego aksjomatu z innych. Wynik ten miał największe znaczenie intelektualne. …a można podać dowód na niemożność udowodnienia pewnych twierdzeń [w tym przypadku postulat równoległy] w ramach danego systemu [w tym przypadku pierwsze cztery postulaty Euklidesa]”. (str. 10)

Wielkie Twierdzenie Fermata

Wielkie Twierdzenie Fermata zostało wymyślone przez Pierre'a de Fermata w XVII wieku, stwierdza niemożność znalezienia rozwiązań w dodatnich liczbach całkowitych dla równania z . Sam Fermat dał dowód na  przypadek n = 4, używając swojej techniki nieskończonego zniżania , a następnie udowodniono inne szczególne przypadki, ale ogólny przypadek został udowodniony dopiero w 1994 r. przez Andrew Wilesa . ${\ Displaystyle x ^ {n} + y ^ {n} = z ^ {n}}$${\displaystyle n>2}$

Paradoks Richarda

Ten głęboki paradoks przedstawiony przez Julesa Richarda w 1905 r . miał wpływ na prace Kurta Gödla (por. Nagel i Newman s. 60 n.) i Alana Turinga. Zwięzła definicja znajduje się w Principia Mathematica :

Paradoks Richarda… jest następujący. Rozważ wszystkie ułamki dziesiętne, które można zdefiniować za pomocą skończonej liczby słów [„słowa” są symbolami; pogrubienie dodane dla podkreślenia] ; niech E będzie klasą takich liczb dziesiętnych. Wtedy E ma [nieskończoną liczbę] wyrazów; stąd jego człony mogą być uporządkowane jako 1., 2., 3., ... Niech X będzie liczbą określoną następująco [Whitehead i Russell stosują teraz metodę przekątną Cantora] . Jeśli n-tą cyfrą w n- tym miejscu po przecinku jest p , niech n- ta cyfra w X będzie p  + 1 (lub 0, jeśli p  = 9). Wtedy X różni się od wszystkich elementów E , ponieważ bez względu na skończoną wartość n , n- ta cyfra w X jest różna od n- tej cyfry n- tej liczby dziesiętnych składających się na E , a zatem X jest różni się od n-tego miejsca po przecinku. Niemniej jednak zdefiniowaliśmy X w skończonej liczbie słów [tj. ta sama definicja „słowa” powyżej.] i dlatego X powinien być członkiem E . Zatem X zarówno jest, jak i nie jest członkiem E.${\displaystyle \aleph_{0}}$

—  Principia Mathematica , 2. wydanie 1927, s. 61

Kurt Gödel uznał swój dowód za „analogię” paradoksu Richarda, który nazwał „ antynomią Richarda ”. Zobacz więcej poniżej o dowodzie Gödla.

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

Czy to twierdzenie można udowodnić na podstawie tych aksjomatów? Dowód Gödla

Cytując Nagela i Newmana (s. 68), „Praca Gödla jest trudna. Czterdzieści sześć wstępnych definicji, wraz z kilkoma ważnymi wstępnymi twierdzeniami, musi zostać opanowane przed osiągnięciem głównych wyników” (s. 68). W rzeczywistości Nagel i Newman wymagali 67-stronicowego wstępu do swojej prezentacji dowodu. Ale jeśli czytelnik czuje się na tyle silny, by zająć się tym artykułem, Martin Davis zauważa, że ​​„Ten niezwykły artykuł jest nie tylko intelektualnym punktem zwrotnym, ale jest napisany z jasnością i wigorem, które sprawiają, że czytanie go jest przyjemnością” (Davis w Nierozstrzygalnym, s. 4). Zaleca się, aby większość czytelników najpierw zobaczyła Nagela i Newmana.

Co więc udowodnił Gödel? W jego własnych słowach:

„Rozsądne jest… przypuszczenie, że… aksjomaty [z Principia Mathematica i Peano ] są… wystarczające do rozstrzygnięcia wszystkich pytań matematycznych, które można formalnie wyrazić w danych systemach. 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 Nierozstrzygalności, s. 4).

Gödel porównał swój dowód z „antynomią Richarda” („ antynomia ” jest sprzecznością lub paradoksem; więcej patrz paradoks Richarda ):

„Analogia tego wyniku z antynomią Richarda jest natychmiast oczywista; istnieje również bliski związek [14] z paradoksem kłamcy (przypis 14 Gödla: Każda antynomia epistemologiczna może być użyta do podobnego dowodu nierozstrzygalności). przed nami twierdzenie, które stwierdza własną niedowodliwość [15].(Jego przypis 15: Wbrew pozorom takie twierdzenie nie jest kołowe, gdyż na początek stwierdza niedowodliwość całkiem określonej formuły)” (Gödel w Nierozstrzygalności). , s. 9).

Czy ta maszyna obliczeniowa zablokuje się w „koło”? Pierwszy dowód Turinga

• Entscheidungsproblem The problem decyzyjny , został po raz pierwszy odpowiedział Kościoła w kwietniu 1935 i wywłaszczony Turinga przez ponad rok, jak papier Turinga został przyjęty do druku w maju 1936 roku (otrzymał również do publikacji w 1936 roku, w październiku, najpóźniej Turing's-było krótki artykuł autorstwa Emila Posta, który omawiał redukcję algorytmu do prostej, podobnej do maszyny „metody”, bardzo podobnej do modelu maszyny liczącej Turinga (szczegóły w maszynie Post-Turinga ).
• Dowód Turinga jest trudny ze względu na liczbę wymaganych definicji i jego subtelną naturę. Zobacz maszynę Turinga i dowód Turinga szczegóły.
• Pierwszy dowód Turinga (z trzech) jest zgodny ze schematem paradoksu Richarda: maszyna licząca Turinga jest algorytmem reprezentowanym przez ciąg siedmiu liter w „maszynie obliczeniowej”. Jego „obliczenia” polegają na przetestowaniu wszystkich maszyn liczących (włącznie ze sobą) pod kątem „kołków” i utworzeniu liczby ukośnej z obliczeń maszyn obliczeniowych niekołowych lub „udanych”. Robi to, zaczynając w kolejności od 1, przekształcając liczby (podstawa 8) na ciągi siedmiu liter do przetestowania. Kiedy dociera do własnego numeru, tworzy własny ciąg liter. Decyduje, że jest to ciąg liter udanej maszyny, ale kiedy próbuje wykonać obliczenia tej maszyny ( swojej ), blokuje się w kółko 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).

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

1. Kwiecień 1935: Proof of Alonzo Church („Nierozwiązywalny problem elementarnej teorii liczb”). Jego dowodem było „...zaproponowanie definicji efektywnej obliczalności... i wykazanie na przykładzie, że nie każdy problem tej klasy jest rozwiązywalny” (Nierozstrzygalny, s. 90)).
2. 1946: Problem z korespondencją pocztową (por. Hopcroft i Ullman s. 193ff, s. 407 dla odniesienia)
3. Kwiecień 1947: Dowód Emila Posta ( rekursywna nierozwiązywalność problemu z czw.) (nierozstrzygalne s. 293). Od tego czasu stało się to znane jako „Problem ze słowem Thue” lub „Tue's Word Problem” ( Axel Thue zaproponował ten problem w artykule z 1914 r. (por. Odnośniki do artykułu Posta w Undecidable, s. 303)).
4. Twierdzenie Rice'a : uogólnione sformułowanie drugiego twierdzenia Turinga (por. Hopcroft i Ullman s. 185ff)
5. Twierdzenie Greibacha : nierozstrzygalność w teorii języka (por. Hopcroft i Ullman s. 205 i odniesienie na s. 401 ibid: Greibach [1963] „The undecyliability of the ambiguity problem for minimal lineal grammars”, 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.)
6. Pytania dotyczące płytek Penrose'a
7. Pytanie o rozwiązania równań diofantycznych i wynikowa odpowiedź w twierdzeniu MRDP; patrz wpis poniżej.

Czy ten ciąg można skompresować? Dowód Chaitina

Ekspozycja odpowiednia dla nie-specjalistów patrz Beltrami s. 108n. 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 zakończenia pracy ” Gregory'ego Chaitina . Starsze leczenie Davisa podchodzi do pytania z punktu widzenia maszyny Turinga . Chaitin napisał wiele książek o swoich przedsięwzięciach i wynikających z nich konsekwencjach filozoficznych i matematycznych.

Ciąg nazywamy (algorytmicznie) losowym, jeśli nie można go wytworzyć z żadnego krótszego programu komputerowego. Chociaż większość ciągów jest losowa , nie można tego udowodnić, z wyjątkiem skończonych wielu krótkich:

„Parafrazą wyniku Chaitina jest to, że nie może być formalnego dowodu, że wystarczająco długi ciąg jest losowy…” (Beltrami s. 109)

Beltrami zauważa, że ​​„dowód Chaitina jest powiązany z paradoksem postawionym przez bibliotekarza z Oxfordu G. Berry'ego na początku XX wieku, który prosi o 'najmniejszą dodatnią liczbę całkowitą, której nie można zdefiniować w zdaniu angielskim zawierającym mniej niż 1000 znaków'. Najwyraźniej najkrótsza definicja tej liczby musi mieć co najmniej 1000 znaków, jednak zdanie w cudzysłowie, które samo jest definicją domniemanej liczby, ma mniej niż 1000 znaków! (Beltrami, s. 108)

Czy to równanie diofantyczne ma rozwiązanie całkowite? Dziesiąty problem Hilberta

Pytanie „Czy dowolne „równanie diofantyczne” ma rozwiązanie całkowite?” jest nierozstrzygalny. Oznacza to, że nie można odpowiedzieć na pytanie we wszystkich przypadkach.

Franzén wprowadza dziesiąty problem Hilberta i twierdzenie MRDP ( twierdzenie Matiyasevicha-Robinsona-Davisa-Putnama), które stwierdza, że ​​„nie istnieje algorytm, który mógłby zdecydować, czy równanie diofantyczne ma w ogóle jakieś rozwiązanie”. MRDP używa dowodu nierozstrzygalności Turinga: „…zbiór rozwiązalnych równań diofantycznych jest przykładem zbioru przeliczalnego, ale nierozstrzygalnego, a zbiór nierozstrzygalnych równań diofantycznych nie jest przeliczalny” (s. 71).

W naukach społecznych

W naukach politycznych , Arrow twierdzenie niemożność stwierdza, że niemożliwe jest, aby opracować system głosowania , który spełnia zestaw pięciu konkretnych aksjomatów. Twierdzenie to jest udowodnione przez pokazanie, że cztery aksjomaty razem implikują przeciwieństwo piątego.

W ekonomii , Holmström to twierdzenie jest twierdzenie niemożność udowodnienia, że żaden system motywacyjny dla zespołu agentów może zaspokoić 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 uznawane za udowodnione do tego stopnia, że ​​są niepodważalne. Podstawą tej silnej akceptacji jest połączenie obszernych dowodów na to, że coś się nie dzieje, 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.

Dwoma przykładami powszechnie akceptowanych niemożliwości w fizyce są perpetuum mobile , które łamią prawo zachowania energii oraz przekraczanie prędkości światła , co łamie implikacje szczególnej teorii względności . Innym jest zasada nieoznaczoności w mechanice kwantowej , która twierdzi niemożliwość jednocześnie wiedząc jednocześnie położenia i pędu cząstki. Również twierdzenie Bella : żadna fizyczna teoria lokalnych ukrytych zmiennych nigdy nie jest w stanie odtworzyć wszystkich przewidywań mechaniki kwantowej.

Chociaż twierdzenie o niemożliwości w naukach przyrodniczych nigdy nie może być absolutnie udowodnione, można je obalić przez obserwację jednego kontrprzykładu . Taki kontrprzykład wymagałby ponownego zbadania założeń leżących u podstaw teorii, która implikowała niemożliwość.

Zobacz też

• Lista nierozwiązanych problemów matematycznych  – Nadal poszukuje się rozwiązań tych problemów. Wiadomo natomiast, że powyższe problemy nie mają rozwiązania.
• Twierdzenie o zakazie , odpowiadające pojęcie fizyczne.

Uwagi i referencje

Bibliografia