Математическая энциклопедия
- арифметический предикат 
обладающий по отношению к данной формальной системе S арифметики следующим свойством: существует такая формула 
в языке арифметики формальной, что для любых натуральных чисел 
1) если 
истинно, то 
2)еслиложно,
то 
где 
означает выводимость в системе S, а 
- результат подстановки в формулу 
вместо переменных 
- термов, изображающих числа 
. В этом случае говорят, что формула 
нумерически выражает предикат 
. Для формальной системы Sарифметики имеет место утверждение: в Sнумерически выразимы все рекурсивные предикаты и только они.
n-местная арифметич. функция f наз. нумерически пррдставимой в формальной системе Sарифметики, если существует такая арифметич. формула 
что для любых натуральных чисел 
В обычных формальных системах арифметики нумерически представимы все общекурсивные функции и только они.
Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. В. Е. Плиско