Matematički dokaz

P. Oksi. 29, jedan od najstarijih sačivanih fragmenata Euklidovih Elemenata, udžbenika koji je milenijumija korišten u nastavi tahnika pisanja dokaza. Dijagram uvršten u Knjigu II, Propoziciju 5.

Matematički dokaz, u matematičkom smislu, je logičko-matematički postupak kojim se dokazuje teorema. U njemu se smeju koristiti samo aksiomi i prethodno dokazane teoreme, zajedno sa prihvaćenim pravilima zaključivanja. Aksiomi se mogu tretirati kao uslovi koji moraju biti ispunjeni pre nego što se izjava primeni. Dokazi su primeri iscrpnog deduktivnog rezonovanja ili induktivnog rezovanja i oni se razlikuju od empirijskih argumenata ili neiscrpnog induktivnog rezonovanja (ili „razumnog očekivanje”). Dokaz mora da demonstrira da je iskaz uvek istinit (povremeno putem navođenja svih mogućih slučajeva i pokazivanjem da važi u svim slučajevima), umesto navođenja mnoštva potvrđujućih slučajeva. Nepotvrđeni predlog koji se smatra istinitim hipotezom.

Jedna od metoda dokazivanja teorema je metoda „pretpostavimo suprotno“. U toj metodi, u kojoj se pokušava da dokaže tvrdnja A, pretpostavi se da vredi tvrdnja „ne A“ i traži se kontradikcija (tvrdnja koja je u suprotnosti s već prethodno dokazanim teoremom ili aksiomom). Među drugim načinima se nalazi i izvođenje. Kreće se od pretpostavke teoreme pa se svi uslovi teoreme primene na pojam na koji se teorema odnosi i tvrdnja teoreme se logično-matematički izvede.

Dokazi primenjuju logiku ali obično obuhvataju izvesnu količinu prirodnog jezika koji obično sadrži neke nejasnoće. Zapravo, velika većina dokaza u matematici se može smatrati primenom rigorozne neformalne logike. Čisto formalni dokazi, napisani u simboličkom jeziku umesto prirodnog jezika, se razmatraju u teoriji dokaza. Razlika između formalnih i neformalnih dokaza je dovela do znatnog preispitivanja sadašnje i istorijske matematičke prakse, kvaziempirizma u matematici, i takozvane folklorne matematike (u oba smisla tog pojma). Filozofija matematike se bavi ulogom jezika i logike u dokazima, i matematike kao jezika.

Istorija i etimologija

Vidi još: Istorija logike

Argumenti pouzdanosti korišćenjem heurističkih pomagala kao što su slike i analogije prethodili su strogom matematičkom dokazu. Moguće je da se ideja o demonstriranju zaključaka prvobitno javila u geometrijskom kontekstu, koji je originalno poistovećivan sa „merenjem zemljišta”. Razvoj matematičkog dokaza je prevashodno proizvod starih grčkih matematičara, i jedan od njihovih najvećih dostignuća. Tales iz Mileta (624–546. p. n. e.) i Hipokrat sa Hiosa (c470-410. p. n. e.) su dokazali iste teoreme u geometriji. Eudoks (408–355. p. n. e.) i Teaetetus (417–369. p. n. e.) su formulisali teoreme ali ih nisu dokazali. Aristotel (384–322. p. n. e.) je smatrao da definicija treba da opiše koncept koji se definiše u smislu već poznatih koncepata. Matematičke dokaze je revolucionisali revolucionirao Euklid (300. p. n. e.), koji je uveo aksiomatski metod koji se još uvek koristi, počevši od nedefinisanih termina i aksioma (propozicija vezanih za nedefinisane termine za koje se pretpostavlja da su samoevidnetno istinite od grčkih „aksiosa” sa značenjem „nešto vredno”), i koristio ih je za dokazivanje teorema primenjujući deduktivnu logiku. Njegovu knjigu, Elemente, su čitali svi koji su se smatrali obrazovanim na Zapadu do sredine 20. veka. Osim geometrijskih teorema, kao što je Pitagorina teorema, Elementi takođe pokrivaju teoriju brojeva, uključujući dokaz da je kvadratni koren od dva iracionalan i da postoji beskonačno mnogo prostih brojeva.

