Rendezési reláció

A Wikipédiából, a szabad lexikonból.

Rendezési reláció, röviden rendezés a matematika halmazelmélet nevű ágában olyan speciális homogén bináris reláció, mely tranzitív és antiszimmetrikus, és ezen túl még általában reflexív (a formális definíciót ld. lentebb).

Az „általában” szó azt jelenti, hogy a szakirodalom sajnos nem egységes az ilyen relációk definíciója tekintetében, és kétféle fogalmat is szokás rendezési relációként definiálni:

  1. Olyan tranzitív és antiszimmetrikus reláció, mely reflexív (gyenge rendezési reláció);
  2. Olyan tranzitív reláció, mely irreflexív (szigorú vagy erős rendezési reláció).

Megjegyzés: matematikailag a fenti megkülönböztetésnek nincs túl nagy szerepe, mert bármelyik előbbi értelemben vett, gyenge rendezéshez egyértelműen tartozik egy olyan utóbbi értelemben vett, szigorú rendezés, melyekre két különböző elem akkor és csak akkor áll az egyik szerint relációban, ha a másik szerint is. Ld. lentebb.


Egy olyan halmazt, melyen rendezés van értelmezve, rendezett (vagy rendezési) struktúrának, pontatlanabbul (de elterjedtebben) rendezett halmaznak nevezünk.


Tartalomjegyzék

[szerkesztés] Formális definíció

Legyen U tetszőleges halmaz, efelett pedig egy R \subseteq U \times U homogén kétváltozós reláció. Legyen továbbá EU az olyan U-beli rendezett párok halmaza, az ún. egységreláció, melyek első koordinátái megegyeznek második koordinátáikkal; tehát az = egyenlőségi reláció U-ra szűkítése! A fenti R reláció akkor és csak akkor (gyenge) rendezés U felett (U-n), ha:

  1. reflexivitás: E_{U} \subseteq R avagy \forall a \in U : \ a R a ;
  2. tranzitivitás: RR \subseteq R avagy \forall a,b \in U : \ \left( aRb \wedge bRc \right) \Rightarrow aRc
  3. antiszimmetria: RR^{-1} \subseteq E_{U} avagy \forall a,b \in U : \ \left( aRb \wedge bRa \right) \Rightarrow a = b .

[szerkesztés] Szigorú és gyenge rendezés

Mint fentebb említettük, a szigorú é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.

[szerkesztés] Részleges és teljes rendezés

Teljes (vagy totális) rendezésnek nevezzük az olyan rendezést, amelyben bármely két elem összehasonlítható. Formálisan:

ha \sqsubset egy szigorú totális rendezés U-n, akkor \forall a,b \in U: a \sqsubset b \vee b \sqsubset a \vee a = b;
ha \sqsubseteq egy gyenge totális rendezés U-n, akkor \forall a,b \in U: a \sqsubseteq b \vee b \sqsubseteq a;

Azokat a rendezéseket, amelyekben vannak nem összehasonlítható elemek, részleges rendezésnek vagy részbenrendezésnek nevezzük.

[szerkesztés] Példák

  • ℕ-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.
  • P(A) felett, egy A halmaz részhalmazainak halmazában, a ⊆ „részhalmazsági” reláció.
  • ℕ-ben az | oszthatósági reláció.


Más nyelveken