Гра Банаха — Мазура

Гра Банаха — Мазура — У загальній топології, теорії множин і теорії ігор це , в яку грають два гравці, вибираючи послідовність вкладених відрізків, довжина яких прямує до нуля. За принципом вкладених відрізків в результаті перетином усіх відрізків буде точка. Виграш кожного з гравців залежить від того, чи отримана точка належить наперед заданій множині. Поняття гри Банаха-Мазура тісно пов'язане з поняттям берівського простору. Ця гра була першою нескінченною позиційною грою з повною інформацією для вивчення.

Історія

Два математики, Стефан Банах і Станіслав Мазур вирішили пограти в гру. Вони визначили для себе деяку множину A на відрізку [0, 1]. Після цього Банах узяв якийсь відрізок, а Мазур всередині нього ще відрізок, і т. д. При цьому вони відразу домовилися, що довжина відрізків буде прямувати до нуля і тому в перетині буде виходити точка. Так от, якщо ця точка міститься в A, то виграв перший гравець, а якщо не міститься, то виграв другий. Банах із Мазуром задумалися, чи для будь-якого A в одного з гравців є виграшна стратегія.

Гра та аксіома детермінованості

Якщо множина A зліченна, то у другого є виграшна стратегія. Він може першим своїм ходом позбутися першої точки, взявши відрізок, що не містить її, другим ходом — другої, і т. д. Якщо A ніде не щільна, то другий може виграти взагалі за один хід, просто взявши відрізок, що не перетинається з A (таких існує величезна кількість за самим означенням). Якщо A — зліченне об'єднання ніде не щільних множин (такі множини Бер називав множинами першої категорії), то другий також може виграти: на першому кроці він позбавляється першої ніде не щільної множини, на другому — другої і т. д.

Множина A називається детермінованою, якщо для неї в одного з гравців є виграшна стратегія. Твердження про те, що всі ${\displaystyle A\subseteq [0;1]}$ є детермінованими — аксіома детермінованості. На відміну від аксіоми вибору навіть невідомо, чи дійсно вона несуперечлива з аксіоматикою Цермело-Френкеля. Зате відомо, що з аксіоми вибору миттєво випливає заперечення аксіоми детермінованості, але з аксіоми детермінованості випливає аксіома вибору для зліченного числа множин (завдяки чому у нас зберігається весь математичний аналіз).

Якщо прийняти аксіому детермінованості, можна отримати цікаві факти:

1. всі множини з [0, 1] вимірні за Лебегом;
2. будь-яка обмежена функція інтегровна за Лебегом;
3. немає вільних максимальних ідеалів;
4. базис є тільки в скінченновимірних лінійних просторах.

Загальна ідея аксіоми детермінованості в тому, що об'єкт існує, тільки якщо можна пояснити, як його будувати. А якщо ні, то об'єкт не існує зовсім.

Означення та властивості

Надалі ми будемо використовувати формалізм визначений в . Узагальнена гра Банаха-Мазура визначається таким чином. Дано топологічний простір ${\displaystyle Y}$, фіксована підмножина ${\displaystyle X\subset Y}$, і сім'я ${\displaystyle W}$ підмножин ${\displaystyle Y}$, які задовольняють таким умовам:

• Кожен член ${\displaystyle W}$ має непорожню внутрішність.
• Кожна непорожня відкрита підмножина ${\displaystyle Y}$ містить член ${\displaystyle W}$.

Ми будемо називати цю гру ${\displaystyle MB(X,Y,W)}$. Два гравці, ${\displaystyle P_{1}}$ і ${\displaystyle P_{2}}$, вибирають альтернативні елементи ${\displaystyle W_{0}}$, ${\displaystyle W_{1}}$, ${\displaystyle \cdots }$ з ${\displaystyle W}$ такі, що ${\displaystyle W_{0}\supset W_{1}\supset \cdots }$. ${\displaystyle P_{1}}$ виграє тоді, і тільки тоді, якщо ${\displaystyle X\cap (\cap _{n<\omega }W_{n})\neq \emptyset }$.

Виконуються такі властивості:

