Rendezett halmaz

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.

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}$ .

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}}$ .

• ℕ-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

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

• 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)

• 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