Эффективная описательная теория множеств

Эффективная описательная теория множеств — это раздел описательной теории множеств, занимающийся множествами вещественных чисел, имеющими световых граней определения ; то есть определения, которые не требуют произвольного вещественного параметра (Moschovakis 1980). Таким образом, эффективная дескриптивная теория множеств сочетает в себе дескриптивную теорию множеств с теорией рекурсии .

Конструкции [ править ]

польское Эффективное пространство

Эффективное польское пространство — это полное сепарабельное метрическое пространство , имеющее вычислимое представление . Такие пространства изучаются как в эффективной дескриптивной теории множеств, так и в конструктивном анализе . В частности, стандартные примеры польских пространств, такие как действительная линия , множество Кантора и пространство Бэра , являются эффективными польскими пространствами.

иерархия Арифметическая

Арифметическая иерархия , арифметическая иерархия или иерархия Клини – Мостовского классифицирует определенные множества на основе сложности формул, которые их определяют. Любое множество, получающее классификацию, называется «арифметическим».

Более формально, арифметическая иерархия присваивает классификации формулам на языке арифметики первого порядка . Классификации обозначаются $\Sigma _{n}^{0}$ и $\Pi _{n}^{0}$ для натуральных чисел n (включая 0). Греческие буквы здесь являются светлыми символами, что указывает на то, что формулы не содержат заданных параметров.

Если формула $\phi$ формуле логически эквивалентна только с ограниченными кванторами , тогда $\phi$ присвоены классификации $\Sigma _{0}^{0}$ и $\Pi _{0}^{0}$ .

Классификации $\Sigma _{n}^{0}$ и $\Pi _{n}^{0}$ определяются индуктивно для каждого натурального числа n по следующим правилам:

Если $\phi$ логически эквивалентна формуле вида $\exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi$ , где $\psi$ является $\Pi _{n}^{0}$ , затем $\phi$ присвоена классификация $\Sigma _{n+1}^{0}$ .
Если $\phi$ логически эквивалентна формуле вида $\forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi$ , где $\psi$ является $\Sigma _{n}^{0}$ , затем $\phi$ присвоена классификация $\Pi _{n+1}^{0}$ .