Кіріспе

Рет пен тор теориясының математикалық салаларында, Бронислав Кнастер мен Альфред Тарскидің есімімен аталатын Кнастер-Тарски теоремасы былай тұжырымдайды:

(L, ≤) толық тор болсын және f : L → L ≤ қатысына қатысты ретті сақтайтын (монотонды) функция болсын. Онда L-дегі f функциясының түрақты нүктелерінің жиыны ≤ бойынша толық тор құрайды. Бұл нәтижені ең жалпы түрінде Тарски тұжырымдаған, сондықтан теорема көбінесе Тарскидің түрақты нүкте теоремасы деп аталады. Кнастер мен Тарски бұрынғы уақытта L жиынның ішкі жиындарының торы, қуат жиыны торы болатын ерекше жағдай үшін бұл нәтижені дәлелдеген. Теорема бағдарламалау тілдерінің формалды семантикасында және абстрактілі интерпретацияда, сондай-ақ ойын теориясында маңызды қолданысқа ие. Анн К. Дэвис осы теореманың бір түрін дәлелдеді: Егер L торындағы f : L → L функциясының кез келген ретті сақтайтын функциясы түрақты нүктеге ие болса, онда L толық тор болады.

Собындар: ең аз және ең үлкен тұрақты нүктелер

Толық торлар бос бола алмайтындықтан (оларда бос жиынның жоғарғы және төменгі шектері болуы керек), теорема, әсіресе, f функциясының кем дегенде бір тұрақты нүктесінің, тіпті ең кіші тұрақты нүктесінің (немесе ең үлкен тұрақты нүктесінің) бар екендігіне кепілдік береді. Көптеген практикалық жағдайларда бұл теореманың ең маңызды салдары болып табылады. f функциясының ең кіші тұрақты нүктесі – f(x) = x шартын қанағаттандыратын ең кіші элемент x, немесе, балама түрінде, f(x) ≤ x шартын қанағаттандыратын элемент; ең үлкен тұрақты нүкте үшін де осыған ұқсас қатынас қолданылады, яғни f(x) = x шартын қанағаттандыратын ең үлкен элемент x. Егер f(lim xn) = lim f(xn) барлық өрлеуші xn тізбектері үшін орындалса, онда f функциясының ең кіші тұрақты нүктесі lim f n(0) болады, мұнда 0 – L тордың ең кіші элементі, бұл теореманың «құрылымдық» нұсқасын береді. (Қараңыз: Клиненің тұрақты нүкте теоремасы.) Жалпы алғанда, егер f монотонды болса, онда f функциясының ең кіші тұрақты нүктесі f α(0) стационарлық шегі болып табылады, мұнда α ординалдар бойынша өтеді, ал f α трансфиниттік индукция арқылы анықталады: f α+1 = f(f α) және f γ, егер γ шекті ординал болса, онда γ-дан кіші барлық β ординалдары үшін f β-ның жоғарғы шегі болады. Ең үлкен тұрақты нүкте үшін де осыған ұқсас теорема орындалады. Мысалы, теориялық информатикада монотонды функциялардың ең кіші тұрақты нүктелері бағдарламалардың семантикасын анықтау үшін қолданылады, мысалы қараңыз. Көбінесе теореманың арнайы түрі қолданылады, онда L – белгілі бір жиынның барлық ішкі жиындарының торы, жиынның ішкі жиынға кіру ретімен реттелген. Бұл көптеген қолданыстарда осындай торлар ғана қарастырылатынын көрсетеді. Одан кейін әдетте f функциясының тұрақты нүктесі болатын ең кіші жиын ізделеді. Абстрактілі түсіндіру Кнастер-Тарски теоремасын және ең кіші және ең үлкен тұрақты нүктелерді анықтайтын формулаларды кеңінен пайдаланады. Кнастер-Тарски теоремасын Кантор-Бернштейн-Шредер теоремасын қарапайым түрде дәлелдеу үшін қолдануға болады.

Теореманың әлсіз нұсқалары

