Předobjednávka - Preorder

V matematice , obzvláště v teorii objednávky , je preorder nebo quasiorder je binární relace , která je reflexivní a tranzitivní . Předobjednávky jsou obecnější než relace ekvivalence a (ne striktní) dílčí řády , oba jsou speciálními případy předobjednávky: antisymetrická předobjednávka je částečná objednávka a symetrická předobjednávka je vztahem ekvivalence.

Název předobjednávky pochází z myšlenky, že předobjednávky (které nejsou dílčími objednávkami) jsou „téměř“ (částečné) objednávky, ale ne zcela; nejsou nezbytně antisymetrické ani asymetrické . Protože předobjednávka je binární relace, může být symbol použit jako notační zařízení pro relaci. Protože však nejsou nutně antisymetrické, některé běžné intuice spojené se symbolem nemusí platit. Na druhou stranu předobjednávku lze přímo použít k definování dílčího řádu a vztahu ekvivalence. V závislosti na studované doméně problému to však není vždy užitečné ani užitečné. ${\ displaystyle \, \ leq \,}$${\ displaystyle \, \ leq \,}$

V slovy, když lze říci, že B Nápovědy týká se , nebo že se předchází b , nebo že b redukuje na . Občas se místo toho použije notace ← nebo${\ displaystyle a \ leq b,}$ ${\ displaystyle \, \ lesssim \,}$${\ Displaystyle \, \ leq.}$

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

Formální definice

Uvažujme homogenní vztah k nějaké dané množině, takže podle definice je nějaká podmnožina a místo toho se použije notace Potom se nazývá předobjednávka nebo kvaziorder, pokud je reflexivní a tranzitivní ; to znamená, že pokud splňuje: ${\ displaystyle \, \ leq \,}$ ${\ displaystyle P,}$${\ displaystyle \, \ leq \,}$${\ displaystyle P \ times P}$${\ Displaystyle a \ leq b}$${\ Displaystyle (a, b) \ in \, \ leq.}$${\ displaystyle \, \ leq \,}$

1. Reflexivita : a${\ displaystyle a \ leq a {\ text {for all}} a \ in P,}$
2. Přechodnost :${\ Displaystyle {\ text {if}} a \ leq b {\ text {and}} b \ leq c {\ text {then}} a \ leq c {\ text {for all}} a, b, c \ v P.}$

Sada, která je vybavena předobjednávkou, se nazývá předobjednaná sada (nebo proset ). Za účelem zdůraznění nebo kontrastu k přísným předobjednávkám může být předobjednávka také označována jako nestandardní předobjednávka .

Pokud je reflexivita nahrazena nereflexivitou (při zachování tranzitivity), pak se výsledek nazývá přísná předobjednávka; explicitně, je striktní preorder na je homogenní binární relace na tom, že jsou splněny následující podmínky: ${\ displaystyle P}$${\ displaystyle \, <\,}$${\ displaystyle P}$

1. Irreflexivita nebo antireflexivita: to znamená, a${\ displaystyle {\ textit {not}} \; a <a \; {\ text {for all}} a \ in P;}$${\ displaystyle \, a <a \; {\ text {is}} {\ textit {false}} {\ text {for all}} a \ in P,}$
2. Přechodnost :${\ Displaystyle {\ text {if}} a <b {\ text {and}} b <c {\ text {then}} a <c {\ text {for all}} a, b, c \ in P. }$

Binární relace je přísný preorder právě tehdy, když se jedná o striktní částečná objednávka . Podle definice je přísný částečný řád asymetrickou přísnou předobjednávkou, kde se nazývá asymetrická, pokud pro všechny Naopak každá přísná předobjednávka je přísným dílčím řádem, protože každý tranzitivní nereflexivní vztah je nutně asymetrický . Ačkoli jsou ekvivalentní, výraz „přísný dílčí řád“ je obvykle upřednostňován před „přísným předobjednávkou“ a čtenáři jsou odkázáni na článek o přísných dílčích řádech, kde jsou podrobnosti o takových vztazích. Na rozdíl od přísných předobjednávek existuje mnoho (přísných) předobjednávek, které nejsou (přísnými) dílčími objednávkami . ${\ displaystyle \, <\,}$${\ displaystyle a <b {\ text {implies}} {\ textit {not}} \ b <a}$${\ displaystyle a, b.}$

