Эффективная дескриптивная теория множеств - Effective descriptive set theory

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

Конструкции

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

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

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

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

Основная статья: Арифметическая иерархия

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

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

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

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

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

Рекомендации

• Мэнсфилд, Ричард; Вайткамп, Гален (1985). Рекурсивные аспекты дескриптивной теории множеств. Издательство Оксфордского университета. стр.124–38. ISBN  978-0-19-503602-2. МИСТЕР  0786122.
• Мощовакис, Яннис Н. (1980). Описательная теория множеств. Северная Голландия. ISBN  0-444-70199-0. Второе издание доступно онлайн