Борельді анықтау теоремасы - Borel determinacy theorem

Жылы сипаттамалық жиынтық теориясы, Борельді анықтау теоремасы төлемдер жиынтығы кез-келген Гейл-Стюарт ойыны болатындығын айтады Борел қойды болып табылады анықталды, яғни екі ойыншының біреуі жеңіске жетеді стратегия ойын үшін.

Теорема дәлелденді Дональд Мартин 1975 ж. және сипаттамада қолданылады жиынтық теориясы Борелдің кіргенін көрсету Поляк кеңістігі сияқты жүйелілік қасиеттеріне ие тамаша жиынтық қасиеті және Байердің мүлкі.

Теорема сонымен бірге белгілі метаматематикалық қасиеттері. 1971 жылы, теорема дәлелденгенге дейін, Харви Фридман теореманың кез-келген дәлелі екенін көрсетті Цермело-Фраенкель жиынтығы теориясы пайдалану керек ауыстыру аксиомасы. Кейінгі нәтижелер көрсеткендей, Зермело-Фраенкель жиынтығы теориясында детерминация теоремаларын салыстырмалы түрде дәлелдеу мүмкін емес тұрақты онымен, егер белгілі болса үлкен кардиналдар сәйкес келеді.

Фон

Гейл-Стюарт ойындары

A Гейл – Стюарт ойын - бұл екі ойыншыдан тұратын тамаша ақпарат. Ойын жиынтықтың көмегімен анықталады A, және белгіленеді GA. Екі ойыншы кезек-кезек ауысады және әр ойыншы келесі жүрісті жасамас бұрын барлық жүрістер туралы біледі. Әр айналымда әр ойыншы -ның жеке элементін таңдайды A ойнау. Бір элементті бірнеше рет шектеусіз таңдауға болады. Ойынды жоғарыда I ойыншының, ал төменде II ойыншының қимылдарымен жүрістер солдан оңға қарай жүретін келесі сызба арқылы бейнелеуге болады.

Ойын шексіз жалғасады, сонда ойынның жалғыз ойыны шексіз реттілікті анықтайды элементтері A. Барлық осындай тізбектердің жиынтығы белгіленеді Aω. Ойыншылар ойын басталғаннан бастап, тұрақты екенін біледі төлемдер жиынтығы (а.к.а.) ұтыс жиынтығы) бұл кім жеңетінін анықтайды. Төлем жиынтығы - а ішкі жиын туралы Aω. Егер ойын пьесасы арқылы жасалған шексіз дәйектілік төлемдер жиынтығында болса, онда I ойыншы жеңеді. Әйтпесе, II ойыншы жеңеді; байланыстар жоқ.

Бұл анықтамада бастапқыда шахмат сияқты дәстүрлі жетілдірілген ақпараттық ойындар жоқ сияқты, өйткені мұндай ойындардағы қозғалыстар жиынтығы әр айналым сайын өзгеріп отырады. Алайда, мұндай жағдайды заңсыз қадам жасаған ойыншы бірден жеңіледі деп жариялау арқылы шешуге болады, осылайша Гейл-Стюарт ойын ұғымы шын мәнінде ойын анықтайтын ойын тұжырымдамасын жалпылайды. ойын ағашы.

Жеңіске жету стратегиялары

A жеңіске жету стратегиясы ойыншы үшін ойыншы кез-келген позициядан қандай қадам жасау керектігін айтатын функция, егер ойыншы осы функцияны орындаса, ол міндетті түрде жеңіске жетеді. Нақтырақ айтсақ, I ойыншы үшін жеңіске жету стратегиясы - бұл функция f жұп ұзындықтағы А элементтерінің тізбегін қабылдайды және элементін қайтарады A, мен ойыншының барлық формаларын ұтып аламын

II ойыншы үшін жеңіске жететін стратегия - бұл функция ж элементтерінің тақ ұзындықтағы тізбегін алады A және элементтерін қайтарады A, сондықтан II ойыншы форманың кез-келген ойынында жеңіске жетеді

Ең көп дегенде бір ойыншының жеңу стратегиясы болуы мүмкін; егер екі ойыншының да жеңу стратегиясы болса және бір-біріне қарсы ойнаған болса, онда екі стратегияның біреуі ғана осы ойын ойынын жеңе алады. Егер ойыншылардың бірінде белгілі бір төлем жиынтығында жеңіске жету стратегиясы болса, онда бұл төлем жиынтығы деп аталады анықталды.

