Клини - мостовского классификация

- классификация теоретико-числовых предикатов, введенная независимо С. Клини [1] и А. Мостовским [2]. Через П 0 и одновременно через е 0 обозначается класс всех рекурсивных предикатов. Для всякого k>0 класс е k определяется как класс всех предикатов, выразимых в виде [img: http://localhost:8080/file/021219-40.jpg] где [img: http://localhost:8080/file/021219-41.jpg] - квантор существования, R(y, x1,..., х п)- предикат из класса П k-1, а класс П k определяется как класс предикатов, выразимых в виде [img: http://localhost:8080/file/021219-42.jpg] где [img: http://localhost:8080/file/021219-43.jpg] - квантор всеобщности, R(у, x1,..., х п)- предикат из класса е k-1. Таким образом получается последовательность классов: [img: http://localhost:8080/file/021219-44.jpg] Если предикат принадлежит классу е k или П k, то он принадлежит классам П j и е j. для любого j>k, т. е. [img: http://localhost:8080/file/021219-45.jpg] и [img: http://localhost:8080/file/021219-46.jpg] для любого j>k. Если k>0, то существуют предикаты из класса е k, не принадлежащие П k, а также предикаты из класса П k, не принадлежащие е k,т. е. [img: http://localhost:8080/file/021219-47.jpg] и [img: http://localhost:8080/file/021219-48.jpg] Предикат принадлежит одному из классов е k или П k тогда и только тогда, когда он выразим в языке арифметики формальной. Если предикат Q(x1,..., х n)принадлежит классу е k (пли П k), то предикат [img: http://localhost:8080/file/021219-49.jpg] где [img: http://localhost:8080/file/021219-50.jpg] - знак отрицания, принадлежит классу П k (соответственно е k). Предикат Q(x1,..., х n)рекурсивен тогда и только тогда, когда предикаты Q(x1,..., х п)и [img: http://localhost:8080/file/021219-51.jpg] принадлежат классу 2t, т. е. е 1 ЗП 1= е 0=П 0. Если k>0,то [img: http://localhost:8080/file/021219-52.jpg] На классификации предикатов основана классификация множеств, определимых в языке формальной арифметики: множество Мпринадлежит классу П k или е k, если этому классу принадлежит предикат [img: http://localhost:8080/file/021219-53.jpg]