Főmenü megnyitása

Rendezett halmaz

(Rendezési reláció szócikkből átirányítva)

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óSzerkesztés

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ésSzerkeszté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égeSzerkesztés

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ákSzerkesztés

  • ℕ-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
  • az egész számok halmazában az oszthatósági reláció részbenrendezés

Lásd mégSzerkesztés

HivatkozásokSzerkesztés

  • 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ásokSzerkesztés

További információkSzerkesztés