Dokončete částečnou objednávku - Complete partial order

v matematika, fráze kompletní částečná objednávka se různě používá k označení nejméně tří podobných, ale odlišných tříd třídy částečně objednané sady, vyznačující se zejména vlastnosti úplnosti. Kompletní dílčí objednávky hrají ústřední roli v teoretická informatika: v denotační sémantika a teorie domény.

Definice

A kompletní částečná objednávka zkráceně CPO může v závislosti na kontextu odkazovat na některý z následujících konceptů.

• Částečně objednaná sada je a řízená-úplná částečná objednávka (dcpo) pokud každý z jeho řízené podmnožiny má supremum. Podmnožina částečného pořadí je směrována, pokud není prázdná a každá dvojice prvků má v podmnožině horní mez. V literatuře se dcpos někdy také objevují pod štítkem up-kompletní poset.

• Částečně objednaná sada je a špičatý zaměřený - kompletní částečná objednávka pokud je to dcpo s nejmenším prvkem. Někdy jsou zkráceny cppos.

• Částečně objednaná sada je a ω - kompletní částečná objednávka (ω-cpo) pokud se jedná o poset, ve kterém každý ω-řetězec (X₁≤X₂≤X₃≤X₄≤ ...) má supremum, které patří do základní množiny posetu. Každé dcpo je ω-cpo, protože každý ω-řetězec je směrovaná množina, ale obrácení není pravda. Avšak každý ω-cpo s a základ je také dcpo (se stejným základem).^[1] Ω-cpo (dcpo) se základnou se také nazývá a kontinuální ω-cpo (kontinuální dcpo).

Všimněte si, že kompletní částečná objednávka se nikdy nepoužívá jako poset, ve kterém Všechno podmnožiny mají suprema; terminologie úplná mříž se používá pro tento koncept.

Požadavek na existenci směrovaného suprema může být motivován prohlížením řízených množin jako generalizovaných aproximačních sekvencí a suprema jako limity příslušných (přibližných) výpočtů. Tato intuice byla v kontextu denotační sémantiky motivací pro vývoj teorie domény.

The dvojí pojem řízené úplné posety se nazývá a filtrováno úplné částečné pořadí. Tento koncept se však v praxi vyskytuje mnohem méně často, protože na duálním řádu lze obvykle pracovat explicitně.

Příklady

• Každý konečný poset je nasměrován kompletní.
• Všechno kompletní mříže jsou také směrovány kompletní.
• Pro jakoukoli posetu sadu všech neprázdný filtry, seřazené podle zařazení podmnožiny, je dcpo. Spolu s prázdným filtrem je také špičatý. Pokud má objednávka binární splňuje, pak tato konstrukce (včetně prázdného filtru) ve skutečnosti dává a úplná mříž.
• Sada všech dílčí funkce na nějaké dané sadě S lze objednat definováním F ≤ G pro funkce F a G kdyby a jen kdyby G rozšiřuje F, tj. pokud doména F je podmnožinou domény G a hodnoty F a G dohodnout se na všech vstupech, pro které jsou obě funkce definovány. (Ekvivalentně, F ≤ G kdyby a jen kdyby F ⊆ G kde F a G jsou identifikováni s jejich příslušnými grafy.) Toto pořadí je špičaté dcpo, kde nejmenším prvkem je funkce nikde definovaná (s prázdnou doménou). Ve skutečnosti je také ≤ ohraničený kompletní. Tento příklad také ukazuje, proč není vždy přirozené mít největší prvek.
• The specializační objednávka ze všech střízlivý prostor je dcpo.
• Pojďme použít výraz „deduktivní systém „Jako soubor vět uzavřených následkem (pro definici pojmu důsledek použijeme např. Alfred Tarski algebraický přístup^[2][3]). Existují zajímavé věty, které se týkají množiny deduktivních systémů, které jsou částečným uspořádáním řízeným a úplným.^[4] Lze také zvolit sadu deduktivních systémů, která bude mít přirozeně nejméně prvku (aby to mohlo být také špičaté dcpo), protože množina všech důsledků prázdné množiny (tj. „Množina logicky prokazatelné / logically valid vety ”) je (1) deduktivní systém (2) obsažený ve všech deduktivních systémech.

Vlastnosti

Objednaná sada P je špičaté dcpo právě tehdy, když každý řetěz má nadřazenost P, tj., P je řetěz kompletní.^[5] Případně objednanou sadu P je špičaté dcpo právě tehdy, když každý zachování objednávek vlastní mapa P má nejméně fixní bod. Každá sada S lze přeměnit na špičaté dcpo přidáním prvku s nejmenším ⊥ a zavedením plochého řádu s ⊥ ≤s a s ≤s pro každého s ∈ S a žádné další řádové vztahy.

Spojité funkce a pevné body

Funkce F mezi dvěma dcpos P a Q je nazýván (Scott) kontinuální pokud mapuje směrované množiny na směrované množiny při zachování jejich suprema:

• ${ displaystyle f (D) subseteq Q}$ je určen pro každého nasměrovaného ${ displaystyle D subseteq P}$.
• ${ displaystyle f ( sup D) = sup f (D)}$ za každého nasměrovaného ${ displaystyle D subseteq P}$.

Všimněte si, že každá spojitá funkce mezi dcpos je a monotónní funkce. Tento pojem kontinuity je ekvivalentní topologické kontinuitě vyvolané Scottova topologie.

Sada všech spojitých funkcí mezi dvěma dcpos P a Q je označeno [P → Q]. Vybaveno bodovým řádem, jedná se opět o DCPO a CPO kdykoli Q je cpo. Kompletní dílčí objednávky se Scottovými spojitými mapami tedy tvoří a kartézská uzavřená kategorie.^[6]

Každá vlastní mapa zachovávající objednávku F CPO (P, ⊥) má nejméně pevný bod.^[7] Li F je spojitý, pak se tento pevný bod rovná supremu iteruje (⊥, F(⊥), F(F(⊥)), … Fⁿ(⊥),…) z ⊥ (viz také Kleeneova věta o pevném bodě ).

Viz také

Řízená úplnost souvisí různými způsoby s jinými úplnost pojmy jako úplnost řetězce. Samotná řízená úplnost je docela základní vlastnost, která se často vyskytuje v jiných vyšetřováních teoretického řádu, například pomocí algebraické posety a Scottova topologie.

Poznámky

Reference

• Davey, B. A.; Priestley, H. A. (2002). Úvod do mřížek a řádu (Druhé vydání.). Cambridge University Press. ISBN  0-521-78451-4.