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

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

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

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

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