Matematički dokaz

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,[2][3][4] 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 rezonovanja 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.

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

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

uredi

Argumenti pouzdanosti korišćenjem heurističkih pomagala kao što su slike i analogije prethodili su strogom matematičkom dokazu.[5] Moguće je da se ideja o demonstriranju zaključaka prvobitno javila u geometrijskom kontekstu, koji je originalno poistovećivan sa „merenjem zemljišta”.[6] 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 samoevidentne 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.[7] 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.[8] 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 Euklidskog postulata paralelnosti.[9]

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

uredi

Direktan dokaz

uredi

U direktnom dokazu, zaključak se izvodi logičkim kombinovanjem aksioma, definicija, i ranijih teorema.[10] 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, 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

uredi

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.[11] 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:[12] 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”.[13]

Dokaz kontrapozicijom

uredi

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  , ako je   je parno, onda je   parno:

Pretpostavimo da   nije paran. Onda je   neparan. Proizvod dva neparna broja je neparan, stoga je   neparno. Iz toga sledi da   nije parno. Stoga, ako jeste   parno, pretpostavka mora biti lažna, tako da   mora biti paran.

Dokaz kontradikcijom

uredi

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   iracionalni broj:

Pretpostavimo da je   racionalni broj, tako da je po definiciji  , 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,  . Kvadrirajući obe strane dobija se 2b2 = a2. Pošto 2 deli levu stranu, 2 isto tako mora deliti desnu stranu (inače bi paran broj bio jednak neparnom broju). Stoga a2 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 2b2 = (2c)2 = 4c2. Deljenjem obe strane sa 2 dobija se b2 = 2c2. Ali onda, istim argumentom kao i ranije, 2 deli b2, 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   iracionalni broj.

Dokaz konstrukcijom

uredi

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

uredi

U dokazu iscrpljivanjem, zaključak se uspostavlja deljenjem u konačan broj slučajeva i dokazivanjem svakog od njih zasebno. Broj slučajeva ponekad 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

uredi

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.[14]

Kombinatorni dokaz

uredi

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.[15] Alternativno, argument dvostrukog brojanja pruža dva različita izraza za veličinu jednog seta, čime se ponovo pokazuje da su dva izraza jednaka.[16][17]

Nekonstruktivni dokaz

uredi

Nekonstruktivni dokaz utvrđuje da matematički objekat sa datim svojstvom postoji bez objašnjavanja kako se takav objekat 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   racionalan broj:

Bilo je   racionalan broj i dokaz je završen (tj.  ), ili je   iracionalan broj, tako da se može pisati   i  . Iz toga zatim sledi  , što je stoga racionalan broj oblika  

Statistički dokazi u čistoj matematici

uredi

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.[18][19][20] On se ređe koristi u kontekstu matematičkih dokaza u matematičkoj grani poznatoj kao matematička statistika.

Računarski potpomognuti dokaz

uredi

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.[5] 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.

Reference

uredi
  1. ^ Bill Casselman. „One of the Oldest Extant Diagrams from Euclid”. University of British Columbia. Pristupljeno 26. 9. 2008. 
  2. ^ Clapham & Nicholson 2009
  3. ^ Cupillari, Antonella (2001). The Nuts and Bolts of Proofs. Academic Press. str. 3. 
  4. ^ Gossett 2009, str. 86 harvnb greška: više ciljeva (2×): CITEREFGossett2009 (help)
  5. ^ a b The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
  6. ^ Kneale & Kneale 1962, str. 2.
  7. ^ Eves 1990, str. 141: "No work, except The Bible, has been more widely used...."
  8. ^ Matvievskaya, Galina (1987), „The Theory of Quadratic Irrationals in Medieval Oriental Mathematics”, Annals of the New York Academy of Sciences, 500: 253-277[260], doi:10.1111/j.1749-6632.1987.tb37206.x 
  9. ^ Eder, Michelle (2000), Views of Euclid's Parallel Postulate in Ancient Greece and in Medieval Islam, Rutgers University, Pristupljeno 23. 1. 2008 
  10. ^ Cupillari 2001, str. 20. sfn greška: više ciljeva (2×): CITEREFCupillari2001 (help)
  11. ^ Cupillari 2001, str. 46. sfn greška: više ciljeva (2×): CITEREFCupillari2001 (help)
  12. ^ Examples of simple proofs by mathematical induction for all natural numbers
  13. ^ Proof by induction Arhivirano na sajtu Wayback Machine (18. februar 2012), University of Warwick Glossary of Mathematical Terminology
  14. ^ While most mathematicians do not think that probabilistic evidence ever counts as a genuine mathematical proof, a few mathematicians and philosophers have argued that at least some types of probabilistic evidence (such as Rabin's probabilistic algorithm for testing primality) are as good as genuine mathematical proofs. See, for example, Davis, Philip J. (1972), "Fidelity in Mathematical Discourse: Is One and One Really Two?" American Mathematical Monthly 79:252-63. Fallis, Don (1997), "The Epistemic Status of Probabilistic Proof." Journal of Philosophy 94:165-86.
  15. ^ Loehr 2011
  16. ^ Klavžar, Sandi (2006), „Counting hypercubes in hypercubes”, Discrete Mathematics, 306 (22): 2964—2967, doi:10.1016/j.disc.2005.10.036 
  17. ^ van Lint, Jacobus H.; Wilson, Richard M. (2001), A Course in Combinatorics, Cambridge University Press, str. 4, ISBN 978-0-521-00601-9 
  18. ^ "in number theory and commutative algebra... in particular the statistical proof of the lemma." [1]
  19. ^ "Whether constant π (i.e., pi) is normal is a confusing problem without any strict theoretical demonstration except for some statistical proof"" (Derogatory use.)[2][mrtva veza]
  20. ^ "these observations suggest a statistical proof of Goldbach's conjecture with very quickly vanishing probability of failure for large E" [3]

Literatura

uredi

Spoljašnje veze

uredi