Доведення (математика)

Математичне доведення (математичний доказ) — процедура у математиці, яка дозволяє встановити істинність гіпотези або будь-якого твердження.

У доведеннях використовується логіка, виражена математичними символами, а також природна мова, яка зазвичай допускає певну неоднозначність. У більшості математичної літератури доведення викладаються з використанням суворої неформальної логіки. Суто формальні докази, написані повністю символічною мовою без використання природної мови, розглядаються в теорії доведень. Відмінність між формальними та неформальними доказами призвела до ретельного вивчення сучасної та історичної математичної практики, квазіемпіризму в математиці та так званої народної математики, усних традицій у основному математичному співтоваристві або в інших культурах. Філософія математики займається роллю мови та логіки в доказах, а також математикою як мовою.

Історія та етимологія

Слово «proof» («доказ») походить від латинського probare — «перевіряти»; до споріднених слів належать англійські probe, probation та probability, а також іспанське probar — «пробувати» (іноді «торкатися» або «перевіряти»),^[2] італійське provare — «пробувати» та німецьке probieren — «пробувати». Юридичний термін «probity» означає авторитет або достовірність, здатність свідчень підтверджувати факти, коли вони надаються особами, які користуються репутацією або мають високий статус.^[3]

Аргументи на користь правдоподібності, що використовували евристичні прийоми, такі як зображення та аналогії, передували строгому математичному доведенню.^[4] Ймовірно, що ідея доведення висновку вперше виникла у зв'язку з геометрією, яка зародилася з практичних проблем вимірювання земельних ділянок.^[5] Розвиток математичного доведення є насамперед надбанням давньогрецької математики.^[6] Фалес (624—546 рр. до н. е.) та Гіппократ Хіоський (бл. 470—410 рр. до н. е.) надали одні з перших відомих доказів теорем у геометрії. Евдокс (408—355 рр. до н. е.) та Теетет (417—369 рр. до н. е.) сформулювали теореми, але не довели їх. Арістотель (384—322 рр. до н. е.) стверджував, що визначення повинні описувати поняття, яке визначається, у термінах інших, вже відомих понять.

Евклід (300 до н. е.) здійснив революцію в математичному доведенні, запровадивши аксіоматичний метод, який використовується й донині. Він починається з невизначених термінів та аксіом — тверджень щодо цих термінів, які вважаються самоочевидними істинами (від грецького axios — «щось варте уваги»). На цій основі метод доводить теореми за допомогою дедуктивної логіки. «Начала» Евкліда читав кожен, кого на Заході вважали освіченою людиною, аж до середини XX століття.^[7] Окрім геометричних теорем, таких як теорема Піфагора, «Начала» також охоплюють теорію чисел, включаючи доказ того, що квадратний корінь з двох є ірраціональним, та доказ того, що існує нескінченно багато простих чисел.

Подальші досягнення відбулися також у середньовічній ісламській математиці. У X столітті іракський математик Аль-Хашімі працював з числами як такими, які називалися «лініями», але не обов'язково розглядалися як виміри геометричних об'єктів, щоб довести алгебраїчні твердження щодо множення, ділення тощо, зокрема існування ірраціональних чисел.^[8] Індуктивний доказ арифметичних прогресій був представлений у Аль-Фахрі (1000) аль-Караджі, який використав його для доведення біноміальної теореми та властивостей трикутника Паскаля.

Сучасна теорія доказів розглядає докази як індуктивно визначені структури даних, не вимагаючи припущення, що аксіоми є «істинними» в будь-якому сенсі. Це дозволяє розглядати паралельні математичні теорії як формальні моделі певної інтуїтивної концепції, що ґрунтуються на альтернативних наборах аксіом, наприклад, аксіоматичну теорію множин та неевклідову геометрію.

Сутність та призначення

Як правило, доказ викладається природною мовою і являє собою строгий аргумент, покликаний переконати слухачів у істинності твердження. Критерії строгості не є абсолютними і змінювалися протягом історії. Доказ може бути викладений по-різному залежно від цільової аудиторії. Щоб бути прийнятим, доказ має відповідати загальноприйнятим стандартам строгості; аргумент, який вважається нечітким або неповним, може бути відхилений.

