Детерминированность

Дэвид Гейл и Ф.М. Стюарт доказали, что открытые и закрытые игры являются определяется. Детерминированность для второго уровня игр иерархии Бореля была показана Вулфом в 1955 году. В течение следующих 20 лет дополнительное исследование с использованием все более сложных аргументов установило, что третий и четвертый уровни иерархии Бореля являются детерминированными.

В 1975 г. Дональд А. Мартин доказал, что все игры Бореля детерминированы; то есть, если A является борелевским подмножеством пространства Бэра, то определяется G A. Этот результат, известный как детерминированность по Борелю, является наилучшим возможным результатом детерминированности, доказуемым в ZFC, в том смысле, что детерминированность следующего более высокого класса Wadge не доказуема в ZFC.

В 1971 году, прежде чем Мартин получил свое доказательство, Харви Фридман показал, что любое доказательство определенности Бореля должно существенно использовать аксиому замены, чтобы повторяйте аксиому powerset бесконечно часто. Работа Фридмана дает поэтапный результат, детализирующий, сколько итераций аксиомы powerset необходимо, чтобы гарантировать определенность на каждом уровне иерархии Бореля.

Для каждого целого числа n ZFC \ P доказывает определенность на n-м уровне иерархии разностей наборов $\Pi \; 3\; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; Pi\}\; \_\; \{3\}\; ^\; \{0\}\}$, но ZFC \ P не доказывает, что для каждого целого числа n nth определен уровень иерархии различий наборов $\Pi \; 3\; 0\; \{\backslash \; displaystyle\; \backslash \; Pi\; \_\; \{3\}\; ^\; \{0\}\}$. См. обратную математику для получения информации о других отношениях между детерминированностью и подсистемами арифметики второго порядка.

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

Измеримые кардиналы

Из существования измеримого кардинала следует, что каждая аналитическая игра (также называемая Σ1игрой) детерминирована, или, что эквивалентно, каждая коаналитическая (или Π1) игра определена. (Определения см. В Проективная иерархия.)

На самом деле измеримого кардинала более чем достаточно. Более слабый принцип - наличие 0 достаточно, чтобы доказать коаналитическую определенность, и даже немного больше: точный результат состоит в том, что существование 0 эквивалентно определенности всех уровней иерархии разностей ниже Уровень ω, то есть ω · n- Π1определенность для каждого $n\; \{\backslash \; displaystyle\; n\}$.

От измеримого кардинала мы можем очень немного улучшить это до определенности ω- Π1. Из существования более измеримых кардиналов можно доказать определенность большего количества уровней иерархии различий по Π1.

Доказательство определенности по точкам

Для каждого действительного числа r $\Sigma \; 1\; 1\; (r)\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{1\}\; ^\; \{1\}\; (r)\}$определенность эквивалентна существованию r. Чтобы проиллюстрировать, как большие кардиналы приводят к определенности, вот доказательство $\Sigma \; 1\; 1\; (r)\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{1\}\; ^\; \{1\}\; (r)\}$определенности при наличии р.

Пусть A будет $\Sigma \; 1\; 1\; (r)\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{1\}\; ^\; \{1\}\; (r)\}$подмножеством пространства Бэра. A = p [T] для некоторого дерева T (построенного из r) на (ω, ω). (Это x∈A, если и только если из некоторого y, $((x\; 0,\; y\; 0),\; (x\; 1,\; y\; 1),...)\; \{\backslash \; displaystyle\; ((x\_\; \{0\},\; y\_\; \{0\}),\; (x\_\; \{1\},\; y\_\; \{1\}),...)\}$- это путь через T.)

Учитывая частичный ход s, пусть $T\; s\; \{\; \backslash \; displaystyle\; T\_\; \{s\}\}$быть поддеревом T, согласованным с s, при условии max (y 0,y1,..., y len (s) -1)T s { \ displaystyle T_ {s}}конечно. Согласованность означает, что каждый путь через $T\; s\; \{\backslash \; displaystyle\; T\_\; \{s\}\}$имеет форму $((\; Икс\; 0,\; Y\; 0),\; (Икс\; 1,\; Y\; 1),....,\; (xi,\; yi))\; \{\backslash \; displaystyle\; ((x\_\; \{0\},\; y\_\; \{0\}),\; (x\_\; \{1\},\; y\_\; \{1)\; \}),...,\; (x\_\; \{i\},\; y\_\; \{i\}))\}$где $(x\; 0,\; x\; 1,...,\; xi)\; \{\backslash \; displaystyle\; (x\_\; \{0\; \},\; x\_\; \{1\},...,\; x\_\; \{i\})\}$- начальный сегмент s.

