Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

Эта запись продолжает предыдущую; прочитайте предыдущую перед этой, если вы ее еще не читали.

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

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

Итак, мы хотим доказать, что √2 не является рациональным числом, т.е. что его нельзя представить в виде дроби a/b, где a и b - целые положительные числа. "Нельзя представить" означает здесь, что дробь a/b, возведенная в квадрат, не может быть равна 2; это то, что мы понимаем под утверждением a/b ≠ √2. Для того, чтобы использовать метод бесконечного спуска, сформулируем это в качестве утверждения P(b), верного для любого потенциального знаменателя b: итак, P(b) гласит, что не существует такого a, чтобы a/b было равно √2. Мы хотим доказать, что P(x) верно для всех x, и это докажет, что √2 - иррациональное число.

Предположим, что есть такое b, для которого верно ¬P(b), отрицание P(b); это значит, что существует какое-то a, такое что a/b = √2. Отнимем от этого равенства 1 и получим (a-b)/b = √2-1. Теперь воспользуемся тем фактом, что 1/(√2-1) = √2+1: словами, если поделить 1 на корень от двух минус 1, то выйдет корень от двух плюс 1. Это легко проверить вручную. Используя это тождество, "перевернем" наше равенство (a-b)/b = √2-1, и получим

b/(a-b) = √2+1

Отнимем от обеих частей 1 и получим

(2b-a)/(a-b) = √2

Мы получили новое представление √2 в виде дроби двух целых положительных чисел, 2b-a и a-b. Это означает, что наше утверждение P(x) верно для x = a-b. Более того, ясно, что a-b < b, потому что это равенство эквивалентно a < 2b или a/b < 2, а это верно, потому что a/b = √2 < 2. Следовательно, мы начали с пары a/b, дающей при делении √2, и нашли новую пару, (2b-a)/(a-b), с тем же свойством, но знаменатель у нее меньше. Если мы теперь повторим этот процесс снова и снова, то будем получать все новые и новые пары, и их знаменатели образуют бесконечный спуск натуральных чисел - но это-то как раз и невозможно. Мы выполнили условие принципа бесконечного спуска (доказали, что из ¬P(b) следует существование x<b так что ¬P(x)), и, следовательно, доказали иррациональность √2.

Вернемся к Дейкстре, согласно утверждениям которого наше использования метода бесконечного спуска в этом доказательстве совершенно идентично использованию метода математической индукции. Как я показал выше, главный шаг в этих двух методах тождественен и отличается в двух случаях ровно тем же, чем A → B отличается от ¬B → ¬A. Это значит, что нам должно быть очень легко переделать наше доказательство так, чтобы оно использовало напрямую математическую индукцию. Давайте попробуем это сделать. Утверждение, которое мы хотим доказать - это то, что P(x) верно для любого x, где P(x) означает "x не может быть знаменателем в дробном представлении корня из двух", или более формально "не существует такого y, чтобы y/x было равно √2":

P(x) = ¬(∃y)(y/x = √2)

Когда мы доказывали, что P(x) верно для любого x с помощью метода бесконечного спуска, мы доказывали следующее утверждение, как объяснено в предыдущей записи:

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

Если P неверно для какого-то x, то есть y меньше его, для которого тоже неверно.

Но, как мы показали раньше, это совершенно тождественно тому, что требуется, чтобы доказать P(x) для всех x методом математической индукции:

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

Значит, это нам должно быть так же легко доказать, и по сути дела тем же путем, что и раньше для метода бесконечного спуска. Так, по крайней мере, утверждает Дейкстра. Давайте попробуем. Итак, мы берем какое-то конкретное x=b и предполагаем (∀y)(y<b → P(y)). Говоря словами, мы предполагаем, что нельзя представить √2 в виде дроби, знаменатель которой меньше b - считаем, что это мы уже доказали. Теперь надо сделать индукционный шаг и показать, что в виде дроби , знаменатель которой равен ровно b, его тоже нельзя представить.

... Ну и как? Как нам это сделать? Что-то никакой конкретный путь доказать напрямую нужный нам факт - что нет такого a, чтобы a/b = √2, не напрашивается, не правда ли? Что да напрашивается - это сказать "гм, давайте предположим, что можно, что есть такое a, и придем к противоречию с нашим предположением о том, что для всех знаменателей меньше нашего b это невозможно, посмотрев на (2b-a)/(a-b)". Это, несомненно, сработает, но это же именно и означает, что мы все-таки используем "косвенное" доказательство желаемого факта P(x), а не прямое, как мы хотели. Это как раз и означает в точности возврат к тому методу, которым мы воспользовались выше, по сути дела к методу бесконечного спуска. Это не то, что нам нужно - мы ведь хотим показать, что можно обойтись без "косвенного", идя напрямую; не доказывать, что из ¬P(b) следует неверность и для какого-то меньшего знаменателя, а напрямую доказать P(b), исходя из истинности для всех меньших знаменателей. Почему же мы не можем это сделать, не возвращаясь к знакомому "косвенному"?

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

Посмотрим на то, что мы собственно доказываем, потому что в этом заключается суть дела - в том, как выглядит утверждение P(x), которое мы хотим доказать. В нашей формулировке P(x) гласит "не существует такого y, чтобы y/x = √2". Отрицание P(x), ¬P(x) гласит "есть такой y, что y/x = √2", т.е. ¬P(x) утверждает существование какого-то конкретного y. Когда мы доказываем методом бесконечного спуска - что мы в данном случае умеем делать - мы начинаем с этого ¬P(x), и стараемся доказать с его помощью утверждение (∃y)(y<x ∧ ¬P(y)) - то есть, тоже утверждение о существовании какого-то конкретного y.

Как мы это делаем, как мы доказываем? Словами мы говорим: согласно нашему предположеню есть такой a, что a/b = √2. Теперь посмотрим на (2b-a)/(a-b) итд. С формальной точки зрения вот это "есть такой a" называется применением принципа экзистенциального воплощения (existential instantiation): если верно утверждение "существует такой y, что...", то мы можем "взять в руки" конкретный пример такого y, назвать его, скажем a, и дальше иметь с ним дело, как будто он есть реальное число. На словах это кажется совершенно тривиальным, но с формальной точки зрения это применение важного (хоть и простого) принципа.

Нам, в нашем мышлении, очень легко и удобно использовать этот принцип, настолько, что мы даже этого не замечаем, если не пытаемся формально все расписать. Но здесь мы можем использовать его именно потому, что мы исходим из существования чего-то. В версии с математической индукцией, когда вместо ¬B → ¬A мы пытались доказать "напрямую" A → B, мы должны были исходить из общего утверждения - а именно "P(x) верно для всех знаменателей меньше b". С общим утверждением так не поступишь - нет столь же удобного способа ввести "новую букву" и обозначить ей число, которое выполняет данное утверждение, и иметь с ней дело как с реальным числом - потому что общее утверждение верно для всех, а не для одного.

То же самое касается не только того, из чего мы исходим, но и того, что мы хотим доказать. Вернемся к бесконечному спуску: там мы исходим из существования (такого y, что y/b = √2), и хотим доказать существование (такого x, которое меньше b, но тоже может служить знаменателем в представлении √2). Существование доказать относительно "легко", потому что достаточно продемонстрировать один пример: и действительно, мы начали с a/b и пришли к (2b-a)/(a-b), и показали, что это и есть такой пример, который подходит - вот и все, существование доказано. А что в математической индукции? В той версии нам надо доказать P(b), т.е. доказать, что для всех возможных a неверно, что a/b = √2 - нам нужно доказать общее утверждение; не привести всего один пример, а пройтись по всем возможным примерам. Это относительно "тяжело".

К чему мы пришли, до сих пор? Мы увидели, что хотя с формальной точки зрения доказать A → B и ¬B → ¬A - одно и то же, на практике, когда утверждения A и B включают в себя кванторы общности и существования, нам оказывается "легко" доказать ту из этих двух версий, в которой условие и следствие являются утверждениями существования, потому что тогда мы можем естественным образом перевести условие о существовании какого-то x - в "конкретный" a, который выполняет это условие, и относиться к нему как к реальному числу. И мы можем, для доказательства существования, привести всего один какой-нибудь пример, построенный с помощью этого a. И это "легко". А версию, в которой условие и следствие являеются утверждениями общности, утверждениями "обо всех" числах, доказать "тяжело", потому что эти естественные приемы не находятся в нашем распоряжении.

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

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

Итак, мы начинаем с (∀y)(y<b → P(y)), то есть, для всех y<b верно, что y не может быть знаменателем в представлении √2 - и доказываем P(b), то есть, что то же верно для b, все время сопротивляясь импульсивному стремлению "перевернуть" и доказать другим путем. P(b) гласит, что для любого a верно, что a/b ≠ √2 - и для того, чтобы это доказать, мы можем ввести "новую букву" - какое-то a, про которое мы ничего не знаем вообще, и доказать для этого a; тогда, исходя из того, что мы не пользовались никакими свойствами a, наше утверждение будет доказано для всех возможных a (этот прием эквивалентен "экзистенциальному воплощению", но не так удобен и не так естественен для нас, потому что в отличие от него не добавляет никакой удобной информации).

Пусть a - какое-то число, и мы хотим доказать, что a/b ≠ √2. Подавляем естественное стремление предположить, что равно, и придти к противоречию - мы не хотим этого. Есть две разных возможности: либо a/b < 2, либо a/b >= 2. Во втором случае ясно, что a/b ≠ √2, поэтому мы можем предположить первый случай. Если a/b < 2, то a < 2b и a-b < b. С другой стороны, если a < b, то ясно, что a/b меньше 1 и не может быть √2, поэтому можем предположить, что a-b > 0. Возьмем наше предположение (∀y)(y<b → P(y)) и подставим в него y = a-b. Поскольку оно верно для всех возможных y>=0, и поскольку a-b>0, верно оно и для этого значения. Мы доказали, таким образом, что a-b < b → P(a-b); поскольку мы предполагаем, что a-b < b (см. выше), получаем, что доказано P(a-b). Это значит, что нет такого x, так, чтобы x/(a-b) = √2, или, другими словами, для любого возможного x выполняется, что x/(a-b) ≠ √2.

В качестве такого возможного x подставим теперь 2b-a (мы уже показали выше, что можем предположить, что a<2b и значит 2b-a>0). Получаем теперь, что (2b-a)/(a-b) ≠ √2. Это - одно из частных следствий нашего индуктивного предположения.

Обратите внимание, что при этом методе доказательства нам приходится вытаскивать "магические" формулы a-b и 2b-a "ниоткуда", непонятно, откуда они берутся. В доказательстве методом бесконечного спуска мы пришли к ним, играя с формулами начиная с a/b, но тут мы не можем этого сделать - еще одно свидетельство "неестественности" прямого подхода в данном случае, несмотря на формальную тождественность.

Итак, мы знаем, что (2b-a)/(a-b) ≠ √2, и осталось только из этого заключить, что a/b ≠ √2. Тут нам опять приходится подавить естественный импульс предположить обратное: что a/b = √2, и из этого придти к (2b-a)/(a-b). Это - еще один обещанный пример того, что с точки зрения нашего мышления не все равно, какой из двух формально тождественных методов выбрать. Нам легче и проще двигаться от равенства к равенству, чем от неравенства к неравенству, даже если формально они тождественны. И поэтому нам тяжелее и неестественнее проделать в обратном порядке с неравенством те шаги, которые мы проводили в первоначальном доказательстве с равенством; а именно, к неравенству

(2b-a)/(a-b) ≠ √2

прибавить 1 с обеих сторон и получить

b/(a-b) ≠ √2+1

Перевернуть обе стороны, используя формулу √2+1 = 1/(√2-1), и получить

(a-b)/b ≠ √2-1

Прибавить 1 еще раз и наконец придти к

a/b ≠ √2

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

Мы доказали иррациональность √2, пользуясь методом математической индукции, ни разу не "переворачивая" его в метод бесконечного спуска; но я предлагаю вам теперь оглянуться и перечитать оба доказательства, и спросить себя, какое из них выглядит проще, легче, естественней. Формально они тождественны. На практике математик всегда предпочтет, в данном случае, бесконечный спуск индукции. В случае, когда теми же методами надо было бы доказывать другое P(x), такое, для которого именно индукция давала бы "удобные" методы введения "новых букв", работы с равенствами, а не неравенствами, и так далее, математик предпочтет метод индукции, и ему и в голову не придет рассматривать проблему сквозь призму метода бесконечного спуска. Эти методы эквивалентны, но различны, и для разных задач подходят по-разному; и то же верно в общем случае выбора между "прямым" доказательством A → B и "косвенным" ¬B → ¬A. Вот почему Дейкстра неправ.

Если вы дочитали до конца - спасибо за внимание :)

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 20 comments