Částečně objednaná sada - Partially ordered set

The Hasseův diagram z sada všech podskupin tříprvkové množiny {x, y, z}, seřazené podle zařazení. Výrazné sady na stejné vodorovné úrovni jsou navzájem nesrovnatelné. Některé další páry, například {x} a {y, z}, jsou také nesrovnatelné.

v matematika, zvláště teorie objednávek, a částečně objednaná sada (taky poset) formalizuje a zevšeobecňuje intuitivní koncept uspořádání, řazení nebo uspořádání prvků a soubor. Poset se skládá ze sady společně s a binární relace což naznačuje, že u určitých párů prvků v sadě předchází jeden z prvků druhý v pořadí. Samotný vztah se nazývá „částečný řád“. Slovo částečný v názvech „částečné pořadí“ a „částečně uspořádaná množina“ se používá jako označení toho, že ne každá dvojice prvků musí být srovnatelná. To znamená, že mohou existovat dvojice prvků, u nichž žádný z prvků předchází v posetu druhý. Dílčí objednávky se tak zobecňují celkový počet objednávek, ve kterém je každý pár srovnatelný.

Formálně je částečným řádem jakýkoli binární vztah, který je reflexní (každý prvek je srovnatelný sám se sebou), antisymetrický (žádné dva různé prvky nepředcházejí), a tranzitivní (začátek řetězce prioritních vztahů musí předcházet konci řetězce).

Jeden známý příklad částečně objednané sady je kolekce lidí objednaných genealogický potomek. Některé páry lidí nesou vztah mezi potomkem a předkem, ale jiné páry lidí jsou nesrovnatelné, přičemž ani jeden z nich není potomkem druhého.

Poset lze vizualizovat prostřednictvím jeho Hasseův diagram, který zobrazuje objednávkový vztah.^[1]

Formální definice

A (non-strict) částečná objednávka^[2] je homogenní binární relace ≤ nad a soubor P splňující jednotlivé axiomy, které jsou popsány níže. Když A ≤ b, říkáme to A je související s b. (To neznamená, že b souvisí také s A, protože vztah nemusí být symetrický.)

Axiomy pro nestriktní dílčí pořadí uvádějí, že vztah ≤ je reflexní, antisymetrický, a tranzitivní. To je pro všechny A, b, a C v P, musí splňovat:

1. A ≤ A (reflexivita: každý prvek souvisí sám se sebou).
2. -li A ≤ b a b ≤ A, pak A = b (antisymetrie: dva odlišné prvky nelze spojit v obou směrech).
3. -li A ≤ b a b ≤ C, pak A ≤ C (tranzitivita: pokud první prvek souvisí s druhým prvkem a tento prvek zase souvisí s třetím prvkem, pak první prvek souvisí se třetím prvkem).

Jinými slovy, částečný řád je antisymetrický předobjednávka.

Sada s částečným pořadím se nazývá a částečně objednaná sada (také nazývaný a poset). Termín objednaná sada někdy se také používá, pokud je z kontextu zřejmé, že není míněn žádný jiný druh řádu. Zejména, zcela objednané sady lze také označit jako „uspořádané množiny“, zejména v oblastech, kde jsou tyto struktury běžnější než posety.

