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óról beszélünk a reflexív, antiszimmetrikus, tranzitív relációk esetében, illetve szigorú rendezési relációról beszélünk az antiszimmetrikus, tranzitív relációk esetében, amelyek azonban irreflexívek.

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 | forrásszöveg szerkesztése]

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  \forall a \in U : \ a R a (reflexivitás);
  •  RR^{-1} \subseteq E_{U} avagy  \forall a,b \in U : \ \left( aRb \wedge bRa \right) \Rightarrow a = b (antiszimmetria);
  •  RR \subseteq R avagy  \forall a,b \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 ha a fenti három feltételel túlmenően a következő feltétel is teljesül:

  • \forall a,b \in U: a R b \vee b R a .

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[szerkesztés | forrásszöveg szerkesztése]

A szigorú rendezésés és a gyenge rendezés fogalmai egyszerűen egymásba alakíthatóak:

  • Legyen \sqsubset egy szigorú rendezés U-n. Ekkor definiálunk hozzá egy gyenge \sqsubseteq rendezést a következőképp:  \sqsubseteq := \sqsubset \cup id_U. Tehát \sqsubset-t kibővítjük az U feletti egységrelációval. Másképp  \forall a,b \in U: \ a \sqsubseteq b \ : \Leftrightarrow \left( a \sqsubset b \vee a=b \right) .
  • Hasonlóan, legyen \sqsubseteq egy gyenge rendezés U-n. Ekkor definiálunk hozzá egy \sqsubset erős rendezést a következőképp: \sqsubset := \sqsubseteq \setminus id_U. Tehát \sqsubseteq-t szűkítjük, kivonva a két azonos elemből álló párok halmazát. Másképp  \forall a,b \in U: \ a \sqsubset b \ : \Leftrightarrow \left( a \sqsubseteq b \wedge a \ne b \right)  .

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

  • Ha \sqsubset egy szigorú teljes rendezés U-n, akkor \forall a,b \in U: a \sqsubset b \vee b \sqsubset a \vee a = b.
  • Ha \sqsubseteq egy gyenge teljes rendezés U-n, akkor \forall a,b \in U: a \sqsubseteq b \vee b \sqsubseteq a .

Sorozatok rendezettsége[szerkesztés | forrásszöveg szerkesztése]

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\neq j esetén a_i\sqsubseteq a_j \Rightarrow b_i\sqsubseteq b_j; illetve ellentétesen rendezettnek nevezünk, ha bármely i\neq j esetén a_i\sqsubseteq a_j \Rightarrow b_i\sqsupseteq b_j.

Példák[szerkesztés | forrásszöveg szerkesztése]

  • ℕ-ben ≤, ti. a≤b :⇔ ∃d∈ℕ: b = a+d a szokásos „additív”, nagyság szerinti rendezés rendezés.
  • ℝ-ben ≤, ti. a≤b :⇔ ∃d∈ℝ+: b = a+d a szokásos „additív”, nagyság szerinti rendezés rendezés.
  • egy A halmaz részhalmazainak P(A) halmazában a  \subseteq  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ég[szerkesztés | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • 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 | forrásszöveg szerkesztése]