Клейн тұрақты нүктелі теорема - Kleene fixed-point theorem

Ең аз нүктесін есептеу f(х) = 1/10х²+атан (х) +1 Клейн теоремасын нақты қолдана отырып аралық [0,7] әдеттегі тапсырыспен

Ішінде математикалық аудандары тапсырыс және тор теориясы, Клейн тұрақты нүктелі теорема, американдық математиктің есімімен аталады Стивен Коул Клейн, келесілерді айтады:

Клейн тұрақты нүктелі теорема. Айталық

{ displaystyle (L, sqsubseteq)}

Бұл бағытталған-толық жартылай тапсырыс (dcpo) ең аз элементі бар және жіберейік

{ displaystyle f: L бастап L}

болуы а Скотт үздіксіз (және сондықтан монотонды ) функциясы. Содан кейін

{ displaystyle f}

бар ең аз нүкте, бұл супремум көтеріліп келе жатқан Клейн тізбегінің

{ displaystyle f.}

The өсіп келе жатқан Kleene тізбегі туралы f болып табылады шынжыр

{ displaystyle bot sqsubseteq f ( bot) sqsubseteq f (f ( bot)) sqsubseteq cdots sqsubseteq f ^ {n} ( bot) sqsubseteq cdots}

алынған қайталау f үстінде ең аз элемент ⊥ туралы L. Формулада көрсетілген теорема бұл туралы айтады

{ displaystyle { textrm {lfp}} (f) = sup left ( left {f ^ {n} ( bot) mid n in mathbb {N} right } right)}

қайда ${ displaystyle { textrm {lfp}}}$ ең аз бекітілген нүктені білдіреді.

Дегенмен Тарскийдің бекітілген нүктелік теоремасы қайталану арқылы тіркелген нүктелерді қалай есептеуге болатындығын қарастырмайды f кейбір тұқымдардан (сонымен қатар, ол жатады) монотонды функциялар қосулы толық торлар ), бұл нәтиже көбіне байланысты болады Альфред Тарски оны аддитивті функциялар үшін кім дәлелдейді ^[1] Сонымен қатар, Kleene тұрақты нүктелі теоремасын кеңейтуге болады монотонды функциялар трансфиниттік қайталануларды қолдану.^[2]

Дәлел^[3]

Алдымен біз Клейннің көтеріліп жатқан тізбегін көрсетуіміз керек ${ displaystyle f}$ бар ${ displaystyle L}$ . Мұны көрсету үшін біз келесіні дәлелдейміз:

Лемма. Егер

{ displaystyle L}

ең аз элементі бар dcpo, және

{ displaystyle f: L бастап L}

Скотт үздіксіз

{ displaystyle f ^ {n} ( bot) sqsubseteq f ^ {n + 1} ( bot), n in mathbb {N} _ {0}}

Дәлел. Біз индукцияны қолданамыз:

N = 0 деп қабылдаңыз. Сонда ${ displaystyle f ^ {0} ( bot) = bot sqsubseteq f ^ {1} ( bot),}$ бері ${ displaystyle bot}$ ең кіші элемент.
N> 0 деп қабылдаңыз. Сонда біз мұны көрсетуіміз керек ${ displaystyle f ^ {n} ( bot) sqsubseteq f ^ {n + 1} ( bot)}$ . Қайта құру арқылы біз аламыз ${ displaystyle f (f ^ {n-1} ( bot)) sqsubseteq f (f ^ {n} ( bot))}$ . Индуктивті болжам бойынша біз мұны білеміз ${ displaystyle f ^ {n-1} ( bot) sqsubseteq f ^ {n} ( bot)}$ ұстайды, ал f - монотонды (Скоттың үздіксіз функциясының қасиеті) болғандықтан, нәтиже де сақталады.

Лемманың қорытындысы ретінде бізде келесі бағытталған ω-тізбек бар:

{ displaystyle mathbb {M} = { bot, f ( bot), f (f ( bot)), ldots }.}

Dcpo анықтамасынан мыналар шығады ${ displaystyle mathbb {M}}$ супремумы бар, оны шақырыңыз ${ displaystyle m.}$ Енді оны көрсету ғана қалады ${ displaystyle m}$ ең аз нүкте.

Біріншіден, біз мұны көрсетеміз ${ displaystyle m}$ тұрақты нүкте болып табылады, яғни ${ displaystyle f (m) = m}$ . Себебі ${ displaystyle f}$ болып табылады Скотт үздіксіз, ${ displaystyle f ( sup ( mathbb {M})) = sup (f ( mathbb {M}))}$ , Бұл ${ displaystyle f (m) = sup (f ( mathbb {M}))}$ . Сонымен қатар, бері ${ displaystyle mathbb {M} = f ( mathbb {M}) cup { bot }}$ және себебі ${ displaystyle bot}$ бізде бар супремумды анықтауға әсер етпейді: ${ displaystyle sup (f ( mathbb {M})) = sup ( mathbb {M})}$ . Бұдан шығатыны ${ displaystyle f (m) = m}$ , жасау ${ displaystyle m}$ нүктесі ${ displaystyle f}$ .

Оның дәлелі ${ displaystyle m}$ шын мәнінде ең аз тіркелген нүктені кез-келген элемент екенін көрсету арқылы жасауға болады ${ displaystyle mathbb {M}}$ нүктесінің кез-келген нүктесінен кіші ${ displaystyle f}$ (өйткені меншігі бойынша супремум, егер жиынның барлық элементтері ${ displaystyle D subseteq L}$ элементінен кіші ${ displaystyle L}$ содан кейін ${ displaystyle sup (D)}$ сол элементтен кіші ${ displaystyle L}$ ). Бұл индукция арқылы жасалады: Айталық ${ displaystyle k}$ болып табылады ${ displaystyle f}$ . Біз қазір индукция арқылы дәлелдейміз ${ displaystyle i}$ бұл ${ displaystyle forall i in mathbb {N}: f ^ {i} ( bot) sqsubseteq k}$ . Индукцияның негізі ${ displaystyle (i = 0)}$ анық: ${ displaystyle f ^ {0} ( bot) = bot sqsubseteq k,}$ бері ${ displaystyle bot}$ болып табылады ${ displaystyle L}$ . Индукциялық гипотеза ретінде біз бұл туралы ойлауымыз мүмкін ${ displaystyle f ^ {i} ( bot) sqsubseteq k}$ . Біз қазір индукция қадамын жасаймыз: индукциялық гипотезадан және монотондылығынан ${ displaystyle f}$ (тағы да, Скотттың сабақтастығы көздейді ${ displaystyle f}$ ), біз келесідей қорытынды жасай аламыз: ${ displaystyle f ^ {i} ( bot) sqsubseteq k ~ білдіреді ~ f ^ {i + 1} ( bot) sqsubseteq f (k).}$ Енді, бұл болжам бойынша ${ displaystyle k}$ нүктесі болып табылады ${ displaystyle f,}$ біз мұны білеміз ${ displaystyle f (k) = k,}$ және біз одан аламыз ${ displaystyle f ^ {i + 1} ( bot) sqsubseteq k.}$