Pro a, b, prvky částečně uspořádané množiny P, pokud A ≤ b nebo b ≤ A, pak A a b jsou srovnatelný. Jinak jsou nesrovnatelný. Na obrázku vpravo nahoře, např. {x} a {x, y, z} jsou srovnatelné, zatímco {x} a {y} nejsou. Částečné pořadí, ve kterém je každá dvojice prvků srovnatelná, se nazývá a celková objednávka nebo lineární pořadí; zcela objednaná sada se také nazývá a řetěz (např. přirozená čísla s jejich standardním uspořádáním). Podmnožina posetu, ve kterém nejsou srovnatelné dva odlišné prvky, se nazývá an antichain (např. sada singletons {{x}, {y}, {z}} na obrázku vpravo nahoře). Prvek A se říká, že je přísně méně než prvek b, pokud A ≤ b a A≠b. Prvek A se říká, že je kryté jiným prvkem b, psaný A⋖b (nebo A<:b), pokud A je přísně menší než b a žádný třetí prvek C zapadá mezi ně; formálně: pokud obojí A≤b a A≠b jsou pravdivé a A≤C≤b je pro každého falešný C s A≠C≠b. Bude uvedena stručnější definice níže pomocí přísného pořadí odpovídajícího „≤“. Například {x} je na obrázku vpravo nahoře pokryto {x, z}, nikoli však {x, y, z}.

Příklady

Standardní příklady posetů vznikajících v matematice zahrnují:

• The reálná čísla objednáno standardem menší než nebo rovný relace ≤ (také zcela objednaná množina).
• Sada podmnožiny dané množiny (její napájecí sada ) objednáno někým zařazení (viz obrázek vpravo nahoře). Podobně sada sekvence objednáno někým subsekvence a soubor struny objednáno někým podřetězec.
• Sada přirozená čísla vybavené vztahem dělitelnost.
• Sada vrcholů a směrovaný acyklický graf objednáno někým dosažitelnost.
• Sada podprostory a vektorový prostor objednáno zahrnutím.
• U částečně objednané sady P, sekvenční prostor obsahující vše sekvence prvků z P, kde sekvence A předchází sekvenci b pokud je každá položka v A předchází odpovídající položku v b. Formálně, (A_n)_n∈ℕ ≤ (b_n)_n∈ℕ kdyby a jen kdyby A_n ≤ b_n pro všechny n v ℕ, tj. a dílčí objednávka.
• Pro sadu X a částečně objednanou sadu P, funkční prostor obsahující všechny funkce z X na P, kde F ≤ G kdyby a jen kdyby F(X) ≤ G(X) pro všechny X v X.
• A plot, částečně uspořádaná množina definovaná střídavou posloupností řádových vztahů A < b > C < d ...
• Soubor událostí v speciální relativita a ve většině případů^[3] obecná relativita, kde pro dvě události X a Y, X ≤ Y právě tehdy, pokud je Y v budoucnosti světelný kužel X. Událost Y může být kauzálně ovlivněna X, pouze pokud X ≤ Y.

Extrema

Nezáporná celá čísla seřazená podle dělitelnosti

Obrázek výše s odstraněnými největšími a nejmenšími prvky. V tomto redukovaném posetu jsou všechny horní řady prvků maximální prvky a spodní řádek jsou všechny minimální prvky, ale není tam žádný největší a žádná nejméně živel. Množina {x, y} je horní hranice pro kolekci prvků {{x}, {y}}.

V posetu existuje několik pojmů „největší“ a „nejméně“ prvek P, zejména:

• Největší prvek a nejméně prvek: prvek G v P je největším prvkem, pokud pro každý prvek A v P, A ≤ G. Prvek m v P je nejméně prvek, pokud pro každý prvek A v P, A ≥ m. Poset může mít pouze jeden největší nebo nejméně prvek.
• Maximální prvky a minimální prvky: prvek G v P je maximální prvek, pokud není žádný prvek A v P takhle A > G. Podobně prvek m v P je minimální prvek, pokud není žádný prvek A v P takové, že A < m. Pokud má poset největší prvek, musí to být jedinečný maximální prvek, ale jinak může existovat více než jeden maximální prvek a podobně pro nejméně prvků a minimální prvky.
• Horní a dolní mez: Pro podmnožinu A z Pprvek X v P je horní hranice A -li A ≤ X, pro každý prvek A v A. Zejména, X nemusí být v A být horní hranicí A. Podobně prvek X v P je dolní mez A -li A ≥ X, pro každý prvek A v A. Největší prvek P je horní hranice P sám o sobě, a nejmenší prvek je dolní mez P.

