Předobjednávka - Preorder

v matematika, speciálně v teorie objednávek, a předobjednávka nebo kvaziorder je binární relace to je reflexní a tranzitivní. Předobjednávky jsou obecnější než ekvivalenční vztahy a (non-strict) dílčí objednávky, oba jsou speciální případy předobjednávky. An antisymetrický předobjednávka je částečná objednávka a symetrický předobjednávka je vztah ekvivalence.

Název předobjednávka vychází z myšlenky, že předobjednávky (které nejsou částečnými objednávkami) jsou „téměř“ (částečnými) objednávkami, ale ne tak úplně; nejsou nutně antisymetrické ani asymetrický. Vzhledem k tomu, že předobjednávka je binární relací, lze symbol ≤ použít jako notační zařízení pro relaci. Protože však nemusí být nutně antisymetrické, nemusí platit některá běžná intuice spojená se symbolem ≤. Na druhou stranu lze předobjednávku použít přímým způsobem k definování dílčího řádu a vztahu ekvivalence. To však není vždy užitečné nebo užitečné, v závislosti na studované problémové doméně.

Slovy, kdy A ≤ b, dalo by se říci, že b kryty A nebo tak A předchází bnebo tak b snižuje na A. Místo ≤ se někdy používá označení ← nebo ≲.

Každému předobjednávce odpovídá a řízený graf, s prvky množiny odpovídajícími vrcholy, a řádový vztah mezi dvojicemi prvků odpovídajících směrovaným hranám mezi vrcholy. Opak není pravdivý: většina směrovaných grafů není reflexivních ani tranzitivních. Obecně mohou příslušné grafy obsahovat cykly. Předobjednávka, která je antisymetrická, již nemá cykly; je to částečný řád a odpovídá a směrovaný acyklický graf. Předobjednávka, která je symetrická, je relací ekvivalence; lze to považovat za ztrátu směrových značek na okrajích grafu. Obecně může mít odpovídající orientovaný graf předobjednávky mnoho odpojených komponent.

Formální definice

Zvažte některé soubor P a a binární relace ≤ zapnuto P. Pak ≤ je a předobjednávkanebo kvaziorder, Pokud to je reflexní a tranzitivní; tj. pro všechny A, b a C v P, máme to:

A ≤ A (reflexivita)

-li A ≤ b a b ≤ C pak A ≤ C (tranzitivita)

Sada, která je vybavena předobjednáním, se nazývá a předobjednaná sada (nebo proset).^[1]

Pokud je předobjednávka také antisymetrický, to znamená, A ≤ b a b ≤ A naznačuje A = b, pak je to částečná objednávka.

Na druhou stranu, pokud ano symetrický, tedy pokud A ≤ b naznačuje b ≤ A, pak je to vztah ekvivalence.

Předobjednávka je celkový -li A ≤ b nebo b ≤ A pro všechny A, b.

Ekvivalentně představa předobjednané sady P lze formulovat do a kategorický rámec jako tenká kategorie; tj. jako kategorie s maximálně jedním morfismem od objektu k druhému. Tady předměty odpovídají prvkům P, a pro objekty, které spolu souvisejí, existuje jeden morfismus, jinak nula. Předobjednanou sadu lze také chápat jako obohacená kategorie, obohacený o kategorii 2 = (0 → 1).

A předobjednaná třída je třída vybaveno předobjednávkou. Každá sada je třída, takže každá předobjednaná sada je předobjednaná třída.

Příklady