Топология

Берілген жиынтық үшін A, ішінара ма Aω оның топологиялық құрылымына байланысты белгілі бір дәрежеде анықталады. Гейл-Стюарт ойындарының мақсаттары үшін жиынтық A -ге ие дискретті топология, және Aω нәтижесімен қамтамасыз етілген өнім топологиясы, қайда Aω ретінде қарастырылады шексіз топологиялық өнім туралы A өзімен бірге. Атап айтқанда, қашан A {0,1} жиынтығы, анықталған топология Aω бұл кәдімгі топология Кантор кеңістігі, және қашан A - бұл натурал сандардың жиынтығы, бұл қарапайым топология Баре кеңістігі.

Жинақ Aω белгілі бір жолдың жиынтығы ретінде қарастырылуы мүмкін ағаш, бұл оның топологиясының екінші сипаттамасына әкеледі. Ағаш элементтердің барлық ақырлы тізбектерінен тұрады A, және the ағаштың белгілі бір түйінінің балалары σ бір элементке кеңейтетін тізбектер. Осылайша, егер A = {0, 1}, ағаштың бірінші деңгейі ⟨0⟩ және ⟨1⟩ тізбектерінен тұрады; екінші деңгей sequ 0, 0⟩, ⟨0, 1⟩, ⟨1, 0⟩, ⟨1, 1 four төрт тізбектен тұрады; және тағы басқа. Ағаштағы соңғы тізбектердің әрқайсысы үшін, барлық элементтерінің жиынтығы Aω σ -дан басталатын а негізгі ашық жиынтық топологияда A. The ашық жиынтықтар туралы Aω дәл осы жиынтықтардың жиынтығы болып табылатын жиынтықтар. The жабық жиынтықтар, әдеттегідей, толықтыру ашық адамдар.

The Борел жиынтығы туралы Aω ішкі топтардың ең кіші класы болып табылады Aω ол ашық жиынтықтарды қамтиды және комплемент пен есептік одақ аясында жабылады. Яғни, Borel жиынтығы ең кішкентай σ-алгебра ішкі жиындарының Aω барлық ашық жиынтықтардан тұрады. Borel жиынтықтары жіктеледі Борел иерархиясы комплемент пен есептелетін одақтың операциялары оларды ашық жиынтықтардан шығару үшін қанша рет қажет болатындығына негізделген.

Алдыңғы нәтижелер

Гейл мен Стюарт (1953) егер төлемдер жиынтығы ашық немесе жабық ішкі жиыны Aω содан кейін Гейл-Стюарт ойыны әрдайым анықталады. Келесі жиырма жыл ішінде бұл деңгейдің сәл жоғары деңгейіне дейін кеңейтілді Борел иерархиясы біршама күрделі дәлелдер арқылы. Бұл ойын төлемі а болған кезде анықталуы керек пе деген сұраққа әкелді Borel ішкі жиыны туралы Aω. Пайдаланып, белгілі болды таңдау аксиомасы, {0,1} ішкі жиынын құруға боладыω бұл анықталмаған (Kechris 1995, 139-бет).

Харви Фридман (1971) Кантор кеңістігінің барлық Borel ішкі жиынтықтарының кез-келген дәлелі екенін дәлелдеді ({0,1})ω ) қайта қолдануды талап ететіні анықталды ауыстыру аксиомасы, аксиома, әдетте Кантор кеңістігі сияқты «кішкентай» нысандар туралы теоремаларды дәлелдеу үшін қажет емес.

Borel детерминациясы

Дональд Мартин (1975) кез-келген жиынтық үшін дәлелдеді A, барлық Borel ішкі жиындары Aω анықталды. Бастапқы дәлелдеу өте күрделі болғандықтан, Мартин 1982 жылы қысқаша дәлелдеме жариялады, ол сонша техникалық машинаны қажет етпейді. Мартиннің қағазына шолу жасау кезінде Дрейк екінші дәлелді «таңқаларлықтай қарапайым» деп сипаттайды.

Өрісі сипаттамалық жиынтық теориясы қасиеттерін зерттейді Поляк кеңістігі (мәні бойынша, бөлінетін метрикалық кеңістіктер). Borel детерминациясы теоремасы осы кеңістіктердің Borel ішкі жиындарының көптеген қасиеттерін анықтау үшін қолданылды. Мысалы, поля кеңістігінің барлық Borel ішкі жиынтықтарында тамаша жиынтық қасиеті және Байердің мүлкі.

