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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Історія[ред.ред. код]

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

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

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

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

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

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

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

Означення та властивості[ред.ред. код]

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

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

Ми будемо називати цю гру MB(X,Y,W). Два гравці, P_1 і P_2, вибирають альтернативні елементи W_0, W_1, \cdots з W такі, що W_0 \supset W_1 \supset \cdots. P_1 виграє тоді, і тільки тоді, якщо X \cap (\cap_{n<\omega} W_n) \neq \emptyset.

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

  • P_2 \uparrow MB(X,Y,W) тоді, і тільки тоді, якщо X множина першої категорії в Y (зліченне об'єднання ніде не щільних множин.).
  • В припущенні, що Y є повним метричним простором, P_1 \uparrow MB(X,Y,W) тоді, і тільки тоді, якщо X залишкова множина в деякій непорожній відкритій підмножині Y.
  • Якщо X має властивість Бера в Y, то MB(X,Y,W) визначена (детермінована).
  • Будь-яка виграшна стратегія  P_2 може бути зведена до стаціонарної виграшної стратегії.
  • Просіювані (англ. Siftable) та сильно-просіювані простори, введені Чоке, можуть бути означені в термінах стаціонарної стратегії у відповідних модифікацій гри. Позначимо через BM(X) модифікацію MB(X,Y,W), де X=Y, W --- сім'я всіх непустих відкритих множин в X, і P_2 виграє гру (W_0, W_1, \cdots) тоді, і тільки тоді, якщо \cap_{n<\omega} W_n \neq \emptyset. Тоді X просіюваний тоді і тільки тоді, коли P_2 має стаціонарну виграшну стратегію в math>BM(X)</math>.
  • Марковська виграшна стратегія для P_2 у BM(X) може бути зведена до стаціонарної виграшної стратегії. Крім того, якщо P_2 має виграшну стратегію в BM(X), то він має виграшну стратегію, що залежить тільки від двох попередніх ходів. Досі нез'ясовано питання про те, чи виграшна стратегія для P_2 може бути зведена до виграшної стратегії, яка залежить тільки від двох останніх ходів P_1.
  • X називаєтся слабо \alpha-сприятлива, якщо P_2 має виграшну стратегію в BM(X). Тоді, X простір Бера, тоді і тільки тоді, якщо P_1 не має виграшну стратегію в BM(X). Звідси випливає, що кожний слабкий \alpha-сприятливий простір є простором Бера.

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

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

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

Факт: P_2 має виграшну стратегію, якщо X зліченна, Y є T1, і Y не має ізольованих точок.

Доведення: Позначимо елементи X через x_1, x_2, \cdots. Припустимо, що W_1 був обраний P_1, і нехай U_1 --- це (непорожня) внутрішність W_1. Тоді U_1 \setminus \{x_1\} непорожня відкрита множина в Y, отже P_2 може вибрати елементи W_2 з W, що міститься в цій множині. Тоді P_1 вибирає підмножину W_3 з W_2 і, аналогічно, P_2 може вибрати елемент W_4 \subset W_3, що виключає x_2. Продовжуючи таким чином, кожна точка x_n буде виключена множиною W_{2n}, так що перетин всіх W_n не буде перетинатися з X. Що й треба було довести.

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

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

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

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

Література[ред.ред. код]

  1. (рос.) Кановей В. Г. Аксиома выбора и аксиома детерминированности. — М.: Физматгиз, 1984.
  2. англ. {{{1}}} 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. англ. {{{1}}} Telgársky, R. J. Topological Games: On the 50th Anniversary of the Banach–Mazur Game, Rocky Mountain J. Math. 17 (1987), pp. 227—276.
  4. англ. {{{1}}} Julian P. Revalski The Banach-Mazur game: History and recent developments, Seminar notes, Pointe-a-Pitre, Guadeloupe, France, 2003—2004