Dalji napreci su ostvareni u srednjovekovnoj islamskoj matematici. Dok su raniji grčki dokazi bili uglavnom geometrijske demonstracije, islamski razvoj aritmetike i algebre omogućio je znato generalnije dokaze koji više nisu bili zavisni od geometrije. U 10. veku, irački matematičar Al-Hašimi proizveo opšte dokaze za brojeve (umesto geometrijskih demonstracija) dok je razmatrao množenje, deljenje, itd. za „linije”. On je koristio taj metod da izvede dokaz postojanja iracionalnih brojeva. Induktivni dokaz za aritmetičke sekvence je uveo Al-Karadži u Al-Fakri (1000), koji je on zatim koristio za dokazivanje binomne teoreme i svojstava Paskalovog trougla. Alhazen je razvio metod svođenja na kontradikciju, kao prvi pokušaj dokazivanja Euklidejskog postulata paralelnosti.

Moderna teorija dokaza tretira dokaze kao induktivno definisane strukture podataka. Više nema pretpostavke da su aksiomi u svakom smislu „istiniti”; ovo omogućava postojanje paralelne matematičke teorije izgrađene na alternativnim setovima aksioma (pogledaj aksiomatsku teoriju skupova i neeuklidsku geometriju na primer).

Metodi

Direktan dokaz

Glavni članak: Direktan dokaz

U direktnom dokazu, zaključak se izvodi logičkim kombinovanjem aksioma, definicija, i ranijih teorema. Na primer, direktni dokaz se može koristiti za utvrđivanje da je suma dva parna cela broja uvek parna:

Razmotrimo dva parna cela broja x i y. Pošto su oni parni, oni se mogu napisati kao x = 2a i y = 2b, respektivno, za cele brojeve a i b. Onda je suma x + y = 2a + 2b = 2(a+b). Stoga x+y ima 2 kao faktor i, po definiciji, je parna. Iz toga sledi da je suma bilo koja dva parna cela broja parna.

Ovaj dokaz koristi definiciju parnih celih brojeva, njihovo svojstvo zatvorenosti pri sabiranju i množenju, i distributivnost.

Dokaz matematičkom indukcijom

Glavni članak: Matematička indukcija

Uprkos svog imena, matematička indukcija je metod dedukcije, a nije forma induktivnog rasuđivanja. U dokazu putem matematičke indukcije, pojedinačni „osnovni slučaj” se dokazuje, i dokazano je „pravilo indukcije” kojim se utvrđuje da svaki proizvoljni slučaj implicira sledeći slučaj. Pošto u principu pravilo indukcije može biti primenjeno više puta počevši od dokazanog osnovnog slučaja, proizilazi da su svi (obično beskonačno mnogobrojni) slučajevi dokazivi. Time se izbegava potreba pojedinačnog dokazivanja svakog slučaja. Varijanta matematičke indukcije je dokaz beskonačnog spuštanja, koji se može koristiti na primer za dokazivanje iracionalnosti kvadratnog korena iz dva.

Uobičajena primena dokaza matematičkom indukcijom je dokazivanje da svojstvo za koje se zna da važi za jedan broj važi za sve prirodne brojeve: Neka je N = {1,2,3,4,...} skup prirodnih brojeva, i neka je P(n) matematički izraz koji obuhvata prirodni broj n iz N takav da je

• (i) P(1) istinito, tj., P(n) je istinito za n = 1.
• (ii) P(n+1) je istinito kad je P(n) istinito, tj., ako je P(n) istinito sledi da je P(n+1) istinito.
• Onda je P(n) istinito za sve prirodne brojeve n.

Na primer, indukcijom se može dokazati da su svi pozitivni celi brojevi oblika 2n − 1 neparni. Neka P(n) predstavlja „2n − 1 je neparan”:

(i) Za n = 1, 2n − 1 = 2(1) − 1 = 1, i 1 je neparan, pošto ostavlja ostatak od 1 kad se podeli sa 2. Stoga P(1) je istinito.

(ii) Za svako n, ako je 2n − 1 neparno (P(n)), onda (2n − 1) + 2 isto tako mora biti neparno, pošto dodavanje 2 neparnom broju rezultira u neparnom broju. Ali je (2n − 1) + 2 = 2n + 1 = 2(n+1) − 1, stoga je 2(n+1) − 1 neparan (P(n+1)). Iz P(n) sledi P(n+1).

Stoga 2n − 1 je neparno, za sve pozitivne cele brojeve n.

Kraća fraza „dokaz indukcijom” se obično koristi umesto „dokaz matematičkom indukcijom”.

Dokaz kontrapozicijom

Glavni članak: Kontrapozicija

