Rendezett halmaz

A Wikipédiából, a szabad enciklopédiából

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és[szerkeszté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[szerkeszté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ák[szerkeszté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
  • a természetes számok halmazában az oszthatósági reláció részbenrendezés

Lásd még[szerkesztés]

Hivatkozások[szerkeszté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ások[szerkesztés]