Svođenje na kontradikciju

Za drugu upotrebu, pogledajte stranicu Svođenje na apsurd.

Svođenje na kontradikciju ili svođenje na protivrečnost ili, kako je Aristotel pisao, svođenje na nemoguće (lat. Reductio ad absurdum) je jedan od najčešćih, a istovremeno i najpopularnijih dokaza u logici. Potiče od prevoda grčkog izraza (grč. ἡ εις άτοπον απαγωγη - hi eis atopon apagogi).

Ovim postupkom se na početku dokaza pretpostavlja suprotno od onoga što se želi dokazati. Ako se na kraju dokaza (u sledu istinitih tvrdnji) dođe do kontradikcije, znači da je početna pretpostavka neodrživa i time je dokaz gotov.

Ovde se implicitno koristi zakon kontradikcije (odnosno zakon o protivrečnosti) koji tvrdi da jedna kategorična izjava ne može biti istovremeno i istinita i neistinita. Takođe je ovde bitan i zakon isključenja treće mogućnosti. Dakle jedna kategorična izjava ne može biti istovremeno ni istinita ni neistinita. Drugim rečima, ako nije istinita ona mora biti neistinita i obrnuto.

Istorija

Ova logička metoda je ponikla kod helenskih filozofa. Pretpostavlja se da prvi put nije upotrebljena u filozofskom ili matematičkom slučaju već kod filozofa sofista koji su ovu metodu koristili kao advokati u sudovima. Tada su dokazivali nevinost svojih štićenika započinjući „pretpostavimo da je moj štićenik kriv..." (lat. argumentum a contrario) i na kraju pokazivali kako to dovodi do protivrečnosti sa postojećim dokazima. Tako su oni efektno i elegantno dokazivali nevinost, a ova metoda je ubrzo postala prihvaćena od svih filozofa kao logički nepobitna.

Sledeća karika je Sokrat, veliki filozof mada ne i matematičar, koji je uveo hipotezu u matematičko mišljenje. On tvrdi da pored istine postoji i hipoteza, pretpostavka, tvrdnja, pa onda izvodi logičke posledice. Ako se tom prilikom naiđe na protivrečnost tada je jedini uzrok bila loša pretpostavka te se ona ima odbaciti. Zbog ovoga neki Sokrata smatraju utemeljivačem logike.

Sokratov učenik Platon je vodeći filozof helenskog doba, idealista, koji je u svojoj borbi protiv materijalista, atomista, išao dotle da je uništavao njihove spise i doslovce, a protiv njihovih učenja i uticaja se borio dokazujući da su neistinita. Atomistička misao je bila plodna u nekim poljima. U geometriji su uspeli da dođu do formula za izračunavanje površine nekih figura ili zapremine nekih tela svojim naivnim ali ipak efektnim metodama. Platon je lepršavi i naivni atomistički sistem odbacio i postavio sistem u kome se sva znanja baziraju na nekoliko osnovnih istina (aksioma) koje se ne dokazuju i ne mogu se dokazivati, već su date kao takve, i sve ostale koje se logički dokazuju odnosno izvode iz ovih istina. Jedna od omiljenih metoda postaje upravo dokazivanje svođenjem na protivrečnost. Nešto kasnije Platonov učenik Eudoks Kniđanin pronalazi autentično novu metodu iscrpljivanja (ekshaustiju) i idealisti pobeđuju u ovoj borbi.

Aristotel je dao ključni doprinos i sistematično razradio pitanja deduktivne logike. Kod njega se metoda svođenja na kontradikciju zove svođenje na nemoguće. Između ostalog je i objasnio zakon o neprotivrečnosti i zakon isključenja treće mogućnosti. Ova metoda je značajno oruđe logike u rukama Euklida i upravo u Elementima je odigrala ključnu ulogu u izgradnji logički zasnovane škole geometrije.

