Konstrukční důkaz - Constructive proof

V matematice je konstruktivní důkaz metoda důkazu, která demonstruje existenci matematického objektu vytvořením nebo poskytnutím metody pro vytvoření objektu. To je v kontrastu s nekonstruktivním důkazem (také známým jako důkaz existence nebo věta o čisté existenci ), který bez uvedení příkladu dokazuje existenci určitého druhu objektu. Aby se zabránilo záměně se silnějším konceptem, který následuje, takový konstruktivní důkaz se někdy nazývá efektivní důkaz .

Konstruktivní důkaz může také se odkazovat na silnější koncept dokladu, který je platný v konstruktivní matematiky . Konstruktivismus je matematická filozofie, která odmítá všechny důkazní metody, které zahrnují existenci objektů, které nejsou výslovně vytvořeny. To vylučuje zejména použití zákona vyloučeného středu , axiomu nekonečna a axiomu volby a vyvolává jiný význam pro určitou terminologii (například výraz „nebo“ má silnější význam v konstruktivním matematika než v klasické).

Některé nekonstruktivní důkazy ukazují, že pokud je určitá věta nepravdivá, následuje rozpor; následně musí být tvrzení pravdivé ( důkaz rozporem ). Nicméně princip exploze ( ex Falso Quodlibet ) byla přijata v některých odrůd konstruktivní matematiky, včetně intuicionismu .

Konstruktivní důkazy lze chápat jako definující certifikované matematické algoritmy : tato myšlenka je prozkoumána v interpretaci Brouwer-Heyting-Kolmogorov z konstruktivní logiky je Curry-Howard korespondence mezi důkazy a programy a takových logických systémů jako je Per Martin-Löf ‚s intuitionistic typu teorie a Thierry Coquand a Gérard Huet ‚s kalkul staveb .

Historický příklad

Až do konce 19. století byly všechny matematické důkazy v zásadě konstruktivní. První nekonstruktivní konstrukce se objevily s teorií nekonečných množin Georga Cantora a formální definicí reálných čísel .

Prvním použitím nekonstruktivních důkazů pro řešení dříve uvažovaných problémů se zdá být Hilbertova Nullstellensatz a Hilbertova základová věta . Z filozofického hlediska je první zajímavý, protože naznačuje existenci dobře specifikovaného objektu.

Nullstellensatz lze konstatovat následovně: Pokud jsou polynomy v n neurčitelné se složitými koeficienty, které nemají společné komplexní nuly , pak existují polynomy takové, že

Taková nekonstruktivní věta o existenci byla pro vtedajší matematiky tak překvapením, že jeden z nich, Paul Gordan , napsal: „toto není matematika, je to teologie “.

O dvacet pět let později poskytla Grete Hermannová algoritmus pro výpočet, který není konstruktivním důkazem v silném smyslu, protože použila Hilbertův výsledek. Dokázala, že pokud existují, lze je najít s nižšími stupni .

To poskytuje algoritmus, protože problém se redukuje na řešení soustavy lineárních rovnic tím , že se jako neznámý považuje konečný počet koeficientů

Příklady

Nekonstruktivní důkazy

Nejprve zvažte vetu, že existuje nekonečno prvočísel . Euclid ‚s důkazem je konstruktivní. Běžný způsob zjednodušení Euklidova důkazu však předpokládá, že na rozdíl od tvrzení ve větě je jich jen konečný počet, v takovém případě je největší, označený n . Pak zvažte číslo n ! + 1 (1 + součin prvních n čísel). Buď je toto číslo prvočíslo, nebo všechny jeho prvočíselné faktory jsou větší než n . Bez stanovení konkrétního prvočísla to dokazuje, že existuje jedno větší než n , na rozdíl od původního postulátu.

Nyní zvažte teorém „existují iracionální čísla a taková, která jsou racionální “. Tuto větu lze dokázat pomocí konstruktivního důkazu i nekonstruktivního důkazu.

Následující důkaz 1953 Dov Jarden byl široce používán jako příklad nekonstruktivního důkazu přinejmenším od roku 1970:

CURIOSA
339. Jednoduchý důkaz, že síla iracionálního čísla pro iracionálního exponenta může být racionální. je buď racionální, nebo iracionální. Pokud je to racionální, naše tvrzení je prokázáno. Pokud je to iracionální, dokazuje to naše tvrzení.      Dov Jarden Jeruzalém

Trochu podrobněji:

  • Připomeňme, že je to iracionální , a 2 je racionální. Zvažte počet . Buď je to racionální, nebo je to iracionální.
  • Pokud je racionální, pak věta je pravdivá, se i oba bytí .
  • Pokud je iracionální, pak věta je pravdivá, s bytím a bytím od té doby

