Иерархия Уэджа

В дескриптивной теории множеств , в рамках математики , степени Ваджа представляют собой уровни сложности для множеств действительных чисел . Наборы сравниваются путем непрерывных сокращений. Иерархия Ваджа представляет собой структуру степеней Ваджа. Эти концепции названы в честь Уильяма В. Уэджа.

Градусы Ваджа

Предполагать $A$ и $B$ являются подмножествами пространства Бэра ω ^ой . Затем $A$ сводится ли Вадж к $B$ или $A$ ≤ _W $B$ если существует непрерывная функция $f$ на о ^ой с $A=f^{-1}[B]$. Порядок Ваджа — это предварительный порядок или квазипорядок на подмножествах пространства Бэра. Классы эквивалентности множеств под этим предпорядком называются степенями Ваджа , степенью множества. $A$ обозначается [ $A$] _В . Набор степеней Ваджа, упорядоченных по порядку Ваджа, называется иерархией Ваджа .

Свойства степеней Ваджа включают их согласованность с мерами сложности, выраженными с точки зрения определимости. Например, если $A$ ≤ _W $B$ и $B$ является счетным пересечением , открытых множеств то также $A$. То же самое работает для всех уровней иерархии Бореля и разностной иерархии . Иерархия Ваджа играет важную роль в моделях аксиомы детерминированности . Дальнейший интерес к степеням Ваджа исходит из информатики , где в некоторых статьях высказывается предположение, что степени Ваджа имеют отношение к алгоритмической сложности .

Лемма Ваджа утверждает, что согласно аксиоме детерминированности ( AD ) для любых двух подмножеств $A,B$ пространства Бэра, $A$ ≤ _W $B$ или $B$ ≤ _W ω ^ой \ $A$. Утверждение о том, что лемма Ваджа справедлива для множеств из Γ, является принципом полулинейного упорядочения для Γ или SLO(Γ). Любой полулинейный порядок определяет линейный порядок на классах эквивалентности по модулю дополнений. Лемма Ваджа может быть применена локально к любому точечному классу Γ, например, к борелевским множествам , Δ ¹ _n наборов, Σ ¹ _n наборов, или Π ¹ _n наборов. Это следует из определенности разностей множеств в Γ. Поскольку детерминированность Бореля доказана в ZFC , из ZFC следует лемма Ваджа для борелевских множеств.

Лемма Ваджа аналогична лемме о конусе из теории вычислимости.

Лемма Ваджа через игры Ваджа и Липшица

Игра Ваджа — это простая бесконечная игра, используемая для исследования понятия непрерывной редукции подмножеств пространства Бэра. Уэдж проанализировал структуру иерархии Ваджа для пространства Бэра с играми к 1972 году, но опубликовал эти результаты лишь намного позже в своей докторской диссертации. В игре Вадж $G(A,B)$, игрок I и игрок II по очереди разыгрывают целые числа, а результат игры определяется путем проверки того, содержатся ли последовательности x и y, сгенерированные игроками I и II, в наборах A и B соответственно. Игрок II выигрывает, если результат одинаков для обоих игроков, т.е. $x$ находится в $A$ тогда и только тогда, когда $y$ находится в $B$. Игрок I выигрывает, если исход разный. Иногда это также называют игрой Липшица , а вариант, в котором игрок II имеет возможность пасовать конечное количество раз, называется игрой Ваджа.

Предположим, что игра определена . Если у игрока I есть выигрышная стратегия, то это определяет непрерывное (даже липшицевое ) отображение, сокращающее $B$ в дополнение к $A$, а если, с другой стороны, игрок II имеет выигрышную стратегию, то у вас есть сокращение $A$ к $B$. Например, предположим, что у игрока II есть выигрышная стратегия. Сопоставьте каждую последовательность x с последовательностью y , в которой играет игрок II . $G(A,B)$ если игрок I разыгрывает последовательность x , а игрок II следует своей выигрышной стратегии. Это определяет непрерывное отображение f со свойством, что x находится в $A$ тогда и только тогда, когда f ( x ) находится в $B$.

Структура иерархии Ваджа

Мартин и Монк доказали в 1973 году, что AD предполагает, что порядок Ваджа для пространства Бэра вполне обоснован . Следовательно, в AD классы Ваджа, дополняемые по модулю, образуют хороший порядок. Ранг Ваджа в наборе $A$ — тип порядка набора степеней Ваджа, дополненных по модулю, строго ниже [ $A$] _В . Было показано, что длина иерархии Ваджа равна Θ . Уодж также доказал, что длина иерархии Ваджа, ограниченной борелевскими множествами, равна φ _{ω 1} (1) (или φ _{ω 1} (2) в зависимости от обозначений), где φ _γ — это γ ^й Функция Веблена по основанию ω ₁ (вместо обычного ω).