Související definice

Pokud je předobjednávka také antisymetrická , to znamená, a znamená to, pak jde o částečné pořadí . ${\ Displaystyle a \ leq b}$${\ Displaystyle b \ leq a}$${\ displaystyle a = b,}$

Na druhou stranu, pokud je symetrický , to znamená, pokud implikuje, pak jde o vztah ekvivalence . ${\ Displaystyle a \ leq b}$${\ Displaystyle b \ leq a,}$

Předobjednávka je celková, pokud nebo pro všechny${\ Displaystyle a \ leq b}$${\ Displaystyle b \ leq a}$${\ Displaystyle a, b \ v P.}$

Pojem předem uspořádané množiny lze v kategorickém rámci formulovat jako tenkou kategorii ; tj. jako kategorie s nejvýše jedním morfismem od objektu k druhému. Zde objekty odpovídají prvkům a existuje jeden morfismus pro související objekty, jinak nula. Alternativně lze předobjednanou sadu chápat jako obohacenou kategorii , obohacenou o kategorii${\ displaystyle P}$${\ displaystyle P,}$${\ Displaystyle 2 = (0 \ to 1).}$

Předobjednal třída je třída vybavena předobjednání. Každá sada je třída, a proto každá předobjednaná sada je předobjednaná třída.

Příklady

Vztah dosažitelnosti v libovolném nasměrovaném grafu (případně obsahujícím cykly) vede k předobjednávce, kde v předobjednávce právě tehdy, je -li v nasměrovaném grafu cesta od x do y . Naopak každá předobjednávka je vztahem dosažitelnosti směrovaného grafu (například graf, který má hranu od x do y pro každý pár ( x , y ) s Mnoho různých grafů však může mít předobjednávku dosažitelnosti stejnou jako každý jiný. Stejným způsobem dosažitelnost řízených acyklických grafů , směrovaných grafů bez cyklů, vede k částečně uspořádaným množinám (předobjednávky splňující další vlastnost antisymetrie). ${\ Displaystyle x \ leq y}$${\ Displaystyle x \ leq y.}$

Každý konečný topological prostor vede k předobjednání na svých místech tím, že definuje právě tehdy, když x patří do každé části z r . Každou konečnou předobjednávku lze tímto způsobem vytvořit jako specializační předobjednávku topologického prostoru. To znamená, že mezi konečnými topologiemi a konečnými předobjednávkami existuje vzájemná korespondence . Vztah mezi nekonečnými topologickými prostory a jejich specializačními předobjednávkami však není individuální. ${\ Displaystyle x \ leq y}$

Síť je zaměřena preorder, to znamená, že každá dvojice prvků, má horní hranici . Definice konvergence prostřednictvím sítí je důležitá v topologii , kde předobjednávky nelze nahradit částečně uspořádanými množinami bez ztráty důležitých funkcí.

Další příklady:

• Vztah definovaný if, kde f je funkce do nějaké předobjednávky.${\ Displaystyle x \ leq y}$${\ Displaystyle f (x) \ leq f (y),}$
• Vztah definovaný, pokud existuje nějaká injekce od x do y . Injekce může být nahrazena surjekcí nebo jakýmkoli typem funkce zachovávající strukturu, jako je kruhový homomorfismus nebo permutace .${\ Displaystyle x \ leq y}$
• Vztah vkládání pro spočítatelné celkové objednávky .
• Vztah graf-minor v teorii grafů .
• Kategorie s nejvýše jedním morfismu z libovolného objektu x na další předměty, y je preorder. 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 odlišný (pojmenovaný) předobjednávací vztah.

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

• Mnohostranná a Turingova redukce jsou předobjednávky tříd složitosti.
• Tyto Subtypizace vztahy jsou obvykle předobjednávky.
• Simulační předobjednávky jsou předobjednávky (odtud název).
• Redukční vztahy v abstraktních přepisovacích systémech .
• Zvládnutí preorder na souboru podmínek , definovaný v případě, že subterm z t je substituce instance z s .${\ Displaystyle s \ leq t}$

Příklad celkové předobjednávky :

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

Využití

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

• Každá předobjednávka může mít topologii, Alexandrovskou topologii ; a skutečně, každá předobjednávka na sadě je v korespondenci jeden s jedním s topologií Alexandrov na této sadě.
• K definování interiérových algeber lze použít předobjednávky .
• Předobjednávky poskytují sémantiku Kripke pro určité typy modální logiky .
• Předobjednávky se používají nutí v teorii množin dokázat, konzistence a nezávislost výsledků.

Stavby

Každý binární relace na množině může být rozšířena na předobjednávku na převzetím tranzitivní uzávěr a reflexivní uzávěr , tranzitivní uzávěr indikuje připojení cesty v případě, a to pouze v případě, že je - cesta od do${\ displaystyle R}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle R^{+=}.}$${\ displaystyle R: xR^{+} y}$${\ displaystyle R}$${\ displaystyle x}$${\ Displaystyle y.}$

