Kleeneova věta o pevném bodě - Kleene fixed-point theorem

Výpočet nejmenšího fixního bodu z F(X) = 1/10X²+opálení (X) +1 pomocí Kleeneovy věty ve skutečnosti interval [0,7] v obvyklém pořadí

V matematický oblasti objednat a teorie mřížky, Kleeneova věta o pevném bodě, pojmenovaný po americkém matematikovi Stephen Cole Kleene, uvádí následující:

Kleeneova věta o pevném bodě. Předpokládat

{ displaystyle (L, sqsubseteq)}

je řízená-úplná částečná objednávka (dcpo) s nejmenším prvkem a nechat

{ displaystyle f: L až L}

být Scott kontinuální (a proto monotónní ) funkce. Pak

{ displaystyle f}

má nejméně pevný bod, který je supremum vzestupného Kleeneova řetězce

{ displaystyle f.}

The vzestupný řetězec Kleene z F je řetěz

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

získané iterace F na nejmenší prvek ⊥ z L. Věta, vyjádřená ve vzorci, to říká

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

kde ${ displaystyle { textrm {lfp}}}$ označuje nejméně pevný bod.

Ačkoli Věta o pevném bodě Tarskiho neuvažuje o tom, jak lze pevné body vypočítat iterací F z nějakého semene (také se týká monotónní funkce na kompletní mříže ), je tento výsledek často přičítán Alfred Tarski kdo to dokazuje pro aditivní funkce ^[1] Kleeneovu teorém s pevným bodem lze navíc rozšířit na monotónní funkce pomocí transfinitních iterací.^[2]

Důkaz^[3]

Nejprve musíme ukázat, že vzestupný Kleeneův řetězec ${ displaystyle f}$ existuje v ${ displaystyle L}$ . Abychom to ukázali, dokazujeme následující:

Lemma. Li

{ displaystyle L}

je dcpo s nejméně prvkem a

{ displaystyle f: L až L}

je tedy Scott kontinuální

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

Důkaz. Používáme indukci:

Předpokládejme n = 0. Potom ${ displaystyle f ^ {0} ( bot) = bot sqsubseteq f ^ {1} ( bot),}$ od té doby ${ displaystyle bot}$ je nejmenší prvek.
Předpokládejme n> 0. Potom to musíme ukázat ${ displaystyle f ^ {n} ( bot) sqsubseteq f ^ {n + 1} ( bot)}$ . Přeskupením dostaneme ${ displaystyle f (f ^ {n-1} ( bot)) sqsubseteq f (f ^ {n} ( bot))}$ . Induktivní předpoklad to víme ${ displaystyle f ^ {n-1} ( bot) sqsubseteq f ^ {n} ( bot)}$ drží, a protože f je monotónní (vlastnost Scottových spojitých funkcí), platí také výsledek.

Jako důsledek Lemmy máme následující směrovaný ω-řetězec:

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

Z definice dcpo to vyplývá ${ displaystyle mathbb {M}}$ má supremum, říkejte tomu ${ displaystyle m.}$ Nyní zbývá jen ukázat ${ displaystyle m}$ je nejméně pevný bod.

Nejprve to ukážeme ${ displaystyle m}$ je pevný bod, tj. to ${ displaystyle f (m) = m}$ . Protože ${ displaystyle f}$ je Scott kontinuální, ${ displaystyle f ( sup ( mathbb {M})) = sup (f ( mathbb {M}))}$ , to je ${ displaystyle f (m) = sup (f ( mathbb {M}))}$ . Také od té doby ${ displaystyle mathbb {M} = f ( mathbb {M}) pohár { bot }}$ a protože ${ displaystyle bot}$ nemá žádný vliv na stanovení nadřazenosti, kterou máme: ${ displaystyle sup (f ( mathbb {M})) = sup ( mathbb {M})}$ . Z toho vyplývá, že ${ displaystyle f (m) = m}$ , tvorba ${ displaystyle m}$ pevný bod ${ displaystyle f}$ .

Důkaz toho ${ displaystyle m}$ je ve skutečnosti nejméně pevný bod lze provést ukázáním, že jakýkoli prvek v ${ displaystyle mathbb {M}}$ je menší než jakýkoli pevný bod ${ displaystyle f}$ (protože podle majetku supremum, pokud jsou všechny prvky sady ${ displaystyle D subseteq L}$ jsou menší než prvek ${ displaystyle L}$ pak také ${ displaystyle sup (D)}$ je menší než stejný prvek ${ displaystyle L}$ ). To se provádí indukcí: Předpokládejme ${ displaystyle k}$ je nějaký pevný bod ${ displaystyle f}$ . Nyní dokazujeme indukcí ${ displaystyle i}$ že ${ displaystyle forall i in mathbb {N}: f ^ {i} ( bot) sqsubseteq k}$ . Základ indukce ${ displaystyle (i = 0)}$ zjevně platí: ${ displaystyle f ^ {0} ( bot) = bot sqsubseteq k,}$ od té doby ${ displaystyle bot}$ je nejmenší prvek ${ displaystyle L}$ . Jako indukční hypotézu to můžeme předpokládat ${ displaystyle f ^ {i} ( bot) sqsubseteq k}$ . Nyní provedeme indukční krok: Z indukční hypotézy a monotónnosti ${ displaystyle f}$ (opět implikováno Scottovou kontinuitou ${ displaystyle f}$ ), můžeme uzavřít následující: ${ Displaystyle f ^ {i} ( bot) sqsubseteq k ~ implikuje ~ f ^ {i + 1} ( bot) sqsubseteq f (k).}$ Nyní, za předpokladu, že ${ displaystyle k}$ je pevný bod ${ displaystyle f,}$ víme, že ${ displaystyle f (k) = k,}$ a z toho dostaneme ${ displaystyle f ^ {i + 1} ( bot) sqsubseteq k.}$