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

Под теоремой обычно понимается математическое утверждение, которое можно доказать. Доказательством теоремыТ называется конечная последовательность теорем Т₁ , Т₂ , … , Т_n = Т , где каждое Т_i является аксиомой или получается из предыдущих утверждений Т₁ , Т₂ , … , Т_i–1 с помощью заранее оговоренных правил логического вывода. Теорема Т₁ , у которой нет предыдущих, очевидно, должна быть аксиомой.

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

Аксиомы специфичны для каждой отрасли математического знания. Уже в школе знакомятся с аксиомами евклидовой геометрии, в институтском курсе алгебры и логики – с аксиомами исчисления высказываний (таблицами истинности для логических связок) и аксиомами Пеано для натуральных чисел. Существуют свои списки аксиом теории множеств, теории действительных чисел, неевклидовых геометрий и многие другие, с которыми вы уже встречались. Поэтому в доказательстве той или иной теоремы могут участвовать аксиомы разной природы – всё зависит от специфики тех объектов, свойства которых устанавливает доказываемая теорема.

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

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

Гарантирует ли наличие доказательства истинность теоремы ? Другими словами, существуют ли в “математической реальности” те объекты и отношения, о которых говорит доказанная теорема ? Вообще говоря, не всегда: если, например, включить в список аксиом ложное утверждение, то из этой аксиомы можно логически вывести любую, в том числе и ложную, теорему. Однако, если хотя бы одно утверждение не выводится из аксиом (аксиомы непротиворечивы), то любая доказанная теорема истинна. Этот нетривиальный факт составляет суть так называемой теоремы о существовании модели (более подробно об этом речь пойдёт в следующей главе).

Таким образом, доказательство теоремы в непротиворечивой аксиоматике гарантирует её истинность. Обратное не верно ! Существуют примеры истинных, но не доказуемых (в данной непротиворечивой системе аксиом) теорем. В самом деле, рассмотрим множество всех натуральных чисел N = {1, 2, 3, …} с операцией “прибавления единицы”, которая сопоставляет каждому натуральному числу n следующее натуральное число n + 1 и подчиняется следующим трём аксиомам: 1 + 1 = 2, 2 + 1 = 3, 3 + 1 = 4. Обычная операция сложения натуральных чисел, конечно, удовлетворяет этим аксиомам, но выполненное для неё свойство 2 + 2 = 4 невозможно доказать, используя только перечисленные аксиомы, т.к. нет возможности с их помощью преобразовать 2 + 2 в 4 : 2 + 2 = (1 + 1) + 2 = (1 + 1) + (1 + 1) = 2 + (1 + 1) и 4 = 3 + 1 = = (2 + 1) + 1 = ((1 + 1) + 1) + 1 – вот все возможные способы записи выражения 2 + 2 и числа 4 с использованием только трёх указанных аксиом. При этом ни одна из записей выражения 2 + 2 не совпадает ни с одной записью числа 4, и отсутствуют иные средства преобразовать эти записи одна в другую, т.к. всё, что можно использовать – это три правила, зафиксированные в рассматриваемых аксиомах. Таким образом, теорема арифметики 2 + 2 = 4 не доказуема, исходя только из трёх приведённых аксиом, но она истинна и доказуема с использованием полной аксиоматики Пеано натуральных чисел.

Упражнения. 1. Доказуемы ли, исходя из рассмотренных трёх аксиом, теоремы 1 + 2 = 2 + 1, 1 + 3 = 4 ?

2. Докажите теоремы 2 + 2 = 4 и 2´2 = 4 на основе аксиом Пеано.

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

I. Метод полного перебора возможных случаев.Пусть нужно доказатьутверждение А(х) о некотором математическом объекте х. Предположим, что для х доказана теорема А₁(х) Ú … Ú А_n(х) , где А₁(х) , … , А_n(х) – некоторые утверждения, и для каждого i (1 £ i £ n) доказана импликация А_i(х) ® А(х). Тогда А(х) следует из теорем А₁(х)Ú …Ú А_n(х) и А_i(х) ® А(х) (1 £ i £ n) на основании правила логического вывода о переборе возможных случаев:

.

Доказательство. Если Т₁ , …, Т_k , А₁(х) Ú … Ú А_n(х) – доказательство теоремы А₁(х) Ú … Ú А_n(х), а T, … , T , A_i(x) ® A(x) – доказательства теорем A_i(x) ® A(x) (1 £ i £ n), то цепочка Т₁ , …, Т_k , А₁(х) Ú …Ú А_n(х), T , … , T , A₁(x) ® A(x), … , T , … , T , A_n(x) ® A(x), A(x) будет доказательством теоремы А(х) с применением (на последнем шаге) упомянутого правила вывода.

Докажем это правило от противного: если С(e) = 0, то из (A_i(e) ® C(e)) = 1 получаем A_i(e) = 0, т.е. A₁(e)Ú … Ú A_n(e) = 0 – противоречие.

Теорема доказана.

Пример. Доказать, что " n Î N n×(n+1) M 2.