Zvažte například kladná celá čísla, seřazeno podle dělitelnosti: 1 je nejméně prvek, protože rozděluje všechny ostatní prvky; na druhou stranu tento poset nemá největší prvek (i když by jeden zahrnoval 0 v posetu, což je násobek libovolného celého čísla, byl by to největší prvek; viz obrázek). Tato částečně uspořádaná sada nemá ani žádné maximální prvky, protože žádné G rozděluje například 2G, což je odlišné od toho, takže G není maximální. Pokud je číslo 1 vyloučeno, při zachování dělitelnosti jako pořadí na prvcích větších než 1, pak výsledná poseta nemá nejmenší prvek, ale jakýkoli prvočíslo je pro to minimální prvek. V tomto posetu je 60 horní mez (i když ne nejméně horní mez) podmnožiny {2,3,5,10}, která nemá žádnou dolní mez (protože 1 není v posetu); na druhé straně 2 je dolní mez podmnožiny mocnin 2, která nemá žádnou horní mez.

Objednávky na kartézský součin částečně objednaných sad

Reflexní uzavření přísné přímé objednávky produktů na ℕ × ℕ. Elementy kryté od (3,3) a obálka (3,3) jsou zvýrazněny zeleně a červeně.

Objednávka produktu na ℕ × ℕ

Lexikografické pořadí na ℕ × ℕ

V pořadí zvyšování síly, tj. Snižování sad párů, tři z možných dílčích řádů na kartézský součin ze dvou částečně uspořádaných sad jsou (viz obrázky):

• the lexikografický řád:   (A,b) ≤ (C,d) pokud A < C nebo (A = C a b ≤ d);
• the objednávka produktu:   (A,b) ≤ (C,d) pokud A ≤ C a b ≤ d;
• the reflexní uzávěr z přímý produkt příslušných přísných objednávek: (A,b) ≤ (C,d) pokud (A < C a b < d) nebo (A = C a b = d).

Všechny tři lze podobně definovat pro kartézský součin více než dvou sad.

Aplikován na uspořádané vektorové prostory přes to samé pole, výsledkem je v každém případě také uspořádaný vektorový prostor.

Viz také objednávky na kartézský součin zcela objednaných sad.

Součty částečně seřazených množin

Hasseův diagram a sériově paralelní částečné pořadí, vytvořený jako pořadový součet tří menších dílčích řádů.

Dalším způsobem, jak kombinovat dvě posety, je pořadový součet^[4] (nebo lineární součet^[5]), Z = X ⊕ Y, definované na sjednocení podkladových sad X a Y podle objednávky A ≤_Z b právě když:

• A, b ∈ X s A ≤_X bnebo
• A, b ∈ Y s A ≤_Y bnebo
• A ∈ X a b ∈ Y.

Pokud jsou dvě posety dobře uspořádané, pak je také jejich pořadový součet.^[6]Operace pořadového součtu je jednou ze dvou operací použitých k vytvoření sériově paralelní dílčí objednávky, a v této souvislosti se nazývá sériové složení. Druhá operace použitá k vytvoření těchto řádů, disjunktní spojení dvou částečně uspořádaných množin (bez relačního vztahu mezi prvky jedné sady a prvky druhé sady) se v tomto kontextu nazývá paralelní kompozice.

Přísné a přísné dílčí objednávky

V některých kontextech se výše definovaný dílčí řád nazývá a non-strict (nebo reflexní) částečná objednávka. V těchto kontextech, a přísný (nebo nereagující) částečná objednávka „<“ je binární relace, která je nereagující, tranzitivní a asymetrický, tj. které uspokojí všechny A, b, a C v P:

• ne a (irreflexivita),
• -li a a b pak a (tranzitivita) a
• -li a pak ne b (asymetrie; implikuje irreflexivitu; a je implikována irreflexivitou a antisymetrií^[7]).