Međutim, najveći doprinos primeni ove metode je dao Arhimed. On je u svojim spisima ovu metodu doterao do neslućenih razmera čak prevazilazeći granice kojima je metoda predodređena. Arhimed je, prema sopstvenom priznanju, našao neke zaturene spise atomista sa njihovim genijalnim, ali logički slabo potkovanim tvrdnjama i shvativši da su njihovi zaključci istiniti uspeo da nađe zaobilazne metode da do tih rezultata dođe na potpuno originalan ali zbunjujući način. Ovo se saznalo tek dvadeset vekova posle njegove smrti, slučajnim pronalaskom jednog zaturenog spisa u kome je on otkrio kako je smišljao i pronalazio rešenja za komplikovane probleme koje je rešavao. Njegova metoda uvođenja međukoraka, zaobilaznih pretpostavki i lema, a potom svođenja na besmislicu početnih tvrdnji je i za matematičare XVII i XVIII veka predstavljala izvor očajanja.

Ovako izgrađeni, Arhimedovi dokazi nisu davali uputstva kako ovu metodu primeniti i na neke druge, srodne slučajeve. Današnjim rečnikom rečeno, ne vidi se kako se generički rešava jedna klasa problema. Tu se videlo još nedostataka ove metode. Ona je dobra za proveru i dokazivanje rezultata (poznatog ili pogođenog) ali je loša za nalaženje novog, još nepoznatog rešenja. Stari matematičari su govorili da metoda više zbunjuje nego što razvija um, jer čitalac ne zna odakle se pojavilo rešenje, pošto nema jasne slike o vezama između istina i postojanju uzročno posledičnog lanca.

Matematika

U matematičkoj logici je svođenje na kontradikciju predstavlja na sledeći način:

ako

$S\cup \{p\}\vdash F$

tada

$S\vdash \neg p$

ili

ako

$S\cup \{\neg p\}\vdash F$

tada

$S\vdash p$

U prethodnom je p tvrđenje koje želimo da potvrdimo ili opovrgnemo, S je skup iskaza koji su dati kao istiniti – to mogu biti aksiome neke teorije koju razvijamo ili prethodno dokazane teoreme. Dodaćemo p, ili negaciju p, skupu S. Ako ovo dodavanje vodi logičkoj kontradikciji F, tada možemo zaključiti da iz iskaza u S sledi negacija p, odnosno p respektivno.

Primer

Dokaz da koren iz 2 nije racionalan broj

Ovaj dokaz je doveo mnoge pitagorejce na rub nervnog sloma, jer je označio kraj vladavine idealnih odnosa i sklada među brojevima (a bogami i njihove škole). Ne zna se da li je odmah izveden na ovaj način, jer ga je tek Aristotel pribeležio ovakvog, ali je bio verovatno sličan.

Pošto dokazujemo da je ${\sqrt {2}}$ iracionalan, krećemo od suprotne pretpostavke. Hajde da pretpostavimo da nije!

• Dakle pretpostavimo da su hipotenuza i kateta jednakokrakog pravouglog trougla samerljivi

• Njihov odnos je odnos dva cela (uzajamno prosta) broja, koje ne možemo dalje skratiti, odnosno da je ${\sqrt {2}}=p/q$

• kvadriranjem se dobija ${p^{2} \over q^{2}}=2$ odnosno $p^{2}=2\cdot q^{2}$

• sledi da je $p^{2}\,$ pa prema tome i $p\,$ paran broj, pa ćemo ga predstaviti kao $p=2\cdot r\,$

• tada je $p^{2}=4\cdot r^{2}=2\cdot q^{2}$ odakle je $q^{2}=2\cdot r^{2}$

• sledi da je $q\,$ takođe paran broj, što je suprotno od naše prve pretpostavke da su i $p\,$ i $q\,$ uzajamno prosti brojevi

Ovim je dokazano postojanje iracionalnih brojeva, međutim za stare Helene je ovo bio momenat napuštanja aritmetike i baratanja brojevima i potpuni prelazak na geometriju.