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

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

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

Слово «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] Це дозволяє уникнути необхідності доводити кожен випадок окремо. Варіантом математичної індукції є доведення нескінченним спуском, яке можна використовувати, наприклад, для доведення ірраціональності квадратного кореня з двох.

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

1. Встановлене, що P₁ вірно. (Це твердження називається базою індукції.)
2. Для будь-якого 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 є числом раціональним.

• Або ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ є раціональним числом і ми маємо приклад (де ${\displaystyle a=b={\sqrt {2}}}$),
• або ж ${\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}={\sqrt {2}}^{2}=2}$ показує, що ми маємо ${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ та ${\displaystyle b={\sqrt {2}}}$.

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

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

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

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

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

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

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

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

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

• Математична логіка
• Доказ
• Бієктивне доведення
• Математичний софізм
• Конструктивне доведення
• Уявний експеримент
• Доведення з нульовим розголошенням
• Що Черепаха сказала Ахіллові

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

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