Математическая логика и теория алгоритмов

1) натуральное число О обладает свойством С/ и 2) для всякого натурального числа 3: из того, что х обладает свойством U следует, что и натуральное число х' обладает свойством U, то свойством U обла­ дают все натуральные числа (принцип математической индукции). Заметим, что иногда аксиома Р\ формулируется иначе: 1 - есть натуральное число. В этом случае легко видеть, что аксиоматика Пеано развивает идею о том, что единица есть корень всякого числа (см. эпиграф). Этих аксиом вместе с некоторыми фактами теории множеств достаточно для построения арифметики натуральных чисел, а также теории рациональных, вещественных и комплексных чисел. Однако это построение недостаточно строго с наших позиций - не является формальной аксиоматической теорией. Поэтому зададим некоторую формальную аксиоматическую теорию, а именно: некоторую теорию первого порядка, которая оказывается достаточной для вывода всех основных результатов элементарной арифметики. Формальнойарифметикой (теорией S) называем теорию перво­ го порядка, имеющую: ® единственную предикатную букву А); ® единственную предметную постоянную а\\ ® три функциональные буквы / { , f \ , f \ , кроме того, очевидно, ее символами являются " ! ,=>, ) , ( , ' , JCi, x2,...,vxbvx2v,3xb3 хъ- Чтобы использовать привычные для нас записи, обозначим (t,s) через t=s; й] через 0; / } ( 0 через Г'; 'У f 1 { t , s ) через t+s; f \ { t , s ) - через понимается как знак умножения), Как известно, аксиомы каждой теории первого порядка, следо­ вательно, и формальной арифметики, делятся на две группы: логиче­ ские аксиомы (аксиомы А \ - А 5 ) и собственные аксиомы. Собственны­ ми аксиомами формальной арифметики являются следующие формулы; 171