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

П. Окси. 29 , один из старейших сохранившихся фрагментов Евклида » « Начал , учебника, который на протяжении тысячелетий использовался для обучения технике корректуры. Диаграмма прилагается к Книге II, Предложению 5.

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

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

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

Смотрите также: История логики

Слово «доказательство» происходит от латинского probe (проверять). Родственные современные слова - английские «зонд», «испытательный срок» и «вероятность», испанский « пробар» (понюхать или попробовать, а иногда потрогать или проверить), Итальянское provare (попробовать) и немецкое probieren (попробовать). Юридический термин «честность» означает авторитет или достоверность, способность свидетельствовать в подтверждение фактов, когда они даны лицами с репутацией или статусом.

Аргументы правдоподобия с использованием эвристических приемов, таких как изображения и аналогии, предшествовали строгим математическим доказательствам. Вероятно, идея доказательства вывода впервые возникла в связи с геометрией , зародившейся в практических задачах землемерия. Разработка математических доказательств — это прежде всего продукт древнегреческой математики и одно из ее величайших достижений. Фалес (624–546 до н. э.) и Гиппократ Хиосский (ок. 470–410 до н. э.) дали одни из первых известных доказательств теорем геометрии. Евдокс (408–355 до н. э.) и Теэтет (417–369 до н. э.) сформулировали теоремы, но не доказали их. Аристотель (384–322 гг. до н. э.) говорил, что определения должны описывать определяемое понятие в терминах других уже известных понятий.

Революцию в математическом доказательстве произвел Евклид (300 г. до н.э.), который представил аксиоматический метод, который используется до сих пор. Он начинается с неопределенных терминов и аксиом , предложений относительно неопределенных терминов, которые считаются самоочевидно истинными (от греческого «аксиос», что-то достойное). На этой основе метод доказывает теоремы с использованием дедуктивной логики . Книгу Евклида « Начала » до середины 20 века читал на Западе каждый, кто считался образованным. В дополнение к теоремам геометрии, таким как теорема Пифагора , «Элементы» также охватывают теорию чисел , включая доказательство того, что квадратный корень из двух иррационален , и доказательство того, что существует бесконечно много простых чисел .

Дальнейшие успехи также имели место в средневековой исламской математике . В 10 веке н.э. иракский математик Аль-Хашими работал с числами как таковыми, называемыми «линиями», но не обязательно рассматриваемыми как измерения геометрических объектов, для доказательства алгебраических утверждений, касающихся умножения, деления и т. д., включая существование иррациональных чисел. . Индуктивное доказательство арифметических последовательностей было введено в « Аль-Фахри» (1000) Аль-Караджи , который использовал его для доказательства биномиальной теоремы и свойств треугольника Паскаля .

Современная теория доказательств рассматривает доказательства как индуктивно определенные структуры данных , не требуя предположения, что аксиомы «истинны» в каком-либо смысле. Это позволяет использовать параллельные математические теории как формальные модели данной интуитивной концепции, основанные на альтернативных наборах аксиом, например аксиоматической теории множеств и неевклидовой геометрии .

Природа и цель

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

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

Определение формального доказательства призвано отразить концепцию доказательств, как она записана в математической практике. Разумность этого определения сводится к убеждению, что опубликованное доказательство в принципе может быть преобразовано в формальное доказательство. Однако за пределами автоматизированных помощников по проверке это редко делается на практике. Классический вопрос философии: являются ли математические доказательства аналитическими или синтетическими . Кант , который ввел аналитическое и синтетическое различие , считал математические доказательства синтетическими, тогда как Куайн » 1951 года утверждал в своих « Двух догмах эмпиризма , что такое различие несостоятельно.

Доказательствами можно восхищаться своей математической красотой . Математик Пауль Эрдеш был известен тем, что описывал доказательства, которые он считал особенно элегантными, поскольку они взяты из «Книги», гипотетического тома, содержащего самые красивые методы доказательства каждой теоремы. Книга «Доказательства из КНИГИ» , опубликованная в 2003 году, посвящена представлению 32 доказательств, которые ее редакторы находят особенно приятными.

Методы доказательства

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

Основная статья: Прямое доказательство

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

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

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

Доказательство методом математической индукции

Основная статья: Математическая индукция

Несмотря на свое название, математическая индукция — это метод дедукции , а не форма индуктивного рассуждения . При доказательстве методом математической индукции доказывается единственный «базовый случай» и доказывается «правило индукции», которое устанавливает, что любой произвольный случай влечет за собой следующий случай. Поскольку в принципе правило индукции можно применять неоднократно (начиная с доказанного базового случая), отсюда следует, что все случаи (обычно бесконечное число) доказуемы. Это позволяет избежать необходимости доказывать каждый случай индивидуально. Вариант математической индукции — доказательство бесконечным спуском , которое можно использовать, например, для доказательства иррациональности квадратного корня из двух .

