Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

арифметику), для которой будут сформулированы (перечислены) собственные аксиомы. 4. Правилами вывода во всякой теории первого порядка являются: 1) modusponens: В является непосредственным следствием^ иА^В; 2) правило обобщения (Gen): из А следует Vxf А, точнее Vxf А является непосредственным следствием из А. Теория первого порядка, не содержащая собственных аксиом, называется исчислением предикатов первого порядка и обозначается через Ki. Единица есть корень всякого числа, и она находится вне чисел. Корень числа она потому, что через неё определяют всякое число. Вне чисел она потому, что определяется сама по себе, т.е. без какого-либо другого числа. Остальные же числа не могут быть найдены без единицы. Аль-Хорезми. § 14. Формальная арифметика (теория S) Первое полуаксиоматическое построение арифметики было предложено Дедекиндом (1901), далее усовершенствовано Пеано и известно под названием "система аксиом Пеано". Эта система формулируется следующим образом: Р1:0 - есть натуральное число; Р2: для любого натурального числа х существует другое натуральное число, обозначаемоех ' и называемое непосредственно следующим за х; РЗ: Офх ' для любого натурального числа х; Р4: еслих ' = ', то х=у; Р5: если и есть свойство, которым, быть может, обладают одни и не обладают другие натуральные числа, и если: 1) натуральное число О обладает свойством U и 2) для всякого натурального числа х из того, что х обладает свойством U следует, что и натуральное числох ' обладает свойством U, то свойством и обладают все натуральные числа (принцип математической индукции). Заметим, что иногда аксиома Р1 формулируется иначе: 1 - есть натуральное число. В этом случае легко видеть, что аксиоматика Пеано развивает идею о том, что единица есть корень всякого числа (см эпиграф). Этих аксиом вместе с некоторыми фактами теории множеств достаточно для построения арифметики натуральных чисел, а также теории рациональных, вещественных и комплексных чисел. Однако это построение недостаточно строго с наших позиций - не является формальной аксиоматической теорией. Поэтому зададим ее в виде формальной аксиоматической теории, а именно в 124