§ 1. Математическая индукция

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

Самым простым видом математической индукции является индукция на множестве натуральных чисел. Предположим, что нам нужно доказать, что все натуральные числа, т.е. числа 1, 2, 3, 4, … , обладают некоторым свойством Р. Чтобы доказать это, мы, согласно аксиоме математической индукции, должны доказать следующее:

1) доказать, что свойство Р верно для единицы 1 (этот шаг носит название базис индукции),

2) предположив, что свойство Р верно для натурального числа k, мы должны на этой основе суметь доказать, что свойство Р верно для числа (k+1) (этот шаг получил название индуктивное предположение).

Если нам удается доказать эти два пункта, то мы можем быть уверены, что свойство Р верно для всех натуральных чисел. В самом деле, в этом случае свойство Р верно для 1. Но если оно верно для 1, то, согласно второму пункту, оно верно для 2. А если верно для 2, то верно и для 3. Если верно для 3, то верно и для 4…, и так далее – верность свойства Р побежит по всей бесконечной цепочке натуральных чисел, охватив их все.

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

(А1) 2 > 1 – два больше единицы

(А2) Если (n > m) и k – любое натуральное число, то n+k > m+k – прибавление числа к обеим частям неравенства не меняет знака неравенства.

Итак, чтобы теперь доказать, что для любого натурального числа n верно свойство (n+1 > n), мы должны доказать базис индукции и индуктивное предположение:

1) базис индукции мы получим из (n+1 > n) при n=1. Это как раз 2 > 1 – наша первая аксиома (А1).

2) индуктивное предположение выражается, во-первых, в допущении, что для натурального числа k свойство выполнено, т.е. (k+1 > k). Теперь, исходя из этого, нам нужно попытаться доказать, что свойство (n+1 > n) верно для n=k+1. При n=k+1 получим, что (n+1 > n) выглядит как ((k+1)+1 > k+1), т.е. как результат прибавления единицы к обеим частям неравенства (k+1 > k), которое мы считаем верным. Следовательно, верным при этом предположении будет и свойство ((k+1)+1 > k+1), согласно второй аксиоме (А2).

Отсюда, согласно аксиоме математической индукции, мы делаем вывод, что свойство (n+1 > n) верно для любого натурального числа.

При таком применении математической индукции есть ряд тонкостей, которые необходимо иметь в виду.

Во-первых, вывод по индукции в этом случае использует понятие переменной n или k по натуральным числам. Переменная – это особый объект, который представляет собой любой конкретный объект и в то же время ни один из этих объектов в частности. Переменная – это именно переменная, т.е., например, переменная n – это и 1, и 2, и 3, и 4, …, но в то же время это и не 1, не 2, не 3, не 4, … . Это общее имя любого натурального числа, обозначающее любое из них, но ни одно в особенности. Переменная замечательна тем, что все то, что мы говорим через переменную, можно сказать о любом конкретном объекте, обозначаемым этой переменной. Например, если верно вообще, что (n+1 > n), то верно, в частности, что (4+1 > 4) или (17+1 > 17). Работая с переменной, мы как бы работаем с тем бесконечно общим, что есть во всех натуральных числах. В этом смысле идея переменной очень важна для научного познания, она как бы концентрирует в себе бесконечность множества индивидуальных объектов. Каждый такой объект, например, числа 1,2,3,…, называются частными значениями переменной. Хотя переменная обобщает нечто во всех своих частных значениях, но сама она продолжает быть обобщенной единичностью – как бы типичным представителем всех индивидуальных объектов. С этой точки зрения переменная не есть и просто общее, но скорее – общая единичность, т.е. общее во всех единичных объектах, но сохраняющая в себе существование как тоже некоторая единичность. Переменная не превращается в общее качество индивидуальных объектов, существующее само по себе и вне этих объектов, как, например, общее качество «быть натуральным числом». Нет, переменная сохраняется как объект вместе с индивидуальными объектами - как объект-общее всех этих частных объектов. Мы как бы вырезаем из всех индивидуальных объектов их общую часть и даем ей существование как самостоятельному единичному объекту наряду с частными объектами – так возникает конструкция переменной, играющая столь важную роль в математике, логике и вообще научном познании.

Во-вторых, следует отличать индуктивное предположение в математической индукции от заключения индукции. Дело в том, что по форме они звучат очень похоже – как допущение некоторого свойства Р для переменной. Но здесь нужно иметь в виду, что в индуктивном предположении мы допускаем верность свойства Р для переменной в условной форме: мы не говорим просто, что Р верно для переменной, мы утверждаем, что если бы Р было верно для переменной, то Р было бы верно и для переменной плюс один. Такая формулировка не есть формулировка самой математической индукции («Р верно для переменной»), и эту тонкость необходимо иметь в виду, чтобы не считать, что в индукции заложена тавтология.

Теперь общую схему аксиомы математической индукции можно было бы изобразить в следующем виде:

Свойство Р верно для 1

Если свойство Р верно для n, то Р верно для (n+1)

Свойство Р верно для n

Над чертой стоят две посылки – базис и индуктивное предположение. Под чертой – заключение индукции. Мы видим здесь пример обобщения – от верности свойства Р для 1 и условной верности Р для пары «переменная n - переменная (n+1)» мы переходим к безусловной верности свойства Р для переменной, т.е. для любого натурального числа. Это обобщение не несет в себе вероятности, но считается достоверным выводом, подобным выводам в формальной логике. Такая особенность математической индукции связана с особой организацией того множества объектов – натуральных чисел, - на которых индукция осуществляется. Это множество линейно упорядочено, все объекты здесь выстроены в бесконечную цепочку, что и позволяет, благодаря такой регулярности, усилить индуктивные средства и добиться более надежного вывода о свойствах всех объектов бесконечного множества на основании поведения части этих объектов. Кроме того, как мы видели, важнейшую роль в индуктивном выводе играет понятие переменной как объективированного общего всех частных объектов.

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