Решительность - Determinacy
Детерминированность - это подраздел теории множеств , раздела математики , который изучает условия, при которых тот или иной игрок в игре имеет выигрышную стратегию, и последствия существования таких стратегий. Альтернативно и аналогично, «детерминированность» - это свойство игры, посредством которого существует такая стратегия.
Игры, изучаемые в теории множеств, - это, как правило, игры Гейла – Стюарта - игры с идеальной информацией для двух игроков, в которых игроки делают бесконечную последовательность ходов без ничьих. Область теории игр изучает более общие виды игр, включая игры с розыгрышем, такие как крестики-нолики , шахматы или бесконечные шахматы , или игры с несовершенной информацией, такие как покер .
Основные понятия
Игры
Первый тип игр, который мы рассмотрим, - это игра двух игроков с совершенной информацией длины ω , в которой игроки играют в натуральные числа . Эти игры часто называют играми Гейла – Стюарта.
В такого рода играх два игрока, часто называемые I и II , по очереди играют в натуральные числа, причем I ходит первым. Они играют «вечно»; то есть их игры индексируются натуральными числами. Когда они закончены, заранее определенное условие решает, какой игрок выиграл. Это условие не обязательно должно определяться каким-либо определяемым правилом ; это может быть просто произвольная (бесконечно длинная) таблица поиска , в которой указывается, кто выиграл при определенной последовательности игр.
Более формально, рассмотрим подмножество А из Бэра пространства ; напомним, что последняя состоит из всех ω-последовательностей натуральных чисел. Тогда в игре G A , я играю натуральное число 0 , то II играет 1 , то я играет на 2 , и так далее. Тогда я выиграю игру тогда и только тогда, когда
и в противном случае II выигрывает. Затем называется взятка набор из G A .
Предполагается, что каждый игрок может видеть все ходы, предшествующие каждому из его ходов, а также знает условия выигрыша.
Стратегии
Неформально стратегия игрока - это способ игры, при котором его действия полностью определяются предыдущими играми. Опять же, такой «способ» не обязательно должен быть уловлен каким-либо объяснимым «правилом», он может быть просто таблицей поиска.
Более формально стратегия для игрока I (для игры в смысле предыдущего подраздела) - это функция, которая принимает в качестве аргумента любую конечную последовательность натуральных чисел четной длины и возвращает натуральное число. Если σ - такая стратегия, а <a 0 ,...,a 2n-1> - последовательность ходов , то σ (<a 0 ,...,a 2n-1> ) - это следующая игра, которую я сделаю. , если I следует стратегии σ . Стратегии для II такие же: замена «нечетного» на «четный».
Обратите внимание, что мы пока ничего не сказали о том, хороша ли стратегия в каком-либо смысле . Стратегия может побуждать игрока делать агрессивно плохие ходы, и это все равно будет стратегией. Фактически, даже не обязательно знать условие выигрыша для игры, чтобы знать, какие стратегии существуют для этой игры.
Стратегии победы
Стратегия является выигрышной, если игрок, следующий за ней, обязательно должен выиграть, независимо от того, что играет его противник. Например, если σ - стратегия для I , то σ - выигрышная стратегия для I в игре G A, если для любой последовательности натуральных чисел, которую должен сыграть II , скажем <a 1 , a 3 , a 5 ,. ..>, последовательность игр, производимая σ, когда II играет таким образом, а именно
является элементом A .
Решительные игры
(Класс) игры (игр) определяется, если для всех экземпляров игры существует выигрышная стратегия для одного из игроков (не обязательно один и тот же игрок для каждого экземпляра). Обратите внимание, что не может быть выигрышной стратегии для обоих игроков в одной и той же игре, поскольку, если бы она была, эти две стратегии можно было бы разыграть друг против друга. В результате, по гипотезе, оба игрока выиграли бы, что невозможно.
Детерминированность из элементарных соображений
Определяются все конечные игры с совершенной информацией, в которых не бывает ничьих.
Реальные игры с идеальной информацией, такие как крестики-нолики , шахматы или бесконечные шахматы , всегда заканчиваются конечным числом ходов (в шахматных играх предполагается, что применяется правило 50 ходов). Если такая игра модифицируется так, что конкретный игрок выигрывает при любом условии, при котором игра была бы названа ничьей, то это всегда определяется. Условие, что игра всегда заканчивается (т. Е. Все возможные расширения конечной позиции приводят к выигрышу для одного и того же игрока) за конечное число ходов соответствует топологическому условию, что множество A, дающее условие выигрыша для G A , открыто. в топологии из Бэра пространства .
Например, изменение правил игры с целью сделать ничью выигрышной для черных делает шахматы решительной игрой. Так получилось, что в шахматах есть конечное количество позиций и правила «ничья за повторением», так что с этими измененными правилами, если игра продолжается достаточно долго без победы белых, то черные могут в конечном итоге форсировать победу (из-за модификации ничьей. = выигрыш за черных).
Доказательство того, что такие игры детерминированы, довольно просто: игрок I просто играет, чтобы не проиграть ; то есть игрок I играет, чтобы убедиться, что у игрока II нет выигрышной стратегии после моего хода. Если игрок I не может этого сделать, значит, у игрока II с самого начала была выигрышная стратегия. С другой стороны, если игрок, которого я могу играть таким образом, я должен выиграть, потому что игра закончится после некоторого конечного числа ходов, и игрок, которого я не мог проиграть в этот момент.
Это доказательство на самом деле не требует, чтобы игра всегда заканчивалась за конечное число ходов, а только чтобы она заканчивалась за конечное число ходов, когда II выигрывает. Это условие, топологический, является то , что множество будет закрыто . Тот факт, что все закрытые игры детерминированы, называется теоремой Гейла – Стюарта . Обратите внимание, что по симметрии также определяются все открытые игры. (Игра открыта, если я могу выиграть, только выиграв за конечное число ходов.)
Решительность от ZFC
Дэвид Гейл и Ф. М. Стюарт доказали, что открытые и закрытые игры решительны. Детерминированность для второго уровня иерархии Бореля была продемонстрирована Вулфом в 1955 году. В течение следующих 20 лет дополнительные исследования с использованием все более сложных аргументов установили, что третий и четвертый уровни иерархии Бореля являются детерминированными.
В 1975 году Дональд А. Мартин доказал, что все игры Бореля детерминированы; то есть, если A - борелевское подмножество пространства Бэра, то G A определена. Этот результат, известный как детерминированность по Борелю , является наилучшим возможным результатом детерминированности, доказуемым в ZFC, в том смысле, что детерминированность следующего более высокого класса Вэджа недоказуема в ZFC.
В 1971 году , прежде, чем Мартин получил свое доказательство, Харви Фридман показал , что любое доказательство Бореля детерминированности следует использовать аксиому замены существенным образом, для того , чтобы итерируем POWERSET аксиому трансфинитно часто. Работа Фридмана дает поэтапный результат, детализирующий, сколько итераций аксиомы powerset необходимо, чтобы гарантировать определенность на каждом уровне иерархии Бореля .
Для каждого целого числа n ZFC \ P доказывает определенность на n- м уровне иерархии разностей множеств, но ZFC \ P не доказывает, что для каждого целого числа n определяется n- й уровень иерархии разностей множеств. См. Обратную математику для других отношений между определенностью и подсистемами арифметики второго порядка .
Решительность и большие кардиналы
Между определенностью и большими кардиналами существует тесная связь . В общем, более сильные большие кардинальные аксиомы доказывают определенность более крупных точечных классов , более высоких в иерархии Уэджа , а определенность таких точечных классов, в свою очередь, доказывает существование внутренних моделей немного более слабых больших кардинальных аксиом, чем те, которые используются для доказательства определенности pointclass в первую очередь.
Измеримые кардиналы
Из существования измеримого кардинала следует, что каждая аналитическая игра (также называемая Σ 1 1 игрой) определена, или, что то же самое, каждая коаналитическая (или Π 1 1 ) игра определена. (См. Определения в Проективной иерархии .)
На самом деле измеримого кардинала более чем достаточно. Более слабый принцип - наличие 0 # достаточно для доказательства коаналитической определенности, и немного больше: точный результат состоит в том, что существование 0 # эквивалентно определенности всех уровней иерархии разностей ниже уровня ω 2 , т.е. ω · n- Π 1 1 определенность для каждого .
От измеримого кардинала мы можем очень немного улучшить это до определенности ω 2 - Π 1 1 . Из существования более измеримых кардиналов можно доказать определенность большего количества уровней иерархии разностей над Π 1 1 .
Доказательство определенности от острых предметов
Для каждого вещественного числа г , детерминированность эквивалентно существованию г # . Чтобы проиллюстрировать, как большие кардиналы приводят к определенности, вот доказательство определенности при наличии r # .
Пусть A - подмножество пространства Бэра. A = p [ T ] для некоторого дерева T (построенного из r ) на (ω, ω). (То есть x∈A тогда и только тогда из некоторых у , это путь через Т .)
Учитывая частичную игру s , пусть будет поддеревом T, согласованным с s, при условии max (y 0 , y 1 , ..., y len (s) -1 ) <len (s). Дополнительное условие гарантирует, что это конечно. Согласованность означает, что каждый проход имеет форму где - начальный сегмент s .
Чтобы доказать, что A определено, определите вспомогательную игру следующим образом:
в дополнение к обычным ходам игрок 2 должен выполнить отображение в ординалы (ниже достаточно большого ординала κ ) так, чтобы
- каждый новый ход расширяет предыдущее отображение и
- упорядочение порядковых согласуется с порядка Клини-Брауэра о .
Напомним, что порядок Клини – Брауэра подобен лексикографическому порядку, за исключением того, что если s правильно расширяет t, то s < t . Это хороший порядок, если дерево хорошо обосновано.
Вспомогательная игра открыта. Доказательство: если игрок 2 не проигрывает на конечном этапе, то объединение всех (которое является деревом, которое соответствует игре) является хорошо обоснованным, и поэтому результат не вспомогательной игры не находится в 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 во вспомогательной игре.
Кардиналы Вудена
Если есть кардинал Вудена с измеримым кардиналом над ним, то Π 1 2 определенность выполняется. В более общем случае, если имеется n кардиналов Вудена с измеримым кардиналом над всеми, то имеет место Π 1 n + 1 определенность. Из Π 1 n + 1 детерминированности следует, что существует транзитивная внутренняя модель, содержащая n кардиналов Вудена.
(светлолицый) детерминированность равнозначна кардиналу Вудена. Если определенность верна, то для конуса Тьюринга x (то есть для каждого действительного x достаточно высокой степени Тьюринга ) L [ x ] удовлетворяет OD-определенности (то есть определенности игр на целых числах длины ω и определимости выигрыша) , а в HOD L [ x ] - кардинал Вудена.
Проективная детерминированность
Если кардиналов Вудена бесконечно много, то проективная определенность имеет место; то есть определяется каждая игра, условие выигрыша которой является проективным множеством . Из проективной детерминированности следует, что для каждого натурального числа n существует транзитивная внутренняя модель, удовлетворяющая наличию n кардиналов Вудена.
Аксиома определенности
Аксиома детерминированности , или AD , утверждает , что каждые два игроков полной информации длину со, в которой игроки играют Naturals, определяются.
AD доказуемо ложно от ZFC; используя аксиому выбора, можно доказать существование неопределенной игры. Однако, если существует бесконечно много кардиналов Вудена с измеримой над всеми, то L (R) - модель ZF , удовлетворяющая AD.
Последствия определенности
Свойства регулярности для множеств вещественных чисел
Если является подмножеством Бэра пространства таким образом, что игра Банаха-Мазура для А определяется, то либо II имеет выигрышную стратегию, в этом случае является скудный , или я имеет выигрышную стратегию, в этом случае является comeager на некоторых открытый район.
Это не совсем означает, что A обладает свойством Бэра , но это близко: простая модификация аргумента показывает, что если Γ является адекватным классом точек , так что каждая игра в Γ определена, то каждый набор вещественных чисел в Γ имеет собственность Бэра.
На самом деле этот результат не является оптимальным; рассматривая развернутую игру Банаха – Мазура, мы можем показать, что из детерминированности Γ (для Γ с достаточными свойствами замыкания) следует, что каждое множество вещественных чисел, являющееся проекцией множества в Γ, обладает свойством Бэра. Так, например, существование измеримого кардинала предполагает Π 1 1 определенность, что, в свою очередь, означает, что каждый набор Σ 1 2 вещественных чисел обладает свойством Бэра.
Рассматривая другие игры, мы можем показать, что из детерминированности Π 1 n следует, что каждое Σ 1 n +1 множество вещественных чисел обладает свойством Бэра, измеримо по Лебегу (фактически универсально измеримо ) и обладает свойством совершенного множества .
Теоремы о периодичности
- Первой периодичности теоремы следует , что для любого натурального числа п , если Δ 1 2 п + 1 детерминированность выполнено, то Π 1 2 п + 1 и Σ 1 2 п + 2 имеют prewellordering свойство (и что Σ 1 2 п + 1 и Π 1 2 п +- у не имеет prewellordering свойства, а скорее имеет свойство разделения ).
- Из второй теоремы о периодичности следует, что для любого натурального числа n , если имеет место определенность ∆ 1 2 n +1 , то Π 1 2 n +1 и Σ 1 2 n обладают свойством масштабирования . В частности, если проективная детерминированность верна, то каждое проективное отношение имеет проективную униформизацию .
- Теорема третьей периодичности дает достаточное условие для игры , чтобы иметь определимую выигрышную стратегию.
Приложения к разрешимости некоторых теорий второго порядка
В 1969 году Майкл О. Рабина доказал , что теория второго порядка из п преемников разрешима . Ключевой компонент доказательства требует показать детерминированность игр с четностью , которые лежат на третьем уровне иерархии Бореля .
Детерминированность вэджа
Вэджа детерминированность является утверждение , что для всех пар A , B подмножеств Бэра пространства , то игра Вэджа G ( , Б ) определяется. Аналогично для класса точек Γ, детерминированность Вэджа - это утверждение, что для всех множеств A , B в Γ определена игра G ( A , B ).
Детерминированность Вэджа подразумевает принцип полулинейного упорядочения для порядка Вэджа . Еще одно следствие детерминированности Вэджа - свойство идеального множества .
В общем случае определенность Γ Wadge является следствием определенности булевых комбинаций множеств в Γ. В проективной иерархии , Π 1 1 Вэджа детерминированность эквивалентно П 1 1 детерминированности, как доказано Лео Харрингтона . Этот результат был распространен Hjorth доказать , что Π 1 2 Wadge детерминированность (а на самом деле полулинейное принцип упорядочения для П - 2 ) уже означает Π 1 2 детерминированности.
Более общие игры
Игры, в которых играемые предметы не являются натуральными числами
Из детерминированности игр на ординалах с ординально определимым выигрышем и длиной ω следует, что для любого регулярного кардинала κ > ω не существует порядковых определимых непересекающихся стационарных подмножеств κ, составленных из ординалов конфинальности ω. Сила последовательности гипотезы детерминированности неизвестна, но ожидается, что она будет очень высокой.
Игры на деревьях
Длинные игры
Существование ω 1 кардиналов Вудена означает, что для каждого счетного ординала α определены все игры с целыми числами длины α и проективным выигрышем. Грубо говоря, α кардиналы Вудена соответствуют определенности игр на вещественных числах длины α (с простым набором выигрышей). Предполагая ограничение числа кардиналов Вудена κ с o ( κ ) = κ ++ и ω кардиналов Вудина выше κ , игры с переменной счетной длиной, в которых игра заканчивается, как только ее длина становится допустимой относительно линии игры и с проективным выигрышем, считаются определенный. Предполагая, что некоторая гипотеза итерабельности доказуема, существование измеримого кардинала Вудена влечет определенность открытых игр длины ω 1 и проективного выигрыша. (В этих играх условие выигрыша для первого игрока запускается на счетной стадии, поэтому выигрыш может быть закодирован как набор реалов.)
Относительно предела Вудина кардиналов Вудина и измеримого над ними, согласованно, что определяется каждая игра с целыми числами длины ω 1 и порядковым определимым выигрышем. Предполагается, что гипотеза детерминированности равно согласуется с пределом Вудина кардиналов Вудина. ω 1 является максимальным в том смысле, что существуют неопределенные игры на целых числах длины ω 1 + ω и порядкового определимого выигрыша.
Игры с несовершенной информацией
В любой интересной игре с неполной информацией выигрышной стратегией будет смешанная стратегия : то есть она дает некоторую вероятность различных ответов на одну и ту же ситуацию. Если оптимальные стратегии обоих игроков являются смешанными, то результат игры не может быть определенно определяющим (как это может быть для чистых стратегий , поскольку они детерминированы ). Но распределение вероятностей исходов противоположных смешанных стратегий можно рассчитать. Игра, требующая смешанных стратегий, определяется как определенная, если существует стратегия, которая дает минимальное ожидаемое значение (по сравнению с возможными контрстратегиями), превышающее заданное значение. Против этого определения четко определены все конечные игры с нулевой суммой для двух игроков . Однако детерминированность бесконечных игр с несовершенной информацией (игры Блэквелла) менее очевидна.
В 1969 году Дэвид Блэквелл доказал, что некоторые «бесконечные игры с несовершенной информацией» (теперь называемые «играми Блэквелла») детерминированы, а в 1998 году Дональд А. Мартин доказал, что обычная (игра с идеальной информацией) определенность для точечного класса, выделенного жирным шрифтом, влечет определенность Блэквелла для класс точки. В сочетании с борелевской теоремой Мартина об определенности это означает, что все игры Блэквелла с борелевскими функциями выигрыша определены. Мартин предположил, что обычная детерминированность и детерминированность Блэквелла для бесконечных игр эквивалентны в строгом смысле (т.е. что детерминированность Блэквелла для точечного класса, выделенного жирным шрифтом, в свою очередь, подразумевает обычную определенность для этого точечного класса), но по состоянию на 2010 г. не было доказано, что определенность Блэквелла подразумевает детерминированность игры с идеальной информацией.
Квазистратегии и квазиопределенность
Смотрите также
Сноски
- ^ Это предполагаетчтояпытаюсь получить пересечение окрестностей играли быть синглтончей единственным элемент является элементомA. Некоторые авторы ставят эту цель вместо игрокаII; это использование требует соответствующего изменения приведенных выше замечаний.
использованная литература
- Гейл, Дэвид и Стюарт, FM (1953). Kuhn, HW; Такер, А.В. (ред.). Бесконечные игры с точной информацией . Вклад в теорию игр, Том II . Анналы математических исследований 28. Princeton University Press. С. 245–266. ISBN 9780691079356.CS1 maint: несколько имен: список авторов ( ссылка )
- Харрингтон, Лео (январь 1978 г.). «Аналитическая определенность и 0 #». Журнал символической логики . 43 (4): 685–693. DOI : 10.2307 / 2273508 . JSTOR 2273508 .
- Хьорт, Грег (январь 1996 г.). « Π 1 2 градуса Wadge» . Летопись чистой и прикладной логики . 77 : 53–74. DOI : 10.1016 / 0168-0072 (95) 00011-9 .
- Jech, Томас (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 .
- Мощовакис, Яннис Н. (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 .