Поняття доведення формалізовано в галузі математичної логіки.^[9] Формальне доведення записується формальною мовою, а не природною. Формальне доведення — це послідовність формул формальною мовою, що починається з припущення, а кожна наступна формула є логічним наслідком попередніх. Це визначення робить поняття доведення доступним для вивчення. Дійсно, галузь теорії доведення вивчає формальні доведення та їхні властивості, найвідомішою та найдивовижнішою з яких є те, що майже всі аксіоматичні системи можуть породжувати певні нерозв'язні твердження, які неможливо довести в межах системи.

Визначення формального доведення покликане відобразити поняття доведення у тому вигляді, в якому воно викладається в математичній практиці. Обґрунтованість цього визначення полягає в переконанні, що опублікований доказ, в принципі, можна перетворити на формальний доказ. Однак поза сферою автоматизованих систем доведення це на практиці робиться рідко. Класичне питання у філософії полягає в тому, чи є математичні докази аналітичними чи синтетичними. Кант, який запровадив розрізнення між аналітичним і синтетичним, вважав, що математичні докази є синтетичними, тоді як Квайн у своїй праці 1951 року «Дві догми емпіризму» стверджував, що таке розрізнення є необґрунтованим.^[10]

Доведення можна захоплюватися їхнью математичну красу. Математик Пал Ердеш був відомий тим, що описував доведення, які він вважав особливо витонченими, як такі, що походять з «Книги» — гіпотетичного фоліанта, що містить найгарніші методи доведення кожної теореми. Книга «Доведення з Книги», видана у 2003 році, присвячена представленню 32 доведень, які її редактори вважають особливо привабливими.

Математичне доведення

У математиці доведенням називається ланцюжок логічних висновків, який показує, що при якомусь наборі аксіом і правил висновування є правильним деяке твердження. Залежно від контексту, може матися на увазі формальне доведення (побудована за спеціальними правилами послідовність тверджень, записана формальною мовою) або текст природною мовою, за яким за бажанням можна відновити формальний доказ. Доказові твердження в математиці називають теоремами (у математичних текстах зазвичай мається на увазі, що доказ знайдений певною особою; виняток з цього звичаю в основному складають роботи з логіки, в яких досліджується саме поняття доказу); якщо ані твердження, ані його заперечення ще не доведені, то таке твердження називають гіпотезою. Іноді в процесі доведення теореми виділяються докази менш складних допоміжних тверджень, званих лемами.

Формальними доведеннями займається спеціальна гілка математики — теорія доведення. Самі формальні докази математики майже ніколи не використовують, оскільки для людського сприйняття вони достатньо складні й часто займають багато місця. Звичайний доказ має вид тексту, в якому автор, спираючись на аксіоми та доведені раніше теореми, за допомогою логічних засобів показує істинність деякого твердження. На відміну від інших наук, в математиці недопустимі емпіричні докази: всі твердження доводяться виключно логічними способами. У математиці важливу роль грають математична інтуїція та аналогії між різними об'єктами й теоремами; проте, всі ці засоби використовуються вченими тільки при пошуку доказів, самі докази не можуть ґрунтуватися на таких засобах. Докази, написані на природних мовах, можуть бути не зовсім докладними з розрахунку на те, що підготовлений читач сам зможе відновити деталі. Строгість доказу гарантується тим, що його можна представити у вигляді запису формальною мовою (це і відбувається при комп'ютерній перевірці доказів).

Помилковим доказом називається текст, що містить логічні помилки, тобто такий, за яким не можна відновити формальний доказ. У історії математики були випадки, коли видатні учені публікували невірні «докази», проте зазвичай їхні колеги або вони самі досить швидко знаходили помилки. (Одна з теорем, що найчастіше неправильно доводилася, — Велика теорема Ферма. Досі трапляються люди, що не знають про те, що вона доведена, і пропонують нові невірні «докази»). Помилковим може бути тільки визнання «доказу» на природній або формальній мові. Формальний доказ помилковим не може бути за визначенням.