Чтобы доказать, что A определено, определите вспомогательную игру следующим образом:. В дополнение к обычным ходам игрок 2 должен выполнить преобразование $T\; s\; \{\backslash \; displaystyle\; T\_\; \{s\}\}$в порядковые числа (ниже достаточно большого порядкового номера κ) так, чтобы

• каждый новый ход расширяет предыдущую ма pping и
• порядок порядковых номеров соответствует порядку Клини – Брауэра на $T\; s\; \{\backslash \; displaystyle\; T\_\; \{s\}\}$.

Напомним, что порядок Клини – Брауэра похож на лексикографический порядок, за исключением того, что если s правильно расширяет t, то s

Вспомогательная игра открыта. Доказательство: если игрок 2 не проигрывает на конечном этапе, тогда объединение всех $T\; s\; \{\backslash \; displaystyle\; T\_\; \{s\}\}$(которое является деревом, которое соответствует игре) является хорошим. -основана, и поэтому результат не вспомогательной игры не находится в A.

Таким образом, вспомогательная игра определяется. Доказательство: с помощью трансфинитной индукции для каждого порядкового номера α вычислите набор позиций, в которых игрок 1 может добиться выигрыша за α шагов, где позиция, в которой игрок 2 должен двигаться, проигрывает (для игрока 2) за α шагов тогда и только тогда, когда для каждого хода полученный результат позиция проигрывает менее чем за α шагов. Одна стратегия для игрока 1 состоит в том, чтобы уменьшать α с каждой позицией (скажем, выбирая наименьшее α и разрывая ничьи, выбирая наименьший ход), а одна стратегия для игрока 2 - выбирать наименьшее (на самом деле любой будет работать) ход, который не ведет на позицию с присвоенным α. Обратите внимание, что L (r) содержит набор выигрышных позиций, а также выигрышные стратегии, указанные выше.

Выигрышная стратегия для игрока 2 в исходной игре приводит к выигрышной стратегии во вспомогательной игре: поддерево T, соответствующее выигрышной стратегии, хорошо обосновано, поэтому игрок 2 может выбирать ординалы на основе Клини– Порядок Брауэра дерева. Также тривиально выигрышная стратегия для игрока 2 во вспомогательной игре дает выигрышную стратегию для игрока 2 в исходной игре.

Остается показать, что с использованием r вышеупомянутая выигрышная стратегия для игрока 1 во вспомогательной игре может быть преобразована в выигрышную стратегию в исходной игре. r дает собственный класс I (L (r), ∈, r) неразличимых ординалов. По неразличимости, если κ и ординалы во вспомогательном ответе находятся в I, то ходы игрока 1 не зависят от вспомогательных ходов (или от κ), и поэтому стратегия может быть преобразована в стратегию исходной игры ( поскольку игрок 2 может продержаться с неразличимыми любое конечное число шагов). Предположим, что игрок 1 проигрывает в исходной игре. Тогда дерево, соответствующее пьесе, хорошо обосновано. Следовательно, игрок 2 может выиграть вспомогательную игру, используя вспомогательные ходы, основанные на неразличимых (поскольку порядок неразличимых элементов превышает порядок Клини – Брауэра в дереве), что противоречит победе игрока 1 во вспомогательной игре.

Кардиналы Вудина

Если есть кардинал Вудина с измеримым кардиналом над ним, то Π2определенность сохраняется. В более общем случае, если имеется n кардиналов Вудена с измеримым кардиналом выше всех, то Πn + 1 определенность сохраняется. Из определенности Πn + 1 следует, что существует транзитивная внутренняя модель, содержащая n кардиналов Вудина.

$\Delta \; 2\; 1\; \{\backslash \; displaystyle\; \backslash \; Delta\; \_\; \{2\}\; ^\; \{1\}\}$(светолицо) определенность равнозначна кардиналу Вудина. Если $\Delta \; 2\; 1\; \{\backslash \; displaystyle\; \backslash \; Delta\; \_\; \{2\}\; ^\; \{1\}\}$определенность сохраняется, то для конуса Тьюринга x (то есть для каждого действительного x достаточно большого Степень Тьюринга ), L [x] удовлетворяет OD-определенности (то есть определенности игр на целых числах длины ω и порядково-определяемом выигрыше), а в HOD $\omega \; 2\; L\; [x]\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{2\}\; ^\; \{L\; [x]\}\}$- кардинал Вудина.

Проективная определенность

Если существует бесконечно много кардиналов Вудена, то проективная определенность имеет место; то есть определяется каждая игра, условием выигрыша которой является проективный набор. Из проективной детерминированности следует, что для каждого натурального числа n существует транзитивная внутренняя модель, удовлетворяющая наличию n кардиналов Вудена.

Аксиома определенности

аксиома определенности, или AD, утверждает, что каждая игра двух игроков с точной информацией длины ω в который игроки играют натуралы, определяется.