Kontrapozicionim dokazom se izvodi zaključak „ako je p onda je q” po pretpostavci „ako nije q onda nije p”. Izjava „ako nije q onda nije p” se naziva kontrapozicijom izjave „ako je p onda je q”. Na primer, kontrapozicija se može koristiti za utvrđivanje da za ceo broj $x$, ako je $x^{2}$ je parno, onda je $x$ parno:

Pretpostavimo da $x$ nije paran. Onda je $x$ neparan. Proizvod dva neparna broja je neparan, stoga je $x^{2}=x\cdot x$ neparno. Iz toga sledi da $x$ nije parno. Stoga, ako jeste $x^{2}$ parno, pretpostavka mora biti lažna, tako da $x$ mora biti paran.

Dokaz kontradikcijom

Glavni članak: Svođenje na kontradikciju

U dokazu kontradikcijom (takođe poznatom kao reductio ad absurdum, u prevodu sa latinskog „redukcijom do apsurda”) se pokazuje da ako bi neka izjava bila istinita, došlo bi do logičke kontradikcije, i stoga izjava mora biti neistinita. Poznati primer dokaza kontradikcijom pokazuje da je ${\sqrt {2}}$ iracionalni broj:

Pretpostavimo da je ${\sqrt {2}}$ racionalni broj, tako da je po definiciji ${\sqrt {2}}={a \over b}$, gde su a i b celi brojevi različiti od nule bez zajedničkog faktora. (Ako postoji zajednički faktor, numerator i imenilac trebaju biti podeljeni njime da bi se uklonio, i postupak treba ponavljati dok više ne bude zajedničkog faktora. Po metodi beskonačnog spuštanja, ovaj proces mora imati kraj.) Stoga, $b{\sqrt {2}}=a$. Kvadrirajući obe strane dobija se 2b² = a². Pošto 2 deli levu stranu, 2 isto tako mora deliti desnu stranu (inače bi paran broj bio jednak neparnom broju). Stoga a² je parno, iz čega sledi da a isto tako mora biti parno. Iz tog razloga se može napisati a = 2c, gde je c takođe ceo broj. Zamenom u originalnoj jednačini se dobija 2b² = (2c)² = 4c². Deljenjem obe strane sa 2 dobija se b² = 2c². Ali onda, istim argumentom kao i ranije, 2 deli b², tako da b mora biti paran. Međutim, ako su a i b oba parni, oni imaju zajednički faktor, naime 2. To je u kontradikciji sa početnom pretpostavkom, tako da se mora izvesti zaključak da je ${\sqrt {2}}$ iracionalni broj.

Dokaz konstrukcijom

Glavni članak: Dokaz konstrukcijom

Dokaz konstrukcijom, ili dokaz pomoću primera, je konstrukcija konkretnog primera sa datim svojstvom, da bi se pokazalo da nešto što ima to svojstvo postoji. Na primer, Žozef Lijuvil je dokazao postojanje transcendentnih brojeva konstruisanjem jednog eksplicitnog primera. Ova pristup se isto tako može koristiti pri konstruisanju kontraprimera s ciljem osporavanja predloga da svi elementi imaju određenu osobinu.

Dokaz iscrpljenjem

Glavni članak: Dokaz iscrpljenjem

U dakazu iscrpljivanjem, zaključak se uspostavlja deljenjem u konačan broj slučajeva i dokazivanjem svakog od njih zasebno. Broj slučajeva pokekad može da bude veoma velik. Na primer, prvi dokaz teoreme četiri boje je bio dokaz iscrpljivanjem sa 1.936 slučaja. Ovaj dokaz je bio kontroverzan zato što je većina slučajeva bila proverena pomoću računarskog programa, a ne manuelno. Najkraći poznati dokaz teoreme četiri boje po podacima iz 2011. godine još uvek ima preko 600 slučaja.

Probabilistički dokaz

Glavni članak: Probabilistički metod

Probabilistički dokaz je onaj u kome se pokazuje da jedan primer postoji sa izvesnošću, koristeći metode teorije verovatnoće. Probabilistički dokaz, poput dokaza konstrukcijom, je jedan od mnogih načina da se pokažu teoremi postojanja.

Ovo ne treba mešati sa argumentom da je teorema verovatno tačna, „argumenta plauzabilnosti”. Rad na Kolatcovoj hipotezi pokazuje koliko je udaljena verodostojnost od pravog dokaza.

Kombinatorni dokaz

