Теорема Бореля об определенности

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

Эта теорема представляет собой далеко идущее обобщение теоремы Цермело об определенности конечных игр. Это было доказано Дональдом А. Мартином в 1975 году и применяется в дескриптивной теории множеств , чтобы показать, что борелевские множества в польских пространствах обладают свойствами регулярности, такими как свойство совершенного множества .

Теорема также известна своими метаматематическими свойствами. В 1971 году, прежде чем теорема была доказана, Харви Фридман показал, что любое доказательство теоремы в теории множеств Цермело-Френкеля должно многократно использовать аксиому замены . Более поздние результаты показали, что более сильные теоремы детерминированности не могут быть доказаны в теории множеств Цермело – Френкеля, хотя они относительно согласуются с ней, если некоторые большие кардиналы непротиворечивы.

Предыстория

-

Основная статья: Решимость

Игра Гейла–Стюарта — это игра для двух игроков с полной информацией. Игра определяется с использованием множества A и обозначается G _A . Два игрока чередуют ходы, и каждый игрок знает обо всех ходах, прежде чем сделать следующий. один элемент A. На каждом ходу каждый игрок выбирает для игры Один и тот же элемент может быть выбран более одного раза без ограничений. Игру можно представить с помощью следующей диаграммы, на которой ходы выполняются слева направо, причем ходы игрока I вверху и ходы игрока II внизу.

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{matrix}}$

Игра продолжается без конца, так что один ход игры определяет бесконечную последовательность. $\langle a_{1},a_{2},a_{3}\ldots \rangle$ элементов A . Множество всех таких последовательностей обозначается A ^ой . С самого начала игры игроки знают о фиксированном наборе выигрышей (так называемом выигрышном наборе ), который определит, кто выиграет. Выигрышное множество подмножеством A является ^ой . Если бесконечная последовательность, созданная в ходе игры, входит в выигрышный набор, то выигрывает игрок I. В противном случае выигрывает игрок II; нет никаких связей.

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

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

Выигрышная стратегия для игрока — это функция, которая сообщает игроку, какой ход следует сделать из любой позиции в игре, так что, если игрок будет следовать этой функции, он обязательно выиграет. Более конкретно, выигрышная стратегия для игрока I — это функция f , которая принимает в качестве входных данных последовательности элементов A четной длины и возвращает элемент A , так что игрок I выиграет каждую игру вида

${\begin{matrix}\mathrm {I} &a_{1}=f(\langle \rangle )&\quad &a_{3}=f(\langle a_{1},a_{2}\rangle )&\quad &a_{5}=f(\langle a_{1},a_{2},a_{3},a_{4}\rangle )&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots .\end{matrix}}$

Выигрышная стратегия для игрока II — это функция g , которая принимает последовательности элементов A нечетной длины и возвращает элементы A , так что игрок II выиграет каждую игру вида

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}=g(\langle a_{1}\rangle )&\quad &a_{4}=g(\langle a_{1},a_{2},a_{3}\rangle )&\quad &a_{6}=g(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )&\cdots .\end{matrix}}$

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

Топология

Для данного набора A независимо от того, является ли подмножество A ^ой будет определен, зависит в некоторой степени от его топологической структуры. Для целей игр Гейла–Стюарта множество A наделено дискретной топологией , а A ^ой наделен результирующей топологией произведения , где A ^ой рассматривается как счетное бесконечное топологическое произведение A с самим собой . В частности, когда A представляет собой множество {0,1}, топология, определенная на A ^ой — это в точности обычная топология в пространстве Кантора , а когда A — набор натуральных чисел, это обычная топология в пространстве Бэра .

Набор А ^ой можно рассматривать как совокупность путей через определенное дерево , что приводит к второй характеристике его топологии. Дерево состоит из всех конечных последовательностей элементов A , а потомками конкретного узла σ дерева являются именно те последовательности, которые расширяют σ на один элемент. Таким образом, если A = { 0, 1 }, первый уровень дерева состоит из последовательностей ⟨ 0 ⟩ и ⟨ 1 ⟩; второй уровень состоит из четырех последовательностей ⟨ 0, 0 ⟩, ⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨ 1, 1 ⟩; и так далее. Для каждой из конечных последовательностей σ в дереве множество всех элементов A ^ой которые начинаются с σ, является базовым открытым множеством в топологии на A . Открытые множества ​ A ^ой являются именно множествами, выражаемыми как объединения этих основных открытых множеств. , Закрытыми множествами как обычно, являются те, дополнение которых открыто.

Борелевские множества ​ A ^ой являются наименьшим классом подмножеств A ^ой которое включает открытые множества и замкнуто относительно дополнения и счетного объединения. То есть борелевские множества — это наименьшая σ-алгебра подмножеств A ^ой содержащий все открытые множества. Множества Бореля классифицируются в иерархии Бореля в зависимости от того, сколько раз необходимо выполнить операции дополнения и счетного объединения для их создания из открытых множеств.

Предыдущие результаты

