Обоснование математических утверждений: от аксиом к доказательствам.

Математические доказательства: логика, аксиомы, теоремы. Отличие от гипотез и эмпирических аргументов. Полная достоверность vs. вероятность.

15 мин чтения

100%

Источник: Mathematical proof — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

Рассуждение математических утверждений

Математическое доказательство — это дедуктивный аргумент в пользу математического утверждения, показывающий, что заявленные предположения логически гарантируют заключение. Аргумент может использовать другие ранее установленные утверждения, такие как теоремы, но каждое доказательство в принципе может быть построено, используя только определенные базовые или исходные предположения, известные как аксиомы, вместе с принятыми правилами вывода. Доказательства являются примерами исчерпывающего дедуктивного рассуждения, устанавливающего логическую достоверность, в отличие от эмпирических аргументов или неисчерпывающего индуктивного рассуждения, устанавливающего «обоснованное ожидание». Приведение множества случаев, в которых утверждение верно, недостаточно для доказательства, которое должно демонстрировать истинность утверждения во всех возможных случаях. Утверждение, которое не было доказано, но считается истинным, называется предположением, или гипотезой, если оно часто используется в качестве предположения для дальнейшей математической работы. Доказательства используют логику, выраженную математическими символами, наряду с естественным языком, который обычно допускает некоторую неоднозначность. В большинстве математической литературы доказательства представлены в терминах строгой неформальной логики. Чисто формальные доказательства, написанные полностью на символическом языке без использования естественного языка, рассматриваются в теории доказательств. Различие между формальными и неформальными доказательствами привело к изучению современной и исторической математической практики, квазиэмпиризма в математике и так называемой народной математики – устных традиций в основном математическом сообществе или в других культурах. Философия математики изучает роль языка и логики в доказательствах, а также математику как язык.

История и этимология

Слово "доказательство" происходит от латинского probare (испытать, проверять). Связанные современные слова – английские "probe", "probation" и "probability", испанское probar (чувствовать на вкус или запах, а иногда и ощупывать или проверять), итальянское provare (пробовать) и немецкое probieren (пробовать). Юридический термин "проби́ти" (probity) означает авторитет или достоверность, силу свидетельства, способного доказывать факты, когда оно дается лицами с репутацией или статусом. Аргументы, основанные на правдоподобии и использующие эвристические приемы, такие как изображения и аналогии, предшествовали строгим математическим доказательствам. Развитие математического доказательства – это в первую очередь результат развития древнегреческой математики и одно из ее величайших достижений. Фалес (624–546 гг. до н.э.) и Гиппократ Хиосский (ок. 470–410 гг. до н.э.) дали одни из первых известных доказательств теорем в геометрии. Эвдокс (408–355 гг. до н.э.) и Теэтет (417–369 гг. до н.э.) сформулировали теоремы, но не доказали их. Аристотель (384–322 гг. до н.э.) утверждал, что определения должны описывать определяемое понятие в терминах других уже известных понятий. Математическое доказательство было революционизировано Евклидом (300 г. до н.э.), который ввел аксиоматический метод, который используется и сегодня. Он начинается с неопределенных терминов и аксиом – утверждений относительно неопределенных терминов, которые считаются самоочевидно истинными (от греческого "axios" – ценный, достойный). На этой основе метод доказывает теоремы, используя дедуктивную логику. Книга Евклида "Начала" была прочитана всеми образованными людьми на Западе вплоть до середины XX века. Помимо теорем геометрии, таких как теорема Пифагора, в "Началах" также рассматривается теория чисел, включая доказательство иррациональности квадратного корня из двух и доказательство бесконечного количества простых чисел. Дальнейшие достижения произошли и в средневековой исламской математике. В X веке н.э. иракский математик Аль-Хашими работал с числами как таковыми, называемыми "линиями", но не обязательно рассматриваемыми как измерения геометрических объектов, чтобы доказать алгебраические утверждения, касающиеся умножения, деления и т.д., включая существование иррациональных чисел. Индуктивное доказательство для арифметических прогрессий было представлено в "Аль-Факхри" (1000 г.) Аль-Караджи, который использовал его для доказательства биномиальной теоремы и свойств треугольника Паскаля. Современная теория доказательств рассматривает доказательства как индуктивно определенные структуры данных, не требуя предположения, что аксиомы являются "истинными" в каком-либо смысле. Это позволяет использовать параллельные математические теории в качестве формальных моделей заданной интуитивной концепции, основанных на альтернативных наборах аксиом, например, аксиоматической теории множеств и неевклидовой геометрии.

