Свођење на контрадикцију

За другу употребу, погледајте страницу Свођење на апсурд.

Свођење на контрадикцију или свођење на противречност или, како је Аристотел писао, свођење на немогуће (лат. Reductio ad absurdum) је један од најчешћих, а истовремено и најпопуларнијих доказа у логици. Потиче од превода грчког израза (грч. ἡ εις άτοπον απαγωγη - хи еис атопон апагоги).

Овим поступком се на почетку доказа претпоставља супротно од онога што се жели доказати. Ако се на крају доказа (у следу истинитих тврдњи) дође до контрадикције, значи да је почетна претпоставка неодржива и тиме је доказ готов.

Овде се имплицитно користи закон контрадикције (односно закон о противречности) који тврди да једна категорична изјава не може бити истовремено и истинита и неистинита. Такође је овде битан и закон искључења треће могућности. Дакле једна категорична изјава не може бити истовремено ни истинита ни неистинита. Другим речима, ако није истинита она мора бити неистинита и обрнуто.

Историја

Ова логичка метода је поникла код хеленских филозофа. Претпоставља се да први пут није употребљена у филозофском или математичком случају већ код филозофа софиста који су ову методу користили као адвокати у судовима. Тада су доказивали невиност својих штићеника започињући „претпоставимо да је мој штићеник крив..." (лат. argumentum a contrario) и на крају показивали како то доводи до противречности са постојећим доказима. Тако су они ефектно и елегантно доказивали невиност, а ова метода је убрзо постала прихваћена од свих филозофа као логички непобитна.

Следећа карика је Сократ, велики филозоф мада не и математичар, који је увео хипотезу у математичко мишљење. Он тврди да поред истине постоји и хипотеза, претпоставка, тврдња, па онда изводи логичке последице. Ако се том приликом наиђе на противречност тада је једини узрок била лоша претпоставка те се она има одбацити. Због овога неки Сократа сматрају утемељивачем логике.

Сократов ученик Платон је водећи филозоф хеленског доба, идеалиста, који је у својој борби против материјалиста, атомиста, ишао дотле да је уништавао њихове списе и дословце, а против њихових учења и утицаја се борио доказујући да су неистинита. Атомистичка мисао је била плодна у неким пољима. У геометрији су успели да дођу до формула за израчунавање површине неких фигура или запремине неких тела својим наивним али ипак ефектним методама. Платон је лепршави и наивни атомистички систем одбацио и поставио систем у коме се сва знања базирају на неколико основних истина (аксиома) које се не доказују и не могу се доказивати, већ су дате као такве, и све остале које се логички доказују односно изводе из ових истина. Једна од омиљених метода постаје управо доказивање свођењем на противречност. Нешто касније Платонов ученик Еудокс Книђанин проналази аутентично нову методу исцрпљивања (ексхаустију) и идеалисти побеђују у овој борби.

Аристотел је дао кључни допринос и систематично разрадио питања дедуктивне логике. Код њега се метода свођења на контрадикцију зове свођење на немогуће. Између осталог је и објаснио закон о непротивречности и закон искључења треће могућности. Ова метода је значајно оруђе логике у рукама Еуклида и управо у Елементима је одиграла кључну улогу у изградњи логички засноване школе геометрије.

Међутим, највећи допринос примени ове методе је дао Архимед. Он је у својим списима ову методу дотерао до неслућених размера чак превазилазећи границе којима је метода предодређена. Архимед је, према сопственом признању, нашао неке затурене списе атомиста са њиховим генијалним, али логички слабо поткованим тврдњама и схвативши да су њихови закључци истинити успео да нађе заобилазне методе да до тих резултата дође на потпуно оригиналан али збуњујући начин. Ово се сазнало тек двадесет векова после његове смрти, случајним проналаском једног затуреног списа у коме је он открио како је смишљао и проналазио решења за компликоване проблеме које је решавао. Његова метода увођења међукорака, заобилазних претпоставки и лема, а потом свођења на бесмислицу почетних тврдњи је и за математичаре XVII и XVIII века представљала извор очајања.

Овако изграђени, Архимедови докази нису давали упутства како ову методу применити и на неке друге, сродне случајеве. Данашњим речником речено, не види се како се генерички решава једна класа проблема. Ту се видело још недостатака ове методе. Она је добра за проверу и доказивање резултата (познатог или погођеног) али је лоша за налажење новог, још непознатог решења. Стари математичари су говорили да метода више збуњује него што развија ум, јер читалац не зна одакле се појавило решење, пошто нема јасне слике о везама између истина и постојању узрочно последичног ланца.

Математика

У математичкој логици је свођење на контрадикцију представља на следећи начин:

ако

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

тада

$S\vdash \neg p$

или

ако

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

тада

$S\vdash p$

У претходном је p тврђење које желимо да потврдимо или оповргнемо, S је скуп исказа који су дати као истинити – то могу бити аксиоме неке теорије коју развијамо или претходно доказане теореме. Додаћемо p, или негацију p, скупу S. Ако ово додавање води логичкој контрадикцији F, тада можемо закључити да из исказа у S следи негација p, односно p респективно.

Пример

Доказ да корен из 2 није рационалан број

Овај доказ је довео многе питагорејце на руб нервног слома, јер је означио крај владавине идеалних односа и склада међу бројевима (а богами и њихове школе). Не зна се да ли је одмах изведен на овај начин, јер га је тек Аристотел прибележио оваквог, али је био вероватно сличан.

Пошто доказујемо да је ${\sqrt {2}}$ ирационалан, крећемо од супротне претпоставке. Хајде да претпоставимо да није!

• Дакле претпоставимо да су хипотенуза и катета једнакокраког правоуглог троугла самерљиви

• Њихов однос је однос два цела (узајамно проста) броја, које не можемо даље скратити, односно да је ${\sqrt {2}}=p/q$

• квадрирањем се добија ${p^{2} \over q^{2}}=2$ односно $p^{2}=2\cdot q^{2}$

• следи да је $p^{2}\,$ па према томе и $p\,$ паран број, па ћемо га представити као $p=2\cdot r\,$

• тада је $p^{2}=4\cdot r^{2}=2\cdot q^{2}$ одакле је $q^{2}=2\cdot r^{2}$

• следи да је $q\,$ такође паран број, што је супротно од наше прве претпоставке да су и $p\,$ и $q\,$ узајамно прости бројеви

Овим је доказано постојање ирационалних бројева, међутим за старе Хелене је ово био моменат напуштања аритметике и баратања бројевима и потпуни прелазак на геометрију.