Glavni članak: Kombinatorni dokaz

Kombinatorni dokaz uspostavlja ekvivalenciju različitih izraza pokazujući da oni prebrojavaju isti objekat na različite načine. Često se bijekcija između dva seta koristi da se pokaže da su izrazi njihove dve veličine jednaki. Alternativno, argument dvostrukog brojanja pruža dva različita izraza za veličinu jednog seta, čime se ponovo pokazuje da su dva izraza jednaka.

Nekonstruktivni dokaz

Glavni članak: Nekonstruktivni dokaz

Nekonstruktivni dokaz utvrđuje da matematički objekat sa datim svojstvom postoji bez objašnjavanja kako se takav ovjekat može naći. Često se ovo uzima u obliku dokaza protivrečnosti u kojoj se nepostojanje objekta dokazuje nemogućom. Nasuprot tome, konstruktivan dokaz uspostavlja da određeni objekat postoji pružajući metod za njegovo nalaženje. Poznati primer je nekonstruktivni dokaz da postoje dva iracionalna broja a i b takva da je $a^{b}$ racionalan broj:

Bilo je ${\sqrt {2}}^{\sqrt {2}}$ racionalan broj i dokaz je završen (tj. $a=b={\sqrt {2}}$), ili je ${\sqrt {2}}^{\sqrt {2}}$ iracionalan broj, tako da se može pisati $a={\sqrt {2}}^{\sqrt {2}}$ i $b={\sqrt {2}}$. Iz toga zatim sledi $\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{2}=2$, što je stoga racionalan broj oblika $a^{b}.$

Statistički dokazi u čistoj matematici

Glavni članak: Statistički dokaz

Izraz „statistički dokaz” se može tehnički ili kolokvijalno koristiti u oblastima čiste matematike, poput onih koje obuhvataju kriptografiju, haotične serije, i probabilističku ili analitičku teoriju brojeva. On se ređe koristi u kontekstu matematičkih dokaza u matematičkoj grani poznatoj kao matematička statistika.

Računarski potpomognuti dokaz

Glavni članak: Računarski potpomognuti dokaz

Do 20. veka se pretpostavljalo da se bilo koji dokaz načelno može proveriti od strane kompetentnog matematičara da bi se potvrdila njegova validnost. Međutim u današnje vreme se koriste računari kako bi dokazale teoreme i izvršili dugi proračuni koji bi zahtevali previše ljudskog vremena; prvi dokaz teoreme četiri boje je primer računarskog dokaza. Neki matematičari su zabrinuti zbog mogućnosti postojanja greške u računarskom programu ili da može doći do grešaka pri izvršavanju programa, što bi moglo da dovede u pitanje validnost takvih kompjuterskih dokaza. U praksi, šanse postojanja greške koja obesnažava računarski-pomognute dokaze se mogu smanjiti korišćenjem redundancije i samoproveravanja pri proračunu, i razvojem višestrukih nezavisnih pristupa i programa. Greške se nikada ne mogu potpuno isključiti ni u slučaju manuelne verifikacije dokaza, posebno ako dokaz sadrži prirodni jezik i zahteva dubok matematički uvid.

Literatura

