Матэматычны доказ

Адзін з найстарэйшых фрагмэнтаў Эўклідавай працы «Элемэнты», падручніка, які захаваўся і выкарыстоўваўся на працягу тысячагодзьдзяў дзеля навучаньня мэтадам напісаньня матэматычных доказаў.

У матэматыцы до́казам называецца ланцуг лягічных вывадаў, які паказвае, што пры якімсьці наборы аксіёмаў і правілаў высновы ёсьць слушным пэўнае сьцьверджаньне. У залежнасьці ад кантэксту, можа мецца на ўвазе доказ у рамках пэўнай фармальнай сыстэмы (пабудаваная па адмысловых правілах пасьлядоўнасьць сьцьверджаньняў, запісаная на фармальнай мове) ці тэкст на натуральнай мове, паводле якога пры жаданьні магчыма аднавіць фармальны доказ. Даказаныя сьцьверджаньні ў матэматыцы называюць тэарэмамі (у матэматычных тэкстах звычайна лічыцца, што доказ кімсьці знойдзены); калі ні сьцьверджаньне, ні яго адмаўленьне яшчэ не даказаныя, тады гэтае сьцьверджаньне называюць гіпотэзай. Часам у працэсе доказу тэарэмы выдзяляюцца доказы меней складаных сьцьверджаньняў, якія завуцца лемамі.

Доказ можа абапірацца на відавочныя або агульнапрынятыя зьявы ці выпадкі, вядомыя як аксіёмы. Доказы зьяўляюцца прыкладамі дэдуктыўнай развагі й адрозьніваюцца ад індуктыўных або эмпірычных аргумэнтаў. Ён павінен прадэманстраваць, што сьцьверджаньне заўсёды дакладна, часам шляхам пералічэньня ўсіх магчымых выпадкаў і паказваючы, што яно дакладнае ў кожным зь іх.

Фармальнымі доказамі займаецца спэцыяльная галіна матэматыкі — тэорыя доказаў. Самі фармальныя доказы матэматыкі амаль ніколі не выкарыстоўваюць, бо для чалавечага ўспрыманьня яны вельмі складаныя й часта займаюць занадта шмат месца. Звычайны доказ мае выгляд тэксту, у якім аўтар, абапіраючыся на аксіёмы й даказаныя раней тэарэмы, з дапамогай лягічных сродкаў паказвае праўдзівасьць некаторага сьцьверджаньня. У адрозьненьне ад іншых навук, у матэматыцы недапушчальныя эмпірычныя доказы, то бок усе сьцьверджаньні даказваюцца выключна лягічнымі спосабамі. У матэматыцы важную ролю гуляюць матэматычная інтуіцыя й аналёгіі паміж рознымі аб’ектамі й тэарэмамі; аднак, усе гэтыя сродкі выкарыстоўваюцца навукоўцамі толькі пры пошуку доказаў, самі доказы ня могуць грунтавацца на такіх сродках.

Мэтады

Довад просты

У простым довадзе выснова выўляецца празь лягічнае спалучэньне аксіёмаў, азначэньняў і раней даказаных тэарэмаў. Напрыклад, разгледзім доказ таго, што сума двух цотных цэлых лікаў таксама цотны:

Кожны з двух цотных цэлых лікаў x і y мы можам вызначыць у выглядзе $x=2a$ і $y=2b$, дзе $a$ і $b$ — некаторыя цэлыя лікі, паколькі $x$ і $y$ дзеляцца на 2. Але тады сума $x+y=2a+2b=2(a+b)$ таксама дзеліцца на 2, таму яна цотная паводле вызначэньня.

Гэты доказ выкарыстоўвае азначэньні цотных цэлых лікаў, уласьцівасьці цэлых лікаў для замыканьня адносна складаньня і множаньня, а таксама разьмеркавальную ўласьцівасьць.

Індуктыўны довад

Не зважаючы на сваю назву, матэматычная індукцыя ёсьць мэтадам дэдукцыі, а ня формай індуктыўнага мысьленьня. У доказе з дапамогай матэматычнай індукцыі даказваецца адзін «базавы выпадак» і «правіла індукцыі», якое сьцьвярджае, што любы зададзены выпадак мае дапушчаць наступны выпадак. Паколькі правіла індукцыі ў прынцыпе можна ўжываць неаднаразова, то бок пачынаючы з даказанага базавага выпадку, з гэтага вынікае, што ўсе, а звычайна бясконцая колькасьць, выпадкаў даказныя. Гэта дазваляе пазьбегнуць неабходнасьці даказваць кожны выпадак асобна. Варыянтам матэматычнай індукцыі ёсьць доказ з дапамогай бясконцага спуску, які можна выкарыстоўваць, напрыклад, дзеля доказу ірацыянальнасьці квадратнага кораня зь ліку 2.

Прыпусьцім, што нам трэба вызначыць справядлівасьць бясконцай пасьлядоўнасьці сьцьверджаньняў, пранумараваных натуральнымі лікамі: $P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots$, ды прыпусьцім што

1. Выяўлена, што $P_{1}$ праўдзівае. Тады гэта сьцьверджаньне называецца асновай індукцыі.
2. Для любога $n$ даказана, што калі $P_{n}$ праўдзівае, тады $P_{n+1}$ таксама праўдзівае. Гэтае сьцьверджаньне называецца індукцыйным пераходам.

Тады ўсе сьцьверджаньні ў нашай пасьлядоўнасьці справядлівыя.

Довад контрапазыцыяй

Мэтад перастаноўкі ўсталёўвае праўдзівасьць сьцьверджаннья «Калі А, тады Б» шляхам доказу эквівалентнага сьцьверджаньня «Калі ня Б, тады ня А».

