Rendelési viszony

Egy érdekében kapcsolatban egy sor egy bináris reláció a készletben, amely lehetővé teszi annak elemet kell összehasonlítani egymással konzisztens módon. Rendelési relációval felruházott halmaz rendezett halmaz . Azt is mondják, hogy a kapcsolat határozza meg ezen halmaz egy megbízás szerkezet vagy egész egyszerűen érdekében .

Definíciók és példák

Rendelési viszony

A rendelés kapcsán egy reflexív , antiszimmetrikus és tranzitív bináris reláció : legyen E az egy sor; egy belső kapcsolatot ≤ on E jelentése érdekében viszonyítva, ha minden x , y és z elemei E :

x ≤ x (reflexivitás)
( x ≤ y és y ≤ x ) ⇒ x = y (antiszimmetria)
( x ≤ y és y ≤ z ) ⇒ x ≤ z (transzitivitás)

Ezeknek az axiómáknak a formája lehetővé teszi számunkra, hogy megerősítsük, hogy azokat a reciprok bináris reláció is igazolja, ≥

y ≥ x akkor és csak akkor, ha x ≤ y .

A sorrend bármely relációjához tehát a sorrend ellentétes relációja társul ugyanabban a halmazban; az x ≤ y és y ≥ x képletek közömbösen olvashatók: " x kisebb, mint y ", vagy " x kisebb, mint y ", vagy " y nagyobb, mint x ", vagy " y nagyobb, mint x " (vagy néha " x egyenlő legfeljebb y-vel ", vagy " y legalább egyenlő x-szel ").

Kapcsolódunk a ≤ rend bármely relációjához, amely a szigorú sorrend néven ismert reláció, amelyet akkor megjegyezünk <(ami nem a korábban definiált értelemben vett rend reláció, mivel a reflexivitás nem teljesül), ami a sorrend relációjának korlátozása. a különálló elemek párjai:

x < y akkor és csak akkor, ha x ≤ y és x ≠ y .

Az x < y képletet szintén y > x-nek írják , és így hangzik: " x szigorúan kisebb, mint y ", vagy " x szigorúan kevesebb, mint y ", " y szigorúan nagyobb, mint x ", vagy " y szigorúan nagyobb, mint x ”.

A fenti meghatározás értelmében vett rendelési relációt néha tág rendnek nevezzük .

Egyes érdekében kapcsolatok teljes kapcsolatok , azaz két eleme E mindig hasonló : minden x , y az E :

x ≤ y vagy y ≤ x .

Ekkor azt mondjuk, hogy a ≤ viszonya áll a teljes rend , és a beállított E mostantól Teljesen rendezett ez a kapcsolat. Az E-vel kapcsolatos rend-relációról azt mondjuk, hogy részleges, ha nem teljes, és E- t ezután részben rendezik . Meg kell jegyezni, hogy angolul a részleges sorrend bármilyen rendet jelöl , ami tehát teljes lehet. Ezt a terminológiát néha a francia nyelvben is használják.

Rendezetten beállítva

A rendezett készlet egy rendelési relációval ellátott készlet. Ha egy rendezett halmaz véges, akkor azt grafikusan ábrázolhatjuk Hasse-diagram formájában , hasonlóan a papíron lévő grafikon szokásos ábrázolásához , ami megkönnyítheti a rajta való munkát. Ha végtelen, akkor megrajzolhatjuk Hasse-diagramjának egy részét.

Példák és ellenpéldák