• ${\displaystyle P_{2}\uparrow MB(X,Y,W)}$ тоді, і тільки тоді, якщо ${\displaystyle X}$ множина першої категорії в ${\displaystyle Y}$ (зліченне об'єднання ніде не щільних множин.).
• В припущенні, що ${\displaystyle Y}$ є повним метричним простором, ${\displaystyle P_{1}\uparrow MB(X,Y,W)}$ тоді, і тільки тоді, якщо ${\displaystyle X}$ залишкова множина в деякій непорожній відкритій підмножині ${\displaystyle Y}$.
• Якщо ${\displaystyle X}$ має властивість Бера в ${\displaystyle Y}$, то ${\displaystyle MB(X,Y,W)}$ визначена (детермінована).
• Будь-яка виграшна стратегія ${\displaystyle P_{2}}$ може бути зведена до стаціонарної виграшної стратегії.
• Просіювані (англ. Siftable) та сильно-просіювані простори, введені Чоке, можуть бути означені в термінах стаціонарної стратегії у відповідних модифікацій гри. Позначимо через ${\displaystyle BM(X)}$ модифікацію ${\displaystyle MB(X,Y,W)}$, де ${\displaystyle X=Y}$, ${\displaystyle W}$ --- сім'я всіх непустих відкритих множин в ${\displaystyle X}$, і ${\displaystyle P_{2}}$ виграє гру ${\displaystyle (W_{0},W_{1},\cdots )}$ тоді, і тільки тоді, якщо ${\displaystyle \cap _{n<\omega }W_{n}\neq \emptyset }$. Тоді ${\displaystyle X}$ просіюваний тоді і тільки тоді, коли ${\displaystyle P_{2}}$ має стаціонарну виграшну стратегію в ${\displaystyle BM(X)}$.
• Марковська виграшна стратегія для ${\displaystyle P_{2}}$ у ${\displaystyle BM(X)}$ може бути зведена до стаціонарної виграшної стратегії. Крім того, якщо ${\displaystyle P_{2}}$ має виграшну стратегію в ${\displaystyle BM(X)}$, то він має виграшну стратегію, що залежить тільки від двох попередніх ходів. Досі не з'ясовано питання про те, чи виграшна стратегія для ${\displaystyle P_{2}}$ може бути зведена до виграшної стратегії, яка залежить тільки від двох останніх ходів ${\displaystyle P_{1}}$.
• ${\displaystyle X}$ називається слабо ${\displaystyle \alpha }$-сприятлива, якщо ${\displaystyle P_{2}}$ має виграшну стратегію в ${\displaystyle BM(X)}$. Тоді, ${\displaystyle X}$ простір Бера, тоді і тільки тоді, якщо ${\displaystyle P_{1}}$ не має виграшну стратегію в ${\displaystyle BM(X)}$. Звідси випливає, що кожний слабкий ${\displaystyle \alpha }$-сприятливий простір є простором Бера.

Багато інших модифікацій і спеціалізацій основної гри були запропоновані: для ретельного обліку цих, зверніться до [1987]. Найпоширеніший окремий випадок, званий ${\displaystyle MB(X,J)}$, полягає в тому, дозволяючи ${\displaystyle Y=J}$, тобто одиничний інтервал ${\displaystyle [0,1]}$, і в оповіщаючи ${\displaystyle W}$ складається з усіх відрізків ${\displaystyle [a,b]}$, що містяться в ${\displaystyle [0,1]}$. Гравці вибирають альтернативні підінтервалів ${\displaystyle J_{0},J_{1},\cdots }$ з ${\displaystyle J}$ таке, що ${\displaystyle J_{0}\supset J_{1}\supset \cdots }$, і ${\displaystyle P_{1}}$ виграє, якщо і тільки якщо ${\displaystyle X\cap (\cap _{n<\omega }J_{n})\neq \emptyset }$. ${\displaystyle P_{2}}$ виграє, якщо і тільки якщо ${\displaystyle X\cap (\cap _{n<\omega }J_{n})=\emptyset }$.

Просте доведення: виграшні стратегії

Природно запитати за те, що відрізняє ${\displaystyle X}$ робить ${\displaystyle P_{2}}$ є ( виграшну стратегію.) Ясно, що якщо ${\displaystyle X}$ порожній, ${\displaystyle P_{2}}$ має виграшну стратегію, тому питання може бути неофіційно перефразувати як «маленький» (відповідно, «великий») не ${\displaystyle X}$ (відповідно, доповнення ${\displaystyle X}$ у ${\displaystyle Y}$) повинні забезпечити, щоб ${\displaystyle P_{2}}$ має виграшну стратегію. Щоб аромат, як докази, використані для отримання властивостей у попередній роботі розділі покажемо, такий факт.

Факт: ${\displaystyle P_{2}}$ має виграшну стратегію, якщо ${\displaystyle X}$ зліченна, ${\displaystyle Y}$ є T₁, і ${\displaystyle Y}$ не має ізольованих точок.

Доведення: Позначимо елементи ${\displaystyle X}$ через ${\displaystyle x_{1},x_{2},\cdots }$. Припустимо, що ${\displaystyle W_{1}}$ був обраний ${\displaystyle P_{1}}$, і нехай ${\displaystyle U_{1}}$ --- це (непорожня) внутрішність ${\displaystyle W_{1}}$. Тоді ${\displaystyle U_{1}\setminus \{x_{1}\}}$ непорожня відкрита множина в ${\displaystyle Y}$, отже ${\displaystyle P_{2}}$ може вибрати елементи ${\displaystyle W_{2}}$ з ${\displaystyle W}$, що міститься в цій множині. Тоді ${\displaystyle P_{1}}$ вибирає підмножину ${\displaystyle W_{3}}$ з ${\displaystyle W_{2}}$ і, аналогічно, ${\displaystyle P_{2}}$ може вибрати елемент ${\displaystyle W_{4}\subset W_{3}}$, що виключає ${\displaystyle x_{2}}$. Продовжуючи таким чином, кожна точка ${\displaystyle x_{n}}$ буде виключена множиною ${\displaystyle W_{2n}}$, так що перетин всіх ${\displaystyle W_{n}}$ не буде перетинатися з ${\displaystyle X}$. Що й треба було довести.

Припущеннях про ${\displaystyle Y}$ є ключовими для доведення: наприклад, якщо ${\displaystyle Y=\{a,b,c\}}$ наділений дискретною топологією і ${\displaystyle W}$ складається з усіх непустих підмножин ${\displaystyle Y}$, то ${\displaystyle P_{2}}$ не має виграшної стратегії, якщо ${\displaystyle X=\{a\}}$ (по суті, його опонент має виграшну стратегію). Аналогічні ефекти трапляються, якщо ${\displaystyle Y}$ наділений топологією і ${\displaystyle W=\{Y\}}$.

Сильніший результат стосується ${\displaystyle X}$ множин першого порядку.

Факт: Нехай ${\displaystyle Y}$ топологічний простір, ${\displaystyle W}$ сім'я підмножин ${\displaystyle Y}$, що задовольняють дві властивості вище, і нехай ${\displaystyle X}$ будь-яка підмножина ${\displaystyle Y}$. ${\displaystyle P_{2}}$ має виграшну стратегію, тоді і тільки тоді, якщо ${\displaystyle X}$ є множиною першої категорії.

Це не означає, що ${\displaystyle P_{1}}$ має виграшну стратегію, якщо ${\displaystyle X}$ залишкова. Насправді, ${\displaystyle P_{1}}$ має виграшну стратегію тоді, і тільки тоді, якщо існує ${\displaystyle W_{i}\in W}$ така, що ${\displaystyle X\cap W_{i}}$ є залишковою підмножиною з ${\displaystyle W_{i}}$. Це може бути той випадок, коли жоден з гравців не має виграшної стратегії: коли ${\displaystyle Y}$ є ${\displaystyle [0,1]}$ і ${\displaystyle W}$ складається з відрізків ${\displaystyle [a,b]}$, гри визначена (детермінована), якщо цільова множина має властивість Бера, тобто якщо вона відрізняється від відкритої множини на множину першої категорії (але зворотне твердження хибне). Припускаючи справедливість аксіоми вибору, існують підмножини ${\displaystyle [0,1]}$, для яких гра Банаха-Мазура не визначена. Насправді, багато математиків заперечують істинність аксіоми вибору, посилаючись на те, що з неї випливають результати, що суперечать здоровому глузду, наприклад, парадокс Банаха — Тарського. Тому деякі з них припускають справедливість одного із її заперечень, а саме, , яка полягає в тому, що будь-яка нескінченна гра детермінована, тобто, хоч один з гравців має виграшну стратегію. Досі не доведено суперечливості ні аксіоми вибору, ні аксіоми детермінованості з системою аксіом Цермело — Френкеля без аксіоми вибору.

Див. також

• Список об'єктів, названих на честь Стефана Банаха

Література

1. (рос.) Кановей В. Г. Аксиома выбора и аксиома детерминированности. — М.: Физматгиз, 1984.
2. (англ.) Oxtoby, J. C. The Banach-Mazur game and Banach category theorem, Contribution to the Theory of Games, Volume III, Annals of Mathematical Studies 39 (1957), Princeton, 159—163
3. (англ.) Telgársky, R. J. Topological Games: On the 50th Anniversary of the Banach–Mazur Game [ 8 грудня 2013 у Wayback Machine.], Rocky Mountain J. Math. 17 (1987), pp. 227—276.
4. (англ.) Julian P. Revalski The Banach-Mazur game: History and recent developments [ 21 липня 2011 у Wayback Machine.], Seminar notes, Pointe-a-Pitre, Guadeloupe, France, 2003—2004