Апология математики (сборник статей)

Принцип наименьшего числа может быть использован для построения нового варианта «стандартного рассуждения», призванного обосновать истинность универсальной формулировки. Вспомним, что мы обосновывали её, делая последовательные переходы от A(1) к A(2), от A(2) к A(3) и т. д. Теперь же будем рассуждать от противного. Покажем, как строится рассуждение, на примере 26. Предположим, что бывают карты указанного вида, которые нельзя правильно раскрасить. Назовём число n «плохим», если существует карта, образованная n прямыми, которую нельзя правильно раскрасить. По предположению «плохие» числа существуют; следовательно, множество всех таких чисел не пусто. Применяя к нему принцип наименьшего числа, получаем, что существует наименьшее «плохое» число a. В силу базиса индукции а ≠ 1. Значит, a = k + 1, где k – натуральное число. Так как a – наименьшее из «плохих» чисел, то k не является плохим; следовательно, всякую карту, образованную k прямыми, можно правильно раскрасить. Но тогда в силу индукционного шага можно правильно раскрасить и всякую карту, образованную a = k + 1 прямыми. Полученное противоречие убеждает нас, что исходное предположение о существовании карт, не допускающих правильной раскраски, не соответствует действительности. Таким образом, мы получили доказательство того, что всякую карту, образованную прямыми, можно раскрасить правильно.

Полная и неполная индукция

Метод индукции в самом общем смысле состоит в переходе от частных формулировок к формулировке универсальной. Различают полную и неполную индукцию. Метод математической индукции позволяет, применяя некоторое логическое рассуждение к произвольному натуральному числу, убедиться, что A истинно для этого произвольного числа, а значит, убедиться что A(n) истинно для всех n. В этом смысле данный метод является методом полной индукции; слово «полная» означает, что мы лишь тогда считаем себя вправе объявить об истинности универсальной формулировки, когда мы убедились в её истинности для каждого отдельного значения n – во всей полноте этих значений, без исключения. Метод неполной индукции состоит в переходе к универсальной формулировке после проверки частных формулировок для отдельных, но не всех значений n.

Примеры неполной индукции встречаются на каждом шагу. Скажем, если не все, то многие уверены, что Бенджамин Франклин был президентом Соединённых Штатов. «Президент Франклин» – такое можно услышать и от кассира в банке, и с экрана телевизора, причём от персонажей, которых трудно заподозрить в глубоком знании американской политической истории. А откуда же возникла подобная уверенность? Дело в том, что портрет Франклина мы видим на 100-долларовой банкноте, а едва ли не каждый знает: на лицевой стороне долларовых банкнот помещены заключённые в овал портреты американских президентов. И действительно, на однодолларовой купюре изображён первый президент Джордж Вашингтон, на двухдолларовой – третий президент Томас Джефферсон, на пятидолларовой – шестнадцатый президент Авраам Линкольн, на двадцатидолларовой – седьмой президент Эндрю Джексон, на пятидесятидолларовой – восемнадцатый президент Улисс Грант. Однако попытка установить порядковый номер президентства Франклина встречает непреодолимые затруднения. Дело в том, что Франклин не был президентом США. (Как не был президентом США и Александр Гамильтон, чей портрет украшает десятидолларовую купюру.)

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

Если магазин, закупающий яблоки ящиками, серьёзно подходит к делу, он подвергнет дегустации не одно, а несколько яблок (но, конечно, не все) из каждого ящика. Если результат дегустации оказался положительным, магазин закупает все ящики целиком, т. е. на практическом уровне принимает решение «Все яблоки хорошие», а следовательно, опять-таки применяет неполную индукцию. Сходная процедура применяется при контроле качества многих товаров. Чтобы проверить, хорошо ли сделана, скажем, электрическая лампочка, нужно её разбить, т. е. уничтожить как товар. Таким образом, полный контроль партии в тысячу лампочек предполагает тотальное уничтожение всей партии. Разработана математическая теория, которая указывает, сколько яблок из ящика или лампочек из тысячи надо опробовать, чтобы при положительном результате их исследования можно было с большой вероятностью заключить о годности всех яблок или всех лампочек партии.