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

P. Oxy. 29, один із найстаріших збережених фрагментів Начал Евкліда, підручника який тисячу років був взірцем техніки математичних доведень.

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

Принципи доведення вивчаються у спеціальній галузі математики — теорії доведень.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цей доказ використовує визначення парних цілих чисел, і також дистрибутивний закон додавання.

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

Припустимо, що потрібно встановити справедливість нескінченної послідовності тверджень, занумерованих натуральними числами: $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 випадків. Більшість цих випадків розглядала комп'ютерна програма, а не людина. Сучасніші коротші докази теореми про чотири фарби все одно вимагають розгляду понад 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}}$.

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

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

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

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

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

Що і треба було довести

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

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

Див. також

• Математична логіка
• Доказ
• Бієктивне доведення

Література

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

Посилання

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