Математическое доказательство

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Математическое доказательство — цепочка логических умозаключений, показывающая, что при каком-то наборе аксиом и правил вывода верно некоторое утверждение. В зависимости от контекста, может иметься в виду доказательство в рамках некоторой формальной системы (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при необходимости можно восстановить формальное доказательство. Необходимость формального доказательства утверждений — одна из основных характерных черт математики как дедуктивной отрасли знаний, соответственно, понятие доказательства играет центральную роль в предмете математики[⇨], а наличие доказательств и их корректность определяют статус любых математических результатов[⇨].

На протяжении всей истории математики[⇨] представление о способах и допустимых методах доказательства существенно менялось, в основном, в сторону большей формализации и бо́льших ограничений. Ключевой вехой в вопросе формализации доказательства стало создание математической логики[⇨] в XIX веке и формализация её средствами основных техник доказательства. В XX веке построена теория доказательств — теория, изучающая доказательство как математический объект[⇨]. С появлением во второй половине XX века компьютеров особое значение получило применение методов математического доказательства для проверки и синтеза программ[⇨], и даже было установлено структурное соответствие между компьютерными программами и математическими доказательствами (соответствие Карри — Ховарда[⇨]), на основе которого созданы средства автоматического доказательства[⇨].

Основные приёмы, используемые при построении доказательств: прямое доказательство[⇨], математическая индукция и её обобщения[⇨], доказательство от противного[⇨], контрапозиция[⇨], построение[⇨], перебор[⇨], установление биекции[⇨], двойной счёт[⇨]; в приложениях в качестве математических доказательств привлекаются также методы, не дающие формального доказательства, но обеспечивающие практическую применимость результата[⇨] — вероятностные, статистические, приближённые. В зависимости от раздела математики, используемого формализма или математической школы не все методы могут приниматься безоговорочно, в частности, конструктивное доказательство[⇨] предполагает серьёзные ограничения.

Значение доказательства в математике[править | править исходный текст]

В отличие от других наук, в математике недопустимы эмпирические доказательства: все утверждения доказываются исключительно логическими способами. В математике важную роль играют математическая интуиция и аналогии между разными объектами и теоремами; тем не менее, все эти средства используются учёными только при поиске доказательств, сами доказательства не могут основываться на таких средствах. Доказательства, написанные на естественных языках, могут быть не очень подробными в расчёте на то, что подготовленный читатель сам сможет восстановить детали. Строгость доказательства гарантируется тем, что его можно представить в виде записи на формальном языке (это и происходит при компьютерной проверке доказательств).

Статус утверждений[править | править исходный текст]

Доказанные утверждения в математике называют теоремами (в математических текстах обычно подразумевается, что доказательство кем-либо найдено; исключения из этого обычая в основном составляют работы по логике, в которых исследуется само понятие доказательства); если ни утверждение, ни его отрицание ещё не доказаны, то такое утверждение называют гипотезой. Иногда в процессе доказательства теоремы выделяются доказательства менее сложных утверждений, называемых леммами.

Ошибочным доказательством называется текст, содержащий логические ошибки, то есть такой, по которому нельзя восстановить формальное доказательство. В истории математики были случаи, когда выдающиеся учёные публиковали неверные «доказательства», однако обычно их коллеги или они сами довольно быстро находили ошибки (одна из наиболее часто неправильно доказывавшихся теорем — Великая теорема Ферма. До сих пор встречаются люди, не знающие о том, что она доказана, и предлагающие новые неверные «доказательства»[1][2]). Ошибочным может быть только признание доказательством «доказательства» на естественном или формальном языке; формальное доказательство ошибочным не может быть по определению.

История[править | править исходный текст]

Античность[править | править исходный текст]

В странах Древнего Востока (Вавилоне, Древнем Египте, Древнем Китае) решение математических задач приводилось, как правило, без обоснования и было догматичным, хотя графическое обоснование теоремы Пифагора можно встретить на вавилонских клинописных табличках[3]. Понятия доказательства не существовало и в Древней Греции в VIII—VII веках до н. э. Однако уже в VI веке до н. э. в Греции логическое доказательство становится основным методом установления истины. В это время были построены первые математические теории и математические модели мира, которые имели вполне современный вид, то есть строились из конечного числа посылок с помощью логических умозаключений.

Первые доказательства использовали простейшие логические построения. В частности Фалес Милетский, доказавший что диаметр делит круг пополам, углы при основании равнобедренного треугольника равны, две пересекающиеся прямые образуют равные углы, видимо, использовал в своих доказательствах методы перегибания и наложения фигур. По словам греческого философа Прокла (V век н. э.) «Иногда он рассматривал вопрос несколько общо, иногда опираясь на наглядность». Уже при Пифагоре доказательство переходит от конкретных представлений к чисто логическим заключениям[4]. В доказательствах Парменида используется закон исключённого третьего, а его ученик Зенон в апориях пользуется приведением к абсурду[5].

Известно, что доказательство несоизмеримости стороны и диагонали квадрата, которое является основой понятия иррациональности, скорее всего принадлежит пифагорейцам, хотя впервые приведено лишь в Началах Евклида (X), происходит от противного и основано на теории делимости чисел на два[6]. Возможно, что расхождение во взглядах на роль математического доказательства явилось одной из причин конфликта между Евдоксом (считающимся основателем традиции организации математики в виде теорем, но принципиально не прибегавшего к доказательствам[7]) и Платоном[8].

Важным моментам на пути к будущей формализации математических доказательств стало создание Аристотелем логики, в которой он попытался систематизировать и кодифицировать все правила рассуждений, используемые для доказательств, описал основные возникающие сложности и двусмысленности. Аристотель предполагал доказательства важной составляющей науки, считая, что доказательство «выявляет сущность вещей»[9]. Но непосредственного влияния на древнегреческую математику аристотелева логика не оказала, и вопросам формальной логики в доказательствах внимания не уделяли[10].

Средневековье и Новое время[править | править исходный текст]

С развитием математики в Средневековье и воспринятой из схоластики опорой на логику постепенно выстраиваются представления о формальном доказательстве и развиваются его методы. К Герсониду относят обоснование и введение в практику метода математической индукции[11]. С XVI века отмечаются отдельные попытки критического осмысления доказательств древнегреческих математиков, например Пелетье (фр. Jacques Peletier du Mans), комментируя «Начала» Евклида, критикует доказательство равенства треугольников перемещением[12].

К Новому времени благодаря успехам применения математики в естественных науках математические утверждения и доказательства считались надёжными, как только дано точное и формальное определение исходных понятий, и математика в целом считалась образцом строгости и доказательности для всех прочих дисциплин. В частности, Лейбниц считает аксиомы и правила вывода незыблемыми и стремится построить формальную систему логики, чтобы «доказать всё доказуемое»[13]. Однако, даже в XVIII веке понятие доказательства было всё ещё слишком неформализованным и умозрительным, свидетельством тому может быть факт того, что Эйлер считал обосновываемыми одновременно следующие утверждения:

\sum_{n=0}^\infty {1 - (n \operatorname{mod} 2) \cdot 2} = 0 и \sum_{n=1}^\infty {1 - (n \operatorname{mod} 2) \cdot 2} = 1,

а также:

\sum_{n=0}^\infty {2^n} = -1,

понимая, естественно, бессмысленность этих утверждений, но считая их «доказуемость» парадоксами[14].

В XIX веке всё чаще возникают идеи необходимости постулирования некоторых интуитивно очевидных правил, которые формальным способом доказать невозможно. Яркий пример — принцип Дирихле, согласно которому в любом наборе из n совокупностей, содержащих в общей сложности более n элементов, есть хотя бы одна, содержащая более одного элемента (наиболее известная формулировка — «если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика»), не прибегая к этому принципу, как выяснил Дирихле, невозможно строго доказать многие важные теоретико-числовые и комбинаторные утверждения[15]. Ещё одним толчком к пониманию относительности доказательств в зависимости от постулируемых принципов стало после многих веков неуспешных попыток доказать аксиому параллельности Евклида создание Лобачевским, Бойяи, Гауссом и Риманом неевклидовых геометрий[16].

Формализация логики и программа Гильберта[править | править исходный текст]

Интуиционизм[править | править исходный текст]

Теоремы о неполноте[править | править исходный текст]

Конструктивизм[править | править исходный текст]

Формальное доказательство[править | править исходный текст]

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

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

Теория доказательств[править | править исходный текст]

Формальными доказательствами занимается специальная ветвь математики — теория доказательств. Сами формальные доказательства математики почти никогда не используют, поскольку для человеческого восприятия они очень сложны и часто занимают очень много места.

В информатике[править | править исходный текст]

В информатике математические доказательства используются для верификации и анализа правильности алгоритмов и программ. см. логика в информатике) в рамках технологий доказательного программирования.