Přísné a přísné dílčí objednávky spolu úzce souvisejí. Nenáročné částečné pořadí lze převést na přísné částečné pořadí odebráním všech vztahů ve formuláři A ≤ A. Naopak striktní částečné pořadí lze převést na nestriktní částečné pořadí sousedením se všemi vztahy tohoto formuláře. Pokud je tedy „≤“ nestranný částečný řád, pak odpovídající přísný dílčí řád „<“ je ireflexivní jádro dána:

A < b -li A ≤ b a A ≠ b

Naopak, pokud „<“ je striktní částečné pořadí, pak odpovídající nestriktní částečné pořadí „≤“ je reflexní uzávěr dána:

A ≤ b -li A < b nebo A = b.

To je důvod pro použití zápisu „≤“.

Pomocí přísného pořadí "<", relace "A je pokryto b„lze ekvivalentně přeformulovat jako“A<b, ale ne A<C<b pro všechny C". Přísné dílčí objednávky jsou užitečné, protože jim odpovídají přímo směrované acyklické grafy (dags): každý přísný dílčí příkaz je dag, a přechodné uzavření dag je jak přísný částečný řád, tak také dag sám.

Inverzní a objednávejte dvojí

Inverzní (nebo konverzní) vztahu částečného řádu ≤ je konverzovat ≤. Typicky se označuje ≥, je to vztah, který uspokojuje X ≥ y kdyby a jen kdyby y ≤ X. Inverzní vztah částečného řádu je reflexivní, přechodný a antisymetrický, a proto je sám o sobě relací částečného řádu. The objednat duální částečně uspořádané množiny je stejná množina s relací částečného řádu nahrazenou její inverzí. Irreflexivní vztah> je na ≥, protože

Kterýkoli ze čtyř vztahů ≤, <, ≥ a> na dané množině jednoznačně určuje další tři.

Obecně dva prvky X a y částečného řádu může stát v kterémkoli ze čtyř vzájemně se vylučujících vztahů: buď X < ynebo X = ynebo X > ynebo X a y jsou nesrovnatelný (žádný z ostatních tří). A úplně objednané set je takový, který vylučuje tuto čtvrtou možnost: všechny páry prvků jsou srovnatelné a my to potom říkáme trichotomie drží. The přirozená čísla, celá čísla, racionální a realita jsou všechny zcela seřazené podle jejich algebraické (podepsané) velikosti, zatímco komplexní čísla nejsou. Tím nechci říci, že složitá čísla nelze zcela objednat; mohli bychom je například objednat lexikograficky prostřednictvím X+iy < u+iproti kdyby a jen kdyby X < u nebo (X = u a y < proti), ale není to řazeno podle velikosti v žádném rozumném smyslu, protože to dělá 1 větší než 100i. Jejich seřazení podle absolutní velikosti vede k předobjednávce, ve které jsou všechny páry srovnatelné, ale nejedná se o částečné pořadí, protože 1 a i mají stejnou absolutní velikost, ale nejsou si rovni, což porušuje antisymetrii.

Mapování mezi částečně seřazenými sadami

Pořadí izomorfismu mezi děliteli 120 (částečně seřazeno podle dělitelnosti) a podmnožinami uzavřenými děliteli {2,3,4,5,8} (částečně seřazeno podle zařazení do souboru)

Zachování řádu, ale nikoli odrážení řádu (od F(u)≤F(proti), ale ne u≤proti) mapa.

