Гра Банаха — Мазура — У загальній топології, теорії множин і теорії ігор це , в яку грають два гравці, вибираючи послідовність вкладених відрізків, довжина яких прямує до нуля. За принципом вкладених відрізків в результаті перетином усіх відрізків буде точка. Виграш кожного з гравців залежить від того, чи отримана точка належить наперед заданій множині. Поняття гри Банаха-Мазура тісно пов'язане з поняттям берівського простору. Ця гра була першою нескінченною позиційною грою з повною інформацією для вивчення.
Історія
Два математики, Стефан Банах і Станіслав Мазур вирішили пограти в гру. Вони визначили для себе деяку множину A на відрізку [0, 1]. Після цього Банах узяв якийсь відрізок, а Мазур всередині нього ще відрізок, і т. д. При цьому вони відразу домовилися, що довжина відрізків буде прямувати до нуля і тому в перетині буде виходити точка. Так от, якщо ця точка міститься в A, то виграв перший гравець, а якщо не міститься, то виграв другий. Банах із Мазуром задумалися, чи для будь-якого A в одного з гравців є виграшна стратегія.
Гра та аксіома детермінованості
Якщо множина A зліченна, то у другого є виграшна стратегія. Він може першим своїм ходом позбутися першої точки, взявши відрізок, що не містить її, другим ходом — другої, і т. д. Якщо A ніде не щільна, то другий може виграти взагалі за один хід, просто взявши відрізок, що не перетинається з A (таких існує величезна кількість за самим означенням). Якщо A — зліченне об'єднання ніде не щільних множин (такі множини Бер називав множинами першої категорії), то другий також може виграти: на першому кроці він позбавляється першої ніде не щільної множини, на другому — другої і т. д.
Множина A називається детермінованою, якщо для неї в одного з гравців є виграшна стратегія. Твердження про те, що всі є детермінованими — аксіома детермінованості. На відміну від аксіоми вибору навіть невідомо, чи дійсно вона несуперечлива з аксіоматикою Цермело-Френкеля. Зате відомо, що з аксіоми вибору миттєво випливає заперечення аксіоми детермінованості, але з аксіоми детермінованості випливає аксіома вибору для зліченного числа множин (завдяки чому у нас зберігається весь математичний аналіз).
Якщо прийняти аксіому детермінованості, можна отримати цікаві факти:
- всі множини з [0, 1] вимірні за Лебегом;
- будь-яка обмежена функція інтегровна за Лебегом;
- немає вільних максимальних ідеалів;
- базис є тільки в скінченновимірних лінійних просторах.
Загальна ідея аксіоми детермінованості в тому, що об'єкт існує, тільки якщо можна пояснити, як його будувати. А якщо ні, то об'єкт не існує зовсім.
Означення та властивості
Надалі ми будемо використовувати формалізм визначений в . Узагальнена гра Банаха-Мазура визначається таким чином. Дано топологічний простір , фіксована підмножина
, і сім'я
підмножин
, які задовольняють таким умовам:
- Кожен член
має непорожню внутрішність.
- Кожна непорожня відкрита підмножина
містить член
.
Ми будемо називати цю гру . Два гравці,
і
, вибирають альтернативні елементи
,
,
з
такі, що
.
виграє тоді, і тільки тоді, якщо
.
Виконуються такі властивості:
тоді, і тільки тоді, якщо
множина першої категорії в
(зліченне об'єднання ніде не щільних множин.).
- В припущенні, що
є повним метричним простором,
тоді, і тільки тоді, якщо
залишкова множина в деякій непорожній відкритій підмножині
.
- Якщо
має властивість Бера в
, то
визначена (детермінована).
- Будь-яка виграшна стратегія
може бути зведена до стаціонарної виграшної стратегії.
- Просіювані (англ. Siftable) та сильно-просіювані простори, введені Чоке, можуть бути означені в термінах стаціонарної стратегії у відповідних модифікацій гри. Позначимо через
модифікацію
, де
,
--- сім'я всіх непустих відкритих множин в
, і
виграє гру
тоді, і тільки тоді, якщо
. Тоді
просіюваний тоді і тільки тоді, коли
має стаціонарну виграшну стратегію в
.
- Марковська виграшна стратегія для
у
може бути зведена до стаціонарної виграшної стратегії. Крім того, якщо
має виграшну стратегію в
, то він має виграшну стратегію, що залежить тільки від двох попередніх ходів. Досі не з'ясовано питання про те, чи виграшна стратегія для
може бути зведена до виграшної стратегії, яка залежить тільки від двох останніх ходів
.
називається слабо
-сприятлива, якщо
має виграшну стратегію в
. Тоді,
простір Бера, тоді і тільки тоді, якщо
не має виграшну стратегію в
. Звідси випливає, що кожний слабкий
-сприятливий простір є простором Бера.
Багато інших модифікацій і спеціалізацій основної гри були запропоновані: для ретельного обліку цих, зверніться до [1987]. Найпоширеніший окремий випадок, званий , полягає в тому, дозволяючи
, тобто одиничний інтервал
, і в оповіщаючи
складається з усіх відрізків
, що містяться в
. Гравці вибирають альтернативні підінтервалів
з
таке, що
, і
виграє, якщо і тільки якщо
.
виграє, якщо і тільки якщо
.
Просте доведення: виграшні стратегії
Природно запитати за те, що відрізняє робить
є ( виграшну стратегію.) Ясно, що якщо
порожній,
має виграшну стратегію, тому питання може бути неофіційно перефразувати як «маленький» (відповідно, «великий») не
(відповідно, доповнення
у
) повинні забезпечити, щоб
має виграшну стратегію. Щоб аромат, як докази, використані для отримання властивостей у попередній роботі розділі покажемо, такий факт.
Факт: має виграшну стратегію, якщо
зліченна,
є T1, і
не має ізольованих точок.
Доведення: Позначимо елементи через
. Припустимо, що
був обраний
, і нехай
--- це (непорожня) внутрішність
. Тоді
непорожня відкрита множина в
, отже
може вибрати елементи
з
, що міститься в цій множині. Тоді
вибирає підмножину
з
і, аналогічно,
може вибрати елемент
, що виключає
. Продовжуючи таким чином, кожна точка
буде виключена множиною
, так що перетин всіх
не буде перетинатися з
. Що й треба було довести.
Припущеннях про є ключовими для доведення: наприклад, якщо
наділений дискретною топологією і
складається з усіх непустих підмножин
, то
не має виграшної стратегії, якщо
(по суті, його опонент має виграшну стратегію). Аналогічні ефекти трапляються, якщо
наділений топологією і
.
Сильніший результат стосується множин першого порядку.
Факт: Нехай топологічний простір,
сім'я підмножин
, що задовольняють дві властивості вище, і нехай
будь-яка підмножина
.
має виграшну стратегію, тоді і тільки тоді, якщо
є множиною першої категорії.
Це не означає, що має виграшну стратегію, якщо
залишкова. Насправді,
має виграшну стратегію тоді, і тільки тоді, якщо існує
така, що
є залишковою підмножиною з
. Це може бути той випадок, коли жоден з гравців не має виграшної стратегії: коли
є
і
складається з відрізків
, гри визначена (детермінована), якщо цільова множина має властивість Бера, тобто якщо вона відрізняється від відкритої множини на множину першої категорії (але зворотне твердження хибне). Припускаючи справедливість аксіоми вибору, існують підмножини
, для яких гра Банаха-Мазура не визначена. Насправді, багато математиків заперечують істинність аксіоми вибору, посилаючись на те, що з неї випливають результати, що суперечать здоровому глузду, наприклад, парадокс Банаха — Тарського. Тому деякі з них припускають справедливість одного із її заперечень, а саме, , яка полягає в тому, що будь-яка нескінченна гра детермінована, тобто, хоч один з гравців має виграшну стратегію. Досі не доведено суперечливості ні аксіоми вибору, ні аксіоми детермінованості з системою аксіом Цермело — Френкеля без аксіоми вибору.
Див. також
Література
- (рос.) Кановей В. Г. Аксиома выбора и аксиома детерминированности. — М.: Физматгиз, 1984.
- (англ.) 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
- (англ.) 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.
- (англ.) Julian P. Revalski The Banach-Mazur game: History and recent developments [ 21 липня 2011 у Wayback Machine.], Seminar notes, Pointe-a-Pitre, Guadeloupe, France, 2003—2004
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Gra Banaha Mazura U zagalnij topologiyi teoriyi mnozhin i teoriyi igor ce v yaku grayut dva gravci vibirayuchi poslidovnist vkladenih vidrizkiv dovzhina yakih pryamuye do nulya Za principom vkladenih vidrizkiv v rezultati peretinom usih vidrizkiv bude tochka Vigrash kozhnogo z gravciv zalezhit vid togo chi otrimana tochka nalezhit napered zadanij mnozhini Ponyattya gri Banaha Mazura tisno pov yazane z ponyattyam berivskogo prostoru Cya gra bula pershoyu neskinchennoyu pozicijnoyu groyu z povnoyu informaciyeyu dlya vivchennya IstoriyaDva matematiki Stefan Banah i Stanislav Mazur virishili pograti v gru Voni viznachili dlya sebe deyaku mnozhinu A na vidrizku 0 1 Pislya cogo Banah uzyav yakijs vidrizok a Mazur vseredini nogo she vidrizok i t d Pri comu voni vidrazu domovilisya sho dovzhina vidrizkiv bude pryamuvati do nulya i tomu v peretini bude vihoditi tochka Tak ot yaksho cya tochka mistitsya v A to vigrav pershij gravec a yaksho ne mistitsya to vigrav drugij Banah iz Mazurom zadumalisya chi dlya bud yakogo A v odnogo z gravciv ye vigrashna strategiya Gra ta aksioma determinovanostiYaksho mnozhina A zlichenna to u drugogo ye vigrashna strategiya Vin mozhe pershim svoyim hodom pozbutisya pershoyi tochki vzyavshi vidrizok sho ne mistit yiyi drugim hodom drugoyi i t d Yaksho A nide ne shilna to drugij mozhe vigrati vzagali za odin hid prosto vzyavshi vidrizok sho ne peretinayetsya z A takih isnuye velichezna kilkist za samim oznachennyam Yaksho A zlichenne ob yednannya nide ne shilnih mnozhin taki mnozhini Ber nazivav mnozhinami pershoyi kategoriyi to drugij takozh mozhe vigrati na pershomu kroci vin pozbavlyayetsya pershoyi nide ne shilnoyi mnozhini na drugomu drugoyi i t d Mnozhina A nazivayetsya determinovanoyu yaksho dlya neyi v odnogo z gravciv ye vigrashna strategiya Tverdzhennya pro te sho vsi A 0 1 displaystyle A subseteq 0 1 ye determinovanimi aksioma determinovanosti Na vidminu vid aksiomi viboru navit nevidomo chi dijsno vona nesuperechliva z aksiomatikoyu Cermelo Frenkelya Zate vidomo sho z aksiomi viboru mittyevo viplivaye zaperechennya aksiomi determinovanosti ale z aksiomi determinovanosti viplivaye aksioma viboru dlya zlichennogo chisla mnozhin zavdyaki chomu u nas zberigayetsya ves matematichnij analiz Yaksho prijnyati aksiomu determinovanosti mozhna otrimati cikavi fakti vsi mnozhini z 0 1 vimirni za Lebegom bud yaka obmezhena funkciya integrovna za Lebegom nemaye vilnih maksimalnih idealiv bazis ye tilki v skinchennovimirnih linijnih prostorah Zagalna ideya aksiomi determinovanosti v tomu sho ob yekt isnuye tilki yaksho mozhna poyasniti yak jogo buduvati A yaksho ni to ob yekt ne isnuye zovsim Oznachennya ta vlastivostiNadali mi budemo vikoristovuvati formalizm viznachenij v Uzagalnena gra Banaha Mazura viznachayetsya takim chinom Dano topologichnij prostir Y displaystyle Y fiksovana pidmnozhina X Y displaystyle X subset Y i sim ya W displaystyle W pidmnozhin Y displaystyle Y yaki zadovolnyayut takim umovam Kozhen chlen W displaystyle W maye neporozhnyu vnutrishnist Kozhna neporozhnya vidkrita pidmnozhina Y displaystyle Y mistit chlen W displaystyle W Mi budemo nazivati cyu gru M B X Y W displaystyle MB X Y W Dva gravci P 1 displaystyle P 1 i P 2 displaystyle P 2 vibirayut alternativni elementi W 0 displaystyle W 0 W 1 displaystyle W 1 displaystyle cdots z W displaystyle W taki sho W 0 W 1 displaystyle W 0 supset W 1 supset cdots P 1 displaystyle P 1 vigraye todi i tilki todi yaksho X n lt w W n displaystyle X cap cap n lt omega W n neq emptyset Vikonuyutsya taki vlastivosti P 2 M B X Y W displaystyle P 2 uparrow MB X Y W todi i tilki todi yaksho X displaystyle X mnozhina pershoyi kategoriyi v Y displaystyle Y zlichenne ob yednannya nide ne shilnih mnozhin V pripushenni sho Y displaystyle Y ye povnim metrichnim prostorom P 1 M B X Y W displaystyle P 1 uparrow MB X Y W todi i tilki todi yaksho X displaystyle X zalishkova mnozhina v deyakij neporozhnij vidkritij pidmnozhini Y displaystyle Y Yaksho X displaystyle X maye vlastivist Bera v Y displaystyle Y to M B X Y W displaystyle MB X Y W viznachena determinovana Bud yaka vigrashna strategiya P 2 displaystyle P 2 mozhe buti zvedena do stacionarnoyi vigrashnoyi strategiyi Prosiyuvani angl Siftable ta silno prosiyuvani prostori vvedeni Choke mozhut buti oznacheni v terminah stacionarnoyi strategiyi u vidpovidnih modifikacij gri Poznachimo cherez B M X displaystyle BM X modifikaciyu M B X Y W displaystyle MB X Y W de X Y displaystyle X Y W displaystyle W sim ya vsih nepustih vidkritih mnozhin v X displaystyle X i P 2 displaystyle P 2 vigraye gru W 0 W 1 displaystyle W 0 W 1 cdots todi i tilki todi yaksho n lt w W n displaystyle cap n lt omega W n neq emptyset Todi X displaystyle X prosiyuvanij todi i tilki todi koli P 2 displaystyle P 2 maye stacionarnu vigrashnu strategiyu v B M X displaystyle BM X Markovska vigrashna strategiya dlya P 2 displaystyle P 2 u B M X displaystyle BM X mozhe buti zvedena do stacionarnoyi vigrashnoyi strategiyi Krim togo yaksho P 2 displaystyle P 2 maye vigrashnu strategiyu v B M X displaystyle BM X to vin maye vigrashnu strategiyu sho zalezhit tilki vid dvoh poperednih hodiv Dosi ne z yasovano pitannya pro te chi vigrashna strategiya dlya P 2 displaystyle P 2 mozhe buti zvedena do vigrashnoyi strategiyi yaka zalezhit tilki vid dvoh ostannih hodiv P 1 displaystyle P 1 X displaystyle X nazivayetsya slabo a displaystyle alpha spriyatliva yaksho P 2 displaystyle P 2 maye vigrashnu strategiyu v B M X displaystyle BM X Todi X displaystyle X prostir Bera todi i tilki todi yaksho P 1 displaystyle P 1 ne maye vigrashnu strategiyu v B M X displaystyle BM X Zvidsi viplivaye sho kozhnij slabkij a displaystyle alpha spriyatlivij prostir ye prostorom Bera Bagato inshih modifikacij i specializacij osnovnoyi gri buli zaproponovani dlya retelnogo obliku cih zvernitsya do 1987 Najposhirenishij okremij vipadok zvanij M B X J displaystyle MB X J polyagaye v tomu dozvolyayuchi Y J displaystyle Y J tobto odinichnij interval 0 1 displaystyle 0 1 i v opovishayuchi W displaystyle W skladayetsya z usih vidrizkiv a b displaystyle a b sho mistyatsya v 0 1 displaystyle 0 1 Gravci vibirayut alternativni pidintervaliv J 0 J 1 displaystyle J 0 J 1 cdots z J displaystyle J take sho J 0 J 1 displaystyle J 0 supset J 1 supset cdots i P 1 displaystyle P 1 vigraye yaksho i tilki yaksho X n lt w J n displaystyle X cap cap n lt omega J n neq emptyset P 2 displaystyle P 2 vigraye yaksho i tilki yaksho X n lt w J n displaystyle X cap cap n lt omega J n emptyset Proste dovedennya vigrashni strategiyiPrirodno zapitati za te sho vidriznyaye X displaystyle X robit P 2 displaystyle P 2 ye vigrashnu strategiyu Yasno sho yaksho X displaystyle X porozhnij P 2 displaystyle P 2 maye vigrashnu strategiyu tomu pitannya mozhe buti neoficijno perefrazuvati yak malenkij vidpovidno velikij ne X displaystyle X vidpovidno dopovnennya X displaystyle X u Y displaystyle Y povinni zabezpechiti shob P 2 displaystyle P 2 maye vigrashnu strategiyu Shob aromat yak dokazi vikoristani dlya otrimannya vlastivostej u poperednij roboti rozdili pokazhemo takij fakt Fakt P 2 displaystyle P 2 maye vigrashnu strategiyu yaksho X displaystyle X zlichenna Y displaystyle Y ye T1 i Y displaystyle Y ne maye izolovanih tochok Dovedennya Poznachimo elementi X displaystyle X cherez x 1 x 2 displaystyle x 1 x 2 cdots Pripustimo sho W 1 displaystyle W 1 buv obranij P 1 displaystyle P 1 i nehaj U 1 displaystyle U 1 ce neporozhnya vnutrishnist W 1 displaystyle W 1 Todi U 1 x 1 displaystyle U 1 setminus x 1 neporozhnya vidkrita mnozhina v Y displaystyle Y otzhe P 2 displaystyle P 2 mozhe vibrati elementi W 2 displaystyle W 2 z W displaystyle W sho mistitsya v cij mnozhini Todi P 1 displaystyle P 1 vibiraye pidmnozhinu W 3 displaystyle W 3 z W 2 displaystyle W 2 i analogichno P 2 displaystyle P 2 mozhe vibrati element W 4 W 3 displaystyle W 4 subset W 3 sho viklyuchaye x 2 displaystyle x 2 Prodovzhuyuchi takim chinom kozhna tochka x n displaystyle x n bude viklyuchena mnozhinoyu W 2 n displaystyle W 2n tak sho peretin vsih W n displaystyle W n ne bude peretinatisya z X displaystyle X Sho j treba bulo dovesti Pripushennyah pro Y displaystyle Y ye klyuchovimi dlya dovedennya napriklad yaksho Y a b c displaystyle Y a b c nadilenij diskretnoyu topologiyeyu i W displaystyle W skladayetsya z usih nepustih pidmnozhin Y displaystyle Y to P 2 displaystyle P 2 ne maye vigrashnoyi strategiyi yaksho X a displaystyle X a po suti jogo oponent maye vigrashnu strategiyu Analogichni efekti traplyayutsya yaksho Y displaystyle Y nadilenij topologiyeyu i W Y displaystyle W Y Silnishij rezultat stosuyetsya X displaystyle X mnozhin pershogo poryadku Fakt Nehaj Y displaystyle Y topologichnij prostir W displaystyle W sim ya pidmnozhin Y displaystyle Y sho zadovolnyayut dvi vlastivosti vishe i nehaj X displaystyle X bud yaka pidmnozhina Y displaystyle Y P 2 displaystyle P 2 maye vigrashnu strategiyu todi i tilki todi yaksho X displaystyle X ye mnozhinoyu pershoyi kategoriyi Ce ne oznachaye sho P 1 displaystyle P 1 maye vigrashnu strategiyu yaksho X displaystyle X zalishkova Naspravdi P 1 displaystyle P 1 maye vigrashnu strategiyu todi i tilki todi yaksho isnuye W i W displaystyle W i in W taka sho X W i displaystyle X cap W i ye zalishkovoyu pidmnozhinoyu z W i displaystyle W i Ce mozhe buti toj vipadok koli zhoden z gravciv ne maye vigrashnoyi strategiyi koli Y displaystyle Y ye 0 1 displaystyle 0 1 i W displaystyle W skladayetsya z vidrizkiv a b displaystyle a b gri viznachena determinovana yaksho cilova mnozhina maye vlastivist Bera tobto yaksho vona vidriznyayetsya vid vidkritoyi mnozhini na mnozhinu pershoyi kategoriyi ale zvorotne tverdzhennya hibne Pripuskayuchi spravedlivist aksiomi viboru isnuyut pidmnozhini 0 1 displaystyle 0 1 dlya yakih gra Banaha Mazura ne viznachena Naspravdi bagato matematikiv zaperechuyut istinnist aksiomi viboru posilayuchis na te sho z neyi viplivayut rezultati sho superechat zdorovomu gluzdu napriklad paradoks Banaha Tarskogo Tomu deyaki z nih pripuskayut spravedlivist odnogo iz yiyi zaperechen a same yaka polyagaye v tomu sho bud yaka neskinchenna gra determinovana tobto hoch odin z gravciv maye vigrashnu strategiyu Dosi ne dovedeno superechlivosti ni aksiomi viboru ni aksiomi determinovanosti z sistemoyu aksiom Cermelo Frenkelya bez aksiomi viboru Div takozhSpisok ob yektiv nazvanih na chest Stefana BanahaLiteratura ros Kanovej V G Aksioma vybora i aksioma determinirovannosti M Fizmatgiz 1984 angl 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 angl Telgarsky R J Topological Games On the 50th Anniversary of the Banach Mazur Game 8 grudnya 2013 u Wayback Machine Rocky Mountain J Math 17 1987 pp 227 276 angl Julian P Revalski The Banach Mazur game History and recent developments 21 lipnya 2011 u Wayback Machine Seminar notes Pointe a Pitre Guadeloupe France 2003 2004