Методы формального доказательства[править | править исходный текст]

Прямое доказательство[править | править исходный текст]

Прямое доказательство[en] предусматривает применение только непосредственного дедуктивного вывода из считающихся верными утверждений (аксиом, ранее доказанных лемм и теорем), без использования суждений с отрицанием каких-либо утверждений[17]. Например, для прямого доказательства считаются приемлемым следующие фигуры (в нотации натурального вывода[en]:

\frac{A, B}{A}, \frac{A \Rightarrow B, B \Rightarrow C}{A \Rightarrow C}, \frac{A, A \Rightarrow B}{B} (modus ponens).

Также методом прямого доказательства считается и подстановка: если утверждение A верно для любых значений входящих в него свободных переменных, то подстановка каких-либо конкретных значений вместо какого-нибудь подмножества из них во всех вхождениях (частный случай формулы) даёт верное утверждение, в нотации натурального вывода (неформальная запись, упрощено до одной переменной):

\frac{\forall x \, A(x)}{A[x:=a]}

В некоторых случаях непрямые доказательства, использующие рассуждения с отрицанием, особенно, относительно конечных объектов, могут быть простым образом сведены к прямым без ущерба общности, но относительно утверждений о бесконечных совокупностях это далеко не всегда так, и с ростом ценности конструктивных доказательств в математике XX века считается важным найти прямое доказательство для утверждений, считавшихся доказанными, но непрямыми методами.

В теории доказательств разработано формальное определение прямого доказательства[18].

Индукция[править | править исходный текст]

Индуктивный метод, позволяющий перейти от частных утверждений ко всеобщим, наиболее интересен в применении к бесконечным совокупностям объектов, но её формулировки и применимость существенно отличаются в зависимости от сферы применения.

Простейший индуктивный метод[19] — математическая индукция, умозаключение относительно натурального ряда, идея которого в утверждении некоторого закона для всех натуральных чисел, исходя из фактов его выполнения для единицы и следования истинности для каждого последующего числа, в нотации натурального вывода:

\frac{P(1), \forall n\in \mathbb N (P(n) \Rightarrow P(n+1))}{\forall n \in \mathbb N (P(n))}.

Метод математической индукции естественным образом может быть применён для любых счётных совокупностей объектов, считается надёжным и легитимным как в классических, так и в интуиционистских и конструктивных системах доказательств. Метод аксиоматизируется в системе аксиом арифметики Пеано.

Более сложный вопрос состоит в возможности распространения индуктивного метода на несчётные совокупности. В рамках наивной теории множеств создан метод трансфинитной индукции, позволяющий распространить индуктивное правило вывода для любых вполне упорядоченных множеств по схеме, сходной с математической индукцией. Найдена возможность применения индуктивноподобного рассуждения для несчётных совокупностей и в интуиционистской логике, известная как бар-индукция[en][20].

Существует конструктивный метод структурной индукции, позволяющий применять индукцию по отношению ко вполне упорядоченным совокупностям объектов, но при условии их рекурсивного определения.

От противного[править | править исходный текст]

Доказательство от противного использует логический приём доведения до абсурда и строится по следующей схеме: чтобы доказать утверждение A предполагается, что оно неверно, а затем по дедуктивной цепочке приходят к заведомо ложному утверждению, например, B \land \neg B, из чего согласно закону двойного отрицания делается вывод об истинности A, в нотации натурального вывода:

\frac{\neg A \Rightarrow (B \land \neg B)}{A}.

В интуиционистских и конструктивных системах доказательство от противного не используется, так как не принимается закон двойного отрицания.

Контрапозиция[править | править исходный текст]

Контрапозиционное доказательство[en] использует закон контрапозиции и состоит в следующем: для доказательства факта, что из утверждения A следует B требуется показать, что из отрицания B следует отрицание A, в символике натурального вывода:

\frac{\neg B \Rightarrow \neg A}{A \Rightarrow B}.

Контрапозиционное доказательство сводится к методу от противного[⇨]: для доказательства A \Rightarrow B проверяется его отрицание \neg (A \Rightarrow B) \equiv \ A \land \neg B, а так как имеет место посылка \neg B \Rightarrow \neg A \equiv A \land \neg B выявляется противоречие.

В качестве примера контрапозиционного доказательства приводится[21] установление факта, что если n^2 нечётно, то n также нечётно (n \in \mathbb N), для этого доказывается контрапозиция, что если n — чётно, то n^2 также чётно.

В системах, не принимающих закон двойного отрицания, контрапозиционное доказательство не применяется.

Построение[править | править исходный текст]

Для утверждений типа теорем существования, в которых формулируется в качестве результата наличие какого-либо объекта, например, существование числа, удовлетворяющего каким-либо условиям, наиболее характерный тип доказательства — непосредственное нахождение искомого объекта с использованием методов соответствующей формальной системы или контексту соответствующего раздела. Многие классические теоремы существования доказаны от противного: приведением к абсурду предположения о несуществовании объекта с заданными свойствами, но такие доказательства считаются неконструктивными, и, соответственно, в интуиционистской и конструктивной математике для такого рода утверждений используются только доказательства построением.

Исчерпывание вариантов[править | править исходный текст]

В некоторых случаях для доказательства утверждения перебираются все возможные варианты совокупности, относительно которой сформулировано утверждение (грубый перебор) или все возможные варианты разбиваются на конечное число классов, представляющих частные случаи, и относительно каждого из которых доказательство проводится отдельно. Как правило, доказательство методом исчерпывания вариантов[en], состоит из двух этапов:

  1. установления всех возможных частных случаев, и доказательства, что других частных случаев нет,
  2. доказательство каждого частного случая.

Количество вариантов может быть достаточно велико, например, при для доказательства гипотезы четырёх красок потребовалось перебрать почти 2 тыс. различных вариантов с помощью компьютера. Появление такого рода доказательств в конце XX века в связи с развитием вычислительной техники, подняли вопрос об их статусе в математической науке из-за возможных проблем с проверяемостью[22].

Биекция[править | править исходный текст]

Доказательство методом установления биекции[en] применяется для установления утверждений о размере или структуре совокупности или сопоставимости совокупности с какой-либо другой совокупностью и состоит в построении взаимно-однозначного соответствия между изучаемым множеством A и множеством с известными свойствами B[23]. Иными словами, доказательство утверждений о некоей совокупности сводится к доказательству построением биекции, возможно, с дополнительными ограничениями, с совокупностью, для которой это утверждение известно.

Простейшие примеры биективных доказательств — доказательства комбинаторных утверждений о числе сочетаний или количестве элементов множеств, более сложные примеры — установление изоморфизмов, гомеоморфизмов, диффеоморфизмов, биморфизмов, за счёт чего на изучаемый объект или совокупность A переносятся свойства уже известного объекта B, инвариантные по отношению к тому или специальному виду биекции.

Двойной счёт[править | править исходный текст]

Геометрическое доказательство[править | править исходный текст]

Геометрическое доказательство теоремы Пифагора

Прикладные методы[править | править исходный текст]

Приближённые методы[править | править исходный текст]

Вероятностные методы[править | править исходный текст]

Статистические методы[править | править исходный текст]

Терминология[править | править исходный текст]

Символы[править | править исходный текст]

Традиционно окончание доказательства обозначалось сокращением «Q.E.D.», от латинского выражения лат. Quod Erat Demonstrandum («Что и требовалось доказать»). В современных трудах для обозначения окончания доказательства чаще используется знак или , , //, а также русская аббревиатура «ч. т. д.».

Примечания[править | править исходный текст]

  1. Гастев Ю., Смолянский М. Несколько слов о Великой теореме Ферма // Квант. — 1972. — Т. 8. — С. 23-25.
  2. Цымбалов А. С. Теорема Ферма. Доклад на конференцию(недоступная ссылка — история). Современная гуманитарная академия. Проверено 14 мая 2011. Архивировано из первоисточника 30 марта 2009.}
  3. Кранц, 2011, The Babylonians had certain diagrams that indicate why the Pythagorean theorem is true, and tablets have been found to validate this fact, p. 44
  4. История математики, том I, 1970, с. 65—66
  5. Бурбаки, 1963, с. 11
  6. История математики, том I, 1970, с. 73
  7. Кранц, 2011, <…> Eudoxus who began the grand tradition of organizing mathematics into theorems <…> What Eudoxus gained in the rigor and precision of his mathematical formulations, he lost because he did not prove anything, p. 44—45
  8. История математики, том I, 1970, с. 95
  9. История математики, том I, 1970, с. 59—61
  10. Бурбаки, 1963, Труды Аристотеля и его преемников, по-видимому, не оказали заметного влияния на математику. Греческие математики в своих исследованиях шли по пути, предложенному пифагорейцами и их последователями в IV в. (Теодором, Теэтетом, Евдоксом), и мало интересовались формальной логикой при изложении своих результатов, с. 12—14
  11. Rabinovich, N. L. Rabbi Levi ben Gershom and the origins of mathematical induction // Archive for History of Exact Sciences. — 1970. — В. 6. — С. 237-248.
  12. Бурбаки, 1963, с. 27
  13. Бурбаки, 1963, с. 22
  14. Кранц, 2011, 3.1. Euler and the Profundity of Intuition, p. 74—75
  15. Кранц, 2011, 3.3. The Pigeonhole Principle, p. 79—81
  16. Бурбаки, 1963, с. 25—26
  17. Хаммак, 2009, Chapter 4. Direct proof, с. 95—109
  18. Справочная книга по математической логике, том IV, 1983, Глава 3. Стетмен Р. Теорема Эрбрана и генценовское понятие прямого доказательства, с. 84-99
  19. Хаммак, 2009, Chapter 10. Mathematical Induction, с. 152—154
  20. Математическое доказательство — статья из Математической энциклопедии. Драгалин А. Г.
  21. Хаммак, 2009, Chapter 7. Proving Non-Conditional Statements, с. 129—138
  22. Самохин А. В. Проблема четырех красок: неоконченная история доказательства // Соросовский образовательный журнал. — 2000. — № 7. — С. 91—96.
  23. Stanley R.[en]. Bijective proof problems (англ.) (18 August 2009). Проверено 12 мая 2013. Архивировано из первоисточника 13 мая 2013.

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]