Кнастер-Тарски теоремасының әлсіз нұсқаларын реттелген жиындықтар үшін тұжырымдауға болады, бірақ оларға күрделі шарттар кіреді. Мысалы:

L – ең кіші элементі (төменгі шегі) бар ішінара реттелген жиындық болсын, ал f : L → L – монотонды функция болсын. Сонымен қатар, L жиынтығында f(u) ≤ u шартын қанағаттандыратын u элементі бар екенін және кіші жиынтықтағы кез келген тізбектің жоғарғы шегі болатынын қарастырайық. Онда f функциясы ең кіші бекітілген нүктеге ие болады. Бұл инвариантты жиындықтарға қатысты түрлі теоремаларды алуға қолданылады, мысалы, Ок теоремасы:

X жиынтығының (жабық) бос емес кіші жиындықтары отбасы үшін монотонды F : P(X) → P(X) бейнесі үшін келесі шарттар эквивалентті: (o) F, P(X) жиынтығында A-ны қанағаттандырады, (i) F, P(X) жиынтығында A инвариантты жиынтығын қанағаттандырады, яғни, (ii) F, A максималды инвариантты жиынтығын қанағаттандырады, (iii) F, A ең үлкен инвариантты жиынтығын қанағаттандырады. Атап айтқанда, Кнастер-Тарски принципін қолдану арқылы қысқартусыз үздіксіз (көпмәнді) итерациялық функциялар жүйелері үшін жаһандық тартымдылық теориясын дамытуға болады. Әлсіз қысқарушы итерациялық функциялар жүйелері үшін Канторович теоремасы (Тарски-Канторовичтің бекітілген нүкте принципі деп те аталады) жеткілікті. Реттелген жиындықтарға арналған бекітілген нүкте принциптерінің басқа да қолданыстары дифференциалдық, интегралдық және операторлық теңдеулер теориясынан туындайды.

Ойын теориясының қолданылуы

Тарскидің тұрақты нүкте теоремасы супермодульдік ойындарға қолданылады. Супермодульдік ойын (стратегиялық толықтырулар ойыны деп те аталады) – әр ойыншының пайда функциясы өспелі айырмашылықтарға ие болғандықтан, ойыншының ең жақсы жауабы басқа ойыншылардың стратегияларының әлсіз өсу функциясы болып табылады. Мысалы, екі фирма арасындағы бәсекелестік ойынын қарастырайық. Әр фирма зерттеуге жұмсалатын қаржы мөлшерін анықтауы керек. Жалпы алғанда, егер бір фирма зерттеуге көбірек қаржы жұмсаса, екінші фирманың ең жақсы жауабы да зерттеуге көбірек қаржы жұмсау болады. Курно бәсекелестігі, Бертрад бәсекелестігі және Инвестициялық ойындар сияқты көптеген таралған ойындарды супермодульдік ойындар ретінде модельдеуге болады. Ең жақсы жауап функциялары монотонды болғандықтан, Тарскидің тұрақты нүкте теоремасын супермодульдік ойында таза стратегиялық Нэш тепе-теңдігінің (PNE) бар екенін дәлелдеу үшін қолдануға болады. Сонымен қатар, Топкис супермодульдік ойынның PNE жиынтығы толық тор екенін көрсетті, сондықтан ойында "ең кіші" PNE және "ең үлкен" PNE бар. Эшеник супермодульдік ойындағы барлық PNE-ді табуға арналған алгоритм ұсынады. Оның алгоритмі ең алдымен ең кіші және ең үлкен PNE-ді табу үшін ең жақсы жауап тізбектерін пайдаланады; содан кейін ол кейбір стратегияларды жояды және барлық PNE табылғанға дейін қайталайды. Оның алгоритмі ең нашар жағдайда экспоненциалды, бірақ практикада жылдам жұмыс істейді. Денг, Ци және Йе ойынмен байланысты ретті сақтау бейнесінің Тарскидің тұрақты нүктесін тауып, PNE-ді тиімді есептеуге болатынын көрсетеді.