У математиці існують невирішені проблеми, рішення яких ученим дуже хотілося б знайти. За докази особливо цікавих і важливих тверджень математичні товариства призначають премії.

Формальне доведення

Докладніше: Формальне доведення

Коли говорять про формальне доведення, то спершу описують формальну систему — набір (або множину) аксіом, записаних за допомогою формальної мови, і правил висновування. Формальним виводом називається скінчена впорядкована множина рядків, написаних формальною мовою, таких, що кожна з них або є аксіомою, або отримана з попередніх рядків застосуванням одного з правил виводу.

Формальним доведенням твердження називається формальний вивід, останнім рядком якого є дане твердження.

Твердження, що має формальний доказ, називається теоремою, а множина всіх теорем в даній формальній моделі (що розглядається разом з алфавітом формальної мови, множиною аксіом і правил виводу) називається формальною теорією.

Теорія називається повною, якщо для будь-якого твердження доведено або воно, або його заперечення, і несуперечливою, якщо в ній не існує тверджень, які можна довести разом з їхніми запереченнями. Більшість математичних теорій, як показує перша теорема Геделя про неповноту, є неповними, тобто в них існують твердження, про істинність яких нічого сказати не можна. Найпоширенішим набором аксіом у наш час є аксіоматика Цермело — Френкеля з аксіомою вибору (хоча деякі математики виступають проти використання останньої). Теорія на основі цієї системи аксіом не повна (наприклад, континуум-гіпотеза не може бути ані доведена, ані спростована в ній). Не зважаючи на повсюдне використання цієї теорії в математиці, її несуперечність не може бути доведена методами її самої. Проте, переважна більшість математиків вірять в її несуперечність, вважаючи, що інакше суперечності вже давно були б виявлені.

Методи доказів

Пряме доведення

Докладніше: Пряме доведення

При прямому доведенні висновок встановлюється через логічну комбінацію аксіом, визначень і раніше доведених теорем.^[11] Для прикладу розглянемо доведення, що сума двох парних цілих чисел також є парною:

кожне з двох парних чисел x та y ми можемо за визначенням записати у вигляді x = 2a та y = 2b, де a і b — деякі цілі числа, бо x та y діляться на 2. Але тоді сума x + y = 2a + 2b = 2(a + b) також ділиться на 2, так що вона є парною за визначенням.

У цьому доведенні використовуються визначення парних цілих чисел, властивості цілих чисел на замкнутість при додаванні та множенні, а також дистрибутивна властивість.

Індуктивне доведення

Докладніше: Математична індукція

Незважаючи на свою назву, математична індукціяє методом дедукції, а не форма індуктивного мислення. У доведенні за допомогою математичної індукції доводиться один «базовий випадок» і «правило індукції», яке встановлює, що будь-який довільний випадок передбачає наступний випадок. Оскільки в принципі правило індукції можна застосовувати багаторазово (починаючи з доведеного базового випадку), з цього випливає, що всі (зазвичай нескінченно багато) випадки є доказовими.^[12] Це дозволяє уникнути необхідності доводити кожен випадок окремо. Варіантом математичної індукції є доведення нескінченним спуском, яке можна використовувати, наприклад, для доведення ірраціональності квадратного кореня з двох.

Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, занумерованих натуральними числами: $P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots$ . Припустимо, що

Встановлене, що P₁ вірно. (Це твердження називається базою індукції.)
Для будь-якого n доведено, що якщо вірно P_n, то вірно P_{n + 1}. (Це твердження називається індукційним переходом.)

Тоді всі твердження нашої послідовності вірні.

Доведення контрапозицією

Докладніше: Контрапозиція

Метод перестановки встановлює істинність твердження «Якщо А, то Б» доведенням еквівалентного твердження «Якщо не Б, то не А».

Доведення від зворотного

Докладніше: Доведення від супротивного