Vzhledem k tomu, dvě částečně objednané sady (S, ≤) a (T, ≤), funkce F: S → T je nazýván zachování objednáveknebo monotónnínebo izoton, pokud pro všechny X a y v S, X≤y naznačuje F(X) ≤ F(y) Pokud (U, ≤) je také částečně uspořádaná množina a obojí F: S → T a G: T → U zachovávají pořádek, jejich složení (G∘F): S → U je také zachování pořadí. Funkce F: S → T je nazýván odrážející objednávku pokud pro všechny X a y v S, F(X) ≤ F(y) naznačuje X≤y.Li F zachovává i odráží pořadí, pak se nazývá an vkládání objednávek z (S, ≤) do (T, ≤). V druhém případě F je nutně injekční, od té doby F(X) = F(y) naznačuje X ≤ y a y ≤ X. Pokud je vložení objednávky mezi dvě posety S a T existuje, říká se to S může být vložený do T. Pokud je vložení objednávky F: S → T je bijektivní, nazývá se to objednávat izomorfismusa dílčí objednávky (S, ≤) a (T, ≤) se říká, že jsou izomorfní. Izomorfní řády jsou strukturálně podobné Hasse diagramy (viz pravý obrázek). Je možné ukázat, že pokud pořadí zachovává mapy F: S → T a G: T → S existují takové G∘F a F∘G výnosy funkce identity na S a Tpak S a T jsou řádově izomorfní.^[8]

Například mapování F: ℕ → ℙ (ℕ) od množiny přirozených čísel (seřazených podle dělitelnosti) do napájecí sada přirozených čísel (seřazených podle zařazení do sady) lze definovat tak, že každé číslo vezmeme do množiny svých čísel hlavní dělitelé. Zachovává pořádek: pokud X rozděluje y, pak každý hlavní dělitel X je také hlavním dělitelem y. Není to však ani injektivní (protože mapuje 12 i 6 na {2,3}), ani odrážející pořadí (protože 12 nerozděluje 6). Vezmeme místo toho každé číslo do sady hlavní síla dělitel definuje mapu G: ℕ → ℙ (ℕ), která zachovává řád, odráží řád, a tedy vkládá řád. Nejedná se o izomorfismus objednávky (protože např. Nemapuje žádné číslo na množinu {4}), ale lze jej vytvořit omezení jeho codomain na G(ℕ). Pravý obrázek ukazuje podmnožinu ℕ a její izomorfní obraz pod G. Konstrukci takového řádu-izomorfismu do mocenské soustavy lze zobecnit na širokou třídu dílčích řádů, tzv distribuční mřížky vizBirkhoffova věta o reprezentaci ".

Počet dílčích objednávek

Sekvence A001035 v OEIS udává počet dílčích objednávek na sadě n označené prvky:

Počet přísných dílčích objednávek je stejný jako počet dílčích objednávek.

Pokud se počítá pouze až do izomorfismus, sekvence 1, 1, 2, 5, 16, 63, 318,… (sekvence A000112 v OEIS ).

Lineární prodloužení

Částečná objednávka ≤^* na setu X je rozšíření jiného dílčího řádu ≤ zapnuto X za předpokladu, že pro všechny prvky X a y z Xkdykoli X ≤ y, je tomu také tak X ≤^* y. A lineární prodloužení je rozšíření, které je také lineárním (tj. celkovým) řádem. Každá dílčí objednávka může být rozšířena na celkovou objednávku (princip prodloužení objednávky ).^[9]

v počítačová věda, algoritmy pro hledání lineárních rozšíření dílčích řádů (reprezentovaných jako dosažitelnost objednávky směrované acyklické grafy ) jsou nazývány topologické třídění.

V teorii kategorií

Každý poset (a každý předobjednaná sada ) lze považovat za a kategorie kde, pro objekty X a y, existuje maximálně jeden morfismus z X na y. Přesněji řečeno, nechte hom (X, y) = {(X, y)} pokud X ≤ y (a jinak prázdná množina) a (y, z)∘(X, y) = (X, z). Takovým kategoriím se někdy říká posetal.

Posety jsou ekvivalent navzájem, pokud a pouze pokud jsou izomorfní. V posetu je nejmenší prvek, pokud existuje, znak počáteční objekt, a největší prvek, pokud existuje, je a koncový objekt. Každá předobjednaná sada je také ekvivalentní posetu. A konečně, každá podkategorie posetu je isomorfismus uzavřen.