Levá reziduální předobjednávka indukovaná binární relací

Vzhledem k tomu, binární relace doplněnými kompozice tvoří preorder nazývá vlevo zbytkový , kde značí opačnou vztah z a označuje komplementu vztah while značí vztahu složení . ${\ displaystyle R,}$${\ displaystyle R \ zpětné lomítko R = {\ overline {R^{\ textyf {T}} \ circ {\ overline {R}}}}}$${\ displaystyle R^{\ textyf {T}}}$${\ displaystyle R,}$${\ displaystyle {\ overline {R}}}$${\ displaystyle R,}$${\ displaystyle \ circ}$

Předobjednávky a dílčí objednávky na oddílech

Vzhledem k předobjednávce na jednom může definovat vztah ekvivalence na tom, že ${\ displaystyle \, \ lesssim \,}$${\ displaystyle S}$ ${\ displaystyle \, \ sim \,}$${\ displaystyle S}$

Výsledný vztah je reflexivní, protože předobjednávka je reflexivní, tranzitivní aplikováním tranzitivity předobjednávky dvakrát a symetrická podle definice. ${\ displaystyle \, \ sim \,}$

Pomocí tohoto vztahu, že je možné konstruovat částečný příkaz na kvocientu rovnocennosti, množina všech tříd ekvivalence v případě, že je preorder je sada - cyklu tříd ekvivalence: jestliže a pouze v případě, nebo je ve -cycle s V každém případě je možné definovat Konstrukce této definice je nezávislá na zvolených zástupcích a odpovídající vztah je skutečně dobře definován. Je snadno ověřeno, že to poskytne částečně uspořádanou sadu. ${\ displaystyle S/\ sim,}$${\ displaystyle \, \ sim.}$${\ displaystyle R^{+=},}$ ${\ displaystyle S/\ sim}$${\ displaystyle R}$${\ displaystyle x \ in [y]}$${\ displaystyle x = y}$${\ displaystyle x}$${\ displaystyle R}$${\ displaystyle y}$${\ displaystyle S/\ sim,}$${\ Displaystyle [x] \ leq [y] {\ text {právě a pouze pokud}} x \ lesssim y.}$${\ displaystyle \, \ sim,}$

Naopak, z částečného pořadí na přepážkou sady lze sestrojit předobjednávky na Existuje jedna ku jedné korespondence mezi preorders a páry (oddílů, částečné pořadí). ${\ displaystyle S}$${\ Displaystyle S.}$

