В дескриптивной теории множеств , в математике , степени Вэджа являются уровнями сложности для множеств действительных чисел . Множества сравниваются с помощью непрерывных сокращений. Иерархия Вэджа является структурой степеней Вэджа. Эти концепции названы в честь Уильяма В. Вэджа.
Предположим, что и являются подмножествами пространства Бэра ω ω . Тогда Вэдж сводим к или ≤ W , если существует непрерывная функция на ω ω с . Порядок Вэджа является предпорядком или квазипорядком на подмножествах пространства Бэра. Классы эквивалентности множеств при этом предпорядке называются степенями Вэджа , степень множества обозначается как [ ] W . Множество степеней Вэджа, упорядоченных порядком Вэджа, называется иерархией Вэджа .
Свойства степеней Вэджа включают их согласованность с мерами сложности, указанными в терминах определимости. Например, если ≤ W и является счетным пересечением открытых множеств , то также является . То же самое работает для всех уровней иерархии Бореля и иерархии разностей . Иерархия Вэджа играет важную роль в моделях аксиомы определенности . Дальнейший интерес к степеням Вэджа исходит из компьютерной науки , где в некоторых работах предполагается, что степени Вэджа имеют отношение к алгоритмической сложности .
Лемма Вэджа утверждает, что в соответствии с аксиомой определенности ( AD ) для любых двух подмножеств пространства Бэра ≤ W или ≤ W ω ω \ . [1] Утверждение о том, что лемма Вэджа верна для множеств в Γ, является полулинейным принципом упорядочения для Γ или SLO(Γ). ЛюбойПолулинейный порядок определяет линейный порядок на классах эквивалентности по модулю дополнений. Лемма Вэджа может быть применена локально к любому точечному классу Γ, например, к борелевским множествам , Δ 1 n множествам, Σ 1 n множествам или Π 1 n множествам. Это следует из определенности разностей множеств в Γ. Поскольку определенность Бореля доказана в ZFC , ZFC влечет лемму Вэджа для борелевских множеств.
Лемма Вэджа аналогична лемме о конусе из теории вычислимости.
Игра Вэджа — простая бесконечная игра , используемая для исследования понятия непрерывной редукции для подмножеств пространства Бэра. Вэдж проанализировал структуру иерархии Вэджа для пространства Бэра с играми к 1972 году, но опубликовал эти результаты лишь гораздо позже в своей докторской диссертации. В игре Вэджа игрок I и игрок II по очереди играют целыми числами, а результат игры определяется проверкой того, содержатся ли последовательности x и y, сгенерированные игроками I и II, в множествах A и B соответственно. Игрок II выигрывает, если результат одинаков для обоих игроков, т. е. находится в , если и только если находится в . Игрок I выигрывает, если результат отличается. Иногда это также называют игрой Липшица , а вариант, в котором игрок II имеет возможность пасовать конечное число раз, называется игрой Вэджа.
Предположим, что игра определена . Если у игрока I есть выигрышная стратегия, то это определяет непрерывное (даже липшицево ) отображение, сводящееся к дополнению , а если с другой стороны у игрока II есть выигрышная стратегия, то у вас есть сведение к . Например, предположим, что у игрока II есть выигрышная стратегия. Отобразить каждую последовательность x в последовательность y , в которой играет игрок II, если игрок I играет последовательность x , а игрок II следует своей выигрышной стратегии. Это определяет непрерывное отображение f со свойством, что x находится в , если и только если f ( x ) находится в .
Мартин и Монк доказали в 1973 году, что AD подразумевает, что порядок Вэджа для пространства Бэра является хорошо обоснованным . Следовательно, при AD классы Вэджа по модулю дополнений образуют хорошо обоснованный порядок. Ранг Вэджа множества — это тип порядка множества степеней Вэджа по модулю дополнений строго ниже [ ] W . Было показано, что длина иерархии Вэджа равна Θ . Вэдж также доказал, что длина иерархии Вэджа, ограниченная борелевскими множествами, равна φ ω 1 (1) (или φ ω 1 (2) в зависимости от обозначений), где φ γ — это γ -я функция Веблена по основанию ω 1 (вместо обычной ω).
Что касается леммы Вэджа, это справедливо для любого точечного класса Γ, предполагая аксиому определенности . Если мы свяжем с каждым набором набор всех множеств, расположенных строго ниже в иерархии Вэджа, это образует точечный класс. Эквивалентно, для каждого ординала α ≤ θ набор W α множеств, которые появляются до этапа α, является точечным классом . Обратно, каждый точечный класс равен некоторому α . Точечный класс называется самодвойственным, если он замкнут относительно дополнения. Можно показать, что W α самодвойственен тогда и только тогда, когда α равно либо 0, либо четному последующему ординалу , либо предельному ординалу счетной конфинальности .
Аналогичные понятия редукции и степени возникают при замене непрерывных функций любым классом функций F , содержащим тождественную функцию и замкнутым относительно композиции . Запишем ≤ F, если для некоторой функции из F . Любой такой класс функций снова определяет предпорядок на подмножествах пространства Бэра. Степени, заданные функциями Липшица, называются степенями Липшица , а степени из функций Бореля — степенями Бореля–Вэджа .
![{\displaystyle A=f^{-1}[B]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e9a5bdfb323be7b7e7abf1373e8ec2472113e57)