Довад ад супраціўнага

Гэты мэтад доказу таксама вядомы як довад да абсурду. Доказ сьцьверджаньня А робіцца наступным чынам. Спачатку высоўваецца мяркеваньне, што сьцьверджаньне А ілжывае. Далей даказваецца, што пры такім дапушчэньні нейкае сьцьверджаньне Б, якое загадзя ілжывае, было б праўдзівым. Атрыманая супярэчнасьць выяўляе, што пачатковае дапушчэньне, што сьцьверджаньне А ёсьць ілжывым, насамрэч самое было ілжывым, і таму сьцьверджаньне А праўдзівае, што, паводле закона падвойнага адмаўленьня, эквівалентнае сьцьверджаньню А.

Канструктыўны доказ

Канструктыўны доказ або доказ паводле прыкладу ёсьць мэтадам, павязаным на пабудове канкрэтнага прыкладу з уласьцівасьцямі, мэтай якога ёсьць давесьці, што існуюць прыклады з гэтымі высунутымі ўласьцівасьцямі. Напрыклад, Жазэф Ліўвіль, каб даказаць існаваньне трансцэндэнтных лікаў, відавочна пабудаваў такі лік.

Довад вычарпаньнем

У доказе шляхам вычарпаньня выснова аб праўдзівасьці сьцьверджаньня дасягаецца шляхам дзяленьня сьцьверджаньня на канечную колькасьць выпадкаў і доказу кожнага такога выпадку асобна. Колькасьць такіх выпадкаў можа быць вельмі вялікай. Напрыклад, першы доказ тэарэмы аб чатырох фарбах складаўся з разгляду 1936 выпадкаў. Большасьць з гэтых выпадкаў разглядаліся кампутарнай праграмай, а не чалавекам. Сучасныя, карацейшыя доказы тэарэмы аб чатырох фарбах усё яшчэ патрабуюць разгляду больш за 600 выпадкаў.

Імавернасны довад

Імавернасным довадам уважаецца мэтад, у якім існаваньне прыкладу даводзіцца з дапамогай тэорыі імавернасьцяў. Аднак гэты мэтад ня варта блытаць з аргумэнтам, што тэарэма «верагодна» праўдзівая. Гэты тып аргумэнта называецца «праўдападабенствам» і ня можа ўважацца за доказ. Імавернасны довад поруч з канструктыўным мэтадам ёсьць адным з многіх спосабаў даказаць тэарэму існаваньня.

Камбінаторны довад

Сутнасьць камбінаторнага доваду палягае на вызначэньні эквівалентнасьці розных выразаў, каб яны прадстаўлялі адзін і той жа аб’ект, але па-рознаму. Звычайна біекцыя выкарыстоўваецца, каб давесьці, што дзьве розныя інтэрпрэтацыі даюць адзін і той жа аб’ект.

Неканструктыўны довад

Неканструктыўны доказ усталёўвае, што пэўны матэматычны аб’ект павінен існаваць, то бок высоўваецца нейкі X, які задавальняе ўмове f(X), не тлумачачы, як гэты аб’ект можна выявіць. Часта гэта робіцца шляхам зьвядзеньня да супярэчнасьці сьцьверджаньня, што такі аб’ект не існуе. Наадварот, канструктыўны доказ усталёўвае існаваньне аб’екта, даючы пры гэтым шлях ягонага вызначэньня.

Вядомым прыкладам неканструктыўнага доваду ёсьць доказ існаваньня двух ірацыянальных лікаў $a$ і $b$ такіх, што $a^{b}$ ёсьць лікам рацыянальным.

• Альбо ${\sqrt {2}}^{\sqrt {2}}$ — рацыянальны лік, і ў нас ёсьць прыклад, дзе $a=b={\sqrt {2}}$;
• альбо $({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}={\sqrt {2}}^{2}=2$ выяўляе, што мы маем $a={\sqrt {2}}^{\sqrt {2}}$ та $b={\sqrt {2}}$.

Ані доказу, ані абвяржэньня

Існуе кляса матэматычных сьцьверджаньняў, для якіх няма ані доказу, ані абвяржэньня, то бок доваду доказу ад супраціўнага, у рамках аксіяматызму Цэрмэлё—Фрэнкеля, стандартнай асновы тэорыі мностваў. Прыкладам гэтага ёсьць кантынуўм-гіпотэза. Калі пагадзіцца зь несупярэчлівасьцю аксіёмы Цэрмэлё—Фрэнкеля, існаваньне такіх прыкладаў гарантуецца першай тэарэмай Гёдэля аб няпоўнасьці. Не заўсёды відавочна тое, ці можна даказаць або абвергнуць пэўнае сьцьверджаньне, і для выяўленьня гэтага факту можа спатрэбіцца надзвычайнае тэхнічнае майстэрства.

Элемэнтарны доказ

Элемэнтарнымі ўважаюцца доказы, якія не патрабуюць складанага аналізу. У некаторых выпадках тэарэмы, як то тэарэма аб простым ліку, патрабавалі выкарыстаньня падыходаў вышэйшай матэматыкі. Але зь цягам часу новыя довады былі атрыманыя з выкарыстаньнем элемэнтарных мэтадаў.

Літаратура

•  Cupillari, Antonella The Nuts and Bolts of Proofs: An Introduction to Mathematical Proofs. — Academic Press, 2005. — ISBN 978-0-12-088509-1

Вонкавыя спасылкі

• Proof theory (анг.) Encyclopedia of Mathematics
• Logic (анг.). 2πix.com. Архіўная копія
• Larry W. Cusick How To Write Proofs (анг.)
• ProofWiki.org (анг.)