Обычное применение доказательства методом математической индукции состоит в том, чтобы доказать, что свойство, которое, как известно, справедливо для одного числа, справедливо и для всех натуральных чисел : Пусть N = {1, 2, 3, 4, ... } — набор натуральных чисел, и пусть P ( n ) — математическое утверждение, включающее натуральное число n, принадлежащее N , такое, что

• (i) P (1) истинно, т. е. P ( n ) истинно для n = 1 .
• (ii) P ( n +1) истинно всякий раз, когда P ( n ) истинно, т.е. P ( n ) истинно, подразумевает, что P ( n +1) истинно.
• Тогда P ( n ) верно для всех натуральных чисел n .

целые числа вида 2 n − 1 нечетны Например, мы можем доказать по индукции, что все положительные . Пусть P ( n ) представляет собой « 2 n − 1 нечетно»:

(i) Для n = 1 , 2 n − 1 = 2(1) − 1 = 1 , и 1 остается остаток 1 нечетно, так как при делении на 2 . Таким образом, P (1) верно.

(ii) Для любого n , если 2 n − 1 нечетно ( P ( n ) ), то (2 n − 1) + 2 также должно быть нечетным, поскольку добавление 2 к нечетному числу приводит к нечетному числу. Но (2 n - 1) + 2 = 2 n + 1 = 2( n +1) - 1 , поэтому 2( n +1) - 1 нечетно ( P ( n +1) ). Итак, P ( n ) подразумевает P ( n +1) .

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

Более короткая фраза «доказательство по индукции» часто используется вместо «доказательство по математической индукции».

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

Основная статья: Противопоставление

Доказательство путем противопоставления выводит утверждение «если p, то q » путем установления логически эквивалентного контрапозитивного утверждения : «если не q, то не p ».

Например, противопоставление можно использовать, чтобы установить, что для данного целого числа $x$, если $x^{2}$ четно, тогда $x$ четный:

Предполагать $x$ это не даже. Затем $x$ странно. Произведение двух нечетных чисел нечетно, следовательно $x^{2}=x\cdot x$ странно. Таким образом $x^{2}$ это не даже. Таким образом, если $x^{2}$ четно , то предположение должно быть ложным, поэтому $x$ должно быть ровным.

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

Основная статья: Доказательство от противного

Доказательство от противного, также известное под латинским выражением reductio ad абсурд (путем сведения к абсурду), показывает, что если какое-то утверждение считается истинным, возникает логическое противоречие , следовательно, это утверждение должно быть ложным. Известный пример связан с доказательством того, что ${\sqrt {2}}$ иррациональное число :

Предположим, что ${\sqrt {2}}$ были рациональным числом. Тогда это можно было бы записать в самых простых терминах как ${\sqrt {2}}={a \over b}$ где a и b — ненулевые целые числа без общего множителя . Таким образом, $b{\sqrt {2}}=a$. Возведение в квадрат обеих частей дает 2 b ² = а ² . Поскольку выражение слева является целым числом, кратным 2, правое выражение по определению делится на 2 . ² четно, а это означает, что a также должно быть четным, как видно из предложения выше (в #Доказательство противопоставлением ). Итак, мы можем написать a = 2 c , где c также является целым числом. Подстановка в исходное уравнение дает 2 b ² = (2 с ) ² = 4 с ² . Разделив обе части на 2, получим b ² = 2 с ² . Но тогда, по тому же рассуждению, что и раньше, 2 делит b ² , поэтому b должно быть четным. Однако, если a и b оба четные, их общий делитель равен 2. Это противоречит нашему предыдущему утверждению о том, что a и b не имеют общего делителя, поэтому мы должны заключить, что ${\sqrt {2}}$ это иррациональное число.

Перефразируя: если бы можно было написать ${\sqrt {2}}$ как дробь , эту дробь никогда нельзя было записать в самых простых терминах, поскольку 2 всегда можно было разложить на множители из числителя и знаменателя.

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

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

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

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

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

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

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

Основная статья: Вероятностный метод

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

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

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

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

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

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

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

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

Неконструктивное доказательство устанавливает, что математический объект с определенным свойством существует, но не объясняет, как такой объект можно найти. Часто это принимает форму доказательства от противного, в котором доказывается невозможность несуществования объекта. Напротив, конструктивное доказательство устанавливает существование конкретного объекта, предоставляя метод его обнаружения. Следующий знаменитый пример неконструктивного доказательства показывает, что существуют два иррациональных числа a и b такие, что $a^{b}$ является рациональным числом . В этом доказательстве используется то, что ${\sqrt {2}}$ иррационально (простое доказательство известно со времен Евклида ), но не то, что ${\sqrt {2}}^{\sqrt {2}}$ иррационально (это верно, но доказательство не элементарно).

Или ${\sqrt {2}}^{\sqrt {2}}$ — рациональное число, и мы закончили (возьмем $a=b={\sqrt {2}}$), или ${\sqrt {2}}^{\sqrt {2}}$ иррационально, поэтому мы можем написать $a={\sqrt {2}}^{\sqrt {2}}$ и $b={\sqrt {2}}$. Это тогда дает $\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{2}=2$, что, таким образом, является рациональным числом вида $a^{b}.$

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

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

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

Компьютерные

Основная статья: Компьютерное доказательство

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

Неразрешимые утверждения

Утверждение, которое не является ни доказуемым, ни опровергнутым на основе набора аксиом, называется неразрешимым (на основании этих аксиом). Одним из примеров является постулат параллельности , который нельзя ни доказать, ни опровергнуть, исходя из остальных аксиом евклидовой геометрии .

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

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

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

Основная статья: Экспериментальная математика

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

Связанные понятия

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

Хотя это и не формальное доказательство, наглядную демонстрацию математической теоремы иногда называют « доказательством без слов ». Левое изображение ниже представляет собой пример исторического визуального доказательства теоремы Пифагора в случае треугольника (3,4,5) .

• 
  Визуальное доказательство треугольника (3,4,5), как в Чжоуби Суаньцзин 500–200 гг. До н.э.
• 
  Анимированное наглядное доказательство теоремы Пифагора путем перестановки.
• 
  Второе анимированное доказательство теоремы Пифагора.

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

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

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

Элементарное доказательство — это доказательство, в котором используются только базовые методы. Более конкретно, этот термин используется в теории чисел для обозначения доказательств, в которых не используется комплексный анализ . Некоторое время считалось, что некоторые теоремы, такие как теорема о простых числах , можно доказать только с помощью «высшей» математики. Однако со временем многие из этих результатов были опровергнуты с использованием лишь элементарных методов.

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

Доказательство в две колонки, опубликованное в 1913 году.

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

доказательства

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

доказательство с

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

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

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

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

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

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

как

Основные статьи: Психологизм и язык мысли

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

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

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

Завершение доказательства

Основная статья: КЭД

Иногда аббревиатуру «QED» пишут, чтобы указать на конец доказательства. Эта аббревиатура расшифровывается как «quod Erat DemonStrandum» , что в переводе с латыни означает «то, что должно было быть продемонстрировано» . Более распространенной альтернативой является использование квадрата или прямоугольника, например □ или ∎, ​​известного как « надгробие » или «халмос» в честь его эпонима Пола Халмоса . Часто «что должно было быть показано» устно указывается при написании «QED», «□» или «∎» во время устного выступления. В Юникоде явно предусмотрен символ «конца доказательства», U+220E (∎) (220E(hex) = 8718(dec)) .

См. также

• Автоматизированное доказательство теорем
• Недействительное доказательство
• Список неполных доказательств
• Список длинных доказательств
• Список математических доказательств
• Неконструктивное доказательство
• Доказательство путем запугивания
• Анализ завершения
• Мысленный эксперимент
• Что черепаха сказала Ахиллесу
• Доказательство с нулевым разглашением

Дальнейшее чтение

• Полиа, Г. (1954), Математика и правдоподобные рассуждения , Princeton University Press, hdl : 2027/mdp.39015008206248 , ISBN  9780691080055 .
• Фаллис, Дон (2002), «Чего хотят математики? Вероятностные доказательства и эпистемические цели математиков» , Logique et Analyse , 45 : 373–88 .
• Франклин, Дж .; Дауд, А. (2011), Доказательство по математике: введение , Kew Books, ISBN  978-0-646-54509-7 .
• Голд, Бонни ; Саймонс, Роджерс А. (2008). Доказательство и другие дилеммы: математика и философия . МАА.
• Солоу, Д. (2004), Как читать и проводить доказательства: введение в математические мыслительные процессы , Wiley , ISBN  978-0-471-68058-1 .
• Веллеман, Д. (2006), Как это доказать: структурированный подход , издательство Кембриджского университета, ISBN  978-0-521-67599-4 .
• Хаммак, Ричард (2018), Книга доказательств , ISBN  978-0-9894721-3-5 .

Внешние ссылки

• СМИ, связанные с математическим доказательством, на Викискладе?
• Доказательства по математике: простые, очаровательные и ошибочные
• Урок . о доказательствах курсе Викиверситета в