Relații de ordine

Relația de ordine este o relație binară pe o mulțime care este reflexivă, antisimetrică și tranzitivă.

Motivație

Ordonarea este o noțiune obișnuită, cu care lucrăm și în viața de zi cu zi. Multe lucruri le putem ordona într-un fel – cuvintele după alfabet, elevii din clasă după înălțime, mărfurile după preț. Toate acestea le descrie relația de ordine, pe care o notăm de obicei cu simbolul ≤. Simbolurile înrudite sunt: <, >, ≥. Semnificația lor este evidentă.

Ce ne-am aștepta de la o astfel de relație? Chiar din simbol se vede că în relația de ordine vor intra și elemente identice – ne interesează deci să definim proprietățile relației „mai mic sau egal”. O astfel de relație ar trebui să fie reflexivă. Trebuie să avem a ≤ a.

Ce mai departe? Sigur nu va fi valabilă simetria – dacă ordonăm după preț și mașina este mai ieftină decât pâinea, atunci sigur pâinea nu este în același timp mai ieftină decât mașina. Ce ne-am aștepta, în general, dacă s-ar întâmpla ca a ≤ b și în același timp b ≤ a? Ar avea vreodată sens? Da, dacă a = b. Singurul caz în care ordinea elementelor puse în relație nu contează este când elementele sunt identice – relația de ordine este deci antisimetrică.

În sfârșit, dacă știm că mașina este mai scumpă decât pâinea și avionul este și mai scump decât mașina, ne așteptăm ca avionul să fie sigur mai scump decât pâinea. Asta descrie tranzitivitatea.

Ordinea parțială

Ceea ce am definit adineauri este, de fapt, doar o relație de ordine parțială, nu totală. De ce nu este totală? Să încercăm să definim o ordine pe mulțimi. În ce fel am putea compara două mulțimi?

Spunem că mulțimea A este mai mică sau egală cu mulțimea B dacă A ⊆ B, adică dacă A este submulțime a lui B. Are sens, pentru că, dacă avem A = {1, 2} și B = {1, 2, 3}, am putea spune despre A că este mai mică – B conține aceleași elemente ca A și, în plus, conține numărul trei. Vom avea deci, de exemplu:

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

Problema apare când vrem să comparăm aceste mulțimi: A = {a, b} și B = {a, c}. Care dintre ele este mai mică sau mai mare? Problema este că, deși ambele mulțimi conțin elementul a, al doilea element este de fiecare dată diferit. Nicio mulțime nu este submulțime a celeilalte, deci nu avem nici A ≤ B, nici B ≤ A. Astfel de mulțimi sunt, în ordinea noastră, necomparabile.

De aceea definim mulțimea total ordonată, numită și lanț, ca mulțimea în care oricare două elemente sunt comparabile. Astfel de mulțimi sunt, de exemplu, mulțimile de numere cu ordinea obișnuită. Pentru oricare două numere reale a, b poți decide dacă a ≤ b sau b ≤ a.

Exemple din viața de zi cu zi

Un exemplu în care este mai bine să nu comparăm ar fi ordonarea după frumusețe, unde relația < ar însemna „a fi mai urât”. Poate ar trebui să o definim mai degrabă invers, > ca „a fi mai frumos”, ca să fim mai corecți :-). Probabil are sens să comparăm între ele două femei, de exemplu „Elena” < „Ioana”, în sensul că Ioana este mai frumoasă decât Elena. Sau doi bărbați: „Radu” < „Matei”, în sensul că Matei este mai chipeș decât Radu.

Problema este că ne e greu să comparăm frumusețea unui bărbat și a unei femei. Este mai frumoasă Ioana sau Matei? Este mai urâtă Elena sau Radu? Cel mai bine să nu căutăm răspunsul…

Dacă în ultimul exemplu ne limităm, de pildă, doar la femei, putem spune că avem o mulțime total ordonată, pentru că putem compara frumusețea tuturor femeilor.

Element minimal și maximal, cel mai mic și cel mai mare element

Dacă avem o mulțime ordonată M, atunci un element min ∈ M se numește minimal dacă nu există x ∈ M astfel încât x < min. Deci nu putem găsi un element care să fie mai mic decât elementul min.

Un element max ∈ M se numește maximal dacă nu există x ∈ M astfel încât x > max. Deci nu putem găsi un element care să fie mai mare.

Cele două noțiuni de mai sus diferă de noțiunile de cel mai mic și cel mai mare element.

Un element a ∈ M se numește cel mai mic element dacă pentru orice x ∈ M avem a ≤ x. Deci cel mai mic element a este mai mic sau egal cu toate celelalte elemente ale mulțimii M.

