Значение ФОРМАЛЬНАЯ АРИФМЕТИКА в Большой советской энциклопедии, БСЭ

ФОРМАЛЬНАЯ АРИФМЕТИКА

арифметика, формулировка арифметики в виде формальной (аксиоматической) системы (см. Аксиоматический метод ) . Язык Ф. а. содержит константу 0, числовые переменные, символ равенства, функциональные символы +, , ' (прибавление 1) и логические связки (см. Логические операции ) . Постулатами Ф. а. являются аксиомы и правила вывода исчисления предикатов (классического или интуиционистского в зависимости от того, какая Ф. а. рассматривается), определяющие равенства для арифметических операций:

а + 0 а , а + b- ( а + b ),

а 0 0, а b- ( а b ) + а ,

аксиомы Пеано:

ù( а- 0), a- b- - а b ,

( a b & а с ) - b с , а b - a ' b '

и схема аксиом индукции:

А (0) & " x ( А ( х ) - А ( x ')) - " xa ( x ).

Средства Ф. а. достаточны для вывода теорем элементарной теории чисел. В настоящее время, по-видимому, неизвестно ни одной содержательной теоретико-числовой теоремы, доказанной без привлечения средств анализа, которая не была бы выводима в Ф. а. В Ф. а. изобразимы рекурсивные функции и доказуемы их определяющие равенства. Это позволяет, в частности, формулировать суждения о конечных множествах. Более того, Ф. а. эквивалентна аксиоматической теории множеств Цермело v Френкеля без аксиомы бесконечности: в каждой из этих систем может быть построена модель другой.

Ф. а. удовлетворяет условиям обеих теорем Гёделя о неполноте. В частности, имеются такие полиномы Р , Q от 9 переменных, что формула " x 1 ... " x 9 ( P ¹ Q ) невыводима, хотя и выражает истинное суждение, а именно непротиворечивость Ф. а. Поэтому неразрешимость диофантова уравнения Р - Q 0 недоказуема в Ф. а. Непротиворечивость Ф. а. доказана с помощью трасфинитной индукции до ординала e0 (наименьшее решение уравнения we e). Поэтому схема индукции до e0 недоказуема в Ф. а., хотя там доказуема схема индукции до любого ординала a < e0. Класс доказуемо рекурсивных функций Ф. а. (т. е. частично рекурсивных функций, общерекурсивность которых может быть установлена средствами Ф. а.) совпадает с классом ординально рекурсивных функций с ординалами < e0.

Не все теоретико-числовые предикаты выразимы в Ф. а.: примером является такой предикат T, что для любой замкнутой арифметической формулы А имеет место Т (e А ù) ' А, где e А ù v номер формулы А в некоторой фиксированной нумерации, удовлетворяющей естественным условиям. Присоединение к Ф. а. символа Т с аксиомами типа

Т (e А & B ù) ' Т (e А ù) & Т (e B ù),

выражающими его перестановочность с логическими связками, позволяет доказать непротиворечивость Ф. а. Похожая конструкция (но уже внутри Ф. а.) доказывает, что схему индукции нельзя заменить никаким конечным множеством аксиом. Ф. а. корректна и полна относительно формул вида $ x 1... $ xk ( P Q ); замкнутая формула из этого класса доказуема тогда и только тогда, когда она истинна. Так как этот класс содержит алгоритмически неразрешимый предикат, отсюда следует, что проблема выводимости в Ф. а. алгоритмически неразрешима.

При задании Ф. а. в виде генценовской системы осуществима нормализация выводов, причём нормальный вывод числового равенства состоит только из числовых равенств. На этом пути было получено первое доказательство непротиворечивости Ф. а. Нормальный вывод формулы с кванторами может содержать сколь угодно сложные формулы. Полная подформульность достигается после замены схемы индукции на со-правило, позволяющее вывести В - " xA ( x ) из В - A (0), B - A (1),... Понятие w-вывода (т. е. вывода с w-правилом) высоты < e0 выразимо в Ф. а., поэтому переход к w-выводам позволяет устанавливать в Ф. а. многие метаматематические теоремы, в частности полноту относительно формул вида $ x1... $ xk ( P Q ) и ординальную характеристику доказуемо рекурсивных функций.

Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Hilbert D., Bernays P., Grundlagen der Mathematik, 2 Aufl., Bd 1v2, В., 1968v70.

Г. Е. Минц.

Большая советская энциклопедия, БСЭ.