Konstruktywny dowód - Constructive proof

W matematyce , o konstruktywny dowód to metoda dowodu , że wykaże istnienie matematycznego obiektu poprzez tworzenie lub dostarczenie sposobu tworzenia obiektu. Kontrastuje to z niekonstruktywnym dowodem (znanym również jako dowód istnienia lub twierdzenie o czystym istnieniu ), który dowodzi istnienia określonego rodzaju przedmiotu bez podania przykładu. Aby uniknąć pomyłki z silniejszą koncepcją, która następuje, taki konstruktywny dowód jest czasami nazywany skutecznym dowodem .

Konstruktywny dowód może również odnosić się do silniejszego pojęcia dowodu, który jest ważny w konstruktywnych matematyki . Konstruktywizm to filozofia matematyczna, która odrzuca wszystkie metody dowodowe, które wiążą się z istnieniem obiektów, które nie zostały wyraźnie zbudowane. Wyklucza to w szczególności użycie prawa wyłączonego środka , aksjomatu nieskończoności i aksjomatu wyboru oraz indukuje inne znaczenie dla niektórych terminologii (na przykład termin „lub” ma silniejsze znaczenie w konstruktywnym matematyka niż w klasycznej).

Niektóre niekonstruktywne dowody pokazują, że jeśli pewne zdanie jest fałszywe, powstaje sprzeczność; w konsekwencji zdanie musi być prawdziwe ( dowód przez sprzeczność ). Jednak zasada eksplozji ( ex falso quodlibet ) została przyjęta w niektórych odmianach matematyki konstruktywnej, w tym w intuicjonizmie .

Konstruktywne dowody mogą być postrzegane jako definiujących certyfikowanych matematycznych algorytmów : idea ta jest badane w interpretacji Brouwer-Heytinga-Kołmogorowa o konstruktywną logiką The korespondencja Curry-Howard między dowodami i programów, a także takich układów logicznych jak Per Martin-Löf „s typu intuicjonistycznej teoria i Thierry Coquand i Gérard Huet „s rachunek konstrukcji .

Przykład historyczny

Do końca XIX wieku wszystkie dowody matematyczne były zasadniczo konstruktywne. Pierwsze konstrukcje niekonstruktywne pojawiły się wraz z teorią zbiorów nieskończonych Georga Cantora i formalną definicją liczb rzeczywistych .

Pierwszym zastosowaniem niekonstruktywnych dowodów do rozwiązywania wcześniej rozważanych problemów wydaje się być podstawowe twierdzenie Hilberta Nullstellensatza i Hilberta . Z filozoficznego punktu widzenia ta pierwsza jest szczególnie interesująca, gdyż zakłada istnienie dobrze określonego przedmiotu.

Nullstellensatz można określić w następujący sposób: Jeśli są wielomiany w n nieokreślonych o złożonych współczynnikach, które nie mają wspólnych zer zespolonych , to istnieją wielomiany takie, że ${\ displaystyle f_ {1}, \ ldots, f_ {k}}$${\ displaystyle g_ {1}, \ ldots, g_ {k}}$

${\ displaystyle f_ {1} g_ {1} + \ ldots + f_ {k} g_ {k} = 1.}$

Takie niekonstruktywne twierdzenie o istnieniu było takim zaskoczeniem dla ówczesnych matematyków, że jeden z nich, Paul Gordan , napisał: „to nie jest matematyka, to teologia ”.

Dwadzieścia pięć lat później Grete Hermann przedstawiła algorytm obliczeniowy, który nie jest konstruktywnym dowodem w mocnym tego słowa znaczeniu, ponieważ wykorzystała wynik Hilberta. Udowodniła, że ​​jeśli istnieją, można je znaleźć ze stopniami niższymi niż . ${\ displaystyle g_ {1}, \ ldots, g_ {k},}$${\ displaystyle g_ {1}, \ ldots, g_ {k}}$${\ Displaystyle 2 ^ {2 ^ {n}}}$

Zapewnia to algorytm, ponieważ problem sprowadza się do rozwiązania układu równań liniowych , biorąc pod uwagę skończoną liczbę współczynników ${\ displaystyle g_ {i}.}$

Przykłady

Dowody niekonstruktywne

