Knaster-Tarski sætning

Den Knaster-Tarski teorem er et fast punkt sætning for en stigende anvendelse af en komplet gitter i sig selv. Det er opkaldt efter Bronislaw Knaster og Alfred Tarski .

Historie

Knaster og Tarski, to matematikervenner i Polen , foreslog den første version af sætningen i 1928. Teasterne om Knaster - Tarski kaldes også simpelthen fast punkt sætning af Tarskis sætning blev offentliggjort af Tarski i sin generelle form i 1955 I 1955, Anne C. Davis viste en slags gensidig.

Faktisk sporer moskovækerne i sin bog om sætteori, der er citeret i bibliografien, denne type fastpunktssætning til Zermelo's bevis for hans eponymiske sætning og nævner ingen anden matematiker om dette emne, sandsynligvis for at undgå Stiglers lov .

Stater

Knaster-Tarski-erklæringen er ikke den mest magtfulde af sin art Men det er relativt simpelt:

Hvis er et komplet gitter og et stigende kort, så er den ordnede delmængde af de faste punkter af et komplet (deraf ikke-tomt) gitter. $T$ ${\ displaystyle f: T \ til T}$ $f$

Især har et mindre og et større fast punkt. $f$

Demonstrationer

Den sædvanlige demonstration er ikke konstruktivt :

Lad være sættet med faste punkter af . Lad os vise, at i , hver del har en øvre grænse . Lad os derfor bemærke den nedre grænse for sættet . Så: $F$ $f$ $F$ $G$ $m$ ${\ displaystyle S: = \ {x \ i T \ mid x \ geq G \ quad {\ text {et}} \ quad f (x) \ leq x \}}$

${\ displaystyle m \ geq G}$ (fordi ); ${\ displaystyle S \ geq G}$
${\ displaystyle f (m) \ leq m}$ . Faktisk fordi for alt på den ene side (fordi ) og på den anden side ; ${\ displaystyle f (m) \ leq S}$ ${\ displaystyle x \ i S}$ ${\ displaystyle f (m) \ leq f (x)}$ ${\ displaystyle m \ leq x}$ ${\ displaystyle f (x) \ leq x}$
${\ displaystyle f (m) \ geq m}$ . Faktisk fordi (i henhold til de to foregående punkter) og ; ${\ displaystyle f (m) \ i S}$ ${\ displaystyle f (m) \ geq f (G) = G}$ ${\ displaystyle f (f (m)) \ leq f (m)}$
ethvert fast punkt, som major tilhører, minimeres derfor af . $f$ $G$ $S$ $m$

Derfor er den øvre grænse for in . $m$ $G$ $F$

Et andet bevis for en svagere sætning er som følger: vi viser ved transfinit induktion, at et fast punkt. $f$

Vi indstiller det mindste element af , så konstruerer vi en "funktion" ved transfinit rekursion som følger: hvis der er nogen ordinal ,, og hvis er en grænse ordinal , er den øvre grænse for . I henhold til valget af og væksten af , øges. Ved at vælge en ordinal, der ikke injiceres i (for eksempel dens Hartogs ordinal ), ser vi, at den ikke kan være injektionsdygtig, og derfor eksisterer den sådan, at . Ved vækst af , derfor : vi har fundet et fast punkt. ${\ displaystyle x_ {0} =}$ $T$ $x$ $\ alpha$ ${\ displaystyle x _ {\ alpha +1}: = f (x _ {\ alpha})}$ $\ alpha$ ${\ displaystyle x _ {\ alpha}}$ ${\ displaystyle \ {x _ {\ beta} \ mid \ beta <\ alpha \}}$ $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})}$

Ansøgninger

I matematik

Vi kan bevise Cantor-Bernsteins sætning ved at anvende Knaster-Tarskis: se afsnittet " Andet bevis " i artiklen om denne sætning.

I datalogi

De vigtigste anvendelsesområder er semantikken i programmeringssprog og analysen af programmet (en) ved abstrakt fortolkning eller modelkontrol , felter, der overlapper stærkt.

Noter og referencer

(in) B. Knaster, " En sætning om sæt af funktioner " , Ann. Soc. Polon. Matematik. , Vol. 6,1928, s. 133–134 Med A. Tarski.
(i) Alfred Tarski, " Et gitter-teoretisk Fixpoint sætning og dens anvendelsesmuligheder " , Pacific Journal of Mathematics , vol. 5: 2,1955, s. 285–309 ( læs online )
(i) Anne C. Davis, " En fuld karakterisering af gitter " , Pacific J. Math. , Vol. 5,1955, s. 311–319 ( DOI 10.2140 / pjm.1955.5.311 , læs online )

Bibliografi

(en) Charalambos D. Aliprantis og Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide , Springer ,2007, 3 e ed. ( læs online ) , s. 17-18
(en) Alfred Tarski , " Et gitterteoretisk fixpoint-sætning og dets anvendelser " , Pacific J. Math. , Vol. 5, nr . 21955, s. 285-309 ( læs online )
(en) Yiannis N. Moschovakis, Notes on Set Theory , Springer,1994( læs online )
B. Knaster, ” En sætning om sætets funktioner ”, Ann. Soc. Polon. Matematik. , Vol. 6,1928, s. 133-134 ( læs online ) - Knaster præsenterer resultater opnået med Tarski.