Vztah objednávky

Vztah pořadí v sadě je binární relace v tomto souboru, která umožňuje jeho prvky, které mají být v porovnání s navzájem v konzistentním způsobem. Sada obdařená relací objednávky je objednávaná sada . Také říkáme, že relace definuje na této množině strukturu objednávky nebo jednoduše objednávku .

Definice a příklady

Vztah objednávky

Relační řád je reflexivní , antisymetrický a přechodný binární vztah : nechť E je množina; vnitřní vztah ≤ na E je příkaz vztah, jestliže pro všechny x , y a z, prvky E :

x ≤ x (reflexivita)
( x ≤ y a y ≤ x ) ⇒ x = y (antisymetrie)
( x ≤ y a y ≤ z ) ⇒ x ≤ z (tranzitivita)

Samotná forma těchto axiomů nám umožňuje potvrdit, že jsou také ověřeny vzájemným binárním vztahem ≥, definovaným

y ≥ x právě tehdy, když x ≤ y .

S libovolným vztahem řádu je tedy spojen opačný vztah řádu na stejné množině; vzorce x ≤ y a y ≥ x lze číst lhostejně: „ x je menší než y “ nebo „ x je menší než y “ nebo „ y je větší než x “ nebo „ y je větší než x “ (nebo někdy „ x je nanejvýš rovno y “ nebo „ y je přinejmenším rovno x “).

Spojujeme také s jakýmkoli vztahem řádu ≤, vztahem známým jako přísné pořadí , který je uveden <(což není řádový vztah ve smyslu definovaném dříve, protože reflexivita není uspokojena), což je omezení vztahu řádu k páry odlišných prvků:

x < y právě tehdy, když x ≤ y a x ≠ y .

Vzorec x < y se také píše y > x a zní: „ x je přísně menší než y “ nebo „ x je přísně menší než y “, „ y je přísně větší než x “ nebo „ y je přísně větší než x “.

Řádový vztah ve smyslu výše uvedené definice se někdy označuje jako široký řád .

Některé pořadí vztahy jsou celkem vztahy , to znamená dva prvky E jsou vždy srovnatelné : pro všechny x , y z E :

x ≤ y nebo y ≤ x .

Potom řekneme, že ≤ je vztah celkového řádu a že množina E je tímto řádem zcela uspořádána . Relační řád na E se říká, že je částečný, pokud není celkový, a E je pak částečně uspořádaný . Je třeba poznamenat, že v angličtině částečná objednávka označuje jakoukoli objednávku, která může být tedy celková. Tato terminologie se někdy používá i ve francouzštině.

Řádná sada

Objednaná sada je sada vybavená relací objednávky. Pokud je uspořádaná množina konečná, může být graficky znázorněna ve formě Hasseova diagramu , podobně jako obvyklá reprezentace grafu na papíře, což usnadňuje práci na ní. Pokud je nekonečný, můžeme nakreslit část jeho Hasseho diagramu.

Příklady a protiklady