Гейл и Стюарт (1953) доказали, что если выигрышное множество является открытым или закрытым подмножеством A ^ой тогда игра Гейла-Стюарта с этим набором выигрышей всегда определена. В течение следующих двадцати лет это было распространено на несколько более высокие уровни иерархии Бореля посредством еще более сложных доказательств. вопросу о том, должна ли игра определяться всякий раз, когда множество выигрышей является борелевским подмножеством A. Это привело к ^ой . Было известно, что с помощью аксиомы выбора можно построить подмножество {0,1} ^ой это не определено (Кехрис 1995, стр. 139).

Харви Фридман (1971) доказал, что любое доказательство того, что все борелевские подмножества канторова пространства ({0,1} ^ой ) были определены, потребует неоднократного использования аксиомы замены , аксиомы, которая обычно не требуется для доказательства теорем о «маленьких» объектах, таких как пространство Кантора.

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

Дональд А. Мартин (1975) доказал, что для любого множества A все борелевские подмножества A ^ой определены. Поскольку первоначальное доказательство было довольно сложным, в 1982 году Мартин опубликовал более короткое доказательство, не требующее такого большого количества технических средств. В своем обзоре статьи Мартина Дрейк описывает второе доказательство как «на удивление прямое».

Область дескриптивной теории множеств изучает свойства польских пространств (по сути, полных сепарабельных метрических пространств). Теорема Бореля об определенности использовалась для установления многих свойства борелевских подмножеств этих пространств. Например, все аналитические подмножества польских пространств обладают свойством совершенного множества , свойством Бэра и измеримы по Лебегу . Однако последние два свойства легче доказать, не используя борелевскую детерминированность, показав, что σ-алгебры измеримых множеств или множеств со свойством Бэра замкнуты относительно операции Суслина. ${\mathcal {A}}$.

-

Теорема Бореля о детерминированности представляет интерес своими метаматематическими свойствами, а также своими следствиями в дескриптивной теории множеств.

Определенность замкнутых множеств A ^ой для произвольного A эквивалентно аксиоме выбора над ZF (Кехрис 1995, стр. 139). При работе в теоретико-множественных системах, где не предполагается аксиома выбора, этого можно обойти, рассматривая обобщенные стратегии, известные как квазистратегии (Кехрис 1995, стр. 139), или рассматривая только игры, в которых A представляет собой множество натуральных чисел, как в аксиоме определенности .

Теория множеств Цермело (Z) — это теория множеств Цермело–Френкеля без аксиомы замены. Он отличается от ZF тем, что Z не доказывает, что операцию над набором степеней можно повторять бесчисленное количество раз, начиная с произвольного набора. В частности, V _{ω + ω} , конкретный счетный уровень кумулятивной иерархии , является моделью теории множеств Цермело. С другой стороны, аксиома замены удовлетворяется V _κ только для значительно больших значений κ, например, когда κ является сильно недоступным кардиналом . Теорема Фридмана 1971 года показала, что существует модель теории множеств Цермело (с аксиомой выбора), в которой детерминированность Бореля неверна, и, таким образом, теория множеств Цермело не может доказать теорему Бореля об детерминированности.

Существования всех чисел Бет счетного индекса достаточно для доказательства теоремы Бореля об определенности.

определенности

Основная статья: Решимость

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

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

Аксиома детерминированности утверждает, что все подмножества всех польских пространств определены. Он несовместим с ZFC, но в ZF + DC (теория множеств Цермело – Френкеля плюс аксиома зависимого выбора ) он эквисовместим с некоторыми большими кардинальными аксиомами.

Ссылки

• Фридман, Харви (1971). «Высшая теория множеств и математическая практика». Анналы математической логики . 2 (3): 325–357. дои : 10.1016/0003-4843(71)90018-0 .
  • Л. Буковский, рецензент журнала «Математическое обозрение» , МР 284327 .
• Гейл, Д. и Ф.М. Стюарт (1953). «Бесконечные игры с совершенной информацией». Вклад в теорию игр, вып. 2 . Анналы математических исследований, том. 28. Том. 28. Издательство Принстонского университета. стр. 245–266.
  • С. Шерман, рецензент журнала Mathematical Reviews , MR 54922 .
• Александр Кехрис (1995). Классическая описательная теория множеств . Тексты для аспирантов по математике . Том. 156. ИСБН  0-387-94374-9 .
• Мартин, Дональд А. (1975). «Борелевская определенность». Анналы математики . Вторая серия. 102 (2): 363–371. дои : 10.2307/1971035 .
  • Джон Берджесс, обозреватель. Математические обзоры , MR 403976 .
• Мартин, Дональд А. (1982). «Чисто индуктивное доказательство детерминированности Бореля». Теория рекурсии . Учеб. Симпозиумы. Чистая математика (Труды летнего института AMS – ASL, проводимого в Итаке, Нью-Йорк, изд.). стр. 303–308.
  • Ф. Р. Дрейк, рецензент журнала Mathematical Reviews , MR 791065 .

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

• Детерминированность Бореля и метаматематика . Росс Брайант. Магистерская диссертация, Университет Северного Техаса, 2001 г.
• «Большие кардиналы и решительность» в Стэнфордской энциклопедии философии