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

Az  párt rendezett halmaznak nevezzük, ha  tetszőleges halmaz,  pedig -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: . Tehát -t kibővítjük az U feletti egységrelációval. Másképp  .
 Hasonlóan, legyen  egy gyenge rendezés U-n. Ekkor definiálunk hozzá egy  erős rendezést a következőképp: . Tehát -t szűkítjük, kivonva a két azonos elemből álló párok halmazát. Másképp  .

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

 Ha  egy szigorú teljes rendezés -n, akkor .
 Ha  egy gyenge teljes rendezés -n, akkor .

Sorozatok rendezettsége 

Rendezett halmaz elemeiből képzett  és  véges sorozatokat egyformán rendezettnek nevezünk, ha bármely  esetén ;
illetve ellentétesen rendezettnek nevezünk, ha bármely  esetén .

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  halmaz részhalmazainak  halmazában a  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

Relációkalkulus