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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ми будемо називати цю гру . Два гравці, і , вибирають альтернативні елементи , , з такі, що . виграє тоді, і тільки тоді, якщо .

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

  • тоді, і тільки тоді, якщо множина першої категорії в (зліченне об'єднання ніде не щільних множин.).
  • В припущенні, що є повним метричним простором, тоді, і тільки тоді, якщо залишкова множина в деякій непорожній відкритій підмножині .
  • Якщо має властивість Бера в , то визначена (детермінована).
  • Будь-яка виграшна стратегія може бути зведена до стаціонарної виграшної стратегії.
  • Просіювані (англ. Siftable) та сильно-просіювані простори, введені Чоке, можуть бути означені в термінах стаціонарної стратегії у відповідних модифікацій гри. Позначимо через модифікацію , де , --- сім'я всіх непустих відкритих множин в , і виграє гру тоді, і тільки тоді, якщо . Тоді просіюваний тоді і тільки тоді, коли має стаціонарну виграшну стратегію в .
  • Марковська виграшна стратегія для у може бути зведена до стаціонарної виграшної стратегії. Крім того, якщо має виграшну стратегію в , то він має виграшну стратегію, що залежить тільки від двох попередніх ходів. Досі не з'ясовано питання про те, чи виграшна стратегія для може бути зведена до виграшної стратегії, яка залежить тільки від двох останніх ходів .
  • називається слабо -сприятлива, якщо має виграшну стратегію в . Тоді, простір Бера, тоді і тільки тоді, якщо не має виграшну стратегію в . Звідси випливає, що кожний слабкий -сприятливий простір є простором Бера.

Багато інших модифікацій і спеціалізацій основної гри були запропоновані: для ретельного обліку цих, зверніться до [1987]. Найпоширеніший окремий випадок, званий , полягає в тому, дозволяючи , тобто одиничний інтервал , і в оповіщаючи складається з усіх відрізків , що містяться в . Гравці вибирають альтернативні підінтервалів з таке, що , і виграє, якщо і тільки якщо . виграє, якщо і тільки якщо .

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

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

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

Доведення: Позначимо елементи через . Припустимо, що був обраний , і нехай --- це (непорожня) внутрішність . Тоді непорожня відкрита множина в , отже може вибрати елементи з , що міститься в цій множині. Тоді вибирає підмножину з і, аналогічно, може вибрати елемент , що виключає . Продовжуючи таким чином, кожна точка буде виключена множиною , так що перетин всіх не буде перетинатися з . Що й треба було довести.

Припущеннях про є ключовими для доведення: наприклад, якщо наділений дискретною топологією і складається з усіх непустих підмножин , то не має виграшної стратегії, якщо (по суті, його опонент має виграшну стратегію). Аналогічні ефекти трапляються, якщо наділений недискретною топологією і .

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

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

Це не означає, що має виграшну стратегію, якщо залишкова. Насправді, має виграшну стратегію тоді, і тільки тоді, якщо існує така, що є залишковою підмножиною з . Це може бути той випадок, коли жоден з гравців не має виграшної стратегії: коли є і складається з відрізків , гри визначена (детермінована), якщо цільова множина має властивість Бера, тобто якщо вона відрізняється від відкритої множини на множину першої категорії (але зворотне твердження хибне). Припускаючи справедливість аксіоми вибору, існують підмножини , для яких гра Банаха-Мазура не визначена. Насправді, багато математиків заперечують істинність аксіоми вибору, посилаючись на те, що з неї випливають результати, що суперечать здоровому глузду, наприклад, парадокс Банаха — Тарського. Тому деякі з них припускають справедливість одного із її заперечень, а саме, аксіоми детермінованості, яка полягає в тому, що будь-яка нескінченна гра детермінована, тобто, хоч один з гравців має виграшну стратегію. Досі не доведено суперечливості ні аксіоми вибору, ні аксіоми детермінованості з системою аксіом Цермело — Френкеля без аксіоми вибору.

Див. також[ред. | ред. код]

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

  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