Věta Knaster – Tarski - Knaster–Tarski theorem - Wikipedia

V matematický oblasti objednat a teorie mřížky, Věta Knaster – Tarski, pojmenoval podle Bronisław Knaster a Alfred Tarski, uvádí následující:

Nechť L je a úplná mříž a nechme f: L → L být funkce zachování objednávky. Pak soubor z pevné body f v L je také úplná mříž.

Byl to Tarski, kdo uvedl výsledek v jeho nejobecnější podobě,^[1] a tak je věta často známá jako Věta o pevném bodě Tarskiho. O nějaký čas dříve stanovili Knaster a Tarski výsledek pro zvláštní případ, kdy L je mřížka podmnožin množiny, napájecí sada mříž.^[2]

Věta má důležité aplikace v formální sémantika programovacích jazyků a abstraktní interpretace.

Druh konverzovat této věty bylo prokázáno Anne C. Davis: Pokud každá funkce zachování objednávky funguje f: L → L na mříž L má tedy pevný bod L je úplná mříž.^[3]

Důsledky: nejmenší a největší pevné body

Protože úplné mříže nemohou být prázdný (musí obsahovat supremum prázdné množiny), věta zejména zaručuje existenci alespoň jednoho pevného bodu F, a dokonce i existence a nejméně (nebo největší) pevný bod. V mnoha praktických případech se jedná o nejdůležitější implikaci věty.

The nejméně fixní bod z F je nejmenší prvek X takhle F(X) = X, nebo ekvivalentně takový F(X) ≤ X; the dvojí platí pro největší fixpoint, největší prvek X takhle F(X) = X.

Li F(lim X_n) = lim F(X_n) pro všechny vzestupné sekvence X_n, pak nejméně fixní bod z F je lim Fⁿ(0) kde 0 je nejmenší prvek L, což dává „konstruktivnější“ verzi věty. (Vidět: Kleeneova věta o pevném bodě.) Obecněji, pokud F je monotónní, pak nejméně fixní bod z F je stacionární limit F^α(0), převzetí α přes řadové, kde F^α je definováno transfinitní indukce: F^{α + 1} = F ( F^α) a F^y pro limitní pořadové číslo γ je nejmenší horní mez z F^β pro všechny β ordinály menší než γ. Dvojitá věta platí pro největší fixní bod.

Například teoreticky počítačová věda, nejméně pevných bodů z monotónní funkce se používají k definování programová sémantika. Často se používá specializovanější verze věty, kde L se předpokládá, že je mřížkou všech podmnožiny určité sady seřazené podle zařazení podmnožiny. To odráží skutečnost, že v mnoha aplikacích se uvažuje pouze s takovými mřížemi. Jeden pak obvykle hledá nejmenší množinu, která má tu vlastnost, že je pevným bodem funkce F. Abstraktní interpretace hojně využívá Knaster-Tarskiho věty a vzorců poskytujících nejmenší a největší fixní body.

Knaster – Tarského teorém lze použít pro jednoduchý důkaz Cantor – Bernstein – Schroederova věta.^[4][5]

Slabší verze věty

Slabší verze věty Knaster – Tarski lze formulovat pro uspořádané množiny, ale zahrnují složitější předpoklady. Například:

Nechť L je a částečně objednaná sada s nejmenším prvkem (dole) a nechť f: L → L je an zachování objednávek funkce. Dále předpokládejme, že v L existuje u takové, že f (u) ≤ u a že nějaké řetěz v podmnožině {x v L: x ≤ f (x), x ≤ u} má převahu. Pak f připouští nejméně pevný bod.

To lze použít k získání různých vět o invariantní množiny, např. Okova věta:

Pro monotónní mapu F: P (X) → P (X) na rodina z (uzavřených) neprázdných podmnožin X jsou ekvivalentní: (o) F připouští A v P (X) s.t. ${ displaystyle A subseteq F (A)}$, (i) F připouští invariantní množinu A v P (X), tj. ${ displaystyle A = F (A)}$, (ii) F připouští maximální invariantní množinu A, (iii) F připouští největší invariantní množinu A.

Zejména pomocí principu Knaster-Tarski je možné vyvinout teorii globálních atraktorů pro nekontaktivní diskontinuální (vícehodnotové) iterované funkční systémy. Pro slabě kontrakční iterované funkční systémy Kantorovitchova věta o pevném bodu (známý také jako princip fixního bodu Tarski-Kantorovitch) stačí.

Další aplikace principů pevného bodu pro uspořádané množiny pocházejí z teorie diferenciálních, integrálních a operátorových rovnic.

Důkaz

Přepracujme teorém.

Pro úplnou mříž ${ displaystyle langle L, leq rangle}$ a monotónní funkce ${ displaystyle f colon L rightarrow L}$ na L, sada všech fixních bodů F je také úplná mříž ${ displaystyle langle P, leq rangle}$, s:

• ${ displaystyle bigvee P = bigvee {x v L mid x leq f (x) }}$ jako největší fixační bod F
• ${ displaystyle bigwedge P = bigwedge {x v L mid x geq f (x) }}$ jako nejméně fixní bod F.

Důkaz. Začneme tím, že to ukážeme P má nejmenší prvek i největší prvek. Nechat D = { X | X ≤ f (x) } a X ∈ D (víme to minimálně 0_L patří D). Pak proto F je monotónní máme f (x) ≤ f (f (x)), to je f (x) ∈ D.

Tak teď ${ displaystyle u = bigvee D}$ (u existuje, protože D ⊆ L a L je úplná mříž). Pak pro všechny X ∈ D je pravda, že X ≤ u a f (x) ≤ f (u), tak X ≤ f (x) ≤ f (u). Proto, f (u) je horní hranice D, ale u je nejmenší horní mez, takže u ≤ f (u), tj. u ∈ D. Pak f (u) ∈ D (protože f (u) ≤ f (f (u))) a tak dále f (u) ≤ u z toho vyplývá f (u) = u. Protože každý fixpoint je uvnitř D máme to u je největší fixpoint F.

Funkce F je monotónní na dvojité (úplné) mřížce ${ displaystyle langle L ^ {op}, geq rangle}$. Jak jsme právě dokázali, existuje jeho největší fixpoint. Je to nejméně fixní bod L, tak P má nejmenší a největší prvky, tedy obecněji, každá monotónní funkce na úplné mřížce má nejmenší fixní bod a největší fixní bod.

Li A ∈ L a b ∈ L, napíšeme [A, b] pro uzavřený interval s mezemi A a b: {x ∈ L | A ≤ x ≤ b }. Li A ≤ b, pak ${ displaystyle langle}$[A, b], ${ displaystyle leq rangle}$ je úplná mříž.

Zbývá dokázat, že P je úplná mříž. Nechat ${ displaystyle 1_ {L} = bigvee L}$, Ž ⊆ P a ${ displaystyle w = bigvee W}$. Ukážeme to F([w, 1_L]) ⊆ [w, 1_L]. Opravdu pro každého X ∈ Ž my máme X = f (x) a od té doby w je nejmenší horní mez Ž X ≤ f (w). Zejména w ≤ f (w). Pak od y ∈ [w, 1_L] z toho vyplývá w ≤ f (w) ≤ f (y)dávat f (y) ∈ [w, 1_L] nebo jednoduše F([w, 1_L]) ⊆ [w, 1_L]. To nám umožňuje podívat se na to F jako funkce na úplné mřížce [w, 1_L]. Pak tam má nejméně fixní bod, což nám dává nejmenší horní hranici Ž. Ukázali jsme, že libovolná podmnožina P má supremum, to znamená, P je úplná mříž.

Viz také

• Modální μ-kalkul

Poznámky

Reference

• Andrzej Granas a James Dugundji (2003). Teorie pevného bodu. Springer-Verlag, New York. ISBN  978-0-387-00173-9.
• Forster, T. (2003-07-21). Logika, indukce a sady. ISBN  978-0-521-53361-4.

Další čtení

• S. Hayashi (1985). „Self-similar sets as Tarski's fixed points“. Publikace Výzkumného ústavu pro matematické vědy. 21 (5): 1059–1066. doi:10,2977 / prims / 1195178796.
• J. Jachymski; L. Gajek; K. Pokarowski (2000). „Tarski-Kantorovitchův princip a teorie iterovaných funkčních systémů“. Býk. Jižní. Matematika. Soc. 61 (2): 247–261. doi:10.1017 / S0004972700022243.
• E.A. Dobře (2004). "Opravená teorie množin pro uzavřenou korespondenci s aplikacemi pro podobnost sebe sama a hry". Nelineární Anal. 56 (3): 309–330. CiteSeerX  10.1.1.561.4581. doi:10.1016 / j.na.2003.08.001.
• B.S.W. Schröder (1999). Msgstr "Algoritmy pro vlastnost pevného bodu". Teoretická. Comput. Sci. 217 (2): 301–358. doi:10.1016 / S0304-3975 (98) 00273-4.
• S. Heikkilä (1990). "Na pevných bodech prostřednictvím zobecněné iterační metody s aplikacemi na diferenciální a integrální rovnice zahrnující nespojitosti". Nelineární Anal. 14 (5): 413–426. doi:10.1016 / 0362-546X (90) 90082-R.
• R. Uhl (2003). Msgstr "Nejmenší a největší pevné body kvazimonotonu zvyšující mapování". Mathematische Nachrichten. 248–249: 204–210. doi:10.1002 / many.200310016.

externí odkazy

• J. B. Nation, Poznámky k teorii mřížky.
• Aplikace na základní kombinatorický problém: Vzhledem k tomu, že kniha má 100 stránek a 100 lemmat, prokažte, že je na stejné stránce jako její rejstřík napsáno nějaké lemma