AD доказуемо ложно от ZFC; используя аксиому выбора, можно доказать существование неопределенной игры. Однако, если существует бесконечно много кардиналов Вудена с измеримой над всеми, то L (R) - это модель ZF, удовлетворяющая AD.

Свойства регулярности для наборов вещественных чисел

Если A - подмножество пространства Бэра такое, что игра Банаха – Мазура для A определяется, то либо II имеет выигрышную стратегию, и в этом случае A является скудным, либо I имеет выигрышную стратегию, и в этом случае A является comeager в некоторой открытой окрестности.

Это не совсем означает, что A имеет свойство Бэра, но это близко: простая модификация аргумента показывает, что если Γ является адекватным классом точек такая, что каждая игра в Γ определена, то каждое множество вещественных чисел в Γ обладает свойством Бэра.

На самом деле этот результат не оптимален; рассматривая развернутую игру Банаха – Мазура, мы можем показать, что из определенности Γ (для Γ с достаточными свойствами замыкания) следует, что каждое множество вещественных чисел, являющееся проекцией множества в Γ, обладает свойством Бэра. Так, например, существование измеримого кардинала подразумевает определенность Π1, что, в свою очередь, означает, что каждый набор Σ2вещественных чисел обладает свойством Бэра.

Рассматривая другие игры, мы можем показать, что Πnопределенность подразумевает, что каждый Σn + 1 набор действительных чисел обладает свойством Бэра, является измеримым по Лебегу ( фактически универсально измеримый ) и обладает свойством идеального множества.

Теоремы периодичности

• Из первой теоремы периодичности следует, что для любого натурального числа n, если Δ2n + 1 определенность сохраняется, тогда Π2n + 1 и Σ2n + 2 имеют свойство предварительного упорядочивания (и что Σ2n + 1 и Π2n + 2 не обладают свойством предварительного упорядочивания, а обладают свойством разделения ).
• Вторая теорема периодичности подразумевает, что для любого натурального числа n, если Δ2n + 1 определенность выполняется, то Π2n + 1 и Σ2nобладают свойством масштабирования. В частности, если проективная определенность выполняется, то каждое проективное отношение имеет проективную униформизацию.
• третья теорема периодичности дает достаточное условие для игры имеют определенную выигрышную стратегию.

Приложения к разрешимости некоторых теорий второго порядка

В 1969 году Майкл О. Рабин доказал, что теория второго порядка из n наследников разрешима. Ключевой компонент доказательства требует демонстрации определенности игр с четностью, которые лежат на третьем уровне иерархии Бореля.

Детерминированность Вэджа

Детерминированность Вэджа - это утверждение, которое для все пары A, B подмножеств пространства Бэра, определяется игра Wadge G (A, B). Аналогично для класса точек Γ, детерминированность Wadge - это утверждение, что для всех множеств A, B в Γ определена игра Wadge G (A, B).

Детерминированность Wadge подразумевает принцип полулинейного упорядочивания для Wadge order. Другим следствием детерминированности Вэджа является свойство совершенного множества.

. В общем случае определенность Г Уэджа является следствием определенности булевых комбинаций множеств в Г. В проективной иерархии , Π1определенность Уэджа эквивалентна определенности Π1, как доказал Лео Харрингтон. Этот результат был расширен Хьортом, чтобы доказать, что определенность Π2Вэджа (и фактически принцип полулинейного порядка для Π2) уже подразумевает определенность Π2.

Игры, в которых играемые объекты не являются натуральными числами

Из определения игр на ординалах с порядковым определимым выигрышем и длиной ω следует, что для каждого регулярного кардинала κ>ω не существует порядковых определимых непересекающихся стационарных подмножеств κ, составленных из ординалов конфинальности ω. Сила последовательности гипотезы детерминированности неизвестна, но ожидается, что она будет очень высокой.

Игры, сыгранные на деревьях

Длинные игры

Существование ω 1 кардиналов Вудина означает, что для каждого счетного порядкового числа α все игры на определяются целые числа длины α и проективный выигрыш. Грубо говоря, α кардиналы Вудена соответствуют определенности игр на вещественных числах длины α (с простым набором выигрышей). Предполагая предел числа кардиналов Вудина κ с o (κ) = κ и ω кардиналов Вудина выше κ, определяются игры переменной счетной длины, в которых игра заканчивается, как только ее длина становится допустимой относительно линии игры и с проективным выигрышем. Предполагая, что некоторая гипотеза итерабельности доказуема, существование измеримого кардинала Вудена влечет определенность открытых игр длины ω 1 и проективного выигрыша. (В этих играх условие выигрыша для первого игрока запускается на счетной стадии, поэтому выигрыш может быть закодирован как набор реалов.)

