БАР-ИНДУКЦИЯ

Расстановка ударений: БА`Р-ИНДУ`КЦИЯ

БАР-ИНДУКЦИЯ - индуктивный способ рассуждения, используемый в интуиционистской математике (см. Интуиционизм) и состоящий в следующем. Пусть на конечных кортежах натуральных чисел заданы нек-рые свойства R и S такие, что: 1) свойство R разрешимо, т. е. для всякого кортежа 〈 n₁, ..., n_m 〉 эффективно выясняется, выполнено R на этом кортеже или нет; 2) для всякой свободно становящейся последовательности а найдется кортеж вида 〈 α (0), ..., α (n - 1)〉, для к-рого выполнено R. При этом, если выполняется 2), то говорят, что R «запирает» пустой кортеж 〈 〉 (отсюда и назв. «Б.-и. », «bar» - «запирать», «замок»); 3) для всякого кортежа π натуральных чисел, если R (π), то S(π) - так наз. базис Б.-и. ; 4) если 〈 n₁, ..., n_m 〉 - кортеж такой, что для всякого натурального k имеет место S(〈 n₁, ..., n_m, k〉), то необходимо S (〈 n₁, ..., n_m 〉); это свойство наз. шагом Б.-и.

Если выполняются перечисленные условия 1)-4), то принцип Б.-и. позволяет заключить, что имеет место S{〈 〉).

Л. Э. Я. Брауэр (L. Е. J. Brouwer) предложил Б.-и. как интуиционистски приемлемый способ рассуждения, указывающий на незавершенность, нек-рую эффективную несчетность совокупности всех свободно становящихся последовательностей. В частности, было показано [С. К. Клини (S. С. Kleene) и независимо А. А. Марковым], что из принципа Б.-и. (фактически даже из нек-рого следствия Б.-и. теоремы о веере) следует, что не все свободно становящиеся последовательности рекурсивны.

С 60-х гг. 20 в. в основаниях математики нашли употребление формы Б.-и., рассматривающие не кортежи натуральных чисел, а кортежи более сложных объектов, напр. кортежи свободно становящихся последовательностей.

На языке формального интуиционистского математич. анализа Б.-и. может быть записана в виде:

Лит. : [1] Kleene S. С., Vesley R. В., The foundations of intuitionistic mathematics, Amst., 1965.

А. Г. Драгалин.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.