Knaster-Tarského věta

Knaster-Tarski věta je bod věta pevný pro rostoucí aplikaci jednoho úplného mřížky v sobě. Je pojmenována po Bronislawovi Knasterovi a Alfredu Tarskim .

Dějiny

Knaster a Tarski, dva matematici přátelé v Polsku , navrhl první verzi věty v roce 1928. Věty o Knaster - Tarski je také nazýván jednoduše pevný bod věta Tarski teorém byl publikován Tarski ve své obecné podobě v roce 1955 V roce 1955, Anne C. Davis projevil určitý druh vzájemnosti.

Ve skutečnosti Moschovakis ve své knize o teorii množin uvedené v bibliografii sleduje tento typ věty o pevném bodě k Zermelovu důkazu jeho stejnojmenné věty a nejmenuje žádného jiného matematika na toto téma, pravděpodobně proto, aby se vyhnul Stiglerovu zákonu .

Státy

Prohlášení Knaster-Tarski není nejmocnější svého druhu Je však relativně jednoduché:

Pokud je úplný svaz a zvyšující se mapa, pak objednal podmnožinou pevných bodů v je kompletní (tedy non-prázdný) mříž. $T$ ${\ displaystyle f: T \ až T}$ $F$

Zejména má menší a větší pevný bod. $F$

Demonstrace

Obvyklá demonstrace je není konstruktivní :

Dovolit být sada pevných bodů . Ukažme, že v každé části je horní hranice . K tomu si povšimněme spodní hranice množiny . Tak : $F$ $F$ $F$ $G$ $m$ ${\ displaystyle S: = \ {x \ v T \ mid x \ geq G \ quad {\ text {et}} \ quad f (x) \ leq x \}}$

${\ displaystyle m \ geq G}$ (protože ); ${\ displaystyle S \ geq G}$
${\ displaystyle f (m) \ leq m}$ . Ve skutečnosti proto , že pro všechno na jedné straně (protože ) a na druhé straně ; ${\ displaystyle f (m) \ leq S}$ ${\ displaystyle x \ v S}$ ${\ displaystyle f (m) \ leq f (x)}$ ${\ displaystyle m \ leq x}$ ${\ displaystyle f (x) \ leq x}$
${\ displaystyle f (m) \ geq m}$ . Ve skutečnosti proto , že (podle dvou předchozích bodů) a ; ${\ displaystyle f (m) \ v S}$ ${\ displaystyle f (m) \ geq f (G) = G}$ ${\ Displaystyle f (f (m)) \ leq f (m)}$
jakýkoli pevný bod, jehož major patří, je proto minimalizován o . $F$ $G$ $S$ $m$

Proto je horní hranice v . $m$ $G$ $F$

Druhý důkaz slabší věty je následující: dokážeme transfinitní indukcí, že pevný bod. $F$

Stanovili jsme na nejmenší prvek z , pak vytvořit „funkce“ od transfinitní rekurze tak, že pokud je nějaký pořadové ,, a pokud je mez pořadový , je horní mez . Podle výběru a růstu , roste. Výběrem ordinálu, který nevstřikuje (například Hartogsův ordinál ), vidíme, že nemůže být injektivní, a proto existuje takový . Růstem , a proto : jsme našli pevný bod. ${\ displaystyle x_ {0} =}$ $T$ $X$ $\ alfa$ ${\ displaystyle x _ {\ alpha +1}: = f (x _ {\ alpha})}$ $\ alfa$ ${\ displaystyle x _ {\ alpha}}$ ${\ displaystyle \ {x _ {\ beta} \ střední \ beta <\ alfa \}}$ $x_ {0}$ $F$ ${\ displaystyle \ alpha \ mapsto x _ {\ alpha}}$ $T$ ${\ displaystyle \ alpha \ mapsto x _ {\ alpha}}$ ${\ displaystyle \ gamma <\ beta}$ ${\ displaystyle x _ {\ gamma} = x _ {\ beta}}$ ${\ displaystyle \ alpha \ mapsto x _ {\ alpha}}$ ${\ displaystyle x _ {\ gamma} \ leq x _ {\ gamma +1} \ leq x _ {\ beta} = x _ {\ gamma}}$ ${\ displaystyle x _ {\ gamma} = x _ {\ gamma +1} = f (x _ {\ gamma})}$

Aplikace

V matematice

Cantor-Bernsteinovu větu dokážeme použitím Knaster-Tarského věty: viz § „ Druhý důkaz “ článku o této větě.

V počítačové vědě

Hlavními oblastmi použití jsou sémantika programovacích jazyků a analýza programu (en) pomocí abstraktní interpretace nebo kontroly modelu , pole, která se silně překrývají.

Poznámky a odkazy

(in) B. Knaster, „ Věta o množině funkcí “ , Ann. Soc. Polon. Matematika. , sv. 6,1928, str. 133–134 S A. Tarskim.
(in) Alfred Tarski, „ Věta o mřížkové teorii fixpointů a její aplikace “ , Pacific Journal of Mathematics , sv. 5: 2,1955, str. 285–309 ( číst online )
(in) Anne C. Davis, „ Úplná charakteristika svazů “ , Pacific J. Math. , sv. 5,1955, str. 311–319 ( DOI 10.2140 / pjm.1955.5.311 , číst online )

Bibliografie

(en) Charalambos D. Aliprantis a Kim C. Border, Nekonečná dimenzionální analýza: Stopařův průvodce , Springer ,2007, 3 e ed. ( číst online ) , s. 17-18
(en) Alfred Tarski , „ Mřížkově teoretická věta o pevném bodě a její aplikace “ , Pacific J. Math. , sv. 5, n O 21955, str. 285-309 ( číst online )
(en) Yiannis N. Moschovakis, Poznámky k teorii množin , Springer,1994( číst online )
B. Knaster, „ Věta o funkcích množin “, Ann. Soc. Polon. Matematika. , sv. 6,1928, str. 133-134 ( číst online ) - Knaster představuje výsledky získané s Tarskim.