Relațiile ordinii

Relația de echivalență este o generalizare a relației de egalitate: elementele echivalente sunt considerate "egale". O relație generală este relația ordinii.







O relație se numește preordonare sau cvasi-ordine dacă R este reflexivă și tranzitivă.

pe set X = este o preorder.

O relație reflexivă, antisimetrică, tranzitivă este numită relație de ordin nestricăcios și este marcată printr-un simbol.

O relație antireflexivă, antisimetrică, tranzitivă se numește o relație de ordin strict și este marcată printr-un simbol. Relațiile de ordine stricte și non-stricte sunt altfel numite relații de ordine. Relația, inversul relației de ordine, este de asemenea o relație de ordonare, adică () =.

1. Fie Y un set, atunci relația incluziunii pe setul tuturor submulțimilor lui P (Y) este o relație de ordine non-strictă.

2. Raportul "x este mai vechi decât y" pe un anumit set de oameni este o relație de ordin strict.

Un set X cu o relație de ordine dată în el se spune că este ordonat de această relație. Dacă două elemente x și y ale mulțimii X sunt în raport cu ordinea, atunci setul X se numește ordonat liniar sau lanț, altfel setul X se numește parțial ordonat. Într-un set parțial comandat, se poate identifica un lanț. Un circuit cu elemente repetitive este numit multi-lanț. Dacă se stabilește o relație de ordin între elementele x și y, ele sunt numite comparabile, altfel - incomparabile. Un antichain (familia Sperner) este un subset al unui set parțial comandat în care oricare două elemente sunt incomparabile. Un tip special de set parțial comandat este intervalul | x, y] = (închis) sau (x, y) P = (deschis).

Un set dublu la un set parțial ordonat este un set parțial comandat definit pe același suport printr-o relație inversă. Acest concept stă la baza principiului dualității, adesea formulat sub forma: dacă o afirmație este adevărată pentru seturile parțial ordonate, atunci afirmația dublă, adică afirmația privind seturile duale parțial comandate, este de asemenea validă.







Considerăm un set X cu o relație de ordine parțială definită pe el.

Se spune că elementul y acoperă elementul x. dacă xy și nu există niciun element zX. astfel încât x z y. Astfel, y acoperă x dacă și numai dacă xy și [x, y] = x, y>. Orice set parțial comandat poate fi reprezentat sub forma unei scheme. Diagrama Hasse a unui set parțial comandat X este un grafic al cărui vârfuri sunt elementele setului X. iar perechea (x, y) formează o margine dacă elementul y acoperă elementul x. și astfel încât, dacă xy. atunci y trage cu o coordonate verticale mai mari decât x.

Un exemplu. Relația de incluziune pe P (X) boolean, unde X = a, b, c>. Este un set parțial comandat. Setul P (X) conține opt elemente: <. a>, b>, c>, a, b>, a, c>, b, c>, a, b, c >>. Diagrama Hasse pentru această relație va avea forma (Figura 2.2).

Regula de citire a diagramelor Hasse este aceea a xy. dacă se poate trece de la punctul x la punctul y. urmând de-a lungul segmentelor ascendente care leagă punctele. Schimbarea direcției de mișcare este permisă numai în punctele din diagramă.

Un exemplu. Să presupunem că A =. Considerăm relația de ordin parțial ≤ pe acest set, dată de regulă: x ≤yy este divizibilă de x. Diagrama Hasse este prezentată în figura 2.3.

Observăm că diagrama Hasse a acestor două relații coincide

Fie X și Y două seturi parțial comandate. Dacă diagramele Hasse coincid, atunci aceste seturi parțial comandate au aceeași structură.

Un exemplu. În Fig. 2.4 prezintă diagrama Hasse a unui set ordonat liniar X = cu relația obișnuită de ordine (≤) pe setul de numere naturale care nu depășesc opt.

Se va da un set parțial ordonat X. Pentru elementele x și y din setul X, legătura lor superioară este orice zX astfel încât și. și legătura lor inferioară este orice element al lui tX. astfel încât x și ty. În limba diagramelor Hasse, xy înseamnă că există o cale de la x la y; limita superioară a lui x și y este vârful la care există o cale de la x și y; limita inferioară a lui x și y este vârful din care există o cale atât în ​​x, cât și în y. În general, pentru anumite elemente, limitele superioare și inferioare pot să nu fie existente sau să nu fie unice, iar diferitele fețe superioare (sau inferioare) să nu fie comparabile.

Un exemplu. În Fig. 2.5 a) se afișează diagrama Hasse a setului. în care elementele nu au o față superioară, iar elementele au o față inferioară. În Fig. 2.5 b) prezintă diagrama Hasse a unui set în care toate elementele au fețe superioare și inferioare, dar, de exemplu, au două limite superioare incomparabile.







Articole similare

Trimiteți-le prietenilor: