КЛИНИ - МОСТОВСКОГО КЛАССИФИКАЦИЯ

- классификация теоретико-числовых предикатов, введенная независимо С. Клини [1] и А. Мостовским [2]. Через П ₀ и одновременно через е ₀ обозначается класс всех рекурсивных предикатов. Для всякого k>0 класс е _k определяется как класс всех предикатов, выразимых в виде где - квантор существования, R(y, x₁, ..., х _п)- предикат из класса П _k-1, а класс П _k определяется как класс предикатов, выразимых в виде где - квантор всеобщности, R( у, x₁, ..., х _п)- предикат из класса е _k-1. Таким образом получается последовательность классов:

Если предикат принадлежит классу е _k или П _k, то он принадлежит классам П _j и е _j. для любого j>k, т. е. и для любого j>k. Если k>0, то существуют предикаты из класса е _k, не принадлежащие П _k, а также предикаты из класса П _k, не принадлежащие е _k,т. е.и

Предикат принадлежит одному из классов е _k или П _k тогда и только тогда, когда он выразим в языке арифметики формальной. Если предикат Q(x₁, ..., х _n )принадлежит классу е _k (пли П _k), то предикат где - знак отрицания, принадлежит классу П _k (соответственно е _k). Предикат Q(x₁, ..., х _n )рекурсивен тогда и только тогда, когда предикаты Q(x₁, . .., х _п )и принадлежат классу 2_t, т. е. е ₁ ЗП ₁= е ₀=П ₀. Если k>0,то

На классификации предикатов основана классификация множеств, определимых в языке формальной арифметики: множество Мпринадлежит классу П _k или е _k, если этому классу принадлежит предикат

Лит.:[1] Кlееne S. С, "Trans. Amer. Math. Soc", 1943, v. 53 p. 41-73; [2] Mostowski A., "Fund, math.", 1947, v. 34, p. 81 -112.

В. Е. Плиско.