Что касается леммы Ваджа, то она справедлива для любого точечного класса Γ в предположении аксиомы определенности . Если мы свяжем с каждым набором $A$ коллекция всех наборов строго ниже $A$ в иерархии Ваджа это образует класс точек. Эквивалентно, для каждого порядкового номера α ≤ θ совокупность W _α множеств, которые появляются перед этапом α, является точечным классом . И наоборот, каждый класс точек равен некоторому $W$_альфа . Поинт-класс называется самодвойственным, если он замкнут относительно дополнения. Можно показать, что W _α является самодвойственным тогда и только тогда, когда равно 0, четному порядковому номеру-преемнику или предельному ординалу счетной α конфинальности .

Другие понятия степени

Аналогичные понятия редукции и степени возникают при замене непрерывных функций любым классом функций F , содержащим тождественную функцию и замкнутым относительно композиции . Писать $A$ ≤ _F $B$ если $A=f^{-1}[B]$ для какой-то функции $f$ в Ф. ​Любой такой класс функций снова определяет предпорядок на подмножествах пространства Бэра. Степени, заданные липшицевыми функциями, называются липшицевыми степенями , а степени борелевских функций — степенями Бореля–Ваджа .

См. также

• Аналитическая иерархия - Понятие математической логики и теории множеств.
• Арифметическая иерархия - Иерархия классов сложности формул, определяющих множества.
• Аксиома детерминированности - Возможная аксиома теории множеств
• Отношение борелевской эквивалентности
• Иерархия Бореля
• Определенность - подраздел теории множеств
• Pointclass - концепция описательной теории множеств
• Сводимость по Вейрауху - понятие из вычислимости

Ссылки

• Александр С. Кекрис ; Бенедикт Лёве; Джон Р. Стил, ред. (декабрь 2011 г.). Степени Уэджа и проективные ординалы: Семинар Кабала, Том II . Конспект лекций по логике. Издательство Кембриджского университета. ISBN  9781139504249 .
• Андретта, Алессандро (2007). «Принцип SLO и иерархия Ваджа». Жирным шрифтом, Стефан; Бенедикт Лёве; Раш, Торальф; и др. (ред.). Бесконечные игры, Материалы конференции «Основы формальных наук V», проходившей в Бонне 26–29 ноября 2004 г. Исследования по логике. Том. 11. Публикации колледжа. стр. 1–38. ISBN  9781904987758 . .
• Канамори, Акихиро (2000). Высшее Бесконечное (второе изд.). Спрингер. ISBN  3-540-00384-3 .
• Кекрис, Александр С. (1995). Классическая описательная теория множеств . Спрингер. ISBN  0-387-94374-9 .
• Уодж, Уильям В. (1983). Сводимость и определенность в пространстве Бэра (PDF) (кандидатская диссертация). унив. Калифорнии, Беркли.

Дальнейшее чтение

• Андретта, Алессандро и Мартин, Дональд (2003). «Градусы Бореля-Ваджа» . Фундамента Математика . 177 (2): 175–192. дои : 10.4064/fm177-2-5 .
• Цензер, Дуглас (1984). «Монотонная сводимость и семейство бесконечных множеств». Журнал символической логики . 49 (3). Ассоциация символической логики: 774–782. дои : 10.2307/2274130 . JSTOR   2274130 . S2CID   37813340 .
• Дюпарк, Жак (2001). «Иерархия Ваджа и иерархия Веблена. Часть I: Борелевские множества конечного ранга». Журнал символической логики . 66 (1): 55–86. дои : 10.2307/2694911 . JSTOR   2694911 . S2CID   17703130 .
• Селиванов, Виктор Львович (2006). «К описательной теории множеств для доменоподобных структур» . Теоретическая информатика . 365 (3): 258–282. дои : 10.1016/j.tcs.2006.07.053 . ISSN   0304-3975 .
• Селиванов, Виктор Львович (2008). «Сводимость Уэджа и бесконечные вычисления». Математика в информатике . 2 (1): 5–36. дои : 10.1007/s11786-008-0042-x . ISSN   1661-8270 . S2CID   38211417 .
• Дон Бриано (2006). Игра Луво для борелевских функций (препринт). унив. Амстердама, Предварительные публикации ILLC PP-2006-24 . Проверено 12 августа 2007 г.