Определенность

«Решительный» перенаправляется сюда. Чтобы узнать о песне 2005 года, см. «Определенный (песня)» .

Детерминированность — это подраздел теории множеств , раздел математики , который исследует условия, при которых тот или иной игрок в игре имеет выигрышную стратегию, и последствия существования таких стратегий. Альтернативно и аналогично «определенность» — это свойство игры, в которой существует такая стратегия. Определенность была введена Гейлом и Стюартом в 1950 году под названием «определенность».

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

Основные понятия

Игры

Первый вид игр, которые мы будем рассматривать, — это игра для двух игроков с полной информацией длины ω , в которой игроки играют натуральными числами . Эти игры часто называют играми Гейла – Стюарта.

В этой игре два игрока, часто называемых I и II , по очереди разыгрывают натуральные числа, причем I ходит первым. Они играют «вечно»; то есть их пьесы индексируются натуральными числами. Когда они закончатся, заранее определенное условие решит, какой игрок выиграет. Это условие не обязательно должно определяться каким-либо определяемым правилом ; это может быть просто произвольная (бесконечно длинная) таблица поиска, показывающая, кто выиграл в определенной последовательности игр.

Более формально, рассмотрим подмножество A пространства Бэра ; напомним, что последняя состоит из всех ω-последовательностей натуральных чисел. Тогда в игре G _A , Я играю натуральное число 0 _затем , затем играю 1 , _и я играю 2 так _II далее. Тогда я выиграю игру тогда и только тогда, когда

$\langle a_{0},a_{1},a_{2},\ldots \rangle \in A$

в противном случае II выигрывает. Тогда A называется выигрышным множеством G _A .

Предполагается, что каждый игрок может видеть все ходы, предшествующие каждому его ходу, а также знает условие выигрыша.

Стратегии

Неформально стратегия игрока — это такой способ игры, при котором его ходы полностью определяются предыдущими ходами. Опять же, такой «способ» не обязательно должен быть описан каким-либо объяснимым «правилом», он может быть просто справочной таблицей.

Более формально, стратегия игрока I (для игры в смысле предыдущего подраздела) — это функция, которая принимает в качестве аргумента любую конечную последовательность натуральных чисел четной длины и возвращает натуральное число. Если σ ₀,...,a_{<a 0 ,...,a 2n-1 >} — такая стратегия и является последовательностью игр, то σ ₍ ,...,a_2n-1<a 0 ,...,a 2n-1 > ) — это следующая игра, которую я сделаю, если я следую стратегии σ . Стратегии для II такие же, с заменой «четного» на «нечетное».

Обратите внимание, что мы еще ничего не сказали о том, хороша ли стратегия в каком-либо отношении . Стратегия может заставить игрока делать агрессивно плохие ходы, и это все равно будет стратегией. На самом деле не обязательно даже знать условие победы в игре, знать, какие стратегии существуют для игры.

Выигрышные стратегии

Стратегия является выигрышной, если игрок, следующий ей, обязательно должен побеждать, независимо от того, как играет его противник. Например, если σ является стратегией для I , то σ является выигрышной стратегией для I в игре _GA , если для любой последовательности натуральных чисел, в которую играет II , скажем, <a ₁ ,a ₃ ,a ₅ ,. ..>, последовательность игр, производимых σ , когда II играет таким образом, а именно

$\langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle$

элементом А. является

Решительные игры

(Класс) игры(-ов) определяется , если для всех случаев игры существует выигрышная стратегия для одного из игроков (не обязательно одного и того же игрока для каждого случая). Не может быть выигрышной стратегии для обоих игроков в одной и той же игре, поскольку, если бы она существовала, обе стратегии можно было бы использовать друг против друга. Тогда, согласно гипотезе, результатом будет победа обоих игроков, что невозможно.

Определенность из элементарных соображений

Определены все конечные игры с полной информацией, в которых не бывает ничьих.

Реальные игры с полной информацией, такие как крестики-нолики , шахматы или бесконечные шахматы , всегда заканчиваются за конечное число ходов (в бесконечных шахматных играх это предполагает применение правила 50 ходов). Если такая игра модифицирована таким образом, что конкретный игрок выигрывает при любом условии, при котором игра была бы названа ничьей, то она всегда определяется. Условие того, что игра всегда окончена (т.е. все возможные расширения конечной позиции приводят к победе одного и того же игрока) за конечное число ходов, соответствует топологическому условию, согласно которому множество A, дающее условие победы для GA _, является замкнуто-замкнутым. в топологии пространства Бэра .

Например, изменение правил игры в шахматы так, чтобы ничья приносила победу черным, делает шахматы решительной игрой. Так получилось, что в шахматах ограниченное число позиций и правила повторения ничьи, поэтому с этими измененными правилами, если игра продолжается достаточно долго без победы белых, то черные могут в конечном итоге добиться победы (из-за модификации схемы ничьи). = победа черных).

Доказательство детерминированности таких игр довольно простое: игрок I просто играет, чтобы не проиграть ; то есть игрок I играет, чтобы убедиться, что у игрока II не будет выигрышной стратегии после моего хода. Если игрок I не может этого сделать, то это означает, что у игрока II с самого начала была выигрышная стратегия. С другой стороны, если с игроком I можно играть таким образом, то я должен выиграть, потому что игра закончится через некоторое конечное число ходов, а игрока, которого я не могу потерять в этот момент.

