Доказательство
Доказательство-цепочка умозаключений, устанавливающая истинность данного суждения.
Метод перебора-один из простейших методов доказательства. Например, чтобы установить, что заданное число, скажем 103, простое, достаточно проверить, что оно не делится ни на одно простое число, не превосходящее корня из данного числа, в нашем случае, что оно не делится на 2, 3, 5, 7.
Однако когда количество объектов бесконечно, то уже невозможно перебрать все варианты. Здесь может помочь метод математической индукции, с помощью которого можно доказывать утверждения уже для бесконечного количества объектов.
Один из методов доказательства-принцип Дирихле (см. Дирихле принцип).
Доказательство - единственный способ установления истины в классической математике. Оно далеко не сразу заняло в математике такую исключительную роль. Например, в египетской и вавилонской математике вычислительные формулы, т. е. "рецепты" решения задач, так или иначе угадывались, они подвергались экспериментальной проверке, а затем сообщались в виде немотивированных утверждений.
Доказательства не сразу появились и в греческой геометрии. Архимед (III в. до н.э.) говорил о результатах, ранее "найденных, но не доказанных". С V в. до н.э. философы, начиная с Парменида и его ученика Зенона, во многом учась у ораторов, вычленяют различные приемы перехода от одних истинных утверждений к другим. Парменид формулирует закон "исключенного третьего" (из двух противоположных утверждений одно, и только одно, истинно), а Зенон использует метод приведения к абсурду (противоречию).
Но в математику эти приемы проникают не сразу: по-видимому, еще Демокрит, живший в V-IV вв. до н.э., обходился без доказательств. В IV в. до н.э. логика завоевывает математику. Несомненно, на первых порах доказательство - это логическое сведение неочевидных утверждений к очевидным или уже известным.
Наши современники не могут точно воссоздать картину, как появилась идея максимально ограничить число очевидных утверждений (аксиом), об истинности которых заключается соглашение и из которых остальные утверждения выводятся чисто логически (см. Аксиоматика и аксиоматический метод). В "Началах" Евклида (III в. до н.э.) грандиозная программа аксиоматизации геометрии уже полностью решена. По правилам Евклида доказательства должны быть чисто логическими выводами из аксиом. Окончательные геометрические тексты тщательно оберегались от дополнительных апелляций к очевидности. Прокл Диадох (V в.), первый комментатор Евклида, писал: "...мы научились от самих пионеров этой науки совсем не принимать в расчет правдоподобные заключения, когда дело касается рассуждений, которые должны войти в науку геометрии". Тем временем Аристотель проводит формализацию и каталогизацию правил умозаключений. Его утверждение об их конечности и обозримости не менее поразительно, чем утверждение о конечности множества аксиом. Полнота этих двух каталогов не оспаривалась до XIX в.
Правила, которыми мы пользуемся при логических рассуждениях (доказательствах), не выходят за пределы простых логических операций. Утверждение, справедливое для некоторого множества (скажем, всех параллелограммов), справедливо и для его подмножества (например, прямоугольников). Если справедливы утверждения А и из А следует В, то справедливо В. При доказательстве теоремы, имеющей вид "из А следует В" (А-то, что дано, В-то, что требуется доказать), при помощи уже известных нам теорем выводятся разные следствия, которые затем комбинируются, и из их комбинаций делаются новые выводы, пока в результате не получится В.
При доказательстве методом от противного теоремы "из А следует В" из справедливости утверждения А и отрицания утверждения В выводится справедливость пары противоположных утверждений, например, достаточно доказать отрицание утверждения А или утверждения В. Вспомним одно из классических доказательств от противного - доказательство Евклида бесконечности множества простых чисел. Если предположить, что множество простых чисел конечно и р1, p2, ..., рk - их полный набор, то число р1 ...рk + 1 не может быть составным, так как оно не делится ни на одно из простых чисел pj, но оно не может быть и простым, так как оно больше каждого рk.
Существуют и другие способы установления справедливости математических утверждений. Так, у Архимеда большинство его замечательных утверждений о площадях криволинейных фигур и объемах тел было получено первоначально при помощи чисто механических рассуждений с центрами тяжести, равновесием рычагов и т. д. В дальнейшем появилось большое число "механических" доказательств геометрических утверждений. Вот одно из самых изящных. Из внутренней точки многогранника на его грани опускаются перпендикуляры. Надо доказать, что хотя бы для одной грани перпендикуляр придется на саму грань, а не на ее продолжение. "Механическое" рассуждение состоит в следующем. Изготовляется массивный многогранник с не-равномерной плотностью, у которого центр тяжести находится в заданной точке. Если все перпендикуляры попадут на продолжения граней, то многогранник не сможет стоять ни на одной грани, и мы получим вечный двигатель. Можно ли считать это рассуждение доказательством? С точки зрения, принятой в геометрии, разумеется, нет. Более того, нет никаких формальных способов преобразовывать "механические" доказательства в геометрические. Архимед справился с этой задачей, он дал геометрические доказательства к найденным им фактам.
Доказательство теоремы, как правило, не несет никакой информации о том, как к этой теореме можно на самом деле прийти. Одним из немногих великих математиков, допускавших посторонних в свою творческую лабораторию, был Л.Эйлер. Тексты Эйлера дают нам возможность проследить за ходом его мысли. Например, он рассматривает бесконечный ряд
Далее, используя, что sinx/x = 0 при х = кπ, к ≠ 0, Эйлер применяет к ряду теорему о разложении на линейные множители, как если бы это был многочлен:
Раскрывая скобки и вычисляя коэффициент при х2, получаем π2/6 = 1 + 1/4 + 1/9 + 1/16 + + ... + 1/n2 .... Разумеется, Эйлер понимал, что его смелое рассуждение доказательством не является. Он ищет косвенные подтверждения: вычисляет с большим числом знаков левую и правую части полученного соотношения, получает другие аналогичные соотношения и в их числе уже доказанное Лейбницем: π/4 = 1 - 1/3 + 1/5 - 1/7 + .... У него появляется уверенность в правильности своего рассуждения, хотя он еще не в состоянии проводить эквивалентные строгие доказательства. Эйлер энергично использует свой прием для открытия новых фактов. Умение открывать новые факты в виде гипотез, умение исследовать гипотезы на правдоподобность, как и умение проводить строгие доказательства, - важнейшие компоненты математического творчества.
С 17 в. математики начинают осознавать, что, в отличие от представителей других наук, они имеют надежный способ установления истины - доказательство. С этим связаны многочисленные попытки перенести доказательства за пределы математики. И. Ньютон строит механику на аксиомах по образцу "Начал" Евклида. Нидерландский философ-материалист XVII в. Б. Спиноза аксиоматизирует этику. Начиная с французского математика и физика П. С. Лапласа (1749-1827) многие пытались внедрить математические рассуждения в юридическую практику. Делались бесконечные попытки решить проблемы человеческих отношений при помощи математики. Но, конечно же, в самой математике доказательства стали играть важнейшую роль.
К началу нашего века аксиоматический метод выходит за пределы геометрии. Большинство фактов о числах, известных со времен Пифагора, носило характер частных наблюдений над конкретными числами, а не обобщающих теорем. В XVI в. теоремы появились в алгебре (у Дж. Кардано), в XVII в. - в теории чисел (у П. Ферма). Однако здесь математики не имели дело с аксиоматическими теориями и понимание доказательства находилось на доевклидовом уровне, когда набор очевидных утверждений не фиксируется. В XIX в. начинается аксиоматизация всей математики. На новом уровне формализуются и перечисляются правила вывода-перехода от одних утверждений к другим. Это позволило доказать, что некоторые утверждения невыводимы из аксиом. Всеобщее удивление вызвало рассуждение немецкого математика К. Геделя о том, что в арифметике и вообще во всякой содержащей ее аксиоматической теории существует такая теорема, что ни она сама, ни ее отрицание невыводимы из аксиом.