Vložení objednávky - Order embedding

V teorii objednávek , odvětví matematiky , je vkládání objednávek zvláštním druhem monotónní funkce , která poskytuje způsob, jak zahrnout jednu částečně uspořádanou množinu do druhé. Stejně jako spojení Galois tvoří i vložení řádů pojem, který je přísně slabší než pojem řádový izomorfismus . Obě tato oslabení lze chápat z hlediska teorie kategorií .

Formální definice

Formálně, uvedené dvě částečně uspořádané množiny (Posets) a , je funkce je pořadí vkládání , když je jak objednávky zachování a pořadí odrážející , tedy pro všechny a v , jeden má ${\ displaystyle (S, \ leq)}$${\ displaystyle (T, \ preceq)}$ ${\ displaystyle f: S \ až T}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle S}$

${\ displaystyle x \ leq y {\ text {tehdy a jen tehdy}} f (x) \ preceq f (y).}$

Taková funkce je nutně injektivní , protože naznačuje a . Pokud existuje objednávka vložená mezi dvě posety a existuje, říká se, že do ní lze vložit . ${\ displaystyle f (x) = f (y)}$${\ displaystyle x \ leq y}$${\ displaystyle y \ leq x}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S}$${\ displaystyle T}$

Vlastnosti

Vkládání vzájemných objednávek a použití v obou směrech. ${\ displaystyle (0,1)}$${\ displaystyle [0,1]}$${\ displaystyle f (x) = (94x + 3) / 100}$

Sada dělitelů 6, částečně seřazená podle x, dělí y . Vložení nemůže být opravou. ${\ displaystyle S}$${\ displaystyle id: \ {1,2,3 \} \ do S}$

Izomorfismus řádu lze charakterizovat jako vložení surjektivního řádu. Důsledkem je, že jakýkoli řád vkládající f se omezuje na izomorfismus mezi jeho doménou S a jeho obrazem f ( S ), což ospravedlňuje termín „vložení“. Na druhou stranu by se mohlo dobře stát, že dvě (nutně nekonečná) posety jsou vzájemně uspořádatelně uspořádaná do řádu, aniž by byla řádově izomorfní.

Příkladem je poskytována otevřeném intervalu z reálných čísel a odpovídajícím uzavřeném intervalu . Funkce mapuje první na podmnožinu druhé a druhá na podmnožinu první, viz obrázek. Řazení obou sad přirozeným způsobem je zachování pořadí i odrážení pořadí (protože se jedná o afinní funkci ). Přesto nemůže existovat žádný izomorfismus mezi těmito dvěma posety, protože např. Má nejméně prvků, zatímco nemá. Podobný příklad použití arctanu k seřazení reálných čísel do intervalu a mapy identity pro obrácený směr viz např. Just a Weese (1996). ${\ displaystyle (0,1)}$ ${\ displaystyle [0,1]}$${\ displaystyle f (x) = (94x + 3) / 100}$ ${\ displaystyle (0,03,0,97)}$${\ displaystyle [0,03,0,97]}$${\ displaystyle f}$${\ displaystyle [0,1]}$${\ displaystyle (0,1)}$

Stažení je dvojice map zachovávajících pořadí, jejichž složení je identita. V tomto případě se nazývá coretraction a musí to být vložení objednávky. Ne každé vložení objednávky je však oprava. Jako triviální příklad nemá jedinečná objednávka vložená z prázdného posetu do neprázdného posetu žádné zatažení, protože neexistuje žádná mapa zachovávající pořadí . Více názorně, zvažovat soubor z dělitele 6, částečně nařízených x dělí y , viz obrázek. Zvažte vloženou podposet . Vyjetí z zalití budou muset poslat někam do výše obou a , ale není tam žádná taková místa. ${\ displaystyle (f, g)}$ ${\ displaystyle g \ circ f}$${\ displaystyle f}$${\ displaystyle f: \ emptyset \ to \ {1 \}}$${\ displaystyle g: \ {1 \} \ to \ emptyset}$${\ displaystyle S}$ ${\ displaystyle \ {1,2,3 \}}$${\ displaystyle id: \ {1,2,3 \} \ do S}$${\ displaystyle 6}$${\ displaystyle \ {1,2,3 \}}$${\ displaystyle 2}$${\ displaystyle 3}$

Další perspektivy

Na posety lze přímo pohlížet z mnoha hledisek a vkládání objednávek je natolik základní, že mají tendenci být viditelné odkudkoli. Například:

• ( Model teoreticky ) poset je sada vybavena (reflexivní, antisymmetric a přechodného) binární relace . Příkaz vkládání A → B je izomorfismus od A k základní nosné konstrukci z B .
• ( Graf teoreticky ) poset je (tranzitivní, acyklický, režie, reflexní) graf . Příkaz vkládání A → B je graf izomorfismus od A do indukované subgrafu části B .
• ( Kategorie teoreticky ) A poset je (malý, tenký a kosterní) kategorie tak, že každá homset má nejvýše jeden prvek. Příkaz vkládání A → B je úplný a věrný funktor z A do B, která je injective na objektech, nebo ekvivalentně izomorfismus od A do plného podkategorii z B .

Viz také

• Dushnik – Millerova věta
• Laverova věta

Reference