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

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

П. Окси. 29, један од најстаријих сачуваних фрагмената Еуклидових Елемената, уџбеника који је миленијумима кориштен у настави тахника писања доказа. Дијаграм уврштен у Књигу , Пропозицију 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 = 2 и y = 2, за целе бројеве и . Онда је сума x + y = . Стога x+y има 2 као фактор и, по дефиницији, је парна. Из тога следи да је сума било која два парна цела броја парна.

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

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

Главни чланак: Математичка индукција

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

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

• P(1) истинито, тј., P(n) је истинито за n = 1.
• 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]

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

Главни чланак: Контрапозиција

Контрапозиционим доказом се изводи закључак „ако је онда је q” по претпоставци „ако није q онда није ”. Изјава „ако није q онда није ” се назива контрапозицијом изјаве „ако је онда је q”. На пример, контрапозиција се може користити за утврђивање да за цео број ${\displaystyle x}$, ако је ${\displaystyle x^{2}}$ је парно, онда је ${\displaystyle x}$ парно:

Претпоставимо да ${\displaystyle x}$ није паран. Онда је ${\displaystyle x}$ непаран. Производ два непарна броја је непаран, стога је ${\displaystyle x^{2}=x\cdot x}$ непарно. Из тога следи да ${\displaystyle x}$ није парно. Стога, ако јесте ${\displaystyle x^{2}}$ парно, претпоставка мора бити лажна, тако да ${\displaystyle x}$ мора бити паран.

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

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

У доказу контрадикцијом (такође познатом као , у преводу са латинског „редукцијом до апсурда”) се показује да ако би нека изјава била истинита, дошло би до логичке контрадикције, и стога изјава мора бити неистинита. Познати пример доказа контрадикцијом показује да је ${\displaystyle {\sqrt {2}}}$ ирационални број:

Претпоставимо да је ${\displaystyle {\sqrt {2}}}$ рационални број, тако да је по дефиницији ${\displaystyle {\sqrt {2}}={a \over b}}$, где су и цели бројеви различити од нуле без заједничког фактора. (Ако постоји заједнички фактор, нумератор и именилац требају бити подељени њиме да би се уклонио, и поступак треба понављати док више не буде заједничког фактора. По методи бесконачног спуштања, овај процес мора имати крај.) Стога, ${\displaystyle b{\sqrt {2}}=a}$. Квадрирајући обе стране добија се . Пошто 2 дели леву страну, 2 исто тако мора делити десну страну (иначе би паран број био једнак непарном броју). Стога ² је парно, из чега следи да исто тако мора бити парно. Из тог разлога се може написати , где је такође цео број. Заменом у оригиналној једначини се добија . Дељењем обе стране са 2 добија се . Али онда, истим аргументом као и раније, 2 дели ², тако да мора бити паран. Међутим, ако су и оба парни, они имају заједнички фактор, наиме 2. То је у контрадикцији са почетном претпоставком, тако да се мора извести закључак да је ${\displaystyle {\sqrt {2}}}$ ирационални број.

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

Главни чланак: Доказ конструкцијом

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

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

Главни чланак: Доказ исцрпљењем

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

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

Главни чланак: Пробабилистички метод

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

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

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

Главни чланак: Комбинаторни доказ

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

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

Главни чланак: Неконструктивни доказ

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

Било је ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ рационалан број и доказ је завршен (тј. ${\displaystyle a=b={\sqrt {2}}}$), или је ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ ирационалан број, тако да се може писати ${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ и ${\displaystyle b={\sqrt {2}}}$. Из тога затим следи ${\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{2}=2}$, што је стога рационалан број облика ${\displaystyle 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. sfn грешка: no target: CITEREFKnealeKneale1962 (help)
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 Архивирано на сајту (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."
19. "Whether constant π (i.e., pi) is normal is a confusing problem without any strict theoretical demonstration except for some statistical proof"" (Derogatory use.)^{[мртва веза]}
20. "these observations suggest a statistical proof of Goldbach's conjecture with very quickly vanishing probability of failure for large E"

Литература

• Cupillari, Antonella (2001). The Nuts and Bolts of Proofs. Academic Press.
• Clapham, C. & Nicholson, J. N. (2009). The Concise Oxford Dictionary of Mathematics (4th изд.). ISBN 978-0199235940.
• Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 978-1-4398-4884-5. Архивирано из оригинала 23. 10. 2015. г. Приступљено 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. стр. 141. ISBN 978-0-03-029558-4.
• Gossett, Eric (2009). Discrete Mathematics with Proof. John Wiley and Sons. стр. 86. ISBN 978-0-470-45793-1.
• Gossett, Eric (2009). Discrete Mathematics with Proof. John Wiley and Sons. стр. 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 одржавање: Вишеструка имена: списак аутора (веза)
• 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. стр. 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 одржавање: Текст вишка: списак аутора (веза)
• 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, ур. (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, ур. (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.

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