Цей метод доведення відомий також як приведення до абсурду (лат. reductio ad absurdum). Доказ твердження A проводиться таким чином: спочатку приймають припущення, що твердження A хибне; доводять, що за такого припущення було б істинне деяке твердження B, яке заздалегідь хибне; отримана суперечність показує, що початкове припущення («твердження A хибне») було хибним, і тому істинне твердження ¬¬A, яке за законом подвійного заперечення рівносильно твердженню A.

Конструктивне доведення

Докладніше: Конструктивне доведення

Конструктивне доведення або доведення наданням прикладу — це конструювання конкретного прикладу з властивостями, мета якого — довести, що існують приклади з цими властивостями. Наприклад, Жозеф Ліувілль, для того, щоб довести існування трансцендентних чисел, явно сконструював таке число.

Доведення вичерпуванням

Докладніше: Доведення вичерпуванням

При доведенні методом вичерпування висновок про істинність твердження досягається розділенням твердження на скінчену кількість випадків і доведенням кожного такого випадку окремо. Кількість таких випадків може бути дуже великою. Наприклад, перший доказ проблеми чотирьох фарб складався з розгляду 1936 випадків. Більшість цих випадків розглядала комп'ютерна програма, а не людина.^[13] Сучасніші коротші докази теореми про чотири фарби все одно вимагають розгляду понад 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}}$ .

Ані доказу, ані заперечення

Існує клас математичних тверджень, для яких не існує ані доказу, ані спростування (тобто доведення зворотного твердження) в рамках аксіоматики Цермело — Френкеля, стандартної основи теорії множин. Як приклад можна навести континуум-гіпотезу. Якщо погодитися з непротиречивістю аксіом Френкеля — Цермело, існування таких прикладів нам гарантує перша теорема неповноти Геделя. Чи можна довести певне твердження, чи його спростування — не завжди очевидно і може вимагати надзвичайної техніки для встановлення цього факту.

Елементарне доведення

Елементарним доведенням називають докази, що не потребують складного аналізу.

В деяких випадках теореми, як, наприклад теорема про асимптотичний розподіл простих чисел, вимагала застосування «вищої» математики. Але з часом були отримані нові докази з використанням елементарної техніки.

Нерозв'язні твердження

Твердження, яке не можна ні довести, ні спростувати з набору аксіом, називається нерозв'язним (з точки зору цих аксіом). Одним із прикладів є постулат паралельності, який не можна довести або спростувати на основі решти аксіом евклідової геометрії.

Математики показали, що в теорії множин Цермело-Френкеля з аксіомою вибору (ZFC) — стандартній системі теорії множин у математиці — існує чимало тверджень, які неможливо ані довести, ані спростувати (за умови, що ZFC є суперечливою).

(Перша) теорема Геделя про неповноту доводить, що в багатьох аксіоматичних системах, які представляють математичний інтерес, існують твердження, які неможливо вирішити.

Закінчення доказу

Традиційно завершення доказу позначалося абревіатурою «Q.E.D.», від латинського виразу лат. Quod Erat Demonstrandum, Що і треба було довести.

Зараз для позначення того ж завершення доведення частіше використовується знак □ або ∎, що можна з іронією інтерпретувати як надгробний камінь.

Іноді для позначення кінця доведення використовується абревіатура «QED». Ця абревіатура розшифровується як «quod erat demonstrandum», що з латинської означає «те, що мало бути продемонстровано». Більш поширеною альтернативою є використання квадрата або прямокутника, наприклад □ або ■, відомого як «надгробний камінь» або «символ Халмоша» на честь його епоніма Пола Халмоша. Часто під час усного викладу при написанні «QED», «□» або «■» усно зазначається «що мало бути доведено». Unicode чітко вказує символ «кінець доведення», U+220E (■) (220E(hex) = 8718(dec)).

Див. також

Примітки

