Rendezési reláció

A rendezési reláció halmazon értelmezett bináris reláció, amely reflexív, antiszimmetrikus és tranzitív.

Motiváció

A rendezés a mindennapi életben is gyakori fogalom. Sok mindent rendezhetünk valamilyen módon – a szavakat ábécé szerint, az iskolásokat magasság szerint, az árut ár szerint. Mindezt a rendezési reláció írja le, amelyet általában a ≤ szimbólummal jelölünk. A kapcsolódó szimbólumok: <, >, ≥. Jelentésük nyilvánvaló.

Mit várnánk egy ilyen relációtól? Már a szimbólumból is látszik, hogy a rendezési relációban szerepelnek egyforma elemek is – a cél tehát a „kisebb vagy egyenlő” reláció tulajdonságainak meghatározása. Egy ilyen reláció tehát legyen reflexív. Teljesülnie kell, hogy a ≤ a.

Mi még? A szimmetria biztosan nem teljesül – ha ár szerint rendezünk, és az autó olcsóbb a kenyérnél, akkor a kenyér biztosan nem lesz egyszerre olcsóbb az autónál. Mit várnánk általában, ha megtörténne, hogy a ≤ b és egyszerre b ≤ a? Lenne ennek valaha értelme? Igen, ha a = b. Az egyetlen eset, amikor a relációba tett elemek sorrendje nem számít, ha az elemek azonosak – a rendezés tehát antiszimmetrikus.

Végül, ha tudjuk, hogy az autó drágább a kenyérnél, a repülő pedig még drágább az autónál, akkor azt várjuk, hogy a repülő biztosan drágább a kenyérnél. Ezt írja le a tranzitivitás.

Részbenrendezés

Amit az imént definiáltunk, valójában csak részbenrendezés, nem teljes rendezés. Miért nem teljes? Próbáljunk rendezést definiálni halmazokon. Hogyan hasonlíthatnánk össze két halmazt?

Azt mondjuk, hogy az A halmaz kisebb vagy egyenlő, mint a B halmaz, ha A ⊆ B, vagyis ha A részhalmaza B-nek. Ennek van értelme, mert ha A = {1, 2} és B = {1, 2, 3}, akkor A-ról mondhatjuk, hogy kisebb – B ugyanazokat az elemeket tartalmazza, mint A, és ráadásul még a hármast is. Így például igaz lesz:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

A gond az, amikor ezeket a halmazokat akarjuk összehasonlítani: A = {a, b} és B = {a, c}. Melyik a kisebb vagy a nagyobb? A baj az, hogy bár mindkét halmaz tartalmazza az a elemet, a másik elemük mindig különböző. Egyik halmaz sem részhalmaza a másiknak, tehát sem A ≤ B, sem B ≤ A nem teljesül. Az ilyen halmazok a mi rendezésünkkel összehasonlíthatatlanok.

Ezért teljesen rendezett halmaznak vagy más néven láncnak nevezzük azt a halmazt, amelyben bármely két elem összehasonlítható. Ilyenek például a számhalmazok a szokásos rendezéssel. Bármely két a, b valós számról el tudod dönteni, hogy a ≤ b vagy b ≤ a.

Példák a mindennapi életből

Olyan példa, amikor érdemes nem összehasonlítani, lehet az aranyosság szerinti rendezés, ahol a < reláció azt jelentené, hogy „kevésbé aranyos”. Talán helyesebb lenne fordítva definiálni: a > jelentse azt, hogy „aranyosabb”. Van értelme két kutyát összehasonlítani egymással, például „Bodri” < „Morzsi” abban az értelemben, hogy Morzsi aranyosabb Bodrinál. Vagy két macskát: „Cirmi” < „Szotyi” abban az értelemben, hogy Szotyi aranyosabb Cirminél.

A gond az, hogy kutya és macska aranyosságát aligha tudjuk összehasonlítani. Aranyosabb Morzsi vagy Szotyi? Kevésbé aranyos Bodri vagy Cirmi? Inkább ne firtassuk…

Ha az utolsó példában például csak a kutyákra szorítkozunk, mondhatjuk, hogy teljesen rendezett halmazunk van, mert az összes kutya aranyosságát össze tudjuk hasonlítani.

Minimális és maximális elem, legkisebb és legnagyobb elem

Ha adott egy rendezett M halmaz, akkor a min ∈ M elemet minimálisnak nevezzük, ha nincs olyan x ∈ M, hogy x < min. Vagyis nem tudunk találni olyan elemet, amely kisebb lenne a min elemnél.

A max ∈ M elemet maximálisnak nevezzük, ha nincs olyan x ∈ M, hogy x > max. Vagyis nem tudunk találni olyan elemet, amely nagyobb lenne.

Az előző két fogalom különbözik a legkisebb és a legnagyobb elem fogalmától.

Az a ∈ M elemet legkisebbnek nevezzük, ha minden x ∈ M esetén a ≤ x. A legkisebb a elem tehát kisebb vagy egyenlő, mint az M halmaz összes többi eleme.

