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:
- Olyan tranzitív és antiszimmetrikus reláció, mely reflexív (gyenge rendezési reláció);
- 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
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:
- reflexivitás:
avagy
; - tranzitivitás:
avagy 
- antiszimmetria:
avagy
.
[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
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.
[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
egy szigorú totális rendezés U-n, akkor
; - ha
egy gyenge totális rendezés U-n, akkor
;
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ó.


Based on work by