Příklad : Dovolme si být formální teorií , což je soubor vět s určitými vlastnostmi (podrobnosti o nich najdete v článku na toto téma ). Může to být například teorie prvního řádu (jako teorie množin Zermelo – Fraenkel ) nebo jednodušší teorie nulového řádu . Jednou z mnoha vlastností je to, že je uzavřena za logických důsledků, takže například pokud věta logicky implikuje nějakou větu, která bude napsána nutně tak a tak, tak Vztah je předobjednávka zapnutá, protože vždy platí a kdykoli a obě platí pak také dále, pro všechny tehdy a jen tehdy ; to znamená, že dvě věty jsou ekvivalentní s ohledem na právě tehdy, pokud jsou logicky ekvivalentní . Tento konkrétní vztah ekvivalence je běžně označován svým vlastním zvláštním symbolem, a proto může být tento symbol použit místo. Třída ekvivalence věty označené větou obsahuje všechny věty, které jsou logicky ekvivalentní (tedy všechny takové ). Částečné pořadí, které bude indukováno a které bude také označováno stejným symbolem, je charakterizováno tehdy a pouze tehdy, když podmínka na pravé straně je nezávislá na výběru zástupců a tříd ekvivalence. Vše, co bylo dosud řečeno , lze také říci o jeho konverzním vztahu Předobjednaná množina je směrovaná množina, protože pokud a pokud označuje větu tvořenou logickou spojkou tehdy a kde Částečně uspořádaná množina je následně také směrovaná množina. Viz lindenbaumova algebra pro příbuzné příklad. ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle A \ in S}$${\ displaystyle B,}$${\ displaystyle A \ Rightarrow B}$${\ displaystyle B \ Leftarrow A,}$${\ Displaystyle B \ v S.}$${\ displaystyle \, \ Leftarrow \,}$${\ displaystyle S}$${\ Displaystyle A \ Leftarrow A}$${\ Displaystyle A \ Leftarrow B}$${\ Displaystyle B \ Leftarrow C}$${\ Displaystyle A \ Leftarrow C.}$${\ displaystyle A, B \ v S,}$ ${\ displaystyle A \ sim B}$${\ Displaystyle A \ Leftarrow B {\ text {and}} B \ Leftarrow A}$${\ displaystyle \, \ Leftarrow \,}$${\ displaystyle A \ sim B}$${\ displaystyle A \ iff B,}$${\ displaystyle \, \ iff \,}$${\ displaystyle \, \ sim.}$${\ displaystyle A,}$${\ displaystyle [A],}$${\ displaystyle B \ in S}$${\ displaystyle A}$${\ displaystyle B \ in S}$${\ displaystyle A \ iff B}$${\ displaystyle S/\ sim}$${\ displaystyle \, \ Leftarrow, \,}$${\ displaystyle \, \ Leftarrow, \,}$${\ Displaystyle [A] \ Leftarrow [B]}$${\ Displaystyle A \ Leftarrow B,}$${\ Displaystyle A \ v [A]}$${\ Displaystyle B \ v [B]}$${\ displaystyle \, \ Leftarrow \,}$ ${\ displaystyle \, \ Rightarrow. \,}$${\ Displaystyle (S, \ Leftarrow)}$${\ displaystyle A, B \ in S}$${\ Displaystyle C: = A \ wedge B}$ ${\ Displaystyle \, \ klín, \,}$${\ Displaystyle A \ Leftarrow C}$${\ Displaystyle B \ Leftarrow C}$${\ Displaystyle C \ v S.}$${\ Displaystyle \ left (S/\ sim, \ Leftarrow \ right)}$

Předobjednávky a přísné předobjednávky

Přísná předobjednávka vyvolaná předobjednávkou