Částečné objednávky v topologických prostorech

Li P je částečně uspořádaná množina, která také dostala strukturu a topologický prostor, pak je obvyklé to předpokládat ${displaystyle {(a, b): aleq b}}$ je Zavřeno podmnožina topologické produktový prostor ${displaystyle P imes P}$. Za tohoto předpokladu se dobře chovají vztahy dílčích řádů limity v tom smyslu, že pokud ${displaystyle a_ {i} o a}$, a ${displaystyle b_ {i} o b}$a pro všechny ${displaystyle i}$   ${displaystyle a_ {i} leq b_ {i}}$, pak ${displaystyle aleq b}$.^[10]

Intervaly

An interval v posetu P je podmnožina Já z P s majetkem, že pro všechny X a y v Já a jakékoli z v P, pokud X ≤ z ≤ y, pak z je také v Já. (Tato definice zobecňuje interval definice reálných čísel.)

Pro A ≤ b, uzavřený interval [A, b] je sada prvků X uspokojující A ≤ X ≤ b (tj. A ≤ X a X ≤ b). Obsahuje alespoň prvky A a b.

Pomocí odpovídajícího přísného vztahu "<" se otevřený interval (A, b) je sada prvků X uspokojující A < X < b (tj. A < X a X < b). Otevřený interval může být prázdný, i když A < b. Například otevřený interval (1, 2) na celá čísla je prázdná, protože nejsou žádná celá čísla Já takhle 1 < Já < 2.

The polootevřené intervaly [A, b) a (A, b] jsou definovány podobně.

Někdy jsou definice rozšířeny tak, aby umožňovaly A > b, v takovém případě je interval prázdný.

Interval Já je ohraničený, pokud existují prvky A a b z P takhle Já ⊆ [A, b]. Každý interval, který lze reprezentovat v intervalové notaci, je samozřejmě ohraničený, ale obrácení není pravdivé. Například pojďme P = (0, 1) ∪ (1, 2) ∪ (2, 3) jako podskupina reálná čísla. Podmnožina (1, 2) je ohraničený interval, ale nemá číslo infimum nebo supremum v P, takže jej nelze zapsat v intervalové notaci pomocí prvků P.

Poset se nazývá místně konečné pokud je každý ohraničený interval konečný. Například celá čísla jsou místně konečné podle jejich přirozeného uspořádání. Lexikografické pořadí na kartézském součinu ℕ × ℕ není od té doby lokálně konečné (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1).Pomocí intervalového zápisu vlastnost "A je pokryto b„lze ekvivalentně přeformulovat jako [A, b] = {A, b}.

Tento koncept intervalu v dílčím pořadí by neměl být zaměňován s konkrétní třídou dílčích řádů známou jako intervalové objednávky.

Viz také

Poznámky

Reference

• Deshpande, Jayant V. (1968). „O kontinuitě částečné objednávky“. Proceedings of the American Mathematical Society. 19 (2): 383–386. doi:10.1090 / S0002-9939-1968-0236071-7.
• Schmidt, Gunther (2010). Relační matematika. Encyklopedie matematiky a její aplikace. 132. Cambridge University Press. ISBN  978-0-521-76268-7.
• Bernd Schröder (11. května 2016). Objednané sady: Úvod do připojení od kombinatoriky k topologii. Birkhäuser. ISBN  978-3-319-29788-0.
• Stanley, Richard P. (1997). Enumerativní kombinatorika 1. Cambridge studia pokročilé matematiky. 49. Cambridge University Press. ISBN  0-521-66351-2.

externí odkazy

• OEIS sekvence A001035 (Počet posetů s n označené prvky)
• OEIS posloupnost A000112 (Počet částečně uspořádaných sad („posetů“) s n neoznačenými prvky.)