• Cupillari, Antonella (2001). The Nuts and Bolts of Proofs. Academic Press. 
• Clapham, C. & Nicholson, J. N. (2009). The Concise Oxford Dictionary of Mathematics (4th izd.). ISBN 978-0199235940. 
• Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 978-1-4398-4884-5. Arhivirano iz originala 23. 10. 2015. g. Pristupljeno 09. 04. 2020. 
• Clapham, C. & Nicholson, JN. The Concise Oxford Dictionary of Mathematics, Fourth edition. „A statement whose truth is either to be taken as self-evident or to be assumed. Certain areas of mathematics involve choosing a set of axioms and discovering what results can be derived from them, providing proofs for the theorems that are obtained.” 
• Clapham, C. & Nicholson, JN. The Concise Oxford Dictionary of Mathematics, Fourth edition. „A statement whose truth is either to be taken as self-evident or to be assumed. Certain areas of mathematics involve choosing a set of axioms and discovering what results can be derived from them, providing proofs for the theorems that are obtained.” 
• Eves, Howard (1990). An Introduction to the History of Mathematics. Saunders. str. 141. ISBN 978-0-03-029558-4. 
• Gossett, Eric (2009). Discrete Mathematics with Proof. John Wiley and Sons. str. 86. ISBN 978-0-470-45793-1. 
• Gossett, Eric (2009). Discrete Mathematics with Proof. John Wiley and Sons. str. 86. ISBN 978-0-470-45793-1. 
• Pólya, G. (1954), Mathematics and Plausible Reasoning, Princeton University Press .
• Fallis, Don (2002), „What Do Mathematicians Want? Probabilistic Proofs and the Epistemic Goals of Mathematicians”, Logique et Analyse, 45: 373—388 .
• Barwise, Jon (1982). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics, Amsterdam, North Holland. ISBN 978-0-444-86388-1. 
• Franklin, J.; Daoud, A. (2011). Proof in Mathematics: An Introduction. Kew Books. ISBN 978-0-646-54509-7. .
• Solow, D. (2004). How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley. ISBN 978-0-471-68058-1. .
• Velleman, D. (2006). How to Prove It: A Structured Approach. Cambridge University Press. ISBN 978-0-521-67599-4. .
• Beaney, Michael, The Frege Reader, London: Blackwell 1997.
• Bochenski, I.M., A History of Formal Logic, Indiana, Notre Dame University Press, 1961.
• Boehner, Philotheus, Medieval Logic, Manchester 1950.
• Buroker, Jill Vance (transl. and introduction), A. Arnauld, P. Nicole (1996). Logic or the Art of Thinking. Cambridge University Press. ISBN 978-0-521-48249-3. CS1 održavanje: Višestruka imena: spisak autora (veza)
• Church, Alonzo, 1936-8. "A bibliography of symbolic logic". Journal of Symbolic Logic 1: 121–218; 3:178–212.
• de Jong, Everard (1989), Galileo Galilei's "Logical Treatises" and Giacomo Zabarella's "Opera Logica": A Comparison, PhD dissertation, Washington, DC: Catholic University of America.
• Ebbesen, Sten "Early supposition theory (12th–13th Century)" Histoire, Épistémologie, Langage 3/1: 35–48 (1981).
• Farrington, B., The Philosophy of Francis Bacon, Liverpool 1964.
• Feferman, Anita B. (1999). Alfred Tarski. American National Biography. Oxford University Press. str. 330—332. ISBN 978-0-19-512800-0. 
• Feferman, Anita B.; Feferman, Solomon (2004). Alfred Tarski: Life and Logic. Cambridge University Press. ISBN 978-0-521-80240-6. OCLC 54691904. 
• Gabbay, Dov; John Woods, eds. Handbook of the History of Logic. 2004. 1. Greek, Indian and Arabic logic; 2. Mediaeval and Renaissance logic; 3. The rise of modern logic: from Leibniz to Frege; 4. British logic in the Nineteenth century; 5. Logic from Russell to Church; 6. Sets and extensions in the Twentieth century; 7. Logic and the modalities in the Twentieth century; 8. The many-valued and nonmonotonic turn in logic; 9. Computational Logic; 10. Inductive logic; 11. Logic: A history of its central concepts; Elsevier. ISBN 978-0-444-51611-4. CS1 održavanje: Tekst viška: spisak autora (veza)
• Geach, P.T. Logic Matters, Blackwell 1972.
• Goodman, Lenn Evan (2003). Islamic Humanism. Oxford University Press. ISBN 978-0-19-513580-0. 
• Goodman, Lenn Evan (1992). Avicenna. Routledge. ISBN 978-0-415-01929-3. 
• Grattan-Guinness, Ivor, 2000. The Search for Mathematical Roots 1870–1940. Princeton University Press.
• Gracia, J.G. and Noone, T.B., A Companion to Philosophy in the Middle Ages, London 2003.
• Haaparanta, Leila, ur. (2009). The Development of Modern Logic. Oxford University Press. 
• Heath, T.L. (1949). Mathematics in Aristotle. Oxford University Press. 
• Heath, T.L., 1931, A Manual of Greek Mathematics, Oxford (Clarendon Press).
• Honderich, Ted, ur. (1995). The Oxford Companion to Philosophy. New York: Oxford University Press. ISBN 978-0-19-866132-0. 
• Kneale, William; Kneale, Martha (1962). The development of logic. Oxford University Press. ISBN 978-0-19-824773-9. 
• Lukasiewicz, Aristotle's Syllogistic, Oxford University Press 1951.
• Potter, Michael (2004). Set Theory and its Philosophy. Oxford University Press. 

Spoljašnje veze

• Proofs in Mathematics: Simple, Charming and Fallacious