Twierdzenie Kleene'a o punkcie stałym

Ten artykuł dotyczy twierdzenia Kleene'a o punkcie stałym w teorii sieci. Aby zapoznać się z twierdzeniem o punkcie stałym w teorii obliczalności, zobacz twierdzenie Kleene'a o rekurencji .

Obliczenie najmniejszego punktu stałego f ( x ) = 1 / 10 x ² + atan ( x )+1 przy użyciu twierdzenia Kleene'a w przedziale rzeczywistym [0,7] ze zwykłą kolejnością

W matematycznych obszarach porządku i teorii krat , twierdzenie Kleene'a o punkcie stałym , nazwane na cześć amerykańskiego matematyka Stephena Cole'a Kleene'a , stwierdza, co następuje:

Twierdzenie Kleene'a o punkcie stałym. Załóżmy , $dcpo )$ jest ukierunkowanym zupełnym porządkiem częściowym najmniejszym elementem i niech $\ Displaystyle f: L \ do$ L Funkcja ciągła Scotta (a zatem monotoniczna ) . Wtedy ma najmniej stały punkt $,$ jest supremum rosnącego łańcucha Kleene ${\ Displaystyle f.}$

Rosnący łańcuch Kleene f jest łańcuchem

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

uzyskany przez iterację f na najmniejszym elemencie ⊥ z L . Wyrażone we wzorze, twierdzenie stwierdza, że

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

gdzie ${\ displaystyle {\ textrm {lfp}}}$ oznacza najmniej stały punkt.

Chociaż twierdzenie Tarskiego o punkcie stałym nie bierze pod uwagę, w jaki sposób można obliczyć punkty stałe, iterując f z jakiegoś materiału siewnego (dotyczy to również funkcji monotonicznych na pełnych kratach ), wynik ten jest często przypisywany Alfredowi Tarskiemu , który udowadnia to dla funkcji addytywnych. Ponadto Kleene Twierdzenie o punkcie stałym można rozszerzyć na funkcje monotoniczne za pomocą iteracji pozaskończonych.

Dowód

Najpierw musimy pokazać, że rosnący $łańcuch$ istnieje $.$ Aby to pokazać, udowodnimy, co następuje:

Lemat. Jeśli ${\ Displaystyle f ^ {n} (\ bot) \ sqsubseteq f ^ {n + 1} (\ bot), n \ w \ mathbb {N} _ {0}$$dcpo$ najmniejszym elementem $,$ Scotta

Dowód. Stosujemy indukcję:

• Załóżmy n = 0. Wtedy ${\ Displaystyle f ^ {0} (\ bot) = \ bot \ sqsubseteq f ^ {1} (\ bot),}$ od ${ \displaystyle \bot }$ jest najmniejszym elementem.
• Załóżmy n > 0. Następnie musimy pokazać, że ${\ Displaystyle f ^ {n} (\ bot) \ sqsubseteq f ^ {n + 1} (\ bot)}$ . Przestawiając otrzymujemy ${\ Displaystyle f (f ^ {n-1} (\ bot)} \ sqsubseteq f (f ^ {n} ( \bot ))}$ . Wiemy to z założenia indukcyjnego ${\ Displaystyle f ^ {n-1} (\ bot) \ sqsubseteq f ^ {n} (\ bot)}$ posiada, a ponieważ f jest monotonne (własność Scotta -funkcje ciągłe), wynik również się utrzymuje.

Jako następstwo lematu mamy następujący skierowany łańcuch ω:

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

Z definicji dcpo wynika, że $​​ma$ , nazwijmy to $to$ Pozostaje teraz pokazać, że $.$ najmniejszy punkt stały

$= m$ pokazujemy, że to punkt stały, tj. że $\ displaystyle$ . fa ${\ displaystyle f}$ jest Scott-continous , $Displaystyle f (\ sup (\ mathbb {M}}) = \ sup (f (\ mathbb {M} ))}$ , czyli ${\ Displaystyle f (m) = \ sup (f (\ mathbb {M}))}$ . Ponadto, ponieważ ${\ Displaystyle \ mathbb {M} = f (\ mathbb {M}) \ kubek \ {\ bot \}}$ i ponieważ nie ma ${\ Displaystyle \ bot}$ wpływ na określenie supremum mamy: ${\ Displaystyle \ sup (f (\ mathbb {M})} = \ sup (\ mathbb {M})}$ . Wynika z tego, że jest to $stały$$(m) = m}$$Displaystyle$ , czyniąc stały .

Dowód, że w rzeczywistości jest najmniej stałym $punktem,$$można$ przeprowadzić, pokazując, że dowolny element w niż dowolny punkt stały $)$ . ponieważ przez właściwość supremum , jeśli wszystkie elementy zbioru są mniejsze niż element z ${\ Displaystyle L},$$to$ także ${\ displaystyle \ sup ($$)$ sam element . Odbywa się to przez indukcję: Załóżmy, że $}$ to jakiś stały punkt ${\ displaystyle f$ . Udowodnimy teraz przez indukcję po $tym$ , że ${\ Displaystyle \ forall i \ in \ mathbb {N}: f ^ {i} (\ bot) \$ . Podstawa indukcji ${\ Displaystyle (i = 0)}$ oczywiście obowiązuje: ${\ Displaystyle f ^ {0} (\ bot) = \ bot \ sqsubseteq k,}$ ponieważ jest ${\ Displaystyle \ bot}$ najmniejszy element . ${\ displaystyle L}$ . Jako hipotezę indukcyjną możemy przyjąć, że ${\ Displaystyle f ^ {i} (\ bot) \ sqsubseteq k}$ . Teraz robimy krok indukcyjny: od hipotezy indukcyjnej i monotoniczności ${\ displaystyle f}$ (ponownie, implikowane przez ciągłość Scotta $)$ , możemy stwierdzić, co następuje ${\ Displaystyle f ^ {i} (\ bot) \ sqsubseteq k ~ \ implikuje ~ f ^ {i + 1} (\ bot) \ sqsubseteq f (k).} Teraz, przy założeniu, że k {\$ displaystyle $}$ jest punktem stałym ${\ Displaystyle f,}$ wiemy, że ${\ Displaystyle f (k) = k,}$ i stąd otrzymujemy ${\ Displaystyle f ^ {i + 1} (\ bot) \ sqsubseteq k.}$

Zobacz też

• Inne twierdzenia o punkcie stałym