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

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

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

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

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

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

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

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

Эта статья по теории множеств — заглушка . Вы можете помочь Википедии, расширив ее.

• в
• т
• е