Доказательство можно записать в две строчки: “любое натуральное число n либо чётно, и тогда n×(n + 1) M 2, либо нечётно – тогда n + 1 чётно, и снова n×(n + 1) M 2”. Более формально, на основе аксиоматики Пеано нужно рассуждать следующим образом.

Здесь А(n) = “n×(n + 1) M 2”. Рассмотрим два утверждения А₁(n) = “n нечётно”, А₂(n) = “n чётно” и докажем теорему А₁(х) Ú А₂(х), представляющую собой очевидное выс­ка­зы­ва­ние о том, что каждое натуральное число n либо чётно, либо нечётно. Если опираться только на аксиомы Пеано, то это утверждение неочевидно, и его доказательство требует привлечения аксиомы индукции. Для этого образуем множества: {n Î N | $ k Î N n = 2×k} – всех чётных чисел, {n Î N | $ k Î N n = 2×k – 1} – всех нечётных чисел и убедимся, что их объединение М равно N. Применим аксиому индукции: ясно, что 1 Î M и " m Î M m + 1 Î M (?!). На основании аксиомы индукции заключаем, что M = N.

Кроме того, доказуемы импликации А₁(х) ® A(x) и А₂(х) ® А(х): если n нечётно, то n = 2×k – 1 и n×(n + 1) = (2k – 1)×2×k = 2·k·(2·k – 1) чётно, а если n чётно, то n = 2×k и снова n×(n + 1) = 2×k×(2·k + 1) чётно. Таким образом, на основании метода перебора возможных случаев утверждение А(n) доказано.

Кстати, в этом доказательстве использована коммутативность умножения натуральных чисел. Вывести этот закон из аксиом Пеано не так-то просто.

II. Метод рассуждения от противного.Пусть о некотором математическом объекте х нужно доказать утверждение А(х). Предположим, что доказаны теоремы В(х) и (т.е. из предположения о ложности доказываемой теоремы следует отрицание доказанного ранее утверждения). Тогда А(х) следует из упомянутых теорем на основании правила опровержения: .

Доказательство. Если T₁ , … , T_k , В(х) – доказательство теоремы B(x), a S₁ , … , S_m ,– доказательство теоремы , то T₁ , … , T_k , В(х), S₁ , … , S_m , , A(x) – доказательство теоремы A(x) с использованием упомянутого правила, которое доказывается стандартно: если B(e) º 1 и ()(e) º 1, то (e)º 0, A(e) º 1.

Теорема доказана.

Пример. Доказать, что в любом прямоугольном треугольнике квадрат гипотенузы не меньше удвоенного произведения катетов.

Предположим, что высказанное утверждение А(х) неверно, т.е. для некоторого пря­мо­у­го­льного треугольника x с гипотенузой с и катетами а, b выполнено неравенство с² < 2×а×b. Используя известное неравенство о среднем арифметическом и среднем геометрическом (" х, у Î R₊ ), получим с² < 2×а×b = = a² + b², что противоречит доказанной в школе теореме Пифагора В(х) о справедливости равенства c² = a² + b². Таким образом, доказана импликация . Значит, доказана и теорема А(х).

III. Доказательство эквивалентности нескольких условий.Пусть для мате­ма­ти­чес­ко­го объекта х сформулированы условия А₁(х), … , А_n(x). Нарисуем граф с вершинами 1, … , n , в котором из вершины i выходит стрелка в вершину j тогда и только тогда, когда доказана импликация А_i(x) ® A_j(x). Если из любой вершины такого графа можно пройти по стре­лкам в любую другую вершину, то можно доказать эквивалентность всех условий А₁(х), … , А_n(x) .

Доказательство. Докажем что для любых i и j (1 £ i, j £ n) доказуема эквивалентность А_i(x) « A_j(x). В самом деле, рассмотрим в графе путь из вершины i в вершину j: i = i₁ ® … ® i_k = j. По условию, ему соответствует цепочка доказуемых импликаций . Применяя несколько раз правило силлогизма в виде , получим доказательство импликации А_i(x) ® A_j(x).

Поменяв в этих рассуждениях i и j местами, докажем А_j(x) ® A_i(x). Поскольку (x « y) º (х® y) Ù (y® x), то доказуема и эквивалентность А_i(x) « A_j(x).

Теорема доказана.

Примеры: 1.Для доказательства эквивалентности n условий А₁(х), … , А_n(x) достаточно доказать импликации А_i(х) ® A_i+1(x) (1 £ i £ n–1), A_n(x) ® A₁(x).

2.Для доказательства эквивалентности четырёх условий достаточно доказать, например, что А₁(х) « A₂(x), A₃(x) « A₄(x), А₂(x)® A₄(x), A₃(x) ® A₁(x). Какие стрелки можно убрать ?

Упражнения: 1.Приведите другие примеры доказательств с использованием перечисленных методов. Какие ещё методы математических доказательств Вы знаете ?

2. Какое минимальное число импликаций нужно доказать, чтобы обосновать эквивалентность n условий ?