A "kisebb (vagy egyenlő)" reláció a teljes sorrend viszonya az egész ( természetes vagy relatív ) halmazon, a racionális vagy a valós halmazon .
Rendezett halmaz ( E , ≤) alapján az E elem n -többszörösének halmazán a lexikográfiai sorrend a „szótári sorrend”, amelyet a hozzá tartozó szigorú sorrenddel egyszerűbb meghatározni : ( x 1 ,…, X n ) < ( y 1 ,…, y n ) ha x i = y i az összes i indexhez egy bizonyos k < n és x k +1 < y k +1 értékig .
A befogadás vonatkozásában, „egy részhalmaza az” vagy „tartalmaz” egy érdekében viszonyítva a beállított E részeinek egy sor X . Ha X véges, E véges (pontosabban, ha X tartalmaz n elemeket, E tartalmaz 2 n ). Az 1. ábra az ( E , ⊂) Hasse-diagramját mutatja n = 3 esetén.
Minden korlátozás egy részének F az E rend az E egy rendelést F . Különösen (az előző pont szerint): az X halmaz részeinek bármelyik F halmazán a beillesztés egy sorrend-reláció - ez a "példa" valójában általános: minden sorrend izomorf egy ilyen alakú sorrendhez képest;
Az oszthatósági reláció a természetes számok parciális rendű kapcsolata . A 2. ábra Hasse diagramját mutatja be 0 és 9 közötti egészekre való korlátozásáról.
Az, hogy a felvétel (lásd fent), a minden részében egy Descartes-szorzat U × V a relatív finomsága bináris kapcsolatok az U a V . Mert V = U , ez a kapcsolat lehetővé teszi, hogy például (a korlátozás, lásd fent) összehasonlítani köztük:
- Az egyenértékűség kapcsolatok az U (vagy, melynek összege ugyanaz: a válaszfalak az U );
- az U kapcsolati viszonyai .
Adott egy család ( E i ) i ∈ I megrendelt készletek, a természet rendje a termék készlet Π i ∈ I E i van a termék sorrendben , meghatározott:( x i ) i ∈ I ≤ ( y i ) i ∈ I akkor és csak akkor, ha bármely i index esetében x i ≤ y i .Például a forgatáson E I funkcióinak I rendezett halmaz E , sorrendben előállított adja meg: f ≤ g , ha minden i ∈ I , F ( i ) ≤ g ( i ). A ℝ ℝ értéken előállított sorrend esetében az egyik függvény kisebb, mint a másik, ha a görbéje mindig a másik görbe alatt van.
Mi lehet általánosítani Iexikografikus sorrendben (elején említett lista) a következőképpen: ha én is jól rendezett , definiáljuk végzését Π i ∈ I E i szerint:( x i ) i ∈ I <( y i ) i ∈ I akkor és csak akkor, ha vannak i indexek , amelyekre x i ≠ y i, és ha a legkisebb közülük x i < y i .Ha az E i megrendelések teljesek, akkor az ∏ i ∈ I E i lexikográfiai sorrendje is teljes (de általában nem a termék sorrendje).
Az előrendelés reláció általában nem rend reláció, mert hiányzik az antiszimmetria tulajdonsága. De az előrendelés bármely hányada a társított ekvivalencia-reláció alapján rend.
A nem üres halmaz szigorú rendkapcsolata nem sorrendkapcsolat, mert nem reflexív. Ha <szigorú sorrend E-n , akkor az " x < y vagy x = y " összefüggés E sorrendje .
A ciklikus sorrend relációja nem a sorrend kapcsolata, mert ez egy hármas reláció . De a három érv egyikének rögzítésével kapott bináris kapcsolatok szigorú rendi viszonyok.
A gyökerezett fa egy aciklusos irányított gráf, amely egy bizonyos részrend-relációhoz kapcsolódik, fontos a számítástechnikában.

Kapcsolódó fogalmak

Monoton alkalmazások

Ha $( E , \leq)$ és $( F , ≼)$ két rendezett halmaz, akkor azt mondják, hogy az $E-$ től $F-$ ig terjedő $f$ térkép növekszik (vagy néha tág értelemben növekszik, vagy izotóniás), amikor megőrzi a rendet, csökken ( tág értelemben), vagy antiton, amikor ezt megfordítja, vagyis:

f

növekszik, amikor minden

x

és

y

E

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

;

f

csökken, amikor az összes

x

és

y

E

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

Azt mondják, hogy szigorúan monoton növekvő , ha tartja a szigorú sorrendben: minden $x$ és $y$ az $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

és szigorúan monoton csökken , ha megfordítja ez: az összes $x$ és $y$ a $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Megjegyzendő, hogy ha egyre térkép $( E , \leq)$ a $( F , ≼)$ az injektív akkor szigorúan növekvő, de a fordítottja hamis általában (ez azonban igaz, ha a rendet $E$ jelentése összesen).

A tág értelemben vett monoton vagy monoton alkalmazás (ill. Szigorúan monoton) növekvő vagy csökkenő alkalmazás (ill. Szigorúan növekvő vagy szigorúan csökkenő).

