Классификации определимых подмножеств

Для структуры $\mathcal{M}$ с носителем $\omega$ и класса синтаксической сложности $\mathfrak{C}$ говорят, что подмножество $A$ является $\mathfrak{C}$-определимым в $\mathcal{M}$, если существует $\mathfrak{C}$-формула $\Theta(x)$ языка структуры $\mathcal{M}$, такая что для всех $x\in\omega$ выполнено следующее: $x\in A$ тогда и только тогда, когда $\Theta(x)$ истинно в структуре. С. С. Гончаров и Н. Т. Когабаев [Вестн. НГУ. Сер. Матем., мех., информ., 8, № 4 (2008), 23—32] обобщили идею, предложенную Фридбергом [J. Symb. Log., 23, No. 3 (1958), 309—316], и ввели понятие $\mathfrak{C}$-классификации для $\mathcal{M}$: классификация задаётся вычислимым списком $\mathfrak{C}$-формул, таким что каждое $\mathfrak{C}$-определимое подмножество определяется единственной формулой из этого списка. Исследуются связи между $\Sigma_1^0$-, $d$-$\Sigma_1^0$- и $\Sigma_2^0$-классификациями в контексте двух семейств структур — неограниченных вычислимых структур эквивалентности и неограниченных вычислимых разнозначных структур. Устанавливается, что любая такая разнозначная структура имеет $\Sigma_1^0$-, $d$-$\Sigma_1^0$- и $\Sigma_2^0$-классификации. Также показывается, что структуры эквивалентности могут реализовать другие возможные случаи.