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

• $E_{U}\subseteq R$ avagy $\forall a\in U:\ aRa$ (reflexivitás);
• $RR^{-1}\subseteq E_{U}$ avagy $\forall a,b\in U:\ \left(aRb\wedge bRa\right)\Rightarrow a=b$ (antiszimmetria);
• $RR\subseteq R$ avagy $\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:

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

Az $(A;R)$ párt rendezett halmaznak nevezzük, ha $A$ tetszőleges halmaz, $R$ pedig $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 $\sqsubset$ egy szigorú rendezés U-n. Ekkor definiálunk hozzá egy gyenge $\sqsubseteq$ rendezést a következőképp: $\sqsubseteq :=\sqsubset \cup id_{U}$. Tehát $\sqsubset$-t kibővítjük az U feletti egységrelációval. Másképp $\forall a,b\in U:\ a\sqsubseteq b\ :\Leftrightarrow \left(a\sqsubset b\vee a=b\right)$ .
• Hasonlóan, legyen $\sqsubseteq$ egy gyenge rendezés U-n. Ekkor definiálunk hozzá egy $\sqsubset$ erős rendezést a következőképp: $\sqsubset :=\sqsubseteq \setminus id_{U}$. Tehát $\sqsubseteq$-t szűkítjük, kivonva a két azonos elemből álló párok halmazát. Másképp $\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 $\sqsubset$ egy szigorú teljes rendezés $U$-n, akkor $\forall a,b\in U:a\sqsubset b\vee b\sqsubset a\vee a=b$.
• Ha $\sqsubseteq$ egy gyenge teljes rendezés $U$-n, akkor $\forall a,b\in U:a\sqsubseteq b\vee b\sqsubseteq a$.

Sorozatok rendezettsége

Rendezett halmaz elemeiből képzett $a_{1},\dots ,a_{n}$ és $b_{1},\dots ,b_{n}\,(n\in \mathbb {N} )$ véges sorozatokat egyformán rendezettnek nevezünk, ha bármely $i\neq j$ esetén $a_{i}\sqsubseteq a_{j}\Rightarrow b_{i}\sqsubseteq b_{j}$; illetve ellentétesen rendezettnek nevezünk, ha bármely $i\neq j$ esetén $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 $A$ halmaz részhalmazainak $P(A)$ halmazában a $\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