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

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

Конструкции

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

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

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

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

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

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

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

• Если ${ displaystyle phi}$ логически эквивалентно формуле вида ${ Displaystyle существует п_ {1} существует п_ {2} cdots существует п_ {к} psi}$, куда ${ displaystyle psi}$ является ${ Displaystyle Пи _ {п} ^ {0}}$, тогда ${ displaystyle phi}$ присвоена классификация ${ Displaystyle Sigma _ {п + 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 Пи _ {п + 1} ^ {0}}$.

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

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

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