Tento důkaz není ve své podstatě konstruktivní, protože se opírá o tvrzení „Buď q je racionální, nebo je iracionální“ - příklad zákona vyloučeného středu , který v konstruktivním důkazu neplatí. Nekonstruktivní důkaz nevytváří příklad a a b ; pouze poskytuje řadu možností (v tomto případě dvě vzájemně se vylučující možnosti) a ukazuje, že jedna z nich - ale neukazuje, která z nich - musí přinést požadovaný příklad.

Jak se ukázalo, je iracionální z důvodu Gelfond-Schneiderovy věty , ale tato skutečnost je pro správnost nekonstruktivního důkazu irelevantní.

Konstruktivní důkazy

Konstruktivní důkaz výše věty o iracionálních sil irrationals by daly skutečný příklad, jako například:

Druhá odmocnina 2 je iracionální a 3 je racionální. je také iracionální: pokud by se rovnalo , pak by podle vlastností logaritmů bylo 9 n rovno 2 m , ale první je lichý a druhý sudý.

Podstatnějším příkladem je věta o grafu . Důsledkem této věty je, že na torus lze nakreslit graf pouze tehdy, pokud žádný z jeho nezletilých nepatří k určité konečné sadě „ zakázaných nezletilých “. Důkaz o existenci této konečné sady však není konstruktivní a zakázané nezletilé osoby nejsou ve skutečnosti specifikovány. Stále nejsou známy.

Brouwerovské protiklady

V konstruktivní matematice může být tvrzení vyvráceno poskytnutím protipříkladu , jako v klasické matematice. Je však také možné dát Brouwerianský protiklad, který ukazuje, že tvrzení je nekonstruktivní. Tento druh protipříkladu ukazuje, že tvrzení implikuje nějaký princip, o kterém je známo, že je nekonstruktivní. Pokud lze konstruktivně dokázat, že tvrzení implikuje nějaký princip, který není konstruktivně dokázatelný, pak nemůže být konstruktivně prokazatelné ani samotné tvrzení.

Například může být ukázáno, že určité tvrzení implikuje zákon vyloučeného prostředku. Příkladem Brouwerianova protikladu tohoto typu je Diaconescova věta , která ukazuje, že plný axiom výběru je v systémech teorie konstruktivní množiny nekonstruktivní , protože v těchto systémech implikuje axiom volby. Pole konstruktivní reverzní matematiky rozvíjí tuto myšlenku dále klasifikací různých principů, pokud jde o to, „jak jsou nekonstruktivní“, tím, že ukazuje, že jsou ekvivalentní různým fragmentům zákona vyloučeného středu.

Brouwer také poskytl „slabé“ protiklady. Takové protipříklady však tvrzení nevyvracejí; pouze ukazují, že v současné době není znám žádný konstruktivní důkaz tvrzení. Jeden slabý protiklad začíná tím, že vezmeme nějaký nevyřešený problém matematiky, jako je Goldbachova domněnka , která se ptá, zda každé sudé přirozené číslo větší než 4 je součtem dvou prvočísel. Definujte posloupnost a ( n ) racionálních čísel takto:

Pro každé n lze hodnotu a ( n ) určit vyčerpávajícím hledáním, a a je tedy konstruktivně dobře definovaná sekvence. Navíc, protože a je Cauchyova posloupnost s pevnou rychlostí konvergence, a konverguje k nějakému reálnému číslu α, podle obvyklého zacházení s reálnými čísly v konstruktivní matematice.

Několik faktů o reálném počtu α lze dokázat konstruktivně. Avšak na základě odlišného významu slov v konstruktivní matematice, pokud existuje konstruktivní důkaz, že „α = 0 nebo α ≠ 0“, pak by to znamenalo, že existuje konstruktivní důkaz Goldbachovy domněnky (v prvním případě) nebo konstruktivní důkaz, že Goldbachova domněnka je nepravdivá (v druhém případě). Protože žádný takový důkaz není znám, citované prohlášení také nesmí mít známý konstruktivní důkaz. Je však zcela možné, že Goldbachova domněnka může mít konstruktivní důkaz (protože v současné době nevíme, zda ano), v takovém případě by citovaný výrok měl také konstruktivní důkaz, i když v současnosti neznámý. Hlavním praktickým využitím slabých protikladů je identifikace „tvrdosti“ problému. Například právě ukázaný protiklad ukazuje, že citované tvrzení je „přinejmenším stejně těžké dokázat“ jako Goldbachova domněnka. Slabé protiklady tohoto druhu často souvisejí s omezeným principem vševědoucnosti .

Viz také

Reference

Další čtení

externí odkazy