↑ Bill Casselman. One of the Oldest Extant Diagrams from Euclid. University of British Columbia. Процитовано 26 вересня 2008.
↑ «proof» New Shorter Oxford English Dictionary, 1993, OUP, Oxford.
↑ Hacking, Ian (1984). The Emergence of Probability: A Philosophical Study of Early Ideas about Probability, Induction and Statistical Inference. Cambridge University Press. ISBN 978-0-521-31803-7.
↑ The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
↑ Kneale, William; Kneale, Martha (Травень 1985). The development of logic (вид. New). Oxford University Press. с. 3. ISBN 978-0-19-824773-9.
↑ Moutsios-Rentzos, Andreas; Spyrou, Panagiotis (Лютий 2015). The genesis of proof in ancient Greece The pedagogical implications of a Husserlian reading. Archive ouverte HAL. Процитовано 20 жовтня 2019.
↑ Eves, Howard W. (Січень 1990). An Introduction to the History of Mathematics (Saunders Series) (вид. 6th). Cengage. с. 141. ISBN 978-0030295584. No work, except The Bible, has been more widely used...
↑ Matvievskaya, Galina (1987), The Theory of Quadratic Irrationals in Medieval Oriental Mathematics, Annals of the New York Academy of Sciences, 500 (1): 253–277 [260], Bibcode:1987NYASA.500..253M, doi:10.1111/j.1749-6632.1987.tb37206.x
↑ Buss, Samuel R. (1998), An introduction to proof theory, у Buss, Samuel R. (ред.), Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics, т. 137, Elsevier, с. 1—78, ISBN 978-0-08-053318-6. See in particular p. 3: «The study of Proof Theory is traditionally motivated by the problem of formalizing mathematical proofs; the original formulation of first-order logic by Frege [1879] was the first successful step in this direction.»
↑ Quine, Willard Van Orman (1961). Two Dogmas of Empiricism (PDF). Universität Zürich – Theologische Fakultät. с. 12. Процитовано 20 жовтня 2019.
↑ Cupillari, p. 20.
↑ Cupillari, p. 46.
↑ See Four color theorem#Simplification and verification.

Література

Доведення // Філософський енциклопедичний словник / В. І. Шинкарук (гол. редкол.) та ін ; Інститут філософії імені Григорія Сковороди НАН України. — Київ : Абрис, 2002. — 742 с. — 1000 екз. — ББК 87я2. — ISBN 966-531-128-X.
Правила доведення // ФЕС, с.507

Посилання

Довід // Універсальний словник-енциклопедія. — 4-те вид. — К. : Теза, 2006.

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] Bill Casselman. One of the Oldest Extant Diagrams from Euclid. University of British Columbia. Процитовано 26 вересня 2008.

[2] «proof» New Shorter Oxford English Dictionary, 1993, OUP, Oxford.

[3] Hacking, Ian (1984). The Emergence of Probability: A Philosophical Study of Early Ideas about Probability, Induction and Statistical Inference. Cambridge University Press. ISBN 978-0-521-31803-7.

[Krantz-4] The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007

[5] Kneale, William; Kneale, Martha (Травень 1985). The development of logic (вид. New). Oxford University Press. с. 3. ISBN 978-0-19-824773-9.

[6] Moutsios-Rentzos, Andreas; Spyrou, Panagiotis (Лютий 2015). The genesis of proof in ancient Greece The pedagogical implications of a Husserlian reading. Archive ouverte HAL. Процитовано 20 жовтня 2019.

[7] Eves, Howard W. (Січень 1990). An Introduction to the History of Mathematics (Saunders Series) (вид. 6th). Cengage. с. 141. ISBN 978-0030295584. 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 (1): 253–277 [260], Bibcode:1987NYASA.500..253M, doi:10.1111/j.1749-6632.1987.tb37206.x

[9] Buss, Samuel R. (1998), An introduction to proof theory, у Buss, Samuel R. (ред.), Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics, т. 137, Elsevier, с. 1—78, ISBN 978-0-08-053318-6. See in particular p. 3: «The study of Proof Theory is traditionally motivated by the problem of formalizing mathematical proofs; the original formulation of first-order logic by Frege [1879] was the first successful step in this direction.»

[10] Quine, Willard Van Orman (1961). Two Dogmas of Empiricism (PDF). Universität Zürich – Theologische Fakultät. с. 12. Процитовано 20 жовтня 2019.

[11] Cupillari, p. 20.

[12] Cupillari, p. 46.

[13] See Four color theorem#Simplification and verification.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]