о доказательствах, часть 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, ( Collapse )
