Арифметика Пеано

Арифметика Пеано — теория первого порядка с равенством, описывающая свойства натуральных чисел. Впервые неформально была предложена итальянским математиком Джузеппе Пеано.

Язык этой теории содержит предикатный символ равенства =, константу 0, одноместный функциональный символ S, и двуместные функциональные символы + и ×. Символ S обозначает функцию «следующее натуральное число»: S(x) = x + 1.

Термы языка арифметики определяются индуктивно: всякая переменная x есть терм; константа 0 есть терм; и если t и s есть термы, то S(t), (t + s) , (t × s) есть термы.

Формулы языка арифметики определяются индуктивно: если t и s есть термы, то выражение (t = s) есть формула; если A и B есть формулы, то A ۸ B, A ۷ B, A → B, ⌐A являются формулами; наконец, если A есть формула, а x есть переменная, то и являются формулами.

Аксиомами арифметики Пеано являются аксиомы логики первого порядка с равенством (в описанном выше языке), а также следующие аксиомы:

(1) ⌐S(x) = 0

(2) S(x) = S(y) → (x = y)

(3) x + 0 = x

(4) x = S(y) = S(x + y)

(5) x × 0 = 0

(6) x × S(y) = x × y +x

(7)

Последняя аксиома является на самом деле схемой аксиом и записывается для каждой формулы A со свободной переменной x (при этом в ней могут быть и другие свободные переменные). Данная теория обозначается PA.

Основные факты об арифметике Пеано и об арифметическом языке:

• Все аксиомы PA истинны в стандартной модели, то есть на множестве натуральных чисел с операциями «следующее натуральное число», сложение и умножение.
• Арифметика Пеано PA неразрешима — то есть не существует алгоритма, который по всякой замкнутой формуле определял бы, выводится ли она из аксиом PA. Этот результат был получен А. Чёрчем (1936) и А. Тьюрингом (1937).
• Арифметика Пеано PA неполна — то есть существует такая замкнутая формула, что ни она, ни её отрицание не доказуемы в PA. Значит, существует утверждение, истинное в стандартной модели, но не доказуемое в PA. Это первая теорема Гёделя о неполноте (1931).
• В арифметике Пеано PA недоказуемо утверждение о её непротиворечивости. Это вторая теорема Гёделя о неполноте (1931). В своей работе Гёдель показал, каким образом в арифметическом языке можно записать утверждение «PA непротиворечива».
• Формально непротиворечивость PA доказал Г. Генцен (1936), пользуясь гораздо более сильными средствами, чем доступны в PA (трансфинитной индукцией).
• В арифметическом языке невыразим предикат истинности (то есть формула, верная лишь на номерах истинных формул). Это — теорема Тарского о невыразимости истины (1936).