The word "proof" comes from the Latin probare (to test). Related modern words are English "probe", "probation", and "probability", Spanish probar (to smell or taste, or sometimes touch or test), Italian provare (to try), and German probieren (to try). The legal term "probity" means authority or credibility, the power of testimony to prove facts when given by persons of reputation or status. Plausibility arguments using heuristic devices such as pictures and analogies preceded strict mathematical proof. The development of mathematical proof is primarily the product of ancient Greek mathematics, and one of its greatest achievements. Thales (624–546 BCE) and Hippocrates of Chios (c. 470–410 BCE) gave some of the first known proofs of theorems in geometry. Eudoxus (408–355 BCE) and Theaetetus (417–369 BCE) formulated theorems but did not prove them. Aristotle (384–322 BCE) said definitions should describe the concept being defined in terms of other concepts already known. Mathematical proof was revolutionized by Euclid (300 BCE), who introduced the axiomatic method still in use today. It starts with undefined terms and axioms, propositions concerning the undefined terms which are assumed to be self evidently true (from Greek "axios", something worthy). From this basis, the method proves theorems using deductive logic. Euclid's book, the Elements, was read by anyone who was considered educated in the West until the middle of the 20th century. In addition to theorems of geometry, such as the Pythagorean theorem, the Elements also covers number theory, including a proof that the square root of two is irrational and a proof that there are infinitely many prime numbers. Further advances also took place in medieval Islamic mathematics. In the 10th century CE, the Iraqi mathematician Al Hashimi worked with numbers as such, called "lines" but not necessarily considered as measurements of geometric objects, to prove algebraic propositions concerning multiplication, division, etc., including the existence of irrational numbers. An inductive proof for arithmetic sequences was introduced in the Al Fakhri (1000) by Al Karaji, who used it to prove the binomial theorem and properties of Pascal's triangle. Modern proof theory treats proofs as inductively defined data structures, not requiring an assumption that axioms are "true" in any sense. This allows parallel mathematical theories as formal models of a given intuitive concept, based on alternate sets of axioms, for example Axiomatic set theory and Non Euclidean geometry.

Характер и цель

Как это практикуется, доказательство выражается на естественном языке и представляет собой строгий аргумент, предназначенный для убеждения аудитории в истинности утверждения. Стандарт строгости не является абсолютным и менялся на протяжении истории. Доказательство может быть представлено по-разному в зависимости от целевой аудитории. Чтобы быть принятым, доказательство должно соответствовать общепринятым стандартам строгости; аргумент, считающийся расплывчатым или неполным, может быть отклонен. Понятие доказательства формализовано в области математической логики. Формальное доказательство написано на формальном языке, а не на естественном языке. Формальное доказательство – это последовательность формул на формальном языке, начинающаяся с предположения, при этом каждая последующая формула является логическим следствием предыдущих. Это определение делает понятие доказательства доступным для изучения. Действительно, теория доказательств изучает формальные доказательства и их свойства, наиболее известным и удивительным из которых является то, что почти все аксиоматические системы могут генерировать определенные неразрешимые утверждения, которые невозможно доказать в рамках этой системы. Определение формального доказательства призвано отразить понятие доказательств, используемых в математической практике. Обоснованность этого определения заключается в убеждении, что опубликованное доказательство, в принципе, может быть преобразовано в формальное доказательство. Однако за пределами области автоматизированных систем проверки доказательств это редко делается на практике. Классический вопрос в философии заключается в том, являются ли математические доказательства аналитическими или синтетическими. Кант, который ввел различие между аналитическими и синтетическими суждениями, считал математические доказательства синтетическими, в то время как Куайн в своей работе 1951 года «Две догмы эмпиризма» утверждал, что такое различие несостоятельно. Доказательства могут вызывать восхищение своей математической красотой. Математик Пол Эрдеш был известен тем, что описывал особенно элегантные доказательства как происходящие из «Книги» – гипотетического тома, содержащего наиболее изящные методы доказательства каждой теоремы. Книга «Доказательства из Книги», опубликованная в 2003 году, посвящена представлению 32 доказательств, которые особенно понравились ее редакторам.

