Twierdzenie Knastera-Tarskiego

W matematycznych obszarach porządku i teorii sieci twierdzenie Knastera -Tarskiego , nazwane na cześć Bronisława Knastera i Alfreda Tarskiego , stwierdza, co następuje:

Niech ( L , ≤) będzie kompletną kratą i niech f : L → L będzie funkcją monotoniczną (wrt ≤ ). Wtedy zbiór stałych punktów f w L również tworzy kompletną kratę pod ≤ .

To Tarski przedstawił wynik w jego najbardziej ogólnej postaci, dlatego twierdzenie to jest często znane jako twierdzenie Tarskiego o punkcie stałym . Jakiś czas wcześniej Knaster i Tarski ustalili wynik dla szczególnego przypadku, w którym L jest siatką podzbiorów zbioru, siatką potęgową .

Twierdzenie to ma ważne zastosowania w formalnej semantyce języków programowania i interpretacji abstrakcyjnej .

Swego rodzaju odwrotność tego twierdzenia udowodniła Anne C. Davis : Jeśli każda funkcja zachowująca porządek f : L → L na siatce L ma punkt stały, to L jest kratą zupełną.

Konsekwencje: najmniejszy i największy punkt stały

Ponieważ kraty kompletne nie mogą być puste (muszą zawierać supremum i infimum zbioru pustego), w szczególności twierdzenie to gwarantuje istnienie co najmniej jednego punktu stałego f , a nawet istnienie najmniejszego punktu stałego (lub największego punktu stałego ). W wielu praktycznych przypadkach jest to najważniejsza implikacja twierdzenia.

Najmniejszym stałym punktem f jest najmniejszy element x taki, że f ( x ) = x , lub równoważnie taki, że f ( x ) ≤ x ; liczba dualna dotyczy największego punktu stałego , największego elementu x takiego, że f ( x ) = x .

Jeśli f (lim x _{n )} = lim f ( x _n ) dla wszystkich ciągów rosnących x _n , to najmniejszym punktem stałym f jest lim f ⁿ (0), gdzie 0 jest najmniejszym elementem L , dając w ten sposób bardziej „konstruktywny” wersja twierdzenia. (Patrz: Kleene twierdzenie o punkcie stałym .) Mówiąc bardziej ogólnie, jeśli f jest monotoniczne, to najmniejszy punkt stały f jest stacjonarną granicą f ^α (0), przejmując α nad liczbami porządkowymi , gdzie f ^α jest definiowane przez indukcję pozaskończoną : f ^α+1 = f ( f ^α ) i f ^γ dla granicy porządkowej γ jest najmniejszą górną granicą f β ^dla wszystkich β liczby porządkowe mniejsze niż γ. Podwójne twierdzenie obowiązuje dla największego punktu stałego.

Na przykład w informatyce teoretycznej do definiowania semantyki programu używa się najmniej stałych punktów funkcji monotonicznych . Często używana jest bardziej wyspecjalizowana wersja twierdzenia, w której L jest kratą wszystkich podzbiorów pewnego zbioru uporządkowanego według włączenia podzbioru . Odzwierciedla to fakt, że w wielu zastosowaniach brane są pod uwagę tylko takie kraty. Poszukuje się wtedy zwykle najmniejszego zbioru, który ma właściwość bycia punktem stałym funkcji f . Interpretacja abstrakcyjna szeroko wykorzystuje twierdzenie Knastera-Tarskiego i wzory dające najmniejsze i największe punkty stałe.

Twierdzenie Knastera – Tarskiego można wykorzystać do prostego dowodu twierdzenia Cantora – Bernsteina – Schroedera .

Słabsze wersje twierdzenia

Słabsze wersje twierdzenia Knastera-Tarskiego można sformułować dla zbiorów uporządkowanych, ale wymagają one bardziej skomplikowanych założeń. Na przykład:

Niech L będzie zbiorem częściowo uporządkowanym z najmniejszym elementem (dół) i niech f : L → L będzie funkcją monotoniczną . Ponadto załóżmy, że istnieje u w L takie, że fa ( u ) ≤ u i że dowolny łańcuch w podzbiorze ${\ Displaystyle \ {x \ w L \ mid x\równoważnik f(x),x\równoważnik u\}}$ ma supremum. Wtedy f przyznaje najmniej stały punkt .

Można to zastosować do uzyskania różnych twierdzeń o zbiorach niezmiennych , np. Twierdzenie Ok:

Dla odwzorowania monotonicznego F : P ( X ) → P ( X ) w rodzinie (zamkniętych) niepustych podzbiorów X następujące są równoważne: (o) F dopuszcza A w P ( X ) st ${\ Displaystyle A \ subseteq F (A)}$ , (i) F dopuszcza niezmienny zestaw A w P ( X ) tj. ${\ Displaystyle A = F (A)}$ , (ii) F dopuszcza maksymalny niezmienny zbiór A, (iii) F dopuszcza największy niezmienny zbiór A.

W szczególności, korzystając z zasady Knastera-Tarskiego, można rozwinąć teorię globalnych atraktorów dla niekontraktywnych nieciągłych (wielowartościowych) iterowanych układów funkcyjnych . W przypadku słabo kurczliwych iterowanych systemów funkcyjnych wystarczy twierdzenie Kantorowicza o punkcie stałym (znane również jako zasada punktu stałego Tarskiego-Kantorowicza).

Inne zastosowania zasad punktu stałego dla zbiorów uporządkowanych wywodzą się z teorii równań różniczkowych , całkowych i operatorskich.

Dowód

Powtórzmy twierdzenie.

