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óról beszélünk a reflexív, antiszimmetrikus, tranzitív relációk esetében, illetve szigorú rendezési relációról beszélünk az antiszimmetrikus, tranzitív relációk esetében, amelyek azonban irreflexívek.

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 : \ a R a$ (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 \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 ha a fenti három feltételel túlmenően a következő feltétel is teljesül:

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

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 é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 \ne 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 rendezés.
• ℝ-ben ≤, ti. a≤b :⇔ ∃d∈ℝ⁺: b = a+d a szokásos „additív”, nagyság szerinti rendezés rendezés.
• egy $A$ halmaz részhalmazainak $P(A)$ halmazában a $\subseteq$ tartalmazási reláció részbenrendezés
• az egész 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

• Ordered Set a MathWorld oldalán
• Totally Ordered Set a MathWorld oldalán