Нумерически Выразимый Предикат

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