Dla pełnej sieci $}$ \ $\ równoważnik$ i funkcji monotonicznej L , wszystkich punktów stałych f jest również kompletną siecią ${\ Displaystyle \ langle P, \ równoważnik \ rangle}$ , gdzie:

• $_$ _ _
• ${\ Displaystyle \ bigwedge P = \ bigwedge \ {x \ w L \ mid x \ geq f (x) \}}$ jako najmniejszy punkt stały f .

Dowód. Zaczniemy od pokazania, że ​​P ma zarówno najmniejszy, jak i największy element. Niech D = { x | x ≤ f ( x )} i x ∈ D (wiemy, że co najmniej 0 _L należy do D ). Wtedy, ponieważ f jest monotoniczne, mamy f ( x ) ≤ f ( f ( x )), czyli f ( x ) ∈ D .

Niech teraz ${\ displaystyle u = \ bigvee D}$ ( u istnieje, ponieważ re ⊆ L i L to kompletna krata). Wtedy dla wszystkich x ∈ D jest prawdą, że x ≤ u i f ( x ) ≤ f ( u ), więc x ≤ f ( x ) ≤ f ( u ). Dlatego f ( u ) jest górną granicą D , ale u jest najmniejszą górną granicą, więc u ≤ f ( u ), tj. u ∈ D . Wtedy f ( u ) ∈ re (ponieważ f ( u ) ≤ f ( f ( u ))) i tak f ( u ) ≤ u z czego wynika f ( u ) = u . Ponieważ każdy punkt stały jest w D , mamy, że u jest największym punktem stałym f .

Funkcja f jest monotoniczna na podwójnej (pełnej) siatce ${\ Displaystyle \ langle L ^ {op}, \ geq \ rangle}$ . Jak właśnie wykazaliśmy, istnieje jego największy punkt mocowania. Jest to najmniejszy punkt stały L , więc P ma najmniejsze i największe elementy, to znaczy bardziej ogólnie, każda funkcja monotoniczna na pełnej sieci ma najmniejszy punkt stały i największy punkt stały.

Dla a , b w L piszemy [ a , b ] dla przedziału domkniętego o granicach aib : { x ∈ L | za ≤ x ≤ b }. Jeśli za ≤ b , to $.$ kompletną siatką _ _ $_$ _

Pozostaje do udowodnienia, że ​​P jest siatką zupełną. Niech ${\ Displaystyle 1_ {L} = \ bigvee L}$ , W ⊆ P i ${\ Displaystyle w = \ bigvee W}$ . Pokazujemy, że f ([ w , 1 _L ]) ⊆ [ w , 1 _L ]. Rzeczywiście, dla każdego x ∈ W mamy x = f ( x ) i ponieważ w jest najmniejszą górną granicą W , x ≤ f ( w ). W szczególności w ≤ fa ( w ). Wtedy z y ∈ [ w , 1 _L ] wynika, że ​​w ≤ f ( w ) ≤ f ( y ), co daje f ( y ) ∈ [ w , 1 _L ] lub po prostu f ([ w , 1 _L ]) ⊆ [ w , 1 _L ]. To pozwala nam spojrzeć na f jako funkcję na całej siatce [ w , 1 _L ]. Wtedy ma tam najmniejszy punkt stały, co daje nam najmniejszą górną granicę W . Pokazaliśmy, że dowolny podzbiór P ma supremum, to znaczy, że P jest kompletną kratą.

Zobacz też

• Rachunek modalny μ

Notatki

•   Andrzej Granas i James Dugundji (2003). Teoria punktu stałego . Springer-Verlag , Nowy Jork. ISBN 978-0-387-00173-9 .
•   Forster, T. (21.07.2003). Logika, indukcja i zbiory . ISBN 978-0-521-53361-4 .

Dalsza lektura

• S. Hayashi (1985). „Zbiory samopodobne jako punkty stałe Tarskiego” . Publikacje Instytutu Nauk Matematycznych . 21 (5): 1059–1066. doi : 10.2977/prims/1195178796 .
• J. Jachymski; L. Gajka; K. Pokarowskiego (2000). „Zasada Tarskiego-Kantorowicza i teoria iterowanych układów funkcyjnych” . Byk. Południowy. Matematyka soc . 61 (2): 247–261. doi : 10.1017/S0004972700022243 .
•   EA Ok (2004). „Teoria zbiorów stałych dla zamkniętych korespondencji z zastosowaniami do samopodobieństwa i gier”. Nieliniowy Analny . 56 (3): 309–330. CiteSeerX 10.1.1.561.4581 . doi : 10.1016/j.na.2003.08.001 .
• BSW Schröder (1999). „Algorytmy dla właściwości punktu stałego” . teoria. Oblicz. nauka . 217 (2): 301–358. doi : 10.1016/S0304-3975(98)00273-4 .
• S. Heikkila (1990). „W punktach stałych za pomocą uogólnionej metody iteracji z zastosowaniami do równań różniczkowych i całkowych obejmujących nieciągłości”. Nieliniowy Analny . 14 (5): 413–426. doi : 10.1016/0362-546X(90)90082-R .
• R. Uhla (2003). „Najmniejsze i największe stałe punkty odwzorowań rosnących quasimonotonów”. Mathematische Nachrichten . 248-249: 204-210. doi : 10.1002/mana.200310016 .

Linki zewnętrzne

• JB Nation, Uwagi na temat teorii sieci .
• Zastosowanie do elementarnego problemu kombinatoryki : Mając książkę ze 100 stronami i 100 lematami, udowodnij, że na tej samej stronie co indeks jest zapisany lemat