Rendezett halmaz

A halmazelméletben rendezési reláció (vagy röviden rendezés) alatt a szövegkörnyezettől függően vagy részbenrendezést vagy pedig teljes rendezést (más néven lineáris rendezést) értünk. Mindkét esetben egy olyan relációról van szó, amely reflexív, antiszimmetrikus és tranzitív, de a teljes rendezés esetében megköveteljük még azt is, hogy az adott relációban bármely két elem összehasonlítható legyen. Részbenrendezett halmaz teljesen rendezett részhalmazát láncnak is szokás nevezni.

Meg kell jegyezni, hogy a szakirodalom nem egységes abban, hogy a reflexivitást meg kell-e követelni a fenti definíciókban és így kétféle fogalmat is szokás rendezési relációként definiálni: gyenge rendezési reláció (reflexív, antiszimmetrikus, tranzitív), ill. szigorú rendezési reláció (irreflexív, antiszimmetrikus, tranzitív).

Matematikailag a fenti megkülönböztetésnek nincs túl nagy szerepe, mert bármelyik gyenge rendezéshez egyértelműen tartozik egy szigorú rendezés például a következőképpen: a gyenge rendezésből kivesszük azokat az elemeket melyek a reflexivitás okán kerültek be.

Egy olyan halmazt, melyen rendezés van értelmezve, rendezett struktúrának, rendezési struktúrának vagy rendezett halmaznak nevezünk.

Definíció

Legyen ${\displaystyle U}$ tetszőleges halmaz, efelett pedig egy ${\displaystyle R\subseteq U\times U}$ homogén kétváltozós reláció. Legyen továbbá ${\displaystyle E_{U}}$ az olyan ${\displaystyle U}$-beli rendezett párok halmaza, az ún. egységreláció, melyek első koordinátái megegyeznek második koordinátáikkal. A fenti ${\displaystyle R}$ reláció akkor és csak akkor (gyenge) részbenrendezés ${\displaystyle U}$ felett, ha teljesülnek a következő feltételek:

• ${\displaystyle E_{U}\subseteq R}$ avagy ${\displaystyle \forall a\in U:\ aRa}$ (reflexivitás);
• ${\displaystyle RR^{-1}\subseteq E_{U}}$ avagy ${\displaystyle \forall a,b\in U:\ \left(aRb\wedge bRa\right)\Rightarrow a=b}$ (antiszimmetria);
• ${\displaystyle RR\subseteq R}$ avagy ${\displaystyle \forall a,b,c\in U:\ \left(aRb\wedge bRc\right)\Rightarrow aRc}$ (tranzitivitás).

Teljes rendezésnek vagy lineáris rendezésnek, illetve röviden rendezésnek nevezzük azokat a részbenrendezéseket, amelyekben bármely két elem összehasonlítható, azaz:

• ${\displaystyle \forall a,b\in U:aRb\vee bRa}$.

Az ${\displaystyle (A;R)}$ párt rendezett halmaznak nevezzük, ha ${\displaystyle A}$ tetszőleges halmaz, ${\displaystyle R}$ pedig ${\displaystyle A}$-n értelmezett rendezés.

Szigorú rendezés és gyenge rendezés

A szigorú rendezés és a gyenge rendezés fogalmai egyszerűen egymásba alakíthatóak:

• Legyen ${\displaystyle \sqsubset }$ egy szigorú rendezés U-n. Ekkor definiálunk hozzá egy gyenge ${\displaystyle \sqsubseteq }$ rendezést a következőképp: ${\displaystyle \sqsubseteq :=\sqsubset \cup id_{U}}$. Tehát ${\displaystyle \sqsubset }$-t kibővítjük az U feletti egységrelációval. Másképp ${\displaystyle \forall a,b\in U:\ a\sqsubseteq b\ :\Leftrightarrow \left(a\sqsubset b\vee a=b\right)}$ .
• Hasonlóan, legyen ${\displaystyle \sqsubseteq }$ egy gyenge rendezés U-n. Ekkor definiálunk hozzá egy ${\displaystyle \sqsubset }$ erős rendezést a következőképp: ${\displaystyle \sqsubset :=\sqsubseteq \setminus id_{U}}$. Tehát ${\displaystyle \sqsubseteq }$-t szűkítjük, kivonva a két azonos elemből álló párok halmazát. Másképp ${\displaystyle \forall a,b\in U:\ a\sqsubset b\ :\Leftrightarrow \left(a\sqsubseteq b\wedge a\neq b\right)}$ .

Nem nehéz belátni, hogy valóban a megfelelő reláció szigorú, ill. gyenge rendezés lesz.

• Ha ${\displaystyle \sqsubset }$ egy szigorú teljes rendezés ${\displaystyle U}$-n, akkor ${\displaystyle \forall a,b\in U:a\sqsubset b\vee b\sqsubset a\vee a=b}$.
• Ha ${\displaystyle \sqsubseteq }$ egy gyenge teljes rendezés ${\displaystyle U}$-n, akkor ${\displaystyle \forall a,b\in U:a\sqsubseteq b\vee b\sqsubseteq a}$.

Sorozatok rendezettsége

Rendezett halmaz elemeiből képzett ${\displaystyle a_{1},\dots ,a_{n}}$ és ${\displaystyle b_{1},\dots ,b_{n}\,(n\in \mathbb {N} )}$ véges sorozatokat egyformán rendezettnek nevezünk, ha bármely ${\displaystyle i\neq j}$ esetén ${\displaystyle a_{i}\sqsubseteq a_{j}\Rightarrow b_{i}\sqsubseteq b_{j}}$; illetve ellentétesen rendezettnek nevezünk, ha bármely ${\displaystyle i\neq j}$ esetén ${\displaystyle a_{i}\sqsubseteq a_{j}\Rightarrow b_{i}\sqsupseteq b_{j}}$.

Példák

• ℕ-ben ≤, ti. a≤b :⇔ ∃d∈ℕ: b = a+d a szokásos „additív”, nagyság szerinti rendezés
• ℝ-ben ≤, ti. a≤b :⇔ ∃d∈ℝ⁺: b = a+d a szokásos „additív”, nagyság szerinti rendezés.
• egy ${\displaystyle A}$ halmaz részhalmazainak ${\displaystyle P(A)}$ halmazában a ${\displaystyle \subseteq }$ tartalmazási reláció részbenrendezés
• a természetes számok halmazában az oszthatósági reláció részbenrendezés

Lásd még

• Részbenrendezés
• Jólrendezés
• Hausdorff–Birkhoff-tétel

Hivatkozások

• Rédei László: Algebra I., Akadémiai Kiadó, Budapest (1954)
• Szász Gábor: Bevezetés a hálóelméletbe, Akadémiai Kiadó, Budapest (1959)
• Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged (1994)

Külső hivatkozások

• Alice és Bob - 12. rész: Alice és Bob rendet tesz
• Alice és Bob - 15. rész: Alice és Bob az absztrakció útján
• Alice és Bob - 19. rész: Alice és Bob ideáljai
• Ordered Set a MathWorld oldalán
• Totally Ordered Set a MathWorld oldalán