Kleene fixpunktssats

Den här artikeln handlar om Kleenes fixpunktssats i gitterteorin. För fixpunktssatsen i beräkningsbarhetsteorin, se Kleenes rekursionssats .

Beräkning av den minsta fixpunkten för f ( x ) = 1 / 10 x ² + atan ( x )+1 med Kleenes sats i det reella intervallet [0,7] med den vanliga ordningen

Inom de matematiska områdena för ordnings- och gitterteorin säger Kleene fixpunktssats , uppkallad efter den amerikanske matematikern Stephen Cole Kleene , följande:

Kleene Fixed-Point Theorem. Antag att $(L,\sqsubseteq )$ är en riktad-komplett partiell ordning (dcpo) med ett minsta element, och låt $f:L\to L$ vara en Scott-kontinuerlig (och därför monoton ) funktion . Då har ${\displaystyle f} en$ minsta fixpunkt , vilket är det högsta av den stigande Kleene-kedjan av $f.$

Den stigande Kleene-kedjan av f är kedjan

$\bot \sqsubseteq f(\bot )\sqsubseteq f(f(\sqsubset)\q \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots$

erhålls genom att iterera f på det minsta elementet ⊥ av L . Uttryckt i en formel säger satsen att

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

där ${\textrm {lfp}}$ anger den minsta fixerade punkten.

Även om Tarskis fixpunktssats inte tar hänsyn till hur fixpunkter kan beräknas genom att iterera f från något frö (det hänför sig också till monotona funktioner på kompletta gitter ), tillskrivs detta resultat ofta Alfred Tarski som bevisar det för additiva funktioner. Dessutom, Kleene Fixed-Point Theorem kan utökas till monotona funktioner med transfinita iterationer.

Bevis

Vi måste först visa att den stigande Kleene-kedjan av $f$ finns i $L$ . För att visa det bevisar vi följande:

Lemma. Om $L$ är en dcpo med minsta element, och $f:L\to L$ är Scott-kontinuerlig, då $f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}$

Bevis. Vi använder induktion:

• Antag att n = 0. Då $f^{0}(\bot )=\bot \sqsubseteq f^{1}(\bot ),$ sedan ${ \displaystyle \bot }$ är det minsta elementet.
• Antag n > 0. Då måste vi visa att $f^{n}(\bot )\sqsubseteq f^{n+1}(\bot )$ . Genom att arrangera om får vi $f(f^{n-1}(\bot ))\sqsubseteq f(f^{n}( \bot ))$ . Genom induktivt antagande vet vi att $f^{n-1}(\bot )\sqsubseteq f^{n}(\bot )$ gäller, och eftersom f är monoton (egenskapen för Scott-kontinuerliga funktioner), resultatet gäller också.

Som en följd av Lemma har vi följande riktade ω-kedja:

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

Av definitionen av en dcpo följer att $\mathbb {M}$ har ett supremum, kalla det $m.$ Det som återstår nu är att visa att $m$ är den minsta fixpunkten.

Först visar vi att $m$ är en fast punkt, dvs att $f(m)=m$ . Eftersom $f$ är Scott-kontinuerlig , $f(\sup(\mathbb {M} ))=\sup(f(\mathbb {M} ))$ , det vill säga $f(m)=\sup(f(\mathbb {M} ))$ . Dessutom, eftersom ${\displaystyle \mathbb {M} =f(\mathbb {M} )\cup \{\bot \}} och$ eftersom $\bot$ inte har någon inflytande vid bestämning av det högsta vi har: $\sup(f(\mathbb {M} ))=\sup(\mathbb {M} )$ . Det följer att $f(m)=m$ , vilket gör $m$ till en fixpunkt för $f$ .

Beviset för att $m$ faktiskt är den minsta fixerade punkten kan göras genom att visa att vilket element som helst i $\mathbb {M}$ är mindre än någon fixpunkt i $f$ ( eftersom av egenskapen supremum , om alla element i en mängd $L}$$) {\displaystyle \sup(D)}$ är mindre än ett element i ${\displaystyle L},$ då även är mindre än samma element i $L$ ). Detta görs genom induktion: Antag att $k$ är någon fixpunkt för $f$ . Vi bevisar nu genom induktion över $i$ att $\forall i\in \mathbb {N} :f^{i}(\bot )\sqsubseteq k$ . Basen för induktionen $(i=0)$ håller uppenbarligen: $f^{0}(\bot )=\bot \sqsubseteq k,$ eftersom $\bot$ är det minsta elementet i $L$ . Som induktionshypotes kan vi anta att $f^{i}(\bot )\sqsubseteq k$ . Vi gör nu induktionssteget: Från induktionshypotesen och monotoniteten för $f$ (återigen, underförstått av Scott-kontinuiteten för $f$ ), kan vi dra följande slutsatser: ${\displaystyle f^{i}(\bot )\sqsubseteq k~\implies ~f^{i+1}(\bot )\sqsubseteq f(k).} Nu, med antagandet att k {\$ displaystyle $}$ är en fixpunkt av $f,$ vet vi att $f(k)=k,$ och från det får vi $f^{i+1}(\bot )\sqsubseteq k.$

Se även

• Andra fixpunktssatser