Введение
В описательной теории множеств, в математике, степени Уаджа — это уровни сложности множеств вещественных чисел. Множества сравниваются посредством непрерывных редукций. Иерархия Уаджа — это структура степеней Уаджа. Эти понятия названы в честь Уильяма У. Уаджа.
Степень улочки
Предположим, что и – это подмножества пространства Байра ωω. Тогда Уодж-редуцируется к или ≤W, если существует непрерывная функция на ωω такая, что Порядок Уоджа является предпорядком или квазипорядком на подмножествах пространства Байра. Классы эквивалентности множеств относительно этого предпорядка называются степенями Уоджа, степень множества обозначается []W. Множество степеней Уоджа, упорядоченных порядком Уоджа, называется иерархией Уоджа. Свойства степеней Уоджа включают их согласованность с мерами сложности, выраженными в терминах определимости. Например, если ≤W и является счетным пересечением открытых множеств, то и тоже является счетным пересечением открытых множеств. То же самое верно для всех уровней иерархии Бореля и иерархии различий. Иерархия Уоджа играет важную роль в моделях аксиомы детерминированности. Дальнейший интерес к степеням Уоджа проявляется в информатике, где в некоторых работах предполагается, что степени Уоджа имеют отношение к алгоритмической сложности. Лемма Уоджа утверждает, что при аксиоме детерминированности (AD) для любых двух подмножеств пространства Байра, ≤W или ≤W ωω. Утверждение о том, что лемма Уоджа выполняется для множеств в Γ, называется полулинейным принципом упорядочения для Γ или SLO(Γ). Любой полулинейный порядок определяет линейный порядок на классах эквивалентности по модулю дополнений. Лемма Уоджа может быть применена локально к любому классу точек Γ, например, к множествам Бореля, множествам Δ1n, множествам Σ1n или множествам Π1n. Это следует из детерминированности различий множеств в Γ. Поскольку детерминированность Бореля доказана в ZFC, ZFC влечет лемму Уоджа для множеств Бореля. Лемма Уоджа аналогична лемме о конусе из теории вычислимости.
Лемма Уэджа через игры Уэджа и Липшица
Игра Уоджа — простая бесконечная игра, открытая Уильямом Уоджем (произносится "wage"). Она используется для исследования понятия непрерывного сведения для подмножеств пространства Байра. Уодж проанализировал структуру иерархии Уоджа для пространства Байра с помощью игр к 1972 году, но опубликовал эти результаты лишь значительно позже в своей докторской диссертации. В игре Уоджа игрок I и игрок II поочередно выбирают целые числа, а исход игры определяется проверкой того, содержатся ли последовательности x и y, сгенерированные игроками I и II, соответственно в множествах A и B. Игрок II выигрывает, если исход одинаков для обоих игроков, то есть x принадлежит A, если и только если y принадлежит B. Игрок I выигрывает, если исход различен. Иногда эту игру также называют игрой Липшица, а вариант, в котором игрок II имеет возможность сделать конечное число ходов, пропуская, называется игрой Уоджа. Предположим, что игра определена. Если у игрока I есть выигрышная стратегия, то это определяет непрерывное (даже липшицево) отображение, сводящее A к дополнению B, а если у игрока II есть выигрышная стратегия, то это определяет сведение B к A. Например, предположим, что у игрока II есть выигрышная стратегия. Отобразим каждую последовательность x в последовательность y, которую играет игрок II, если игрок I играет последовательность x, следуя своей выигрышной стратегии. Это определяет непрерывное отображение f, обладающее свойством: x принадлежит A тогда и только тогда, когда f(x) принадлежит B.
Структура иерархии Уоджа
Мартин и Монк доказали в 1973 году, что AD влечет за собой хорошо обоснованный порядок Уоджа для пространства Бейра. Следовательно, при AD классы Уоджа по модулю дополнений образуют вполне упорядоченное множество. Ранг Уоджа множества — это тип упорядочения множества степеней Уоджа по модулю дополнений, строго меньших []W. Длина иерархии Уоджа показана равной Θ. Уодж также доказал, что длина иерархии Уоджа, ограниченной множествами Бореля, равна φω1(1) (или φω1(2) в зависимости от обозначений), где φγ — γ-я функция Веблена с основанием ω1 (вместо обычного ω). Что касается леммы Уоджа, то она справедлива для любого класса точек Γ при условии аксиомы детерминированности. Если сопоставить каждому множеству коллекцию всех множеств, строго меньших его в иерархии Уоджа, то получится точечный класс. Эквивалентно, для каждого ординала α ≤ θ коллекция Wα множеств, появляющихся до стадии α, является точечным классом. Обратно, каждый точечный класс равен некоторому α. Точечный класс называется самодвойственным, если он замкнут относительно дополнений. Можно показать, что Wα самодвойственен тогда и только тогда, когда α равно 0, четному преемственному ординалу или предельному ординалу со счетной кофинальностью.
Другие понятия степени
Подобные понятия редукции и степени возникают при замене непрерывных функций любым классом функций F, содержащим тождественную функцию и замкнутым относительно композиции. Обозначим ≤F, если для некоторой функции f из F. Любой такой класс функций снова определяет предзаказ на подмножествах пространства Бейра. Степени, задаваемые функциями Липшица, называются степенями Липшица, а степени, полученные из функций Бореля, – степенями Бореля–Вадже.