Индуктивными называют рассуждения, в которых осуществляется переход от частных заключений к общим. Некоторое свойство подмечается на каком-то числе примеров, в какой-то момент высказывается общая гипотеза, которая затем подвергается дальнейшей экспериментальной проверке. В естественных науках наступает момент, когда проверка считается достаточной для того, чтобы принять гипотезу, посчитать ее доказанной. Вспомним, например, открытие Ч. Дарвиным закона эволюции. В математике же, когда высказывание делается о бесконечной совокупности, проверка любого конечного набора случаев не может заменить доказательства.
«Большая часть великих идей современных математиков, если не все, получила свое начало в наблюдении». Дж. Сильвестр
На заре теории чисел математики открыли многие факты индуктивным путем: Л. Эйлер и К. Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в нее. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Числа Ферма оказались простыми при k=0,1,2,3,4, но у F5 Эйлер обнаружил делитель. Числа Мерсенна Mp=2p-1, где p – простые числа, сами являются простыми при p=2,3,5,7, но не при p=11 (а потом вновь будут простыми при p=13,17,19,...). Лейбниц думал какое-то время, что n2k+1-n делится на 2k+1, проверив это при k=1,2,3. Но при k=4 это не так.
Итак, для индуктивного перехода от утверждения, проверенного для конечного подмножества, к аналогичному утверждению для всего бесконечного множества необходимо доказательство. Но как осуществить проверку бесконечного числа случаев? Такой способ предложили Б. Паскаль и Я. Бернулли. Теперь он носит название метода математической индукции. Пусть некоторое свойство надо доказать для элементов последовательности a1,a2,...,ak,.... Тогда достаточно:
1) проверить это утверждение для a1 (этот шаг называется началом или базисом индукции);
2) в предположении, что утверждение справедливо для ak, надо доказать его справедливость для ak+1(индуктивный переход).
После проведения этих рассуждений можно сделать вывод, что доказываемое утверждение справедливо для всех an.
Метод математической индукции можно образно представить как цепочку людей, в которой каждый последующий положил руки на плечи предыдущего. Тогда возникает связанная шеренга, хотя непосредственное взаимодействие происходит лишь между ближайшими соседями.
Приведем несколько примеров. Пусть an=1+2+...+n - сумма первых n натуральных чисел. Надо доказать, что an=n(n+1)/2. При n=1 имеем a1=1. Далее, если ak = k(k+1)/2, то ak+1 = ak + k + 1 = (k+1)(k+2)/2 - и теорема доказана. Другой пример: an = 1 + 3 + ... + (2n-1) - сумма нечетных чисел. Надо доказать, что an=a2. При n=1 это верно. Если ak = k2, то ak+1 = ak + (2k + 1) = k2 + 2k + 1 = (k+1)2 - и индуктивный переход проведен.
Провести индуктивный переход не всегда просто. Прежде всего, он, как и исходное утверждение, связан с бесконечным числом ситуаций (k любое). Однако успех метода математической индукции основывается на том, что очень часто провести индуктивный переход в общем случае много проще, чем непосредственно доказать исходное утверждение. Поэтому при проведении индуктивного перехода надо очень тщательно убеждаться, что рассуждение в самом деле проходит для любого k.
Часто приходится доказывать по индукции утверждение, справедливое не для всех n, а лишь для достаточно больших n, т.е. для всех n, больших некоторого заданного числа N. Тогда в основании индукции лежит проверка для aN. Докажем, что имеет место неравенство n3 - 4 > 1000n2 + 3n при n ≥ 2000. Нетрудно непосредственно убедиться, что при n = 2000 оно справедливо. Чтобы сделать индуктивный переход, заметим, что при переходе от k и k+1 к левой части прибавляется 3k2 + 3k + 1, а к правой – 2000k + 1003. Все будет доказано, если мы докажем справедливость вспомогательного неравенства 3k2 + 3k + 1 ≥ 2000k + 1003 при k ≥ 2000. При k = 2000 оно справедливо (проверяется непосредственно), а далее рассуждаем аналогично: при переходе от k и k+1 к левой части добавляется 6k + 6, а к правой - 2000. Поскольку 6k + 6 ≥ 2000 при k ≥ 2000, доказательство окончено. Этот пример иллюстрирует одновременно важную ситуацию: индуктивное предположение, в свою очередь, иногда целесообразно доказывать по индукции. При этом возникает цепочка индуктивных доказательств, причем на каждом шагу получается все более простое утверждение.
По индукции не только удобно проводить доказательства, но и давать некоторые определения. Пусть имеется некоторый человек A. Его родственниками первого порядка назовем его родителей и детей. Если определены родственники k-го порядка, то родственниками (k+1)-го порядка для A назовем родственников первого порядка для родственников A k-го порядка, которые не являются родственниками A меньшего порядка. В частности, братья и сестры при таком определении являются родственниками второго порядка. Индуктивные определения играют важную роль в математической логике и математической лингвистике.
Доказательства по индукции прочно вошли в обиход математической деятельности. Придумано огромное число модификаций метода, ориентированных на разные приложения.
МАТЕМАТИЧЕСКАЯ ЛОГИКА
«Если все вороны черные, то все нечерные предметы – не вороны». Это высказывание несомненно истинно, и, чтобы утверждать это, не нужно быть знатоком птиц. Точно так же не нужно быть специалистом в теории чисел, чтобы сказать, что если все совершенные числа четны, то все нечетные числа несовершенны. Мы привели примеры утверждений, истинных независимо от смысла входящих в них понятий (вороны, черные, совершенные, четные) – истинных уже в силу самой своей формы. Изучение такого рода утверждений входит в задачу логики. Более общо: логика изучает правильные способы рассуждений – такие способы рассуждений, которые приводят к верным результатам в тех случаях, когда верны исходные посылки.
Предметом математической логики служат в основном рассуждения. При их изучении она пользуется математическими методами. Разъясним сказанное.
Математики строят и развивают математические теории, дают определения, доказывают теоремы и т.п. Специалисты по математической логике, наблюдая за этим, анализируют, как математики это делают и что при этом получается. Образно говоря, соотношение между математикой и математической логикой похоже на соотношение между концертом и теорией музыки. Можно сказать, что математическая логика изучает основания математики, принципы построения математических теорий.
«Книга философии – это то, что всегда раскрыто перед нашими глазами, но так как она написана иными буквами, чем буквы нашего алфавита, то она не может быть прочитана всеми буквами этой книги являются треугольники, круги, шары, конусы, пирамиды и другие математические фигуры, очень пригодные для чтения ее». Г. Галилей
Установив, что изучает математическая логика, перейдем к тому, как она это делает. Нам уже известно, что она пользуется математическими методами. Объясним, что это значит. Как применяются математические методы, например, в физике? Строится математическая модель рассматриваемого физического процесса, отражающая какие-то его существенные свойства. Математические методы могут применяться не только в физике, но и в других науках. Например, применение математических методов в биологии состоит в построении математических моделей биологических процессов. Можно строить математические модели и для процесса развития математических теорий. Это и делает математическая логика.
Как устроена математическая теория? Она содержит какие-то утверждения. Некоторые из них принимаются без доказательств, другие удается доказать (в этом случае утверждения называют теоремами). Значение слов «утверждение» и «доказательство» в повседневной практике весьма расплывчато. Поэтому если мы хотим строить математическую модель, то первым делом нужно уточнить эти понятия, т.е. построить их формальные аналоги в нашей модели. Для этого математические логики придумали специальные формальные языки, предназначенные для записи математических утверждений. Утверждения, записанные на формальных языках, называют формулами, чтобы отличить их от предложений естественных языков. Построив формальный язык, мы получаем возможность записывать некоторые математические утверждения в виде формул. Этого, разумеется, еще не достаточно. Нам нужно уметь записывать формально не только утверждения, но и доказательства. Для этого математические логики придумали формальный аналог понятия «доказательство» - понятие вывода (доказательства, записанного на формальном языке). Формальным аналогом понятия «теорема» является понятие «выводимая формула» (т.е. формула, имеющая вывод). Формальный язык вместе с правилами построения выводов называется формальной системой.
Какие требования естественно предъявлять к формальной системе? Мы хотим, чтобы она была как можно более похожа на «живую», неформальную математику. Для этого нужно, чтобы все интересующие нас содержательные утверждения (или, по крайней мере, большая их часть) могли быть «переведены на формальный язык», т.е. записаны в виде формул этой системы. Кроме того, нужно, чтобы неформальные доказательства можно было перевести в выводы соответствующих формул.
В настоящее время построены вполне удовлетворительные модели (формализации) большинства математических теорий. Наиболее важны формальная арифметика и аксиоматическая теория множеств. Формальная арифметика предназначается для формализации рассуждений о натуральных числах, а аксиоматическая теория множеств – о множествах.