Un element b ∈ M se numește cel mai mare element dacă pentru orice x ∈ M avem b ≥ x. Cel mai mare element b este mai mare sau egal cu toate celelalte elemente ale mulțimii M.

Care este diferența dintre cel mai mare element și elementul maximal? Pot exista mai multe elemente maximale, pentru că mulțimea nu trebuie neapărat să fie total ordonată. Dacă revenim la exemplul comparării oamenilor după înfățișare, putem spune că Ioana este cea mai frumoasă femeie, iar Matei cel mai chipeș bărbat. Dar pe acești doi nu îi mai putem compara între ei, nu știm dacă Ioana este mai frumoasă decât Matei sau invers.

Ambele elemente sunt deci maximale. Nu putem găsi o persoană care să fie mai frumoasă decât Matei – Matei este mai chipeș decât toți ceilalți bărbați, iar cu femeile nu îl putem compara. La fel pentru Ioana – ea este mai frumoasă decât toate femeile, iar cu bărbații nu o putem compara.

Dar niciunul dintre ei nu este cel mai mare element, în acest sens cel mai frumos. Pentru ca Matei să fie cel mai frumos/cel mai mare, ar trebui să fie mai frumos decât toate persoanele, inclusiv toate femeile. Dar am spus deja că cu femeile nu îl putem compara, deci nu poate fi cel mai frumos om, este doar, în terminologia teoriei ordinii, maximal.

Se vede ușor că, dacă o mulțime are cel mai mare element, acesta este în același timp și maximal. Dacă elementul a este mai mare decât toate celelalte elemente ale mulțimii (definiția celui mai mare element), atunci sigur nu vom găsi un element și mai mare (definiția elementului maximal).

Un exemplu de mulțime care are cel mai mare și cel mai mic element este intervalul închis [0, 1]. Dacă alegem același interval, dar deschis, nu ar avea nici cel mai mare, nici cel mai mic element: (0, 1).

Dacă am vrea infinit de multe elemente minimale, am putea defini ordinea R astfel. Mai întâi definim mulțimile ajutătoare M_x. Mulțimile au această formă: pentru toți x din intervalul (0, 1) definim mulțimea M_x = {y ∣ y = x + n}, unde n ∈ ℕ. Obținem astfel, de exemplu, mulțimile următoare:

$$\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}$$

Pe fiecare mulțime M_x definim ordinea obișnuită, pe care o notăm R_x. La sfârșit reunim aceste ordini: R = ∪ R_x. În această ordine putem compara întotdeauna doar în interiorul lanțurilor inițiale. Putem afla dacă 0,5 ≤ 2,5, dar nu mai putem afla dacă 0,5 ≤ 2,7, pentru că aceste numere nu se aflau în aceeași mulțime M_x și deci relația dintre ele nu este definită.

În această relație de ordine, fiecare element din intervalul (0, 1) este element minimal.

Diagramele Hasse

Mulțimile ordonate le putem desena cu ajutorul diagramei Hasse. Este un graf în care vârfurile reprezintă elementele mulțimii, iar muchia dintre vârfurile (a, b) ne spune că a < b și, în același timp, nu există c astfel încât a < c < b. Deci între elementele a și b nu mai există niciun alt element. Totodată, în graf vârful a trebuie să fie mai jos decât vârful b. Exemplu de diagramă Hasse:

Această diagramă Hasse reprezintă mulțimea ordonată {A, B, C, D, E, F}. Avem: A < B, B < E, desigur avem și A < E, dar între aceste vârfuri nu există muchie, pentru că există vârful B pentru care A < B < E. Elementele E și D sunt necomparabile, pentru că niciunul nu se află deasupra sau dedesubtul celuilalt.

Deși diagramele Hasse se desenează de obicei frumos aliniate, asta nu este neapărat obligatoriu. Diagrama Hasse de mai sus poate arăta și așa:

Un alt exemplu poate fi mulțimea: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Acestea sunt divizorii naturali ai numărului 60. Ordinea dată de divizibilitate poate fi reprezentată astfel:

Ordinea dată de divizibilitate înseamnă că (a, b) ∈ R dacă și numai dacă a îl divide pe b. Din diagramă observăm că deasupra fiecărui număr se află numerele pe care el le divide. De exemplu, deasupra numărului 6 sunt numerele 12, 30 și 60. Deasupra numărului 4 sunt numerele 12, 20 și 60. Și așa mai departe. În schimb, numărul 3 nu are deasupra numărul 10, pentru că nu îl divide – atenție, numărul 10 este vizual deasupra numărului 3, dar nu duce la el nicio linie „de jos în sus”. Dacă de la numărul 3 ne deplasăm doar în sus, putem merge spre numerele 15 și 6, iar de la ele spre numărul 30. La numărul 10 am putea ajunge doar coborând, ceea ce nu avem voie să facem.