Нумерически выразимый предикат

- арифметический предикат [img: http://localhost:8080/file/031513-26.jpg] обладающий по отношению к данной формальной системе S арифметики следующим свойством: существует такая формула [img: http://localhost:8080/file/031513-27.jpg] в языке арифметики формальной, что для любых натуральных чисел [img: http://localhost:8080/file/031513-28.jpg] 1) если [img: http://localhost:8080/file/031513-29.jpg] истинно, то [img: http://localhost:8080/file/031513-30.jpg] 2)еслиложно, [img: http://localhost:8080/file/031513-31.jpg] то [img: http://localhost:8080/file/031513-32.jpg] где [img: http://localhost:8080/file/031513-33.jpg] означает выводимость в системе S, а [img: http://localhost:8080/file/031513-34.jpg] [img: http://localhost:8080/file/031513-35.jpg] - результат подстановки в формулу [img: http://localhost:8080/file/031513-36.jpg] [img: http://localhost:8080/file/031513-37.jpg] вместо переменных [img: http://localhost:8080/file/031513-38.jpg] - термов, изображающих числа [img: http://localhost:8080/file/031513-39.jpg]. В этом случае говорят, что формула [img: http://localhost:8080/file/031513-40.jpg] нумерически выражает предикат [img: http://localhost:8080/file/031513-41.jpg]. Для формальной системы Sарифметики имеет место утверждение: в Sнумерически выразимы все рекурсивные предикаты и только они. n-местная арифметич. функция f наз. нумерически пррдставимой в формальной системе Sарифметики, если существует такая арифметич. формула [img: http://localhost:8080/file/031513-42.jpg] что для любых натуральных чисел [img: http://localhost:8080/file/031513-43.jpg] [img: http://localhost:8080/file/031513-44.jpg] В обычных формальных системах арифметики нумерически представимы все общекурсивные функции и только они.