Доведение

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

Принципы доказывания изучаются специальной областью математики - теории доказательств.


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

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

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

Ошибочным доказательством называется текст, содержащий логические ошибки, то есть, по которому нельзя восстановить формальное доказательство. В истории математики были случаи, когда выдающиеся ученые публиковали неверные "доказательства", однако обычно их коллеги или они сами довольно быстро находили ошибки. (Одна из теорем, чаще неправильно приходилось, - Великая теорема Ферма. До встречаются люди, не знают о том, что она доказана, и предлагают новые неверные "доказательства"). Ошибочным может быть только признание "доказательства" на естественном или формальном языке доказательством; формальное доказательство ложным не может быть по определению.

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


2. Формальное доказательство

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

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


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

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

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

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

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


3.2. Индуктивный доказательство

Подробнее в статье Математическая индукция

Предположим, что нужно установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: P_1, P_2, \ ldots, P_n, P_ {n +1}, \ ldots . Предположим, что

  1. Установлено, что P 1 верно. (Это утверждение называется базой индукции.)
  2. Для любого n доказано, что если верно P n, то верно P n + 1. (Это утверждение называется индукционным переходом.)

Тогда все утверждения нашей последовательности верны.


3.3. Метод перестановки

Метод перестановки устанавливает истинность утверждения Если А, то Б доведением эквивалентного утверждения Если НЭРБ, это не А.

3.4. Доказательство от обратного

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

Этот метод доказательства известный также как приведение к абсурду ( лат. reductio ad absurdum ). Доказательство утверждения A производится следующим образом. Сначала принимают предположение, что утверждение A неверно, а затем показывают, что при таком предположение было бы верно некоторое утверждение B, которое заранее неверно. Полученная противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение ? ? A, которое по закону двойного отрицания равносильно утверждению A.


3.5. Конструктивный доказательство

Подробнее в статье Конструктивный доказательство

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

3.6. Метод подъемников

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


3.7. Вероятностный доказательство

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

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

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

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

Неконструктивное доказательства устанавливает, что определенный математический объект должен существовать () есть определенный 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} .

3.10. Ани доказательства, ни возражения

Существует класс математических утверждений, для которых не существует ни доказательства, ни опровержения (т.е. доведения обратной утверждение) в рамках аксиоматики Цермело - Френкеля, стандартной основе теории множеств. В качестве примера можно привести континуума гипотезу. Если согласиться с непротивоичнистю аксиом Френкеля - Цермело, существование таких примеров нам гарантирует первая теорема неполноты Геделя. Можно доказать определенное утверждение или его опровержения, не всегда очевидно и может потребовать чрезвычайной техники для установления этого факта.


3.11. Элементарный доказательство

Элементарным доведением называют доказательства, которые не требуют сложного анализа.

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

4. Что и требовалось доказать

Традиционно завершения доказательства сказывалось Абривиатура "QED", от латинского выражения лат. Quod Erat Demonstrandum , Что и требовалось доказать.

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

5. Смотрите также


Сигма Это незавершенная статья математики.
Вы можете помочь проекту, исправив и дополнив ее.