Спирина, М.С. Дискретная математика

5.6.3. Формальная аксиоматическая теория для арифметики натуральных чисел В основании арифметики или теории чисел, как и в геомет­ рии, лежит система аксиом, в которой неопределяемыми поня­ тиями являются единица, натуральное число, множество и отно­ шение «следовать за». С их помощью определяются другие понятия теории чисел. Основные аксиомы арифметики сформулировал ита­ льянский математик Д .Пеано (1858— 1932). Остальные выводи­ мые свойства, теоремы, доказываются с помощью этих аксиом, а также неопределяемых и определяемых понятий. Следует помнить выводы первой теоремы Гёделя, согласно которой даже в непро­ тиворечивой теории существуют невыводимые формулы. Формальная аксиоматическая теория S для арифметики нату­ ральных чисел. I. Введем формальные символы в качестве букв алфавита языка теории S. Будем использовать алфавит из 12 букв: • логические символы: =>, V, =; • символы для обозначения предметных переменных языка те ­ ории: х, I; • символы, обозначающие операции в теории S: 0, ', +, •; • левая и правая скобки: ( , ). Других знаков в теории S нет, кроме слов метаязыка. Так, переменные предметного языка системы S можно запи­ сать с помощью двух букв х и I в виде х(, Хи и т .д . Но записи вида *шшш 1 — громоздкие, и для удобства принято в записи перемен­ ных использовать арабские цифры 1, 2, ..., 9, ... (т.е. х11Ш1Ш= Хд) и др. Так как алфавит теории S не содержал таких символов, то их взяли из другого языка — метаязыка, поэтому мы называем их метазнаками. Подчеркнем еще раз, что их используют исключи­ тельно для удобства, и при желании от них можно отказаться. Рассмотрим семантический смысл знаков. 1. Выбрав в качестве минимального набор логических символов (отрицание), = (равенство), => (логическое следование), V (знак общности), мы сможем через них выразить и все остальные логи- ческие символы, такие, как v , 3, например 3 Р (х) = VxP(x). Знак = будем применять при совпадении объектов. 2. Переменные предметного языка (т.е. метаматематические обозначения х ь х2, ..., х„) принимают значения из натурального ряда чисел и числа 0. 3. Функциональная буква ' (штрих) обозначает функцию с одним аргументом (унарную операцию) — операцию перехода d e f от числа х к следующему за ним, т.е. х ' = х+ 1. Функциональные знаки +, • совпадают по смыслу с привычными бинарными опе­ рациями сложения и умножения. Умножение определяется через 267