Najpierw rozważ twierdzenie, że istnieje nieskończoność liczb pierwszych . Euklides „s dowód jest konstruktywne. Jednak powszechny sposób uproszczenia dowodu Euklidesa zakłada, że ​​w przeciwieństwie do twierdzenia zawartego w twierdzeniu jest ich tylko skończona liczba, w którym to przypadku jest największa, oznaczona n . Następnie rozważ liczbę n ! + 1 (1 + iloczyn pierwszych n liczb). Albo ta liczba jest liczbą pierwszą, albo wszystkie jej czynniki pierwsze są większe niż n . Bez ustalenia konkretnej liczby pierwszej dowodzi to, że istnieje jedna, która jest większa od n , wbrew pierwotnemu postulatowi.

Rozważmy teraz twierdzenie „istnieją liczby niewymierne i takie, które są racjonalne ”. Twierdzenie to można udowodnić, używając zarówno dowodu konstruktywnego, jak i dowodu niekonstruktywnego. ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a ^ {b}}$

Poniższy dowód z 1953 roku autorstwa Dova Jardena był szeroko stosowany jako przykład niekonstruktywnego dowodu od co najmniej 1970 roku:

CURIOSA
339. Prosty dowód, że potęga liczby nieracjonalnej w wykładniku irracjonalnym może być racjonalna. jest racjonalne lub irracjonalne. Jeśli jest racjonalne, nasze stwierdzenie jest udowodnione. Jeśli jest irracjonalne, potwierdza nasze stwierdzenie.      Dov Jarden Jerozolima
${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ displaystyle ({\ sqrt {2}} ^ {\ sqrt {2}}) ^ {\ sqrt {2}} = 2}$

Bardziej szczegółowo:

• Przypomnij sobie, że jest to irracjonalne , a 2 to racjonalne. Rozważ liczbę . Albo jest to racjonalne, albo irracjonalne. ${\ displaystyle {\ sqrt {2}}}$ ${\ displaystyle q = {\ sqrt {2}} ^ {\ sqrt {2}}}$
• Jeśli jest racjonalne, to twierdzenie jest prawdziwe, zarówno z bytem, ​​jak iz bytem . ${\ displaystyle q}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle {\ sqrt {2}}}$
• Jeśli jest irracjonalne, to twierdzenie jest prawdziwe, z bytem i bytem , ponieważ ${\ displaystyle q}$${\ displaystyle a}$${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ displaystyle b}$${\ displaystyle {\ sqrt {2}}}$

${\ displaystyle \ left ({\ sqrt {2}} ^ {\ sqrt {2}} \ right) ^ {\ sqrt {2}} = {\ sqrt {2}} ^ {({\ sqrt {2}} \ cdot {\ sqrt {2}})} = {\ sqrt {2}} ^ {2} = 2.}$

W istocie dowód ten nie jest konstruktywny, ponieważ opiera się na stwierdzeniu „Albo q jest racjonalne, albo nieracjonalne” - na przykładzie prawa wyłączonego środka , które nie jest ważne w ramach dowodu konstruktywnego. Dowód niekonstruktywny nie tworzy przykładu a i b ; daje jedynie pewną liczbę możliwości (w tym przypadku dwie wzajemnie wykluczające się możliwości) i pokazuje, że jedna z nich - ale nie pokazuje, która z nich - musi dać pożądany przykład.

Jak się okazuje, jest irracjonalne ze względu na twierdzenie Gelfonda – Schneidera , ale fakt ten nie ma znaczenia dla poprawności niekonstruktywnego dowodu. ${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$

Konstruktywne dowody

Konstruktywne dowód wyżej twierdzenia nieracjonalne uprawnień niewymiernych dałoby rzeczywisty przykład, takich jak:

${\ Displaystyle a = {\ sqrt {2}} \ ,, \ quad b = \ log _ {2} 9 \ ,, \ quad a ^ {b} = 3 \ ,.}$

Pierwiastek kwadratowy z 2 jest irracjonalne, a 3 jest racjonalne. jest również nieracjonalne: gdyby było równe , to według własności logarytmów 9 ⁿ byłoby równe 2 ^m , ale to pierwsze jest nieparzyste, a drugie jest parzyste. ${\ displaystyle \ log _ {2} 9}$${\ Displaystyle m \ ponad n}$

Bardziej konkretnym przykładem jest twierdzenie o grafie molowym . Konsekwencją tego twierdzenia jest to, że wykres można narysować na torusie wtedy i tylko wtedy, gdy żaden z jego nieletnich nie należy do pewnego skończonego zbioru „ zabronionych nieletnich ”. Jednak dowód na istnienie tego skończonego zbioru nie jest konstruktywny, a zabronione nieletnie nie są w rzeczywistości określone. Nadal są nieznani.

Brouwerowskie kontrprzykłady

W matematyce konstruktywnej twierdzenie można obalić, podając kontrprzykład , jak w matematyce klasycznej. Można jednak również podać kontrprzykład Brouwerian, aby wykazać, że stwierdzenie nie jest konstruktywne. Ten rodzaj kontrprzykładu pokazuje, że stwierdzenie implikuje pewną zasadę, o której wiadomo, że nie jest konstruktywna. Jeśli można konstruktywnie udowodnić, że stwierdzenie implikuje jakąś zasadę, której nie można w konstruktywny sposób udowodnić, to samo stwierdzenie nie może być konstruktywnie udowodnione.

Na przykład, można wykazać, że określone stwierdzenie implikuje prawo wyłączonego środka. Przykładem tego typu kontrprzykładu Brouwerowskiego jest twierdzenie Diaconescu , z którego wynika, że ​​pełny aksjomat wyboru nie jest konstruktywny w systemach konstruktywnej teorii mnogości , ponieważ aksjomat wyboru implikuje prawo wyłączonego środka w takich systemach. Dziedzina konstruktywnej matematyki odwrotnej rozwija tę ideę dalej, klasyfikując różne zasady pod względem „niekonstruktywności”, pokazując, że są one równoważne różnym fragmentom prawa wyłączonego środka.

Brouwer podał również „słabe” kontrprzykłady. Takie kontrprzykłady nie obalają jednak stwierdzenia; pokazują tylko, że obecnie nie jest znany żaden konstruktywny dowód tego stwierdzenia. Jeden słaby kontrprzykład rozpoczyna się od podjęcia nierozwiązanego problemu matematycznego, takiego jak hipoteza Goldbacha , w której pyta się, czy każda parzysta liczba naturalna większa niż 4 jest sumą dwóch liczb pierwszych. Zdefiniuj ciąg a ( n ) liczb wymiernych w następujący sposób:

${\ Displaystyle a (n) = {\ rozpocząć {przypadków} (1/2) ^ {n} i {\ mbox {jeśli każda parzysta liczba naturalna w przedziale}} [4, n] {\ mbox {to suma dwóch liczb pierwszych}}, \\ (1/2) ^ {k} & {\ mbox {if}} k {\ mbox {jest najmniejszą parzystą liczbą naturalną w przedziale}} [4, n] {\ mbox { która nie jest sumą dwóch liczb pierwszych}} \ end {przypadki}}}$

Dla każdego n wartość a ( n ) można określić za pomocą wyszukiwania wyczerpującego, a więc a jest konstruktywnie dobrze zdefiniowaną sekwencją. Co więcej, ponieważ a jest ciągiem Cauchy'ego ze stałą szybkością zbieżności, a zbiega się do pewnej liczby rzeczywistej α, zgodnie ze zwykłym traktowaniem liczb rzeczywistych w matematyce konstruktywnej.

Można konstruktywnie udowodnić kilka faktów dotyczących liczby rzeczywistej α. Jednak opierając się na innym znaczeniu słów w matematyce konstruktywnej, jeśli istnieje konstruktywny dowód, że „α = 0 lub α ≠ 0”, oznaczałoby to, że istnieje konstruktywny dowód hipotezy Goldbacha (w pierwszym przypadku) lub konstruktywny dowód, że hipoteza Goldbacha jest fałszywa (w tym drugim przypadku). Ponieważ żaden taki dowód nie jest znany, cytowane stwierdzenie nie może również zawierać znanego konstruktywnego dowodu. Jest jednak całkowicie możliwe, że hipoteza Goldbacha może mieć konstruktywny dowód (którego nie wiemy obecnie), w którym to przypadku przytoczone stwierdzenie miałoby również dowód konstruktywny, choć obecnie nieznany. Głównym praktycznym zastosowaniem słabych kontrprzykładów jest określenie „twardości” problemu. Na przykład, właśnie pokazany kontrprzykład pokazuje, że cytowane stwierdzenie jest „co najmniej tak trudne do udowodnienia”, jak przypuszczenie Goldbacha. Tego rodzaju słabe kontrprzykłady są często związane z ograniczoną zasadą wszechwiedzy .

Zobacz też

• Konstruktywizm (filozofia matematyki)
• Errett Bishop - autor książki „Foundations of Constructive Analysis”.
• Twierdzenie o istnieniu § Wyniki „czystego” istnienia
• Dowody na istnienie niekonstruktywnych algorytmów
• Metoda probabilistyczna

Bibliografia

Dalsza lektura

Zewnętrzne linki

• Słabe kontrprzykłady : Mark van Atten, Stanford Encyclopedia of Philosophy