Это доказательство на самом деле не требует, чтобы игра всегда заканчивалась за конечное число ходов, а лишь требует, чтобы она заканчивалась за конечное число ходов всякий раз, когда II выигрывает. что множество A замкнуто Топологически это условие состоит в том , . Этот факт — что все закрытые игры детерминированы — называется теоремой Гейла-Стюарта . Обратите внимание, что по симметрии определяются и все открытые игры. (Игра открыта , если я могу выиграть, только выиграв за конечное число ходов.)

Определенность от ZFC

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

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

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

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

Определенность и большие кардиналы

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

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

Основная статья: Измеримый кардинал

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

На самом деле измеримого кардинала более чем достаточно. Более слабый принцип — существование 0 ^# достаточно, чтобы доказать коаналитическую определенность, и даже немного больше: точный результат состоит в том, что существование 0 ^# эквивалентно определенности всех уровней разностной иерархии ниже ω ² уровень, т. е. ω·n- Π ¹ ₁ решимость на каждый $n$.

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

Доказательство защиты от острых предметов

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

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

Учитывая частичную игру s , пусть $T_{s}$ — поддерево T , соответствующее s, при условии max(y ₀ ,y ₁ ,...,y _len(s)-1 )<len(s). Дополнительное условие гарантирует, что $T_{s}$ конечно. Последовательность означает, что каждый путь через $T_{s}$ имеет форму $((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))$ где $(x_{0},x_{1},...,x_{i})$ является начальным сегментом s .

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

• каждый новый ход расширяет предыдущее отображение и
• порядок ординалов согласуется с порядком Клини – Брауэра на $T_{s}$.

Напомним, что порядок Клини-Брауэра подобен лексикографическому порядку, за исключением того, что если s правильно расширяет t, то s < t . Это хорошо упорядоченное дерево тогда и только тогда, когда дерево обосновано.

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

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

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

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

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

Основная статья: Кардинал Вуда

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

$\Delta _{2}^{1}$ (светлое лицо) определенность эквивалентна кардиналу Вудина. Если $\Delta _{2}^{1}$ определенность выполняется, то для конуса Тьюринга x (то есть для каждого вещественного x достаточно высокой степени Тьюринга ) L[ x ] удовлетворяет OD-детерминированности (то есть определенности игр на целых числах длины ω и ординально определяемом выигрыше), и в ХОД ^{Л[ х ]} $\omega _{2}^{L[x]}$ кардинал Вудина.

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

Основная статья: Проективная детерминированность

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

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

Основная статья: Аксиома детерминированности

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

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

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

Свойства регулярности для множеств действительных чисел

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

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

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

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

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

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

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

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

Определенность Уэджа

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

Определенность Уэджа подразумевает полулинейный принцип упорядочения порядка Уэджа . Другим следствием детерминированности Уоджа является свойство совершенного множества .

В общем, детерминированность Γ Ваджа является следствием определенности булевых комбинаций множеств в Γ. В проективной иерархии Π ¹ ₁ Определенность Ваджа эквивалентна Π ¹ ₁ определенность, как доказал Лео Харрингтон . Этот результат был расширен Хьёртом, чтобы доказать, что Π ¹ ₂ Определенность Ваджа (и, по сути, принцип полулинейного упорядочения для Π ¹ ₂ ) уже влечет Π ¹ ₂ решительность.

Более общие игры

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

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

Длинные игры

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

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

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

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

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

См. также

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

Сноски

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

Ссылки

• Гейл, Дэвид ; Стюарт, FM (1953). «Бесконечные игры с совершенной информацией». В Куне, Гарольд Уильям; Такер, Альберт Уильям (ред.). Вклад в теорию игр . Анналы математических исследований. Том. 28. Принстон, Нью-Джерси: Издательство Принстонского университета. стр. 245–266. ISBN  978-0-691-07935-6 .
• Харрингтон, Лео (январь 1978 г.). «Аналитическая определенность и 0#». Журнал символической логики . 43 (4): 685–693. дои : 10.2307/2273508 . JSTOR   2273508 . S2CID   46061318 .
• Хьёрт, Грег (январь 1996 г.). " П ¹ ₂ степени Ваджа» . Анналы чистой и прикладной логики . 77 : 53–74. doi : 10.1016/0168-0072(95)00011-9 .
• Джех, Томас (2002). Теория множеств, издание третьего тысячелетия (переработанное и дополненное) . Спрингер. ISBN  978-3-540-44085-7 .
• Мартин, Дональд А. (1975). «Борелевская определенность». Анналы математики . Вторая серия. 102 (2): 363–371. дои : 10.2307/1971035 . JSTOR   1971035 .
• Мартин, Дональд А. и Джон Р. Стил (январь 1989 г.). «Доказательство проективной детерминированности» . Журнал Американского математического общества . 2 (1): 71–125. дои : 10.2307/1990913 . JSTOR   1990913 .
• Мошовакис, Яннис Н. (1980). Описательная теория множеств . Северная Голландия. ISBN  978-0-444-70199-2 .
• Вудин, В. Хью (1988). «Сверхкомпактные кардиналы, множества вещественных чисел и слабооднородные деревья» . Труды Национальной академии наук Соединенных Штатов Америки . 85 (18): 6587–6591. Бибкод : 1988PNAS...85.6587W . дои : 10.1073/pnas.85.18.6587 . ПМК   282022 . ПМИД   16593979 .
• Мартин, Дональд А. (2003). «Простое доказательство того, что из определенности следует измеримость по Лебегу». Ренд. Сем. Мат. унив. Пол. Турин . 61 (4): 393–399. ( PDF )
• Вулф, П. (1955). «Строгая определенность некоторых бесконечных игр» . Пасифик Дж. Математика . 5 (5): Приложение I: 841–847. дои : 10.2140/pjm.1955.5.841 .

Внешние ссылки

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