В дескриптивной теории множеств , то Борель детерминированности теорема утверждает , что любая Gale-Stewart игра, расплата множество является борелевским будет определено , что означает , что один из двух игроков будет иметь выигрышную стратегию для игры.
Теорема была доказана Дональдом А. Мартином в 1975 году и применяется в описательной теории множеств, чтобы показать, что борелевские множества в польских пространствах обладают свойствами регулярности, такими как свойство совершенного множества и свойство Бэра .
Теорема также известна своими метаматематическими свойствами. В 1971 году, до того, как теорема была доказана, Харви Фридман показал, что любое доказательство теоремы теории множеств Цермело – Френкеля должно многократно использовать аксиому замещения . Более поздние результаты показали, что более сильные теоремы об определенности не могут быть доказаны в теории множеств Цермело – Френкеля, хотя они относительно согласуются с ней, если согласованы некоторые большие кардиналы .
Задний план
Игры Гейла – Стюарта
Gale-Stewart игра двух игроков игра полной информации. Игра определяется с помощью набора А , и обозначается G A . Два игрока по очереди ходят, и каждый игрок знает обо всех своих ходах перед тем, как сделать следующий. На каждом повороте, каждый игрок выбирает один элемент из А в игре. Один и тот же элемент может быть выбран более одного раза без ограничений. Игру можно визуализировать с помощью следующей диаграммы, на которой ходы делаются слева направо, с движениями игрока I вверху и движениями игрока II внизу.
Игра продолжается без конца, так что одиночный ход игры определяет бесконечную последовательность. элементов A . Множество всех таких последовательностей обозначается A ω . С самого начала игры игрокам известно о фиксированном наборе выплат (также известном как набор выигрышей ), который определит, кто победит. Множество выигрыша является подмножеством из A со . Если бесконечная последовательность, созданная ходом игры, входит в набор выплат, то игрок I выигрывает. В противном случае выигрывает игрок II; нет галстуков.
Это определение изначально не включает традиционные игры с идеальной информацией, такие как шахматы, поскольку набор ходов, доступных в таких играх, меняется каждый ход. Тем не менее, в подобном случае можно справиться, объявив, что игрок, который делает недопустимый ход, немедленно проигрывает, так что понятие игры Гейла-Стюарта действительно обобщает концепцию игры, определяемую деревом игр .
Стратегии победы
Выигрышная стратегия для игрока является функцией , которая сообщает игроку , что двигаться , чтобы сделать из любой позиции в игре, так что если игрок следует за функцией он или она, несомненно , выиграет. Более конкретно, выигрышная стратегия для игрока I - это функция f, которая принимает в качестве входных последовательностей элементов A четной длины и возвращает элемент A , так что игрок I выигрывает каждую игру формы
Выигрышной стратегией для игрока II является функция g, которая принимает последовательности элементов нечетной длины из A и возвращает элементы из A , так что игрок II выиграет каждую игру вида
Максимум один игрок может иметь выигрышную стратегию; если оба игрока имели выигрышные стратегии и использовали их друг против друга, только одна из двух стратегий могла выиграть в этой игре. Если один из игроков имеет выигрышную стратегию для определенного набора выплат, то говорят, что этот набор выплат определен .
Топология
Для данного множества A , будет ли определено подмножество A ω , в некоторой степени зависит от его топологической структуры. Для целей Гейла-Стюарт игр, множество наделено дискретной топологией и со , наделенным полученной топологией произведения , где ω рассматривается как счетное топологическое произведение из А с самими собой. В частности, когда A - множество {0,1}, топология, определенная на A ω, является в точности обычной топологией на пространстве Кантора , а когда A - множество натуральных чисел, это обычная топология на пространстве Бэра .
Множество A ω можно рассматривать как множество путей через некоторое дерево , что приводит к второй характеристике его топологии. Дерево состоит из всех конечных последовательностей элементов A , а потомки конкретного узла σ дерева - это в точности последовательности, расширяющие σ на один элемент. Таким образом, если A = {0, 1}, первый уровень дерева состоит из последовательностей ⟨0⟩ и ⟨1⟩; второй уровень состоит из четырех последовательностей ⟨0, 0⟩, ⟨0, 1⟩, ⟨1, 0⟩, ⟨1, 1⟩; и так далее. Для каждого из конечных последовательностей сга в дереве, множество всех элементов А со , которые начинаются с а является базисным открытым множеством в топологии А . В открытых множествах из A ω является в точности множество представимы союзами этих основных открытых множеств. В замкнутых множеств , как обычно, являются те , чье дополнение открыто.
В борелевские из A ω являются наименьший класс подмножеств А со , что включает в себя открытые множества и замкнуто относительно дополнения и счетного объединения. То есть борелевские множества - это наименьшая σ-алгебра подмножеств A ω, содержащая все открытые множества. Множества Бореля классифицируются в иерархии Бореля на основе того, сколько раз требуются операции дополнения и счетного объединения, чтобы произвести их из открытых множеств.
Предыдущие результаты
Гейл и Стюарт (1953) доказали, что если множество выигрышей является открытым или замкнутым подмножеством A ω, то игра Гейла – Стюарта с этим множеством выигрышей всегда определяется. В течение следующих двадцати лет это было распространено на несколько более высокие уровни иерархии Бореля за счет еще более сложных доказательств. Это привело к вопросу о том, должна ли игра быть определена , когда множество взятки является борелевское из А со . Было известно, что, используя аксиому выбора , можно построить подмножество {0,1} ω , которое не определено (Kechris 1995, стр. 139).
Харви Фридман (1971) доказал, что любое доказательство того, что все борелевские подмножества пространства Кантора ({0,1} ω ) были определены, потребует многократного использования аксиомы замены , аксиомы, которая обычно не требуется для доказательства теорем о «малых» объектах, таких как как пространство Кантора.
Борелевская определенность
Дональд А. Мартин (1975) доказал, что для любого множества A все борелевские подмножества A ω определены. Поскольку первоначальное доказательство было довольно сложным, Мартин опубликовал в 1982 году более короткое доказательство, для которого не требовалось столько технических средств. В своем обзоре статьи Мартина Дрейк описывает второе доказательство как «удивительно простое».
Область описательной теории множеств изучает свойства польских пространств (по сути, полных сепарабельных метрических пространств). Теорема Бореля об детерминированности использовалась для установления многих [ необходима цитата ] свойств борелевских подмножеств этих пространств. Например, все борелевские подмножества польских пространств обладают свойством идеального множества и свойством Бэра .
Теоретико-множественные аспекты
Теорема Бореля об определенности представляет интерес своими метаметематическими свойствами, а также своими следствиями в описательной теории множеств.
Детерминированность замкнутых множеств A ω для произвольного A эквивалентна аксиоме выбора над ZF (Kechris 1995, стр. 139). При работе в теоретико-множественных системах, где аксиома выбора не предполагается, этого можно избежать, рассматривая обобщенные стратегии, известные как квазистратегии (Kechris 1995, стр.139), или рассматривая только игры, в которых A - множество натуральных чисел, как в аксиоме детерминированности .
Теория множеств Цермело (Z) - это теория множеств Цермело – Френкеля без аксиомы замены. Он отличается от ZF тем, что Z не доказывает, что операция набора мощности может повторяться несчетное количество раз, начиная с произвольного набора. В частности, V ω + ω , частный счетный уровень кумулятивной иерархии , является моделью теории множеств Цермело. Аксиома замены, с другой стороны, удовлетворяется только V κ для значительно больших значений κ, например, когда κ является сильно недоступным кардиналом . Теорема Фридмана 1971 года показала, что существует модель теории множеств Цермело (с выбранной аксиомой), в которой борелевская детерминированность не работает, и, таким образом, теория множеств Цермело не может доказать теорему Борелевской детерминированности.
Более сильные формы определенности
В описательной теории множеств изучаются несколько теоретико-множественных принципов детерминированности, более сильных, чем детерминированность по Борелю. Они тесно связаны с большими кардинальными аксиомами .
Аксиома проективной детерминированности утверждает , что все проективные подмножества польского пространства определяются. Известно, что это недоказуемо в ZFC, но относительно согласуется с ним и подразумевается некоторыми большими кардинальными аксиомами. Существования измеримого кардинала достаточно, чтобы над ZFC предполагалось, что все аналитические подмножества польских пространств определены.
Аксиома детерминированности состояний , что все подмножества всех польских пространств определяются. Это несовместимо с ZFC, но в ZF + DC (теория множеств Цермело – Френкеля плюс аксиома зависимого выбора ) оно равно совместимо с некоторыми большими кардинальными аксиомами.
Рекомендации
- Фридман, Харви (1971). «Высшая теория множеств и математическая практика» . Анналы математической логики . 2 (3): 325–357. DOI : 10.1016 / 0003-4843 (71) 90018-0 .
- Л. Буковский, рецензент, Mathematical Reviews , MR284327 .
- Гейл Д. и Ф. М. Стюарт (1953). «Бесконечные игры с точной информацией». К теории игр, т. 2 . Анналы математических исследований, т. 28. 28 . Издательство Принстонского университета. С. 245–266.
- С. Шерман, рецензент, Mathematical Reviews , MR54922 .
- Александр Кечрис (1995). Классическая описательная теория множеств . Тексты для выпускников по математике . 156 . ISBN 0-387-94374-9. CS1 maint: обескураженный параметр ( ссылка )
- Мартин, Дональд А. (1975). «Борелевская определенность». Анналы математики . Вторая серия. 102 (2): 363–371. DOI : 10.2307 / 1971035 .
- Джон Берджесс, рецензент. Математические обзоры , MR403976 .
- Мартин, Дональд А. (1982). «Чисто индуктивное доказательство определенности Бореля». Теория рекурсии . Proc. Симпозиумы. Чистая математика (Труды летнего института AMS – ASL, проведенного в Итаке, штат Нью-Йорк, ред.). С. 303–308.
- FR Drake, рецензент, Mathematical Reviews , MR791065 .
Внешние ссылки
- Борелевская детерминированность и метаматематика . Росс Брайант. Магистерская работа, Университет Северного Техаса, 2001 г.
- «Большие кардиналы и решительность» в Стэнфордской энциклопедии философии