Vzhledem k předobjednávce lze definovat nový vztah prohlášením, že pokud a pouze tehdy nebo ekvivalentně, pomocí výše uvedeného vztahu ekvivalence, takže vztah splňuje ${\ displaystyle \, \ lesssim,}$${\ displaystyle \, <\,}$${\ displaystyle a <b}$${\ displaystyle (a \ lesssim b {\ text {a ne}} b \ lesssim a),}$${\ displaystyle (a \ lesssim b {\ text {a ne}} a \ sim b)}$

Vztah je přísný dílčí řád a každé přísné dílčí pořadí může být výsledkem takové konstrukce. Pokud je předobjednávka antisymetrická, a tedy částečné pořadí, pak je ekvivalencí rovnost (to znamená ) a vztah, který lze tuto definici přepsat jako: ${\ displaystyle \, <\,}$${\ displaystyle \, \ lesssim \,}$${\ displaystyle a \ sim b {\ text {právě tehdy, když}} a = b}$${\ displaystyle \, <\,}$

$${\ Displaystyle a <b \ quad {\ text {if and only if}} \ quad (a \ leq b {\ text {and}} a \ neq b) \ quad \ quad ({\ text {if}} \ lesssim {\ text {je antisymetrický}}).}$$

Ale důležitější je, že je to není obecná definice vztahu (to znamená, že je není definován jako: pouze v případě ), protože v případě, že preorder není antisymetrická pak výsledný vztah nebude tranzitivní (přemýšlet o tom, jak odpovídá ne-rovná prvky vztahovat se). To je důvod pro použití symbolu „ “ místo „menšího nebo rovného“ symbolu ” “, což by mohlo způsobit zmatek v předobjednávce, která není antisymetrická, protože může zavádějícím způsobem naznačovat, že to znamená${\ displaystyle \, <\,}$${\ displaystyle \, <\,}$${\ displaystyle a <b}$${\ Displaystyle (a \ lesssim b {\ text {and}} a \ neq b)}$${\ displaystyle \, \ lesssim \,}$${\ displaystyle \, <\,}$${\ displaystyle \ lesssim}$${\ displaystyle \ leq}$${\ Displaystyle a \ leq b}$${\ Displaystyle a <b {\ text {nebo}} a = b.}$

Předobjednávky vyvolané přísnou předobjednávkou

S touto konstrukcí může mít několik předobjednávek " " za následek stejný vztah, přísnou předobjednávku, takže bez dalších informací, jako je například " " ekvivalenční vztah, nelze " " rekonstruovat z " ". Možné předobjednávky zahrnují následující: ${\ displaystyle \, \ lesssim \,}$${\ displaystyle \, <, \,}$${\ displaystyle \, \ lesssim \,}$${\ displaystyle <}$

• Definujte jako (tj. Vezměte reflexní uzavření vztahu). To dává částečný řád spojený s přísným dílčím řádem " " prostřednictvím reflexního uzavření; v tomto případě je ekvivalencí rovnost, takže nepotřebujeme notace a${\ Displaystyle a \ leq b}$${\ displaystyle a <b {\ text {or}} a = b}$${\ displaystyle <}$${\ displaystyle \, \ lesssim \,}$${\ displaystyle \, \ sim.}$
• Definujte jako „ “ (tj. Vezměte inverzní doplněk vztahu), což odpovídá definování jako „ani “; tyto vztahy a obecně nejsou tranzitivní; pokud však jsou, je to rovnocennost; v tom případě je

přísný slabý řád . Výsledná předobjednávka je spojena (dříve nazývaná celkem), tj. Celková předobjednávka .${\ displaystyle a \ lesssim b}$${\ displaystyle {\ text {not}} b <a}$${\ displaystyle a \ sim b}$${\ Displaystyle a <b {\ text {nor}} b <a}$${\ displaystyle \, \ lesssim \,}$${\ displaystyle \, \ sim \,}$${\ displaystyle \, \ sim \,}$${\ displaystyle <}$

Počet předobjednávek