A b ∈ M elemet legnagyobbnak nevezzük, ha minden x ∈ M esetén b ≥ x. A legnagyobb b elem nagyobb vagy egyenlő, mint az M halmaz összes többi eleme.

Mi a különbség a legnagyobb és a maximális elem között? Maximális elemből több is lehet, mert a halmaz nem feltétlenül teljesen rendezett. Ha visszatérünk a kedvencek aranyosság szerinti összehasonlításához, mondhatjuk, hogy Morzsi a legaranyosabb kutya, Szotyi pedig a legaranyosabb macska. De ezt a kettőt már nem tudjuk egymással összehasonlítani, nem tudjuk, hogy Morzsi vagy Szotyi aranyosabb.

Mindkét elem tehát maximális. Nem tudunk találni olyan állatot, amely aranyosabb lenne Morzsinál – Morzsi aranyosabb az összes többi kutyánál, a macskákkal pedig nem hasonlíthatjuk össze. Hasonlóan Szotyival – ő aranyosabb az összes macskánál, a kutyákkal pedig nem hasonlíthatjuk össze.

De egyikük sem a legnagyobb, ebben az értelemben a legaranyosabb. Mert ahhoz, hogy Morzsi a legaranyosabb/legnagyobb legyen, aranyosabbnak kellene lennie az összes állatnál, a macskákat is beleértve. De már megmondtuk, hogy a macskákkal nem hasonlíthatjuk össze, ezért nem lehet a legaranyosabb állat, a rendezéselmélet terminológiájában csak maximális.

Könnyen belátható, hogy ha egy halmaznak van legnagyobb eleme, akkor ez az elem egyben maximális is. Ha az a elem nagyobb a halmaz összes többi eleménél (a legnagyobb elem definíciója), akkor biztosan nem találunk nála is nagyobb elemet (a maximális elem definíciója).

Olyan halmaz, amelynek van legnagyobb és legkisebb eleme, például a [0; 1] zárt intervallum. Ha ugyanezt az intervallumot nyíltan választjuk, akkor sem legnagyobb, sem legkisebb eleme nem lenne: ]0; 1[.

Ha végtelen sok minimális elemet szeretnénk, definiálhatjuk az R rendezést így. Először definiáljuk az M_x segédhalmazokat. A halmazok alakja ez: minden x-re a ]0; 1[ intervallumból definiáljuk az M_x = {y | y = x + n} halmazt, ahol n nemnegatív egész szám. Így például ilyen halmazokat kapunk:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Minden M_x halmazon definiáljuk a klasszikus rendezést, amelyet R_x-szel jelölünk. A végén ezeket a rendezéseket egyesítjük: R = ∪ R_x. Ebben a rendezésben tehát mindig csak az eredeti láncokon belül hasonlíthatunk. Megállapíthatjuk, hogy 0,5 ≤ 2,5, de azt már nem tudjuk eldönteni, hogy 0,5 ≤ 2,7, mert ezek a számok nem ugyanabban az M_x halmazban voltak, így a kapcsolatukat nem definiáltuk.

Ebben a rendezési relációban a ]0; 1[ intervallum minden eleme minimális elem.

Hasse-diagramok

A rendezett halmazokat Hasse-diagrammal ábrázolhatjuk. Ez olyan gráf, amelyben a csúcsok a halmaz elemei, a csúcsok közötti (a; b) él pedig azt mondja, hogy a < b, és nincs olyan c, hogy a < c < b. Tehát az a és b elem között már nincs más elem. Emellett teljesülnie kell, hogy a gráfban az a csúcs lejjebb van, mint a b csúcs. Példa Hasse-diagramra:

Ez a Hasse-diagram az {A, B, C, D, E, F} rendezett halmazt ábrázolja. Itt igaz: A < B, B < E, természetesen igaz az is, hogy A < E, de e csúcsok között nincs él, mert létezik a B csúcs, amelyre A < B < E. Az E és D elem összehasonlíthatatlan, mert egyik sincs a másik fölött vagy alatt.

Bár a Hasse-diagramokat általában ilyen szépen elrendezve rajzolják, ez nem feltétlenül szükséges. Az előző Hasse-diagram kinézhet így is:

Másik példa lehet az A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} halmaz. Ezek a 60 természetes osztói. Az oszthatóság szerinti rendezés így ábrázolható:

Az oszthatóság szerinti rendezés azt jelenti, hogy (a; b) ∈ R akkor és csak akkor, ha a osztja b-t. A diagramon észrevehetjük, hogy minden szám fölött azok a számok vannak, amelyeket oszt. Például a 6 fölött a 12, 30 és 60 áll. A 4 fölött a 12, 20 és 60. És így tovább. Ezzel szemben a 3 fölött nincs ott a 10, mert nem osztja – vigyázat, a 10 vizuálisan a 3 fölött van, de nem vezet hozzá „alulról felfelé” vonal. Ha a 3-tól csak felfelé haladunk, eljuthatunk a 15 és a 6 számhoz, onnan pedig a 30-hoz. A 10-hez csak úgy juthatnánk el, hogy lemászunk lefelé, amit nem szabad.