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

• $\mathrm{\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 $⊏$ egy szigorú rendezés U-n. Ekkor definiálunk hozzá egy gyenge $⊑$ rendezést a következőképp: $⊑:=⊏\cup i{d}_U$. Tehát $⊏$-t kibővítjük az U feletti egységrelációval. Másképp $\mathrm{\forall }a,b\in U:a⊑b:\iff (a⊏b\vee a=b)$ .
• Hasonlóan, legyen $⊑$ egy gyenge rendezés U-n. Ekkor definiálunk hozzá egy $⊏$ erős rendezést a következőképp: $⊏:=⊑\setminus i{d}_U$. Tehát $⊑$-t szűkítjük, kivonva a két azonos elemből álló párok halmazát. Másképp $\mathrm{\forall }a,b\in U:a⊏b:\iff (a⊑b\wedge a\ne b)$ .

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

• Ha $⊏$ egy szigorú teljes rendezés $U$-n, akkor $\mathrm{\forall }a,b\in U:a⊏b\vee b⊏a\vee a=b$.
• Ha $⊑$ egy gyenge teljes rendezés $U$-n, akkor $\mathrm{\forall }a,b\in U:a⊑b\vee b⊑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\ne j$ esetén $a_i⊑a_j\Rightarrow b_i⊑b_j$; illetve ellentétesen rendezettnek nevezünk, ha bármely $i\ne j$ esetén $a_i⊑a_j\Rightarrow b_i⊒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