Vztah „je menší (nebo rovný)“ je vztah celkového řádu na množině celých čísel ( přirozených nebo relativních ), na množině racionálních nebo množině reálných .
Vzhledem k uspořádané množině ( E , ≤) je lexikografický řád na množině n -uples prvků E „slovníkovým řádem“, který lze snáze definovat přidruženým přísným řádem : ( x 1 ,…, X n ) < ( y 1 ,…, y n ) pokud x i = y i pro všechny indexy i do určitého k < n a x k +1 < y k +1 .
Vztah začlenění, „je podmnožinou z“ nebo „je obsažena v“ je vztah pořadí na nastavené E z částí nastavené X . Pokud X je konečný, E je konečný (přesněji, pokud X obsahuje n prvků, E obsahuje 2 n ). Obrázek 1 představuje Hasseův diagram ( E , ⊂) pro n = 3.
Jakékoliv omezení na část F z E objednávky na E je o řád F . Zejména (podle předchozího bodu): na libovolné množině F částí množiny X je zahrnutí řádovým vztahem - tento „příklad“ je ve skutečnosti obecný: každý řád je izomorfní s řádem této formy;
Relace dělitelnosti je relace dílčího řádu na přirozených číslech . Obrázek 2 představuje Hasseův diagram omezení na celá čísla od 0 do 9.
Pořadí začleňování (viz výše), na všech částech kartézského produktu U x V je relativní jemnost binárních relací z U v V . U V = U tento vztah umožňuje například (podle omezení, viz výše) jejich vzájemné porovnání:
- je ekvivalence na U (nebo, což je totéž: jsou příčky z U );
- že objednávka vztahy na U .
Vzhledem k tomu, rodina ( E i ) i ∈ I uspořádaných množin, přirozený řád o sadu produktů Π i ∈ I E i je v pořadí produktů , definovaný:( x i ) i ∈ I ≤ ( y i ) i ∈ I tehdy a jen tehdy, když pro jakýkoli index i , x i ≤ y i .Například na množině E I funkcí I v uspořádané množině E je vytvořené pořadí dáno vztahem: f ≤ g, pokud pro všechna i ∈ I , f ( i ) ≤ g ( i ). U pořadí vytvořeného na ℝ ℝ je jedna funkce menší než jiná, pokud je její křivka vždy pod druhou křivkou.
Můžeme zobecnit lexicographic objednávky (uvedené na začátku seznamu) takto: pokud bych je dobře uspořádané , definujeme pořadí o n i ∈ I E I podle:( x i ) i ∈ I <( y i ) i ∈ I tehdy a jen tehdy, když existují indexy i, pro které x i ≠ y i a pokud pro nejmenší z nich máme x i < y i .Pokud jsou objednávky na E i celkové, je lexikografické pořadí na ∏ i ∈ I E i také celkové (ale ne obecně objednávka produktu).
Preorder vztah není objednávka vztah obecně, protože to postrádá vlastnost antisymetrie. Ale jakýkoli kvocient předobjednávky přidruženým vztahem ekvivalence je řád.
Přísný řád vztah na nonempty není vztah pořadí, protože to není reflexivní. Je-li <je přísný pořadí na E , vztah „ x < y nebo x = y “ je o řád E .
Vztah cyklickém pořadí není vztah pořadí, protože to je ternární vztah . Ale binární vztahy získané stanovením jednoho ze tří argumentů jsou vztahy přísného řádu.
Kořeny strom je acyklický orientovaný graf spojena s konkrétní dílčí objednávky vztahu, důležitý v oblasti počítačové vědy.

Související pojmy

Monotónní aplikace

Pokud $( E , \leq)$ a $( F , ≼)$ jsou dvě uspořádané množiny, říká se , že mapa $f$ od $E$ do $F$ roste (nebo někdy roste v širším slova smyslu, nebo je izotonická), když zachovává pořadí, klesá (v v širokém smyslu), nebo antimon, když obrátí tento, to znamená, že:

f

se zvyšuje, když pro všechny

x

y

E

x \leq y \Rightarrow f ( x ) ≼ f ( y )

;

f

klesá, když pro všechny

x

y

E

x \leq y \Rightarrow f ( x ) ≽ f ( y )

Říká se, že musí být přísně rostoucí , když se udržuje striktní pořadí: pro všechny $x$ a $y$ z $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

a přísně klesá , když se obrátí: pro všechny $x$ a $y$ z $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Všimněte si, že v případě, že zvyšující se mapa $( E , \leq)$ v $( F , ≼)$ je injective pak je přísně rostoucí, ale že hovořit je falešný obecně (je však pravda, v případě, že pořadí na $E$ je celkem).

Monotónní nebo monotónní aplikace v širším slova smyslu (resp. Přísně monotónní) je aplikace rostoucí nebo klesající (resp. Přísně rostoucí nebo přísně klesající).

Reciproční bijection z rostoucí bijekci $f : ( E , \leq) \to ( F , ≼)$ nemusí být nutně zvyšuje (se například na mapování identity , z $E$ = ℝ obdařen pořadí rovnosti v $F$ = ℝ opatřené obvyklým objednat). Je-li však ≤ je celkem (pokud $f -1 ( y 1 ) \geq f -1 ( y 2 ),$ poté, růstem $f$ , $y 1 ≽ y 2.$ Takže contraposed : jestliže $y 1 ≺ y 2$ a pokud ≤ je celkem, pak $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

Izomorfismus mezi dvěma uspořádaných množin $( E , \leq)$ a $( F , ≼)$ je bijection $f$ z $E$ do $F$ , která se zvyšuje a jehož opačný se zvyšuje, což představuje tím, že $f$ je bijective a splňuje pro všechny $x$ a $y$ z $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

Vkládání uspořádaných množin z $( E , \leq)$ do $( F , ≼)$ je mapa $f$ od $E$ až $F$ , vyhovující pro všechny $x$ a $y$ z $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

(taková žádost je nutně injektivní ). Řádové izomorfismy jsou proto surjektivní vložení .

V kategorii uspořádaných množin jsou morfismy podle definice rostoucími mapami a izomorfismy jsou tedy ty, které byly zavedeny výše.

Největší prvek a maximální prvek

V uspořádané množině E nemusí nutně existovat větší prvek . Pokud je E konečné, bude obsahovat (alespoň) jeden maximální prvek . Pokud E je nekonečná indukční množina , Zornovo lemma stále zaručuje existenci maximálního prvku.

Přísný vztah objednávky

Vidíme, že ke vztahu stavu ≤ ke stanovenému E , přirozeně přiřadit vztah <na E , který je pak vztah přesném pořadí , tj. Antireflexive ( x < x n 'platí pro jakékoli prvek x z E ) a tranzitivní.

Jakýkoli přísný řádový vztah je však antisymetrický a dokonce asymetrický (což je ekvivalentní: antisymetrický a antireflektivní), to znamená, že pro všechna x a y :

x < y ⇒ ne ( y < x) .

V důsledku toho lze recipročně s jakýmkoli vztahem řádu přísného <na E spojit vztah řádu ≤ na E tím, že představuje:

x ≤ y právě tehdy, když x < y nebo x = y .

Je snadné ověřit, že uspořádáním těchto dvou konstrukcí od začátku do konce, z objednávky nebo přísného řádu, najdeme počáteční vztah. Volba jedné nebo druhé z axiomatizací proto není sama o sobě důležitá.

U přísného pořadí je souhrn vyjádřen následovně:

∀ x , y ∈ E ( x < y nebo x = y nebo y < x ).

a my pak říkáme, že se jedná o vztah úplného přísného řádu . Neexistuje žádná možná záměna s pojmem totální relace , protože vztahy přísného řádu jsou antireflexní, zatímco totální vztahy jsou reflexivní.

Přísného celkového pořadí, tři možnosti - x < y , x = y a y < x - jsou exkluzivní, a my se občas mluví po Cantor , z trichotomii majetku .

Acyklický vztah

Tranzitivní reflexivní uzávěr z relace R je příkaz vztah - nebo znovu: ZAŘÍZENÍ tranzitivním uzávěrem z R je antisymetrická - právě tehdy, když R je acyklická .

Tranzitivní uzavření R je přísné pořadí právě tehdy, když R je přísně acyklický, tj. Pokud je jeho graf acyklický .

Negace (nebo doplněk) vztahu objednávky

Negace binární relace definované na sadě je vztah Graph komplementární o to v . Bereme to na vědomí . Jinými slovy, dva prvky jsou spojeny tím, zda a pouze v případě, že tomu tak není . $R$ $NA$ $R$ $A \ krát A$ $\ ne \! R$ $\ ne \! R$ $R$

Chcete-li říci, že objednávka je úplná, znamená to, že její negace je přísné obrácené pořadí. To znamená, že existuje ekvivalence pro pořadí mezi: $\ leqslant$

$\ leqslant$ je celkem;
$x \ not \ leqslant y \ iff y <x$ .

Na druhou stranu, jakmile existují dva odlišné prvky, které nejsou příkazem srovnatelné, jeho negace nemůže být příkazem (přísným nebo širokým), protože není antisymetrický. Negace jiné než celkové objednávky proto nikdy není objednávkou.

Například, negace zařazení ⊄ na množině částí sady nejméně dvou prvků, není pořadí, protože, pokud ≠ b , máme vždy { } ≠ { b } se však { } ⊄ { b } a { b } ⊄ { a }.

Duální objednávka

Dvojí pořadí (nebo obráceném pořadí ) z uspořádaná množina P = ( E , ≤) je uspořádaná množina P op = ( E , ≤ op ), kde ≤ op je opačné pořadí vztah ≤, c ‚, tj vztah ≥ (někdy používáme * místo op ).

Bidual ( P op ) op z P se rovná P .

Předobjednávka

Preorder je reflexivní a tranzitivní binární relace .

Jakákoli předobjednávka ℛ na množině $E$ indukuje relační řád na množině $E$ kvocientově vztahem ekvivalence ~ definovaným „ $x ~ y právě a jen tehdy ( x ℛ y a y ℛ x )$ “.

Další podrobnosti a příklady najdete v podrobném článku.

Doplňkové vlastnosti

Kompatibilita

Kompatibilitu relace objednávky s algebraickou strukturou lze definovat pouze případ od případu.

Příkaz ≤ na polovinu skupiny ( G , +), se říká, že jsou slučitelné, jestliže pro všechny x , y a z, v G tak, že x ≤ y , máme x + z ≤ y + z a z + x ≤ z + y .
Když ( G , +) je skupina , pak řekneme, že ( G , +, ≤) je uspořádaná skupina a že prvek je kladný, pokud je větší než neutrální prvek .
Jakákoli plně uspořádaná archimédská skupina je abelianská a je ponořena do ( ℝ , +, ≤).
Kruh nebo pole ( , +, x) se říká, že objednat , pokud má příkaz ≤ takové, že ( , +, ≤) je uspořádaná skupina a produkt ze dvou pozitivních prvků je pozitivní. Jakékoli plně objednané archimédovské tělo je ponořeno do (ℝ, +, ×, ≤). Ve zcela uspořádaném poli –1 nikdy není čtverec nebo dokonce součet čtverců.
Objednat vektorový prostor (de) je reálný vektorový prostor ( E , +, ∙) obdařen pořadí ≤ tak, že ( E , +, ≤) je uspořádaná skupina a že jakýkoliv vektor produkt pozitivní reálné kladným vektorem je pozitivní.

Dobře uspořádaná sada

Uspořádaná množina je prý dobře objednal jestliže každý podmnožina není vyprázdnění tato sada má nejmenší prvek .

Mřížoví

Sada se nazývá mříž , je-li nařízena a pokud některá dvojice prvků má horní a dolní hranici .

Aplikace

Objednávejte topologii

Objednaná sada může být opatřena několika topologiemi vyplývajícími z objednávky : topologie objednávky, topologie objednávky vpravo a topologie objednávky vlevo.

Odkazy na zjednodušené komplexy

Důležitá třída zjednodušených komplexů pochází z konečných uspořádaných množin. Definujeme komplex řádu D (P) konečné množiny P jako množinu řetězců P. Komplex řádu je triviálně zjednodušený komplex.

Studium uspořádané množiny samo o sobě poskytuje informace o jejím řádovém komplexu, a proto je zajímavé studovat zjednodušený komplex jako řádový komplex uspořádané množiny.

Poznámky a odkazy

N. Bourbaki , Základy matematiky : Teorie množin [ detail vydání ], str. III.4 .
Bourbaki , str. III.5.
(in) AG Kurosh , Přednášky v obecné algebře , Pergamon Press ,1965( číst online ) , s. 11.
Bourbaki , str. III.22-23.
Nathalie Caspard, Bruno Leclerc a Bernard Monjardet, Konečné uspořádané množiny: koncepty, výsledky a použití , Springer,2007( číst online ) , s. 73.
Bourbaki , str. III.7 a III.14.
Gustave Choquet , Kurz analýzy , 1966, s. 23 .
(in) Steven Roman, Mřížky a objednané sady , Springer ,2008, 305 s. ( ISBN 978-0-387-78900-2 , číst online ) , s. 13.
Roman 2008 , s. 284.
Například J. Riguet , „ Binární vztahy, uzávěry, korespondence Galois “, Bull. Soc. Matematika. Fr. , sv. 76,1948, str. 114-155 ( číst online ).
(en) George Bergman (en) , Pozvánka na obecnou algebru a univerzální konstrukce , Cham, Springer ,2015, 2 nd ed. ( 1 st ed. 1988), 572 str. ( ISBN 978-3-319-11478-1 , číst online ) , s. 113.
Bourbaki , str. III.4 a III.77.
Jean-Pierre Ramis , André Warusfel a kol. , All-in-one Mathematics for the License: Level L1 , Dunod ,2013, 2 nd ed. ( číst online ) , s. 37.

Podívejte se také

Související články

Antichaine
Řádné tělo
Galoisova korespondence
Ideální (teorie objednávek)
Objednávka , matematický časopis zabývající se teorií objednávek
Opodstatněný řád
Cyklický řád
Plná částečná objednávka
Sekce pro začátečníky
Věta o rozšíření Szpilrajn
Typ objednávky

Bibliografie

(en) Richard P. Stanley , Enumerative Combinatorics , sv. 1 [ detail vydání ] ( online prezentace )
(en) Efe A. Ok, Teorie objednávek a její aplikace ( číst online )