Иерархия Вейджа

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

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

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

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

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

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

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

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

Что касается леммы Вэджа, это справедливо для любого точечного класса Γ, предполагая аксиому определенности . Если мы свяжем с каждым набором набор всех множеств, расположенных строго ниже в иерархии Вэджа, это образует точечный класс. Эквивалентно, для каждого ординала α  ≤ θ набор W _α множеств, которые появляются до этапа α, является точечным классом . Обратно, каждый точечный класс равен некоторому _α . Точечный класс называется самодвойственным, если он замкнут относительно дополнения. Можно показать, что W _α самодвойственен тогда и только тогда, когда α равно либо 0, либо четному последующему ординалу , либо предельному ординалу счетной конфинальности .${\displaystyle А}$${\displaystyle А}$${\displaystyle W}$

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

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

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

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