• The dosažitelnost vztah v jakémkoli řízený graf (případně obsahující cykly) vede k předobjednávce, kde X ≤ y v předobjednávce právě tehdy, pokud existuje cesta z X na y v orientovaném grafu. Naopak, každá předobjednávka je vztahem dosažitelnosti směrovaného grafu (například grafu, který má hranu z X na y pro každý pár (X, y) s X ≤ y). Mnoho různých grafů však může mít stejné předobjednávky dosažitelnosti. Stejným způsobem dosažitelnost směrované acyklické grafy, směrované grafy bez cyklů, dává vzniknout částečně objednané sady (předobjednávky splňující další vlastnost antisymetrie).
• Každý konečný topologický prostor dává vzniknout předobjednávce na svých bodech definováním X ≤ y kdyby a jen kdyby X patří každému sousedství z y. Každý konečný předobjednávka může být vytvořena jako předobjednávka specializace topologického prostoru tímto způsobem. To znamená, že existuje osobní korespondence mezi konečnými topologiemi a konečnými předobjednávkami. Vztah mezi nekonečnými topologickými prostory a jejich předobjednáním specializace však není individuální.
• A síť je režie předobjednávka, to znamená, že každá dvojice prvků má horní hranice. Definice konvergence prostřednictvím sítí je důležitá v topologie, kde předobjednávky nelze nahradit částečně objednané sady bez ztráty důležitých funkcí.
• Vztah definovaný X ≤ y -li F(X) ≤ f (y), kde F je funkce do nějakého předobjednávky.
• Vztah definovaný X ≤ y pokud nějaké existují injekce z X na y. Injekce může být nahrazena surjection, nebo jakýkoli typ funkce zachovávající strukturu, například kruhový homomorfismus nebo permutace.
• The vkládání vztah pro spočetné celkový počet objednávek.
• The menší graf vztah v teorie grafů.
• A kategorie maximálně s jedním morfismus z jakéhokoli objektu X na jakýkoli jiný objekt y je předobjednávka. Takovým kategoriím se říká tenký. V tomto smyslu kategorie „zobecňují“ předobjednávky tím, že umožňují více než jeden vztah mezi objekty: každý morfismus je zřetelný (pojmenovaný) předobjednávkový vztah.

V informatice lze najít příklady následujících předobjednávek.

• Mnoho a Turingovy redukce jsou předobjednávky na třídách složitosti.
• The podtypování vztahy jsou obvykle předobjednávky.^[2]
• Předobjednávky simulace jsou předobjednávky (odtud název).
• Redukční vztahy v abstraktní přepisovací systémy.
• The předobjednávka zahrnutí na množině podmínky, definován s ≤ t Pokud dílčí termín z t je substituční instance z s.

Příklad a celková předobjednávka:

• Přednost, podle běžných modelů.

Použití

Předobjednávky hrají klíčovou roli v několika situacích:

• Každá předobjednávka může mít topologii, Alexandrovská topologie; a opravdu, každá předobjednávka na množině je v osobní korespondenci s alexandrovskou topologií na této množině.
• K definování lze použít předobjednávky vnitřní algebry.
• Předobjednávky poskytují Kripkeho sémantika pro určité typy modální logika.
• Předobjednávky se používají v nutit v teorie množin dokázat konzistence a nezávislost Výsledek.^[3]

Stavby

Každý binární vztah R na množině S lze rozšířit na předobjednávku na S pomocí přechodné uzavření a reflexní uzávěr, R.⁺⁼. Tranzitivní uzávěr označuje připojení cesty dovnitř R: X R⁺ y právě když existuje R-cesta z X do r.

Vzhledem k předobjednávce ≲ na S lze definovat vztah ekvivalence ~ na S takové, že A ~ b kdyby a jen kdyby A ≲ b a b ≲ A. (Výsledný vztah je reflexivní, protože předobjednávka je reflexivní, přechodná dvojitým použitím přechodnosti předobjednávky a podle definice symetrická.)

Pomocí tohoto vztahu je možné sestrojit částečný řád na kvocientové množině ekvivalence, S / ~, množině všech třídy ekvivalence z ~. Všimněte si, že pokud je předobjednávka R⁺⁼, S / ~ je sada R-cyklus třídy ekvivalence: X ∈ [y] kdyby a jen kdyby X = y nebo X je v R-cyklu s y. V každém případě na S / ~ můžeme definovat [X] ≤ [y] kdyby a jen kdyby X ≲ y. Konstrukcí ~ je tato definice nezávislá na vybraných zástupcích a odpovídající vztah je skutečně dobře definován. Je snadno ověřitelné, že se tak získá částečně uspořádaná sada.

Naopak, z částečného pořadí na oddíle množiny S lze sestavit předobjednávku na S. Mezi předobjednávkami a dvojicemi (rozdělení, částečné pořadí) existuje korespondence 1: 1.

Pro předobjednávku „≲“ lze definovat relaci „<“ jako A < b kdyby a jen kdyby (A ≲ b a ne b ≲ A) nebo ekvivalentně pomocí výše popsaného vztahu ekvivalence, (A ≲ b a ne A ~ b). Je to přísné částečné pořadí; každá přísná dílčí objednávka může být výsledkem takové konstrukce. Pokud je předobjednávka antisymetrická, tedy částečný řád „≤“, ekvivalence je rovnost, takže vztah „<“ lze také definovat jako A < b kdyby a jen kdyby (A ≤ b a A ≠ b).

(My ano ne definovat vztah "<" jako A < b kdyby a jen kdyby (A ≲ b a A ≠ b). Pokud by předobjednávka nebyla antisymetrická, mohlo by to způsobit problémy, protože výsledný vztah „<“ by nebyl přechodný (přemýšlejte o tom, jak se vztahují rovnocenné nerovné prvky).)

Naopak máme A ≲ b kdyby a jen kdyby A < b nebo A ~ b. To je důvod pro použití zápisu „≲“; „≤“ může být matoucí pro předobjednávku, která není antisymetrická, může to naznačovat A ≤ b to naznačuje A < b nebo A = b.

Všimněte si, že s touto konstrukcí může více předobjednávek „≲“ poskytnout stejný vztah „<“, takže bez dalších informací, například relace ekvivalence, nelze „≲“ rekonstruovat z „<“. Možné předobjednávky zahrnují následující:

• Definovat A ≤ b tak jako A < b nebo A = b (tj. vezměte reflexní uzavření vztahu). To dává částečné pořadí spojené s přísným částečným řádem „<“ prostřednictvím reflexního uzavření; v tomto případě je ekvivalence rovnost, takže nepotřebujeme notace ≲ a ~.
• Definovat A ≲ b jako „ne b < A"(tj. převezme inverzní doplněk vztahu), což odpovídá definování A ~ b jako „ani jeden A < b ani b < A"; tyto vztahy ≲ a ~ obecně nejsou přechodné; pokud jsou, ~ je ekvivalentní; v takovém případě" <"je přísný slabý řád. Výsledná předobjednávka je celkový, tj celková předobjednávka.

Vzhledem k binárnímu vztahu ${displaystyle R}$, doplněná kompozice ${displaystyle R ackslash R = {overline {R ^ {extsf {T}} circle {overline {R}}}}}$ tvoří předobjednávku zvanou zbylé zbytky,^[4] kde ${displaystyle R ^ {extsf {T}}}$ označuje konverzní vztah z ${displaystyle R}$, a ${displaystyle {overline {R}}}$ označuje doplněk vztah ${displaystyle R}$, zatímco ${displaystyle circ}$ označuje relační složení.

Počet předobjednávek

Jak je vysvětleno výše, mezi předobjednávkami a páry (rozdělení, částečné pořadí) existuje korespondence 1: 1. Počet předobjednávek je tedy součtem počtu dílčích objednávek na každém oddílu. Například:

Interval

Pro A ≲ b, interval [A, b] je množina bodů X uspokojující A ≲ X a X ≲ b, také písemné A ≲ X ≲ b. Obsahuje alespoň body A a b. Jeden se může rozhodnout rozšířit definici na všechny páry (A, b). Intervaly navíc jsou prázdné.

Pomocí odpovídajícího přísného vztahu „<“ lze také definovat interval (A, b) jako množina bodů X uspokojující A < X a X < b, také písemné A < X < b. Otevřený interval může být prázdný, i když A < b.

Taky [A, b) a (A, b] lze definovat podobně.

Viz také

• Částečná objednávka - předobjednat to je antisymetrický
• Vztah ekvivalence - předobjednat to je symetrický
• Celková předobjednávka - předobjednat to je celkový
• Celková objednávka - předobjednávka, která je antisymetrická a celková
• Řízená sada
• Kategorie předobjednaných sad
• Prewellordering
• Dobře kvazi-objednávání

Poznámky

Reference

• Schmidt, Gunther, „Relational Mathematics“, Encyclopedia of Mathematics and its Applications, sv. 132, Cambridge University Press, 2011, ISBN  978-0-521-76268-7
• Schröder, Bernd S. W. (2002), Objednané sady: Úvod, Boston: Birkhäuser, ISBN  0-8176-4128-9