As practiced, a proof is expressed in natural language and is a rigorous argument intended to convince the audience of the truth of a statement. The standard of rigor is not absolute and has varied throughout history. A proof can be presented differently depending on the intended audience. To gain acceptance, a proof has to meet communal standards of rigor; an argument considered vague or incomplete may be rejected. The concept of proof is formalized in the field of mathematical logic. A formal proof is written in a formal language instead of natural language. A formal proof is a sequence of formulas in a formal language, starting with an assumption, and with each subsequent formula a logical consequence of the preceding ones. This definition makes the concept of proof amenable to study. Indeed, the field of proof theory studies formal proofs and their properties, the most famous and surprising being that almost all axiomatic systems can generate certain undecidable statements not provable within the system. The definition of a formal proof is intended to capture the concept of proofs as written in the practice of mathematics. The soundness of this definition amounts to the belief that a published proof can, in principle, be converted into a formal proof. However, outside the field of automated proof assistants, this is rarely done in practice. A classic question in philosophy asks whether mathematical proofs are analytic or synthetic. Kant, who introduced the analytic–synthetic distinction, believed mathematical proofs are synthetic, whereas Quine argued in his 1951 "Two Dogmas of Empiricism" that such a distinction is untenable. Proofs may be admired for their mathematical beauty. The mathematician Paul Erdős was known for describing proofs which he found to be particularly elegant as coming from "The Book", a hypothetical tome containing the most beautiful method(s) of proving each theorem. The book Proofs from THE BOOK, published in 2003, is devoted to presenting 32 proofs its editors find particularly pleasing.

Прямые доказательства

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

Рассмотрим два четных целых числа x и y. Поскольку они четные, их можно представить в виде x = 2a и y = 2b, где a и b – некоторые целые числа. Тогда их сумма будет x + y = 2a + 2b = 2(a + b). Следовательно, x + y имеет 2 в качестве множителя и, по определению, является четным. Таким образом, сумма любых двух четных целых чисел является четной. В этом доказательстве используется определение четного целого числа, свойства целых чисел относительно замкнутости при сложении и умножении, а также дистрибутивное свойство.

Доказательство противоречия

В доказательстве от противного, также известном под латинской фразой reductio ad absurdum (доведение до абсурда), показывается, что если какое-либо утверждение принять за истинное, то возникнет логическое противоречие, следовательно, это утверждение должно быть ложным. Знаменитый пример – доказательство того, что √2 является иррациональным числом:

Предположим, что √2 является рациональным числом. Тогда его можно было бы представить в виде несократимой дроби a/b, где a и b – ненулевые целые числа, не имеющие общих делителей. Возводя обе части в квадрат, получим 2b² = a². Поскольку левая часть уравнения кратна 2, то и правая часть по определению делится на 2. То есть, a² является четным, что подразумевает, что a также должно быть четным, как было показано выше (в #Доказательстве от обратного). Следовательно, мы можем записать a = 2c, где c – также целое число. Подставляя в исходное уравнение, получаем 2b² = (2c)² = 4c². Деля обе части на 2, получаем b² = 2c². Но тогда, по тому же рассуждению, 2 делит b², следовательно, b также должно быть четным. Однако, если a и b оба четные, то у них есть общий делитель – 2. Это противоречит нашему предыдущему утверждению о том, что a и b не имеют общих делителей, поэтому мы должны заключить, что √2 является иррациональным числом. Другими словами: если бы √2 можно было представить в виде дроби, то эта дробь никогда не могла бы быть несократимой, поскольку 2 всегда можно было бы вынести за числитель и знаменатель.

Доказательство построением

Доказательство посредством построения, или доказательство примером, заключается в создании конкретного примера, обладающего определенным свойством, чтобы показать, что существуют объекты, обладающие этим свойством. Например, Жозеф Лиувилль доказал существование трансцендентных чисел, построив явный пример. Также этот метод может быть использован для построения контрпримера, опровергающего утверждение о том, что все элементы обладают определенным свойством.

Доказательство исчерпанием

При доказательстве от противного (или исчерпывающим перебором) заключение устанавливается путем разбиения его на конечное число случаев и доказательства каждого из них по отдельности. Число случаев иногда может оказаться очень большим. Например, первое доказательство теоремы о четырех красках было доказательством от противного, состоящим из 1936 случаев. Это доказательство вызвало споры, поскольку большинство случаев были проверены компьютерной программой, а не вручную. По состоянию на 2011 год, самое короткое из известных доказательств теоремы о четырех красках по-прежнему содержит более 600 случаев.

Вероятностное доказательство

Вероятностное доказательство – это доказательство существования примера, которое демонстрируется с уверенностью, с использованием методов теории вероятностей. Вероятностное доказательство, как и конструктивное доказательство, является одним из множества способов доказательства теорем о существовании. В вероятностном методе ищут объект, обладающий заданным свойством, начиная с большого множества кандидатов. Каждому кандидату присваивается определенная вероятность быть выбранным, а затем доказывается, что существует ненулевая вероятность того, что выбранный кандидат будет обладать желаемым свойством. Это не определяет, какие именно кандидаты обладают свойством, но вероятность не может быть положительной, если хотя бы одного такого кандидата нет. Вероятностное доказательство не следует путать с аргументом о том, что теорема "вероятно" верна – аргументом правдоподобия. Исследования в области гипотезы Коллатца показывают, насколько далеки аргументы правдоподобия от настоящего доказательства, как и опровержение гипотезы Мертенса. Хотя большинство математиков не считают вероятностные свидетельства свойств объекта достаточными для признания их полноценным математическим доказательством, некоторые математики и философы утверждают, что по крайней мере некоторые типы вероятностных свидетельств (например, вероятностный алгоритм Рабина для проверки простоты) столь же надежны, как и настоящие математические доказательства.

Комбинаторное доказательство

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

Неконструктивное доказательство

Неконструктивное доказательство устанавливает, что математический объект с определенным свойством существует, не объясняя, как такой объект можно найти. Часто это принимает форму доказательства от противного, в котором доказывается невозможность несуществования объекта. Конструктивное доказательство, напротив, устанавливает существование конкретного объекта, предоставляя метод его нахождения. Следующий известный пример неконструктивного доказательства показывает, что существуют два иррациональных числа a и b, такие что a + b является рациональным числом. Это доказательство использует тот факт, что √2 является иррациональным (легкое доказательство известно со времен Евклида), но не использует тот факт, что √3 является иррациональным (это верно, но доказательство не элементарно). Либо a + b является рациональным числом, и мы закончили (возьмем b = 0), либо a + b является иррациональным, так что мы можем записать a + b = √3, и тогда a = √3 - b, что является рациональным числом вида √3 - b.

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

Выражение "статистическое доказательство" может употребляться в техническом или разговорном контексте в областях чистой математики, таких как криптография, хаотические ряды и вероятностная или аналитическая теория чисел. Оно реже используется для обозначения математического доказательства в области математики, известной как математическая статистика. См. также раздел "Статистическое доказательство на основе данных" ниже.

Компьютерная проверка

До двадцатого века считалось, что любое доказательство в принципе может быть проверено компетентным математиком для подтверждения его верности. Однако в настоящее время компьютеры используются как для доказательства теорем, так и для выполнения вычислений, которые слишком сложны для проверки человеком или группой людей. Первое доказательство теоремы о четырёх красках является примером компьютерно-ассистированного доказательства. Некоторые математики обеспокоены тем, что возможность ошибки в компьютерной программе или ошибки во время выполнения вычислений ставит под вопрос достоверность подобных компьютерно-ассистированных доказательств. На практике вероятность ошибки, способной опровергнуть компьютерно-ассистированное доказательство, можно снизить, внедряя избыточность и самопроверки в вычисления, а также разрабатывая несколько независимых подходов и программ. Ошибки нельзя полностью исключить и при проверке доказательств людьми, особенно если доказательство содержит естественный язык и требует глубокого математического понимания для выявления потенциальных скрытых предположений и логических ошибок.

Неопределенные заявления

Утверждение, которое нельзя ни доказать, ни опровергнуть, исходя из заданного набора аксиом, называется неразрешимым (относительно этих аксиом). Примером является параллельный постулат, который нельзя ни доказать, ни опровергнуть, исходя из остальных аксиом евклидовой геометрии. Математики показали, что существует множество утверждений, которые нельзя ни доказать, ни опровергнуть в теории множеств Цермело — Френкеля с аксиомой выбора (ZFC), являющейся стандартной системой аксиоматизации теории множеств в математике (при условии, что ZFC непротиворечива); см. Список неразрешимых утверждений в ZFC. Первая теорема о неполноте Гёделя показывает, что многие аксиоматические системы, представляющие интерес для математики, содержат неразрешимые утверждения.

Эвристическая математика и экспериментальная математика

В то время как ранние математики, такие как Евдокс из Книда, не использовали доказательства, от Евклида до основополагающих математических разработок конца XIX и XX веков доказательства были неотъемлемой частью математики. С ростом вычислительной мощности в 1960-х годах началась активная работа по исследованию математических объектов, выходящих за рамки формализма доказательств теорем, в рамках экспериментальной математики. Первопроходцы этих методов предполагали, что результаты в конечном итоге будут обоснованы в рамках классического формализма доказательств теорем, как, например, произошло в раннем развитии фрактальной геометрии.

Визуальное доказательство

Хотя это и не является формальным доказательством, визуальная демонстрация математической теоремы иногда называется "доказательством без слов". Изображение слева ниже – пример исторической визуальной демонстрации теоремы Пифагора для треугольника (3,4,5). Некоторые иллюзорные визуальные доказательства, такие как головоломка с недостающим квадратом, могут быть построены таким образом, что кажутся доказательством некоторого математического утверждения, но на самом деле достигают этого, игнорируя незначительные ошибки (например, линии, которые кажутся прямыми, но на самом деле слегка изогнуты), которые остаются незамеченными до тех пор, пока изображение не будет тщательно изучено с точным измерением или вычислением длин и углов.

Элементарное доказательство

Элементарное доказательство – это доказательство, использующее только базовые приемы. В частности, этот термин в теории чисел относится к доказательствам, не использующим комплексный анализ. Долгое время полагали, что некоторые теоремы, например, теорема о простых числах, могут быть доказаны лишь с помощью "более продвинутой" математики. Однако со временем многие из этих результатов были повторно доказаны, используя только элементарные приемы.

Двухколонный провод

Особый способ организации доказательства с использованием двух параллельных столбцов часто применяется в качестве математического упражнения на уроках элементарной геометрии в Соединенных Штатах. Доказательство представляется в виде последовательности строк, разделенных на два столбца. В каждой строке левый столбец содержит утверждение, а правый – краткое обоснование того, что соответствующее утверждение в левом столбце является аксиомой, гипотезой или логически вытекает из предыдущих утверждений. Левый столбец обычно озаглавливается как "Утверждения", а правый – как "Обоснования".

Распространенное использование "математического доказательства"

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

Статистическое доказательство с использованием данных

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

Индуктивные логические доказательства и байесовский анализ

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

Доказательства как ментальные объекты

Психологизм рассматривает математические доказательства как психологические или ментальные объекты. Философы-математики, такие как Лейбниц, Фреге и Карнап, по-разному критиковали этот подход и пытались разработать семантику для того, что они считали языком мышления, посредством которой стандарты математического доказательства могли бы быть применены к эмпирической науке.

Влияние математических методов доказательства за пределами математики

Философы, занимающиеся математикой, такие как Спиноза, пытались сформулировать философские аргументы аксиоматически, чтобы стандарты математического доказательства могли быть применены к аргументации в философии в целом. Другие философы-математики стремились использовать стандарты математического доказательства и рассуждения, без опоры на эмпиризм, для получения утверждений, выходящих за рамки математики, но обладающих той же степенью достоверности, что и выводимые в математическом доказательстве положения, как, например, аргумент "Я мыслю, следовательно, существую" Декарта.

Окончание доказательства

Иногда для обозначения конца доказательства используется сокращение "Q. E. D.". Это сокращение расшифровывается как "quod erat demonstrandum", что с латыни переводится как "что и требовалось доказать". Более распространенной альтернативой является использование квадрата или прямоугольника, например □ или ∎, известные как "надгробный камень" или "хальмос" в честь Пола Халмоса, их создателя. При устной презентации, когда пишут "QED", "□" или "∎", часто произносят фразу "что и требовалось показать". В Unicode специально предусмотрен символ "конец доказательства" U+220E (∎) (220E(hex) = 8718(dec)).