Počet binárních relací n -prvků různých typů

Prvky	Žádný	Tranzitivní	Reflexní	Předobjednávka	Dílčí objednávka	Celková předobjednávka	Celková objednávka	Vztah ekvivalence
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3,994	4,096	355	219	75	24	15
n	2 n 2		2 n 2 - n			${\ textstyle \ sum _ {k = 0}^{n} k!}$S ( n , k )	n !	${\ textstyle \ sum _ {k = 0}^{n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Jak bylo vysvětleno výše, mezi předobjednávkami a páry (oddíl, čá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:

• pro ${\ displaystyle n = 3:}$
  • 1 oddíl 3, což dává 1 předobjednávku
  • 3 oddíly 2 + 1 , dávající předobjednávky${\ displaystyle 3 \ times 3 = 9}$
  • 1 oddíl 1 + 1 + 1 , což dává 19 předobjednávek
  Tedy dohromady 29 předobjednávek.
• pro ${\ displaystyle n = 4:}$
  • 1 oddíl po 4, což dává 1 předobjednávku
  • 7 oddílů se dvěma třídami (4 z 3 + 1 a 3 z 2 + 2 ), dávající předobjednávky${\ displaystyle 7 \ times 3 = 21}$
  • 6 oddílů 2 + 1 + 1 , dávající předobjednávky${\ displaystyle 6 \ times 19 = 114}$
  • 1 oddíl 1 + 1 + 1 + 1 , což dává 219 předobjednávek
  Tedy dohromady 355 předobjednávek.

Interval

Pro v

intervalu je množina bodů x splňujících a také psáno , že obsahuje alespoň body a b . Jeden se může rozhodnout rozšířit definici na všechny páry . Další intervaly jsou prázdné. ${\ displaystyle a \ lesssim b,}$ ${\ displaystyle [a, b]}$${\ displaystyle a \ lesssim x}$${\ displaystyle x \ lesssim b,}$${\ Displaystyle a \ lesssim x \ lesssim b.}$${\ displaystyle (a, b)}$

Pomocí odpovídajícího přísného vztahu " " lze také definovat interval jako množinu bodů

x, které jsou uspokojivé a také zapsané . Otevřený interval může být prázdný, i když${\ displaystyle <}$${\ displaystyle (a, b)}$${\ displaystyle a <x}$${\ displaystyle x <b,}$${\ Displaystyle a <x <b.}$${\ Displaystyle a <b.}$

Také a mohou být definovány podobně. ${\ displaystyle [a, b)}$${\ displaystyle (a, b]}$

Viz také

• Částečné pořadí - předobjednávka, která je antisymetrická
• Vztah ekvivalence - předobjednávka, která je symetrická
• Celková předobjednávka - předobjednávka, která je celková
• Celková objednávka - předobjednávka, která je antisymetrická a celková
• Řízená sada
• Kategorie předobjednaných sad
• Předvánoční objednávka
• Dobře kvazi-uspořádání

Poznámky

1. ^ Pro „proset“ viz např. Eklund, Patrik; Gähler, Werner (1990), „Generalized Cauchy spaces“, Mathematische Nachrichten , 147 : 219–233, doi : 10,1002/mana.19901470123 , MR  1127325.
2. ^ Pierce, Benjamin C. (2002). Typy a programovací jazyky . Cambridge, Massachusetts/Londýn, Anglie: The MIT Press. s. 182 a násl. ISBN 0-262-16209-1.
3. ^ Kunen, Kenneth (1980), Teorie množin, Úvod do důkazů nezávislosti , Studie logiky a základy matematiky, 102 , Amsterdam, Nizozemsko: Elsevier.
4. ^ V tomto kontextu „“ neznamená „nastavit rozdíl“.${\ displaystyle \ zpětné lomítko}$

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 SW (2002), Ordered Sets: An Introduction , Boston: Birkhäuser, ISBN 0-8176-4128-9