Относительно лимита Вудина кардиналов Вудина и измеримого выше Для них согласованно, что определяется каждая игра на целых числах длины ω 1 и порядкового определяемого выигрыша. Предполагается, что гипотеза детерминированности равно согласуется с пределом Вудина кардиналов Вудена. ω 1 является максимальным в том смысле, что существуют неопределенные игры с целыми числами длины ω 1 + ω и порядковым определимым выигрышем.

Игры с несовершенной информацией

В любой интересной игре с несовершенной информацией выигрышной стратегией будет смешанная стратегия : то есть она будет дают некоторую вероятность различных ответов на одну и ту же ситуацию. Если оптимальные стратегии обоих игроков являются смешанными стратегиями, то результат игры не может быть определенно определяющим (как это может быть для чистых стратегий, поскольку они детерминированы ). Но распределение вероятностей исходов противоположных смешанных стратегий можно вычислить. Игра, требующая смешанных стратегий, определяется как определенная, если существует стратегия, которая дает минимальное ожидаемое значение (сверх возможных контр-стратегий), которое превышает заданное значение. В противовес этому определению четко определены все конечные игры с нулевой суммой для двух игроков. Однако детерминированность бесконечных игр с несовершенной информацией (игры Блэквелла) менее ясна.

В 1969 Дэвид Блэквелл доказал, что некоторые «бесконечные игры с несовершенной информацией» (теперь называемые «играми Блэквелла» ") определены, и в 1998 году Дональд А. Мартин доказал, что обычная (игра с точной информацией) определенность для класса точек, выделенных жирным шрифтом, подразумевает определенность Блэквелла для класса точек. Это, в сочетании с теоремой Бореля об определенности Мартина, означает, что все игры Блэквелла с функциями выигрыша Бореля определены. Мартин предположил, что обычная детерминированность и детерминированность Блэквелла для бесконечных игр эквивалентны в строгом смысле (т. Е. Определенность Блэквелла для точечного класса, выделенного жирным шрифтом, в свою очередь, подразумевает обычную определенность для этого точечного класса), но с 2010 г. не было доказано, что определенность Блэквелла подразумевает детерминированность игры с совершенной информацией.

• ω-автомат
• Решенная игра
• Строго детерминированная игра
• Топологическая игра

1. ^Предполагается, что я пытаюсь сделать пересечение играемых окрестностей единичным элементом, уникальный элемент которого является элементом A. Некоторые авторы ставят это целью вместо игрока II; это использование требует соответствующего изменения приведенных выше замечаний.

• Гейл, Дэвид и Стюарт, Ф. М. (1953). Kuhn, H.W.; Такер, А. В. (ред.). Бесконечные игры с точной информацией. Вклад в теорию игр, Том II. Анналы математических исследований 28. Princeton University Press. С. 245–266. ISBN 9780691079356. CS1 maint: несколько имен: список авторов (ссылка )
• Харрингтон, Лео (январь 1978 г.). «Аналитическая определимость и 0 #». Журнал символической логики. 43 (4): 685–693. doi : 10.2307 / 2273508. JSTOR 2273508.
• Хьорт, Грег (январь 1996 г.). «Π2Степени Уэджа». Анналы чистой и прикладной логики. 77 : 53–74. doi : 10.1016 / 0168-0072 (95) 00011-9.
• Jech, Thomas (2002). Теория множеств, издание третьего тысячелетия (исправленное и дополненное). Springer. ISBN 978-3 -540-44085-7.
• Мартин, Дональд А. (1975). «Определенность Бореля». Анналы математики. Вторая серия. 102 (2): 363–371. doi : 10.2307 / 1971035. JSTOR 1971035.
• Мартин, Дональд А. и Джон Р. Стил (январь 1989 г.). «А Доказательство проективной детерминированности ". Журнал Американского математического общества. 2 (1): 71–125. doi : 10.2307 / 1990913. JSTOR 1990913.
• Moschovakis, Яннис Н. (1980). Описательная теория множеств. Северная Голландия. ISBN 978-0-444-70199-2.
• Вудин, У. Хью (1988). «Сверхкомпактные кардиналы, множества вещественных чисел и слабо однородные деревья». Труды Национальной академии наук Соединенных Штатов Америки. 85 (18): 6587–6591. Bibcode : 1988PNAS... 85.6587W. doi : 10.1073 / pnas.85.18.6587. PMC 282022. PMID 16593979.
• Мартин, Дональд А. (2003). «Простое доказательство того, что определенность предполагает измеримость по Лебегу». Ренд. Сем. Мат. Univ. Pol. Турин. 61 (4): 393–399. (PDF )
• Вулф, П. (1955). «Строгая определенность некоторых бесконечных игр». Pacific J. Math. 5 (5): Дополнение I: 841–847. doi : 10.2140 / pjm.1955.5.841.

• «Большие кардиналы и решительность» в Стэнфордской энциклопедии философии