Теоретикалық аспектілер

Borel анықтау теоремасы оны қызықтырады метаметематикалық сипаттамалық жиынтық теориясындағы қасиеттері, сондай-ақ оның салдары.

Жабық жиынтықтарын анықтау Aω ерікті үшін A дегенге тең таңдау аксиомасы аяқталды ZF (Кечрис 1995, 139 бет). Таңдау аксиомасы қабылданбаған теориялық жүйелерде жұмыс істеген кезде оны жалпыланған стратегияларды ескере отырып айналып өтуге болады. квазистратегиялар (Kechris 1995, 139-бет) немесе тек мұндағы ойындарды қарастыру арқылы A сияқты натурал сандардың жиынтығы детерминация аксиомасы.

Зермело жиынтығы теориясы (Z) болып табылады Цермело-Фраенкель жиынтығы теориясы ауыстыру аксиомасынсыз. Оның ZF-тен айырмашылығы, Z-тің дәлелдемеуі қуат орнатылды операцияны ерікті жиыннан басталатын сансыз қайталауға болады. Соның ішінде, Vω + ω, нақты деңгейінің кумулятивті иерархия, Зермело жиынтығы теориясының моделі болып табылады. Ауыстыру аксиомасы, екінші жағынан, қанағаттандырылады Vκ larger мәнінің едәуір үлкен мәндері үшін, мысалы, a а болған кезде қол жетімді емес кардинал. Фридманның 1971 жылғы теоремасы Зермело жиынтық теориясының (таңдау аксиомасымен) моделі бар екенін көрсетті, онда Борель детерминациясы сәтсіздікке ұшырайды, осылайша Зермело жиын теориясы Борель детерминациясы теоремасын дәлелдей алмайды.

Анықтаудың күшті түрлері

Анықтама туралы Borel детерминациясына қарағанда күшті бірнеше теоретикалық принциптер сипаттамалық жиынтық теориясында зерттелген. Олар тығыз байланысты үлкен кардиологиялық аксиомалар.

The проективті детерминация аксиомасы барлығын білдіреді проективті поляк кеңістігінің ішкі жиынтықтары анықталды. ZFC-де дәлелденбейтіні белгілі, бірақ онымен салыстырмалы түрде сәйкес келеді және белгілі біреулер айтады үлкен кардинал аксиомалар. А-ның болуы өлшенетін кардинал бәрін ZFC арқылы білдіруге жеткілікті аналитикалық ішкі жиындар поляк кеңістігі анықталды.

The детерминация аксиомасы барлық поляк кеңістігінің барлық жиынтықтары анықталғанын айтады. Бұл ZFC-ге сәйкес келмейді, бірақ ZF + DC (Zermelo-Fraenkel жиынтығы теориясы плюс тәуелді таңдау аксиомасы ) ол белгілі бір үлкен кардиналды аксиомалармен сәйкес келеді.

Әдебиеттер тізімі

  • Фридман, Харви (1971). «Жоғары жиынтық теориясы және математикалық практика». Математикалық логиканың жылнамалары. 2 (3): 325–357. дои:10.1016/0003-4843(71)90018-0.
  • Гейл, Д. және Ф.М. Стюарт (1953). «Мінсіз ақпараты бар шексіз ойындар». Ойындар теориясына қосқан үлестері, т. 2018-04-21 121 2. Математикалық зерттеулер жылнамасы, т. 28. 28. Принстон университетінің баспасы. 245–266 бет.
  • Александр Кечрис (1995). Классикалық сипаттама жиынтығы теориясы. Математика бойынша магистратура мәтіндері. 156. ISBN  0-387-94374-9.
  • Мартин, Дональд А. (1975). «Borel детерминациясы». Математика жылнамалары. Екінші серия. 102 (2): 363–371. дои:10.2307/1971035.
  • Мартин, Дональд А. (1982). «Borel детерминациясының таза индуктивті дәлелі». Рекурсия теориясы. Proc. Симпозиумдар. Таза математика (Нью-Йорктегі Итака қаласында өткен AMS – ASL жазғы институтының еңбектері). 303–308 бет.

Сыртқы сілтемелер