A kölcsönös bijekciót egy növekvő bijekciót $F : ( E , \leq) \to ( F , ≼)$ nem feltétlenül növekszik (Vegyük például a térképezési identitását , az $E$ = ℝ felruházott sorrendjének egyenlőség az $F$ = ℝ látva a szokásos rendelés). Ez azonban akkor van, ha ≤ teljes (ha $f -1 ( y 1 ) \geq f -1 ( y 2 ),$ akkor $f$ növekedésével , $y 1 ≽ y 2.$ Ezért ellentétes : ha $y 1 ≺ y 2$ és ha ≤ teljes, akkor $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

Egy közötti izomorfizmus két megrendelt készletek $( E , \leq)$ és $( F , ≼)$ az bijekciót $f$ re $E$ figyelembe $F$ amely növekszik, és amelynek ellenkezője növekszik, ami annyit jelent, hogy $f$ egy bijektív és kielégíti minden $x$ és $y$ a $E$ :

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

Egy beágyazást megrendelt készleteket $( E , \leq)$ a $( F , ≼)$ térképe $f$ re $E$ és $F$ kielégíti minden $x$ és $y$ az $E$ :

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

(egy ilyen alkalmazás szükségszerűen injekciós jellegű ). A rendi izomorfizmusok tehát szürjektív beágyazások .

A rendezett halmazok kategóriájában a morfizmusok definíció szerint a növekvő térképek, az izomorfizmusok tehát a fentiekben bemutatottak.

Legnagyobb elem és maximális elem

Rendezett E halmazban nem feltétlenül létezik nagyobb elem . Ha E véges, akkor (legalább) egy maximális elemet tartalmaz . Ha E egy végtelen induktív halmaz , Zorn lemma még garantálja, hogy létezik egy maximális elem.

Szigorú rend kapcsolat

Láttuk, hogy az E halmazon ≤ rendű relációhoz természetesen társítunk egy < E relációt , amely ekkor szigorú rend relációja , vagyis anti-reflexív ( x < x n 'igaz bármelyikre eleme x az E ) és tranzitív.

Bármely szigorú sorrend-kapcsolat antiszimmetrikus , sőt aszimmetrikus is (ami egyenértékű: antiszimmetrikus és antireflektív), vagyis minden x és y esetében :

x < y ⇒ nem ( y < x) .

Következésképpen kölcsönösen, az E-nél szigorú <sorrend bármilyen relációjával társíthatjuk az ≤ E sorrend relációját az E-hez , feltéve:

x ≤ y akkor és csak akkor, ha x < y vagy x = y .

Könnyű ellenőrizni, hogy e két konstrukció végről végére történő elrendelésével, egy sorrend vagy szigorú sorrend alapján, megtaláljuk a kiindulási összefüggést. Ezért az axiomatizációk egyikének vagy másikának megválasztása önmagában nem fontos.

Szigorú sorrendben az összeget a következőképpen fejezzük ki:

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

és akkor azt mondjuk, hogy ez a teljes szigorú rend viszonya . A teljes reláció fogalmával nem lehet összetéveszteni , mert a szigorú rendi viszonyok antreflexívek, míg a totális kapcsolatok reflexívek.

Egy szigorú teljes rend, a három lehetőség - x < y , x = y és y < x - exkluzív, és néha beszélni, következő Cantor , a hármas felosztás ingatlan .

Aciklusos kapcsolat

A tranzitív visszaható bezárása egy kapcsolatban R jelentése sorrendben kapcsolatban -, vagy ismét: a tranzitív lezárása az R jelentése antiszimmetrikus - ha, és csak akkor, ha R jelentése aciklikus .

R tranzitív lezárása akkor és csak akkor szigorú sorrend, ha R szigorúan aciklikus, azaz ha gráfja aciklikus .

Sorrend reláció tagadása (vagy kiegészítése)

A halmazon definiált bináris reláció tagadása a gráf kapcsolata, amely kiegészíti az in- jét . Megjegyezzük . Más szavakkal, két elem akkor és csak akkor kapcsolódik egymáshoz, ha nem . $R$ $NÁL NÉL$ $R$ $A \ szer A$ $\ nem \! R$ $\ nem \! R$ $R$

Ha azt mondjuk, hogy egy megrendelés teljes, az azt jelenti, hogy negációja a szigorú fordított sorrend. Vagyis a sorrendben ekvivalencia van: $\ leqslant$

$\ leqslant$ teljes;
$x \ not \ leqslant y \ iff y <x$ .

Másrészt, amint két különálló elem létezik, amelyek nem hasonlíthatók össze egy rendeléssel, annak tagadása nem lehet (szigorú vagy tág) sorrend, mert nem antiszimmetrikus. A nem teljes megrendelés tagadása tehát soha nem parancs.

Például, a tagadása a felvétel ⊄ a sor a részei egy sor, legalább két elem nem egy sorrendben, mert, ha egy ≠ b , mindig van { a } ≠ { b } a azonban { a } ⊄ { b } és { b } ⊄ { a }.

Kettős sorrend

A kettős érdekében (vagy fordított sorrendben ) egy rendezett halmaz P = ( E , ≤) a rendezett halmaza P op = ( E , ≤ op ), ha ≤ op az ellenkező sorrendben kapcsolatban a ≤, c „azaz a kapcsolatban ≥ (néha * helyett op-ot használunk ).

A bidual ( P op ) op a P egyenlő P .

Előrendelés

Az előrendelés egy reflexív és transzitív bináris reláció .

Bármilyen előrendelésre ℛ egy sor $E$ indukál érdekében kapcsolatban a forgatáson $E$ quotiented a ekvivalenciareláció ~ által meghatározott „ $x ~ y , ha, és csak akkor, ha ( x ℛ y és y ℛ x )$ ”.

További részletek és példák a részletes cikkben találhatók.

Kiegészítő tulajdonságok

Kompatibilitás

A rendelési reláció kompatibilitása egy algebrai struktúrával csak eseti alapon határozható meg.

A félcsoporton ( G , +) szereplő ≤ sorrend akkor mondható kompatibilisnek, ha a G összes x , y és z esetében úgy, hogy x ≤ y , x + z ≤ y + z és z + x ≤ z + y . Ha ( G , +) csoport , akkor azt mondjuk, hogy ( G , +, ≤) rendezett csoport , és hogy egy elem pozitív, ha nagyobb, mint a semleges elem . Bármely teljesen rendezett archimedesi csoport jelentése Abel és elmerül a ( ℝ , +, ≤).
Egy gyűrűt vagy egy mezőt ( A , +, ×) akkor mondunk rendezettnek, ha annak ≤ olyan sorrendje van, hogy ( A , +, ≤) rendezett csoport, és két pozitív elem szorzata pozitív.
Bármely teljesen rendezett arkhimédészi test belemerül (ℝ, +, ×, ≤).
Teljesen rendezett mezőben a –1 soha nem négyzet vagy akár négyzetösszeg.
A rendezett vektortér (de) egy valós vektortér ( E , +, ∙), amelynek rendje ≤ olyan, hogy ( E , +, ≤) rendezett csoport, és hogy a pozitív valós bármely vektorterméke pozitív vektorral pozitív.

Jól rendezett készlet

A rendezett készletet akkor mondjuk jól rendezettnek, ha minden nem üres részhalmaznak van egy legkisebb eleme .

Lugas

A halmazt rácsnak nevezzük, ha rendezett, és ha bármely elempárnak van felső és alsó határa .

Alkalmazások

Rend topológia

A rendezett halmaz több sorrendből eredő topológiával is ellátható : a sorrend topológiája, a jobb oldali rend topológiája és a bal oldali rend topológiája.

Kapcsolatok egyszerűsítő komplexumokkal

Az egyszerűsítő komplexek fontos osztálya a véges rendezett halmazokból származik. Definiáljuk a komplex sorrendben D (P) egy véges rendezett halmaza, P, hogy a készlet a láncok P. A komplex rend triviális egy simplicial komplex.

A rendezett halmaz tanulmányozása önmagában ad információt annak rendelési komplexumáról, ezért érdekes egy egyszerűsített komplexet, mint egy rendezett halmaz rendelési komplexumát tanulmányozni.

Megjegyzések és hivatkozások

N. Bourbaki , A matematika elemei : halmazelmélet [ a kiadások részlete ], P. III.4 .
Bourbaki , p. III.5.
(in) AG Kurosh , Előadások a General Algebra , Pergamon Press ,1965( online olvasható ) , p. 11..
Bourbaki , p. III.22-23.
Nathalie Caspard, Bruno Leclerc és Bernard Monjardet, véges rendezett halmazok: fogalmak, eredmények és felhasználások , Springer,2007( online olvasható ) , p. 73..
Bourbaki , p. III.7 és III.14.
Gustave Choquet , Elemzési tanfolyam , 1966, p. 23 .
(in) Steven Roman, Rácsok és rendezett készletek , Springer ,2008, 305 p. ( ISBN 978-0-387-78900-2 , online olvasás ) , p. 13..
Roman 2008 , p. 284.
Például J. Riguet , „ Bináris kapcsolatok, lezárások, Galois levelezése ”, Bull. Soc. Math. Fr. , vol. 76,1948, P. 114–155 ( online olvasás ).
(en) George Bergman (en) , Meghívó általános algebra és univerzális konstrukciókra , Cham, Springer ,2015, 2 nd ed. ( 1 st ed. 1988), 572 p. ( ISBN 978-3-319-11478-1 , online olvasás ) , p. 113.
Bourbaki , p. III.4 és III.77.
Jean-Pierre Ramis , André Warusfel et al. , All-in-one matematika a licenchez : L1 szint , Dunod ,2013, 2 nd ed. ( online olvasható ) , p. 37.

Lásd is

Kapcsolódó cikkek

Antikain
Rendezett test
Galois levelezés
Ideális (rendeléselmélet)
Rend , matematikai folyóirat, amely a megrendelések elméletével foglalkozik
Megalapozott rend
Ciklikus rend
Teljes részrendelés
Kezdő szakasz
Szpilrajn kiterjesztés tétel
Rendelés típusa

Bibliográfia

(en) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ a kiadások részlete ] ( online bemutató )
(en) Efe A. Ok, Rendeléselmélet és alkalmazásai ( online )