Иерархия Уэджа
В описательной теории множеств , в рамках математики , степени Уоджа представляют собой уровни сложности для множеств действительных чисел . Наборы сравниваются путем непрерывных сокращений. Иерархия Ваджа представляет собой структуру степеней Ваджа. Эти концепции названы в честь Уильяма В. Уэджа.
Градусы Ваджа [ править ]
Предполагать и являются подмножествами пространства Бэра ω ой . Затем сводится ли Вадж к или ≤ 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 классы Ваджа, дополняемые по модулю, образуют хороший порядок. Ранг Ваджа в наборе — тип порядка набора степеней Ваджа, дополненных по модулю строго ниже [ ] В . Было показано, что длина иерархии Ваджа равна Θ . Уодж также доказал, что длина иерархии Ваджа, ограниченной борелевскими множествами, равна φ ω 1 (1) (или φ ω 1 (2) в зависимости от обозначений), где φ γ — это γ й Функция Веблена по основанию ω 1 (вместо обычного ω).
Что касается леммы Ваджа, то она справедлива для любого точечного класса Γ в предположении аксиомы определенности . Если мы свяжем с каждым набором коллекция всех наборов строго ниже в иерархии Ваджа это образует класс точек. Эквивалентно, для каждого порядкового номера α ≤ θ совокупность W α множеств, которые появляются перед этапом α, является точечным классом . И наоборот, каждый класс точек равен некоторому альфа . Поинт-класс называется самодвойственным, если он замкнут относительно дополнения. Можно показать, что W α является самодвойственным тогда и только тогда, когда равно 0, четному порядковому номеру-преемнику или предельному ординалу счетной α конфинальности .
степени понятия Другие
Аналогичные понятия редукции и степени возникают при замене непрерывных функций любым классом функций F , содержащим тождественную функцию и замкнутым относительно композиции . Писать ≤ F если для какой-то функции в Ф. Любой такой класс функций снова определяет предпорядок на подмножествах пространства Бэра. Степени, заданные липшицевыми функциями, называются липшицевыми степенями , а степени борелевских функций — степенями Бореля–Ваджа .
См. также [ править ]
- Аналитическая иерархия - Понятие математической логики и теории множеств.
- Арифметическая иерархия - Иерархия классов сложности формул, определяющих множества.
- Аксиома детерминированности - Возможная аксиома теории множеств
- Отношение борелевской эквивалентности
- Иерархия Бореля
- Определенность - подраздел теории множеств
- Pointclass - концепция описательной теории множеств
- Сводимость по Вейрауху - понятие из вычислимости
Ссылки [ править ]
- ^ Д. Мартин, Х. Г. Дейлс, «Истина в математике» , гл. «Математические доказательства», стр.224. Оксфордские научные публикации, 1998.
- Александр С. Кекрис ; Бенедикт Лёве; Джон Р. Стил, ред. (декабрь 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 г.