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

[avva]

В одной из своих замечательных заметок (англ., PDF) Дейкстра протестует против, по его мнению, вредного и приводящего к путанице понятия косвенного доказательства. Если, желая доказать A--->B (из A следует B), мы начинаем с предположения "не-B", и доказываем исходя из этого "не-A", это называется косвенным доказательством (в отличие от прямого доказательства, когда мы предполагаем A и доказываем B напрямую).

Дейкстра считает, что разделять эти два метода - нелепо, и они есть одно и то же. Действительно, с точки зрения чистой логики утверждения A--->B и (не-B)--->(не-A) совершенно эквивалентны, и доказать одно означает доказать другое. Собственно, они оба тождественно утверждению "не-A или B", которое Дейкстра предлагает считать более фундаментальным, чем обе эти версии.

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

Обратимся к еще одному примеру вредной терминологии с точки зрения Дейкстры, тесно связанному с только что упомянутым. Принцип математической индукции можно сформулировать следующим образом: если мы хотим доказать какой-то предикат (какое-то свойство) P(x) для любого натурального числа x (x = 0, 1, 2, ...), то нам достаточно доказать следующее: из того, что P выполняется для всех y меньше x, следует, что P выполняется для x. В символьном виде (∀x читается "для каждого икс...", а ∃x - "существует икс такой, что...", и эти два символа называются кванторами общности и существования): (∀y)(y<x ---> P(y)) ---> P(x). Еще раз словами: если для любого y верно, что из того, что y меньше x следует истинность P(y), тогда верно и P(x). Если мы докажем это, то принцип математической индукции гласит, что мы доказали P(x) для любого x.

(более привычная формулировка индукции, когда переходят от P(n) к P(n+1), является частным и несколько более слабым вариантом. В более общей формулировке, приведенной выше, для доказательства P(n+1) нам разрешено пользоваться не только доказанностью для предыдущего числа, P(n), но и для всех чисел, уже доказанных до сих пор, начиная с 0 - переменная y как раз и пробегает весь их список).

С другой стороны, принцип бесконечного спуска - приоритет сознательного и плодотворного его использования принадлежит Ферма - является вариантом принципа математической индукции, хоть это может и не быть очевидным заранее. При использовании принципа бесконечного спуска, желая доказать P(x) для всех x, мы доказываем следующее: если для какого-то x верно ¬P(x) (¬ означает отрицание: "не-P(x)"), то существует какое-то y меньше x, для которого тоже верно ¬P(y). Если мы докажем это, то принцип бесконечного спуска гласит, что мы доказали P(x) для всех x. С интуитивной точки зрения это объясняется так: если P(x) неверно хотя бы для какого-то x, то доказанное нами утверждение позволяет построить нисходящую цепочку таких иксов, для которых P неверно: начиная с x, потом какой-то x' меньше его, потом x'' меньше этого, и так далее без конца. Но не бывает бесконечной нисходящей цепочки натуральных чисел (не бывает "бесконечного спуска"): если, например, мы начали цепочку с числа 1000, то дальше в ней может быть не больше тысячи членов, но никак не бесконечное число.

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

(∀y)(y<x → P(y)) → P(x)

Если мы теперь "перевернем" это утверждение (т.е. от A→B перейдем к эквивалентному ¬B→¬A), то получим

¬P(x) → ¬(∀y)(y<x → P(y))

Используя формулы, связывающие два квантора, а именно тот факт, что ¬∀ эквивалентно ∃¬ (словами: если неверно, что "для всех x" выполняется то-то и то-то, то "существует" какой-то x, для которого не выполняется то-то и то-то), это можно записать как

¬P(x) → (∃y)¬(y<x → P(y))

А отрицать утверждение (y<x → P(y)) - все равно, что сказать, что его условие выполняется, а следствие - нет, т.е. одновременно верно y<x и ¬P(y), и сделав эту замену, мы приходим (используя символ ∧ в значении "и") к

¬P(x) → (∃y)(y<x ∧ ¬P(y))

что является в точности тем, что нам полагается доказать для применения принципа бесконечного спуска: если неверно P(x), то есть какой-то y, который меньше x, и для которого неверно P(y).

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

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

Об этом - через час-два в следующей записи :)

Comments

[faceted-jacinth.livejournal.com]

Хм.
А всё же.
Известно ли Вам более элегантное доказательство неравномощности вещественных и натуральных чисел, чем от противного?

Если Ваш ответ заведомом не принесёт мне ничего нового, лучше его и не пишите, я ж не для спора сюда встрял, а ради Знания, как ни пафосно это не прозвучит.

[french-man.livejournal.com]

Я не утверждаю, что доказательства от противного ВСЕГДА менее элегантны. Я утверждаю, что они чаще всего менее элегантны, чем соответсвующие прямые д-ва. Но, разумеется, есть немало исключений.

[avva.livejournal.com]

Пусть f:N->R. Построим вещественное число r, у которого целая часть 0, а десятичное разложение после запятой определяется по индукции так, что его n-я цифра не равна n-ой цифре числa f(n). Для каждого n верно, что f(n) ≠ r. Следовательно, r не принадлежит f(N). Следовательно, f(N) ≠ R. Следовательно, f не является биекцией между N и R. Поскольку мы не накладывали на f никаких условий, из этого следует, что не существует биекции между N и R.

Не от противного, верно?

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

[faceted-jacinth.livejournal.com]

Да, не от противного.

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

Ой, "на вкус и цвет все фломастеры разные", и тут это применимо в полной мере. Это спор о вкусах.

[avva.livejournal.com]

Действительно еще проще, спасибо.

[ppetya.livejournal.com]

Лучше уж (так не используется десятичное разложение) строить сразу стягивающуюся в точку систему вложенных отрезков, так что n-й отрезок не содержит первых n членов последовательности. Он и стянется к точке вне f(N).

[french-man.livejournal.com]

Вот именно это я имею в виду, говоря, что прямые д-ва изящнее и элегантнее.

[ppetya.livejournal.com]

А Вы какое доказательство имеете в виду?