элементарную теорию чисел (в отличие, напр., от аналитической теории чисел). Среди них особое место занимает система, связанная с аксиоматикой Дж. Пеано. Эта формальная система (система Р) является отправным пунктом многих современных логико-матем. исследований. Язык системы Р содержит символы О и 1 и знаки арифм. операций сложения и умножения. Выражения вида 
служат для обозначения натуральных чисел; они наз. цифрами (0 и 1 тоже включаются в число цифр). Кроме того, язык системы Р содержит потенциально бесконечное число символов для переменных: а, 
Выражения, которые можно построить из символов 0,1 и переменных с помощью сложения и умножения, наз. термами (цифры — это частный случай термов). Выражения вида где 
термы, суть элементарные формулы. Остальные формулы арифметики строятся из элементарных согласно обычным правилам логики предикатов, т. е. с помощью логич. связок и кванторов. Различают свободные и связанные переменные. Формула, не имеющая свободных переменных, представляет собой некоторое высказывание о натуральных числах (истинное или ложное). Формула, зависящая от n свободных переменных, задает некоторый 
-местный теоретико-числовой предикат.
Дедуктивный аппарат системы Р устроен следующим образом. Помимо аксиом и правил вывода классического исчисления предикатов с равенством, имеются еще арифм. аксиомы, описывающие некоторые характерные свойства натуральных чисел:
Кроме того, имеется схема аксиом матем. индукции:
где 
— любая арифм. формула. Используя указанные аксиомы и правила вывода, определяют понятие доказуемости. В рамках системы Р можно построить значительную часть арифметики. С помощью схемы индукции доказываются осн. законы сложения и умножения (переместительный, сочетательный, распределительный). Отношение 
выражается формуле 
при этом доказуемыми оказываются осн. свойства неравенств. Аналогично в языке системы Р выражается ряд отношений, связанных с делимостью. Напр., утверждение о том, что при делении а на 
получают частное 
и остаток 
, записывается так:
Таким путем формализуется теория делимости (включая теоремы о наибольшем общем делителе, элементарные свойства простых чисел и т. п.). Приведенные факты показывают, что система Р достаточно сильна. Опираясь на указанные возможности данной формальной системы, в ее рамках можно моделировать любые вычисления и провести т. о. далеко идущую аналогию между системой Р и вычисл. машиной.
Механизм такого моделирования разработал австр. математик К. Гёдель 1931. Он показал, что для каждой примитивно рекурсивной ф-ции 
можно построить арифм. формулу 
выражающую отношение 
Построение этой формулы проводится индукцией по длине примитивно-рекурсивного описания ф-ции 
Так, напр., если 
является суперпозицией примитивно рекурсивных ф-ций 
и если соответствующие формулы 
и уже построены, то формула 
определяется так:
Аналогично, если ф-ция 
получена по схеме примитивной рекурсии из более простых ф-ций g (х) и h (х, у, z), то формула 
строится как некоторая стандартная комбинация соответствующих формул 
Выражаясь современным языком, можно сказать, что процедура построения формул вида 
(процедура Гёделя) представляет собой транслятор с языка примитивно-рекурсивных программ на язык А. ф. Благодаря гёделевской процедуре, в Р можно доказывать различные свойства примитивно-рекурсивных ф-ций. Напр., исходя из примитивно-рекурсивного описания показательной ф-ции 
легко доказать по индукции тождество 
Гёделев-ская процедура позволяет сформулировать и доказать это тождество в системе Р, несмотря на то, что в последней отсутствует знак для операции возведения в степень. Вообще имеет место следующее утверждение. Пусть к языку системы Р присоединены добавочные символы, обозначающие какие-либо примитивно-рекурсивные ф-ции. Добавим в качестве новых аксиом определяющие равенства для этих ф-ций. Тогда полученная таким способом расширенная система Р оказывается по существу эквивалентной исходной системе Р. Каждая формула, выводимая в Р, после некоторой перекодировки переходит в формулу, выводимую в Р (перекодировка нужна для устранения избыточных символов, осуществляется она с помощью гёделевской процедуры и, конечно, не меняет смысла формулы). Разобранное свойство обеспечивает системе Р значительную гибкость и делает удобным ее использование в различных метаматем. исследованиях (см. Арифметизация метаматематики).
Важным проявлением описанного эффекта, достигаемого процедурой Гёделя, является возможность моделировать в системе Р произвольные вычисления. Известно, что работу
любого алгоритма в любое заданное число шагов можно описать посредством подходящей примитивно-рекурсивной ф-ции. Но для каждой такой ф-ции 
имеет место следующее утверждение. Пусть 
. Тогда в Р доказуема формула 
и для любого 
доказуема формула 
. Отсюда следует, напр., что для любой Тьюринга машины и для любого набора исходных данных можно построить вывод, который воспроизводит шаг за шагом процесс работы данной машины. Поэтому, если машина применима к исходным данным и вычисляет некоторый результат, то этот факт может быть установлен в системе Р.
Несмотря на богатство выразительных и дедуктивных средств, система Р неполна, т. е. в ней нельзя вывести все истинные арифм. утверждения (см. Гёделя теоремы о неполноте). Можно строить более сильные формальные системы, присоединяя к системе Р какие-нибудь истинные, но не выводимые в ней утверждения в качестве новых аксиом. Требуется лишь, чтобы множество аксиом полученной системы можно было перечислить посредством подходящего алгоритма. Всякая такая система тоже неполна. Однако можно построить трансфинитную последовательность формальных систем возрастающей силы, которые в совокупности исчерпывают все истинные утверждения о натуральных числах, выразимые в арифм. языке. В этом направлении ведутся интенсивные исследования.
Лит.: К лини С. К. Математическая логика. Пер. с англ. М., 1973 [библиогр. с. 451—465], Гуцстейн Р. Л. Математическая логика. Пер. с англ. М., 1961; Feferman S. Transfinite recursive progressions of axiomatic theories. «The journal of symbolic logic», 1962, v. 27, № 3. H. В. Белякин.
