Jump to content

Иерархия Уэджа

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

Градусы Ваджа [ править ]

Предполагать и являются подмножествами пространства Бэра ω ой . Затем сводится ли Вадж к или 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 если для какой-то функции в Ф. ​Любой такой класс функций снова определяет предпорядок на подмножествах пространства Бэра. Степени, заданные липшицевыми функциями, называются липшицевыми степенями , а степени борелевских функций — степенями Бореля–Ваджа .

См. также [ править ]

Ссылки [ править ]

  1. ^ Д. Мартин, Х. Г. Дейлс, «Истина в математике» , гл. «Математические доказательства», стр.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) (кандидатская диссертация). унив. Калифорнии, Беркли.

Дальнейшее чтение [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 75ebcd6b4a7b11aa90adbd432b12444d__1714789800
URL1:https://arc.ask3.ru/arc/aa/75/4d/75ebcd6b4a7b11aa90adbd432b12444d.html
Заголовок, (Title) документа по адресу, URL1:
Wadge hierarchy - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)