Философская энциклопедия - бесконечная индукция

БЕСКОНЕ́ЧНАЯ ИНДУКЦИЯ

тот крайний вид индуктивного умозаключения, когда общее высказывание (суждение, положение) получается как заключение из бесконечной совокупности посылок, исчерпывающих все частные случаи.

Пример Б. и.: 1 + 0 = 0 + 1; 1 + 1 = 1 + 1; 1 +2 = 2 + 1; 1 + 3 = 3 + 1; 1 + 4 = 4 + 1; 1 + 5 = 5 + 1; 1 + 6 = 6 + 1; 1 + 7 = 7 + 1,...; следовательно, для всякого натурального (т.е. целого неотрицательного) числа x имеет место равенство 1 + х = х + 1.

Этот пример является частным случаем более общей схемы умозаключения:

0 обладает свойством S,

1 обладает свойством S,

2 обладает свойством S,

3 обладает свойством S.

......................................

Следовательно, все натуральные числа обладают свойством S.

Формально такое умозаключение выражается в виде схемы

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

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

[S (x) → S (x + 1) означает: "если x обладает свойством S, то и х + 1 обладает свойством S"].

Однако Б. и. играет важную роль в ряде теоретич. построений, особенно в области математич. логики и оснований математики. Потребность в рассмотрении Б. и. объясняется тем, что иные виды индукции не могут вполне ее заменить: полная математич. индукция значительно слабее Б. и., т.к. применима лишь в случае наличия уже среди посылок нек-рого общего положения [S (x) → S (x + 1)]; неполная индукция неточна, а ее высшая форма – естеств.-науч. индукция – не поддается точному изучению математич. методами, т.к. ее отличие от обычной неполной индукции имеет скорее диалектич., чем формальный, характер.

Необходимость привлечения Б. и. при обосновании тех или иных областей математики вызывается наличием серьезных трудностей в деле обоснования даже таких ее элементарных разделов, как арифметика. Это те трудности, к-рые связаны с открытым К. Гёделем (1931) явлением принципиальной неполноты и непополнимости всякого формального исчисления, получающегося в результате формализации арифметики (т.е. такого уточнения ее логич. основ., к-рое позволяет сделать их предметом математич. изучения) и содержащего конечное число аксиом и правил вывода (т.е. схем умозаключения), каждое из к-рых финитно (в том смысле, что имеет лишь конечное число посылок и допускает алгоритм, позволяющий в каждом частном случае по посылкам и заключению проверять, правильно ли сделанное умозаключение). Как показал Гёдель, во всяком таком исчислении можно найти формулу, недоказуемую и неопровержимую в нем. Это усугубило высказывавшиеся ранее лишь интуиционистами (см. Интуиционизм) сомнения в том, что всякое арифметич. предложение является истинным или ложным (см. Исключенного третьего закон). Кроме того, обнаружилась возможность получения все новых и новых истинных предложений арифметики, но недоказуемых в рамках уже построенных исчислений (пример формулы Гёделя как раз таков), а поэтому таких, что их истинность все менее и менее обоснована.

Попыткой выхода из этих трудностей и является использование принципа Б. и. в вопросах обоснования математики. Только использование это состоит не в том, что на самом деле умозаключают по этому принципу (это физически невозможно), а имеет более абстрактный характер. Этот принцип, напр. в виде схемы (*), добавляют к формальному исчислению в качестве правила вывода, в отличие от обычных, не финитного. При этом исследуется вопрос о том, что дает такое добавление, каков становится в результате класс доказуемых формул.

Впервые такой путь предложил в 1934 в связи с изучением свойств формальных "языков", охватывающих язык арифметики, Карнап, показавший, что после добавления схемы (*) к обычной формальной арифметике всякое ее элементарное (т.е. не содержащее иных переменных, кроме имеющих областью своих значений множество натуральных чисел) предложение становится либо доказуемым, либо опровержимым. В связи с этим схему (*) часто называют "правилом Карнапа". Именно схему (*) обычно и называют также "правилом Б. и.", хотя не всякая Б. и. может быть сведена к этой схеме, а лишь такая, при к-рой посылки можно перенумеровать натуральными числами; последнее же возможно не во всех случаях из-за существования различных мощностей бесконечных множеств (см. Множеств теория).

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

При изучении нек-рых вопросов достаточно использования ограниченной Б. и., т. е. такой, при к-рой "длины" доказательств ограничены сверху нек-рым фиксированным конструктивным порядковым числом. Ее достаточно, напр., при обосновании непротиворечивости закона исключенного третьего в формальной арифметике (по методам Г. Генцена, К. Шютте и др.). Однако, как показали исследования Б. Россера (1937), развитые далее учеником П. С. Новикова Б. Я. Фалевичем (1955), в случае, когда в предложениях данного исчисления есть переменные, имеющие областью значений множество действит. чисел или множество свойств натуральных чисел (предикатные переменные), никакой ограниченной Б. и. недостаточно для преодоления явления неполноты, аналогичного имеющемуся в формальной арифметике без Б. и.

В случае же неогранич. Б. и., т. е. использования схемы (*) при сколь угодно длинных трансфинитных доказательствах, формальная арифметика с предикатными переменными (но без кванторов по ним) уже становится полной в том смысле, что всякое ее истинное (при всех значениях переменных) предложение является доказуемым. Это имеет место, как показал А. В. Кузнецов (1956), и в случае использования лишь т.н. конструктивной Б. и., т. е. такой Б. и., когда всякому доказательству сопоставлен нек-рый конструктивный объект (см. Алгоритм), напр. номер, с ним связанный, и применение схемы (*) допускается лишь тогда, когда существует алгоритм, дающий по числу n номер доказательства n-й посылки [т.е. S (n)]. При этом номера доказательств должны строиться так, чтобы можно было по номеру алгоритмически восстанавливать весь ход доказательства, в частности выписывать последнее в виде такой трансфинитной цепочки предложений, к-рая в процессе ее написания на каждом шагу конечна, причем каждый следующий выписываемый член ставится, относительно уже написанных членов, на такое место, к-рое ему указывается алгоритмом.

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

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Кузнецов А. В., Полнота системы аксиом арифметики с правилом конструктивно-бесконечной индукции, "Успехи матем. наук", М., 1957, т. 12, вып. 4(76); Carnap R., Logische Syntax der Sprache, W.,1934, в англ. пер. – The logical syntax of language, N. Y. – L., 1937, [pacшир. изд.].

А. Кузнецов. Москва.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.