Математички доказ

(преусмерено са Mathematical proof)

Математички доказ, у математичком смислу, је логичко-математички поступак којим се доказује теорема. У њему се смеју користити само аксиоми и претходно доказане теореме,[2][3][4] заједно са прихваћеним правилима закључивања. Аксиоми се могу третирати као услови који морају бити испуњени пре него што се изјава примени. Докази су примери исцрпног дедуктивног резоновања или индуктивног резоновања и они се разликују од емпиријских аргумената или неисцрпног индуктивног резоновања (или „разумног очекивање”). Доказ мора да демонстрира да је исказ увек истинит (повремено путем навођења свих могућих случајева и показивањем да важи у свим случајевима), уместо навођења мноштва потврђујућих случајева. Непотврђени предлог који се сматра истинитим хипотезом.

П. Окси. 29, један од најстаријих сачуваних фрагмената Еуклидових Елемената, уџбеника који је миленијумима кориштен у настави тахника писања доказа. Дијаграм уврштен у Књигу II, Пропозицију 5.[1]

Једна од метода доказивања теорема је метода „претпоставимо супротно“. У тој методи, у којој се покушава да докаже тврдња А, претпостави се да вреди тврдња „не А“ и тражи се контрадикција (тврдња која је у супротности с већ претходно доказаним теоремом или аксиомом). Међу другим начинима се налази и извођење. Креће се од претпоставке теореме па се сви услови теореме примене на појам на који се теорема односи и тврдња теореме се логично-математички изведе.

Докази примењују логику али обично обухватају извесну количину природног језика који обично садржи неке нејасноће. Заправо, велика већина доказа у математици се може сматрати применом ригорозне неформалне логике. Чисто формални докази, написани у симболичком језику уместо природног језика, се разматрају у теорији доказа. Разлика између формалних и неформалних доказа је довела до знатног преиспитивања садашње и историјске математичке праксе, квазиемпиризма у математици, и такозване фолклорне математике (у оба смисла тог појма). Филозофија математике се бави улогом језика и логике у доказима, и математике као језика.

Историја и етимологија

уреди

Аргументи поузданости коришћењем хеуристичких помагала као што су слике и аналогије претходили су строгом математичком доказу.[5] Могуће је да се идеја о демонстрирању закључака првобитно јавила у геометријском контексту, који је оригинално поистовећиван са „мерењем земљишта”.[6] Развој математичког доказа је превасходно производ старих грчких математичара, и један од њихових највећих достигнућа. Талес из Милета (624–546. п. н. е.) и Хипократ са Хиоса (c470-410. п. н. е.) су доказали исте теореме у геометрији. Еудокс (408–355. п. н. е.) и Теаететус (417–369. п. н. е.) су формулисали теореме али их нису доказали. Аристотел (384–322. п. н. е.) је сматрао да дефиниција треба да опише концепт који се дефинише у смислу већ познатих концепата. Математичке доказе је револуционисали револуционирао Еуклид (300. п. н. е.), који је увео аксиоматски метод који се још увек користи, почевши од недефинисаних термина и аксиома (пропозиција везаних за недефинисане термине за које се претпоставља да су самоевидентне истините од грчких „аксиоса” са значењем „нешто вредно”), и користио их је за доказивање теорема примењујући дедуктивну логику. Његову књигу, Елементе, су читали сви који су се сматрали образованим на Западу до средине 20. века.[7] Осим геометријских теорема, као што је Питагорина теорема, Елементи такође покривају теорију бројева, укључујући доказ да је квадратни корен од два ирационалан и да постоји бесконачно много простих бројева.

Даљи напреци су остварени у средњовековној исламској математици. Док су ранији грчки докази били углавном геометријске демонстрације, исламски развој аритметике и алгебре омогућио је знато генералније доказе који више нису били зависни од геометрије. У 10. веку, ирачки математичар Ал-Хашими произвео опште доказе за бројеве (уместо геометријских демонстрација) док је разматрао множење, дељење, итд. за „линије”. Он је користио тај метод да изведе доказ постојања ирационалних бројева.[8] Индуктивни доказ за аритметичке секвенце је увео Ал-Караџи у Ал-Факри (1000), који је он затим користио за доказивање биномне теореме и својстава Паскаловог троугла. Алхазен је развио метод свођења на контрадикцију, као први покушај доказивања Еуклидског постулата паралелности.[9]

Модерна теорија доказа третира доказе као индуктивно дефинисане структуре података. Више нема претпоставке да су аксиоми у сваком смислу „истинити”; ово омогућава постојање паралелне математичке теорије изграђене на алтернативним сетовима аксиома (погледај аксиоматску теорију скупова и нееуклидску геометрију на пример).

Методи

уреди

Директан доказ

уреди

У директном доказу, закључак се изводи логичким комбиновањем аксиома, дефиниција, и ранијих теорема.[10] На пример, директни доказ се може користити за утврђивање да је сума два парна цела броја увек парна:

Размотримо два парна цела броја x и y. Пошто су они парни, они се могу написати као x = 2a и y = 2b, за целе бројеве a и b. Онда је сума x + y = 2a + 2b = 2(a+b). Стога x+y има 2 као фактор и, по дефиницији, је парна. Из тога следи да је сума било која два парна цела броја парна.

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

Доказ математичком индукцијом

уреди

Упркос свог имена, математичка индукција је метод дедукције, а није форма индуктивног расуђивања. У доказу путем математичке индукције, појединачни „основни случај” се доказује, и доказано је „правило индукције” којим се утврђује да сваки произвољни случај имплицира следећи случај. Пошто у принципу правило индукције може бити примењено више пута почевши од доказаног основног случаја, произилази да су сви (обично бесконачно многобројни) случајеви доказиви.[11] Тиме се избегава потреба појединачног доказивања сваког случаја. Варијанта математичке индукције је доказ бесконачног спуштања, који се може користити на пример за доказивање ирационалности квадратног корена из два.

Уобичајена примена доказа математичком индукцијом је доказивање да својство за које се зна да важи за један број важи за све природне бројеве:[12] Нека је N = {1,2,3,4,...} скуп природних бројева, и нека је P(n) математички израз који обухвата природни број n из N такав да је

  • (i) P(1) истинито, тј., P(n) је истинито за n = 1.
  • (ii) P(n+1) је истинито кад је P(n) истинито, тј., ако је P(n) истинито следи да је P(n+1) истинито.
  • Онда је P(n) истинито за све природне бројеве n.

На пример, индукцијом се може доказати да су сви позитивни цели бројеви облика 2n − 1 непарни. Нека P(n) представља „2n − 1 је непаран”:

(i) За n = 1, 2n − 1 = 2(1) − 1 = 1, и 1 је непаран, пошто оставља остатак од 1 кад се подели са 2. Стога P(1) је истинито.
(ii) За свако n, ако је 2n − 1 непарно (P(n)), онда (2n − 1) + 2 исто тако мора бити непарно, пошто додавање 2 непарном броју резултира у непарном броју. Али је (2n − 1) + 2 = 2n + 1 = 2(n+1) − 1, стога је 2(n+1) − 1 непаран (P(n+1)). Из P(n) следи P(n+1).
Стога 2n − 1 је непарно, за све позитивне целе бројеве n.

Краћа фраза „доказ индукцијом” се обично користи уместо „доказ математичком индукцијом”.[13]

Доказ контрапозицијом

уреди

Контрапозиционим доказом се изводи закључак „ако је p онда је q” по претпоставци „ако није q онда није p”. Изјава „ако није q онда није p” се назива контрапозицијом изјаве „ако је p онда је q”. На пример, контрапозиција се може користити за утврђивање да за цео број  , ако је   је парно, онда је   парно:

Претпоставимо да   није паран. Онда је   непаран. Производ два непарна броја је непаран, стога је   непарно. Из тога следи да   није парно. Стога, ако јесте   парно, претпоставка мора бити лажна, тако да   мора бити паран.

Доказ контрадикцијом

уреди

У доказу контрадикцијом (такође познатом као reductio ad absurdum, у преводу са латинског „редукцијом до апсурда”) се показује да ако би нека изјава била истинита, дошло би до логичке контрадикције, и стога изјава мора бити неистинита. Познати пример доказа контрадикцијом показује да је   ирационални број:

Претпоставимо да је   рационални број, тако да је по дефиницији  , где су a и b цели бројеви различити од нуле без заједничког фактора. (Ако постоји заједнички фактор, нумератор и именилац требају бити подељени њиме да би се уклонио, и поступак треба понављати док више не буде заједничког фактора. По методи бесконачног спуштања, овај процес мора имати крај.) Стога,  . Квадрирајући обе стране добија се 2b2 = a2. Пошто 2 дели леву страну, 2 исто тако мора делити десну страну (иначе би паран број био једнак непарном броју). Стога a2 је парно, из чега следи да a исто тако мора бити парно. Из тог разлога се може написати a = 2c, где је c такође цео број. Заменом у оригиналној једначини се добија 2b2 = (2c)2 = 4c2. Дељењем обе стране са 2 добија се b2 = 2c2. Али онда, истим аргументом као и раније, 2 дели b2, тако да b мора бити паран. Међутим, ако су a и b оба парни, они имају заједнички фактор, наиме 2. То је у контрадикцији са почетном претпоставком, тако да се мора извести закључак да је   ирационални број.

Доказ конструкцијом

уреди

Доказ конструкцијом, или доказ помоћу примера, је конструкција конкретног примера са датим својством, да би се показало да нешто што има то својство постоји. На пример, Жозеф Лијувил је доказао постојање трансцендентних бројева конструисањем једног експлицитног примера. Ова приступ се исто тако може користити при конструисању контрапримера с циљем оспоравања предлога да сви елементи имају одређену особину.

Доказ исцрпљењем

уреди

У доказу исцрпљивањем, закључак се успоставља дељењем у коначан број случајева и доказивањем сваког од њих засебно. Број случајева понекад може да буде веома велик. На пример, први доказ теореме четири боје је био доказ исцрпљивањем са 1.936 случаја. Овај доказ је био контроверзан зато што је већина случајева била проверена помоћу рачунарског програма, а не мануелно. Најкраћи познати доказ теореме четири боје по подацима из 2011. године још увек има преко 600 случаја.

Пробабилистички доказ

уреди

Пробабилистички доказ је онај у коме се показује да један пример постоји са извесношћу, користећи методе теорије вероватноће. Пробабилистички доказ, попут доказа конструкцијом, је један од многих начина да се покажу теореми постојања.

Ово не треба мешати са аргументом да је теорема вероватно тачна, „аргумента плаузабилности”. Рад на Колатцовој хипотези показује колико је удаљена веродостојност од правог доказа.[14]

Комбинаторни доказ

уреди

Комбинаторни доказ успоставља еквиваленцију различитих израза показујући да они пребројавају исти објекат на различите начине. Често се бијекција између два сета користи да се покаже да су изрази њихове две величине једнаки.[15] Алтернативно, аргумент двоструког бројања пружа два различита израза за величину једног сета, чиме се поново показује да су два израза једнака.[16][17]

Неконструктивни доказ

уреди

Неконструктивни доказ утврђује да математички објекат са датим својством постоји без објашњавања како се такав објекат може наћи. Често се ово узима у облику доказа противречности у којој се непостојање објекта доказује немогућом. Насупрот томе, конструктиван доказ успоставља да одређени објекат постоји пружајући метод за његово налажење. Познати пример је неконструктивни доказ да постоје два ирационална броја a и b таква да је   рационалан број:

Било је   рационалан број и доказ је завршен (тј.  ), или је   ирационалан број, тако да се може писати   и  . Из тога затим следи  , што је стога рационалан број облика  

Статистички докази у чистој математици

уреди

Израз „статистички доказ” се може технички или колоквијално користити у областима чисте математике, попут оних које обухватају криптографију, хаотичне серије, и пробабилистичку или аналитичку теорију бројева.[18][19][20] Он се ређе користи у контексту математичких доказа у математичкој грани познатој као математичка статистика.

Рачунарски потпомогнути доказ

уреди

До 20. века се претпостављало да се било који доказ начелно може проверити од стране компетентног математичара да би се потврдила његова валидност.[5] Међутим у данашње време се користе рачунари како би доказале теореме и извршили дуги прорачуни који би захтевали превише људског времена; први доказ теореме четири боје је пример рачунарског доказа. Неки математичари су забринути због могућности постојања грешке у рачунарском програму или да може доћи до грешака при извршавању програма, што би могло да доведе у питање валидност таквих компјутерских доказа. У пракси, шансе постојања грешке која обеснажава рачунарски-помогнуте доказе се могу смањити коришћењем редунданције и самопроверавања при прорачуну, и развојем вишеструких независних приступа и програма. Грешке се никада не могу потпуно искључити ни у случају мануелне верификације доказа, посебно ако доказ садржи природни језик и захтева дубок математички увид.

Референце

уреди
  1. ^ Bill Casselman. „One of the Oldest Extant Diagrams from Euclid”. University of British Columbia. Приступљено 26. 9. 2008. 
  2. ^ Clapham & Nicholson 2009
  3. ^ Cupillari, Antonella (2001). The Nuts and Bolts of Proofs. Academic Press. стр. 3. 
  4. ^ Gossett 2009, стр. 86 harvnb грешка: више циљева (2×): CITEREFGossett2009 (help)
  5. ^ а б The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
  6. ^ Kneale & Kneale 1962, стр. 2.
  7. ^ Eves 1990, стр. 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, Приступљено 23. 1. 2008 
  10. ^ Cupillari 2001, стр. 20. sfn грешка: више циљева (2×): CITEREFCupillari2001 (help)
  11. ^ Cupillari 2001, стр. 46. sfn грешка: више циљева (2×): CITEREFCupillari2001 (help)
  12. ^ Examples of simple proofs by mathematical induction for all natural numbers
  13. ^ Proof by induction Архивирано на сајту Wayback Machine (18. фебруар 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, стр. 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][мртва веза]
  20. ^ "these observations suggest a statistical proof of Goldbach's conjecture with very quickly vanishing probability of failure for large E" [3]

Литература

уреди

Спољашње везе

уреди