Relații binare

Relația binară este un tip special de relație de aritate doi. Printre relațiile binare tipice se numără, de exemplu, „mai mic decât”, egalitatea, divizibilitatea, „mai mare decât” și altele.

Exemple

Relația binară este una dintre relațiile tipice și des întâlnite. În același timp, are câteva proprietăți interesante, pe care le descriem aici.

Un exemplu de relație binară poate fi legătura „tată – fiu”, perechea „mijloc de transport – număr de roți” sau, mai general, „obiect – proprietate a obiectului”. Obiectul poate fi un animal, iar proprietatea numărul de picioare, durata medie de viață, numărul de fire de păr de pe cap și așa mai departe.

O relație binară R între mulțimile M₁ și M₂ o putem defini astfel: R ⊆ M₁ × M₂. Relația binară este deci o mulțime de perechi, iar această mulțime este o submulțime a produsului cartezian al celor două mulțimi între care introducem relația. Astfel, relația „tată – fiu” poate fi o relație între mulțimea tuturor oamenilor, între mulțimea tuturor oamenilor din Europa sau din București. Mulțimea o putem restrânge și în altă direcție: putem spune că definim relația între mulțimea tuturor bărbaților, nu a oamenilor în general.

Pentru relațiile binare folosim de obicei o notație specială. În loc să scriem (a, b) ∈ R, putem scrie aRb. De exemplu, în loc de (3, 1) ∈ > putem scrie 3 > 1. La fel și pentru alte relații. Deci scrierea aSb este echivalentă cu scrierea (a, b) ∈ S.

Relația inversă

Relația inversă este relația opusă relației date. (Atenție, nu o confunda cu complementara unei relații.) Care este relația opusă relației „mai mic decât”? „Mai mare decât”. Dacă relația „mai mic decât” conține elementul (4, 7), adică 4 < 7, atunci elementul invers va fi cel opus: 7 > 4, iar în relația inversă va fi perechea inversată (7, 4).

Dacă avem relația R ⊆ M₁ × M₂, relația inversă R⁻¹ o construim luând toate elementele (a, b) ∈ R și punând în R⁻¹ inversul lor. Deci, dacă relația R conține elementul (a, b), atunci relația R⁻¹ trebuie să conțină elementul (b, a). Este valabil și invers: dacă R⁻¹ conține elementul (b, a), atunci relația R trebuie să conțină elementul (a, b).

Dacă ar fi să o definim, relația R⁻¹ este inversa lui R exact atunci când:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

Așadar, 6 < 8 dacă și numai dacă 8 > 6. La fel și pentru alte perechi.

Compunerea relațiilor

Relațiile binare le putem compune între ele. Fie două relații: prima, R, este „a fi tatăl fiului său”, iar a doua, S, „a fi fratele surorii sale”. Relația R conține deci perechi (tată, fiu), iar a doua relație conține perechi (frate, soră).

Acum încercăm să compunem relațiile. Obținem o relație nouă, pe care o notăm R ∘ S, iar această relație conține elementul (a, c) exact atunci când (a, b) ∈ R și, în același timp, (b, c) ∈ S. Observă că b apare în ambele perechi, o dată pe locul al doilea și apoi pe locul întâi. Acesta este elementul de legătură al compunerii.

Exemplu: R = {(Tudor, Marius), (Petru, Iacob)} și S = {(Marius, Ioana), (Marius, Lena), (Iacob, Lucia)}. Tudor este tatăl lui Marius, Petru este tatăl lui Iacob. Marius are surorile Ioana și Lena, iar Iacob are sora Lucia.

Acum compunem relațiile: R ∘ S. Căutăm o pereche din R care are pe locul fiului pe cineva care apare ca frate în relația S. De exemplu, aceste două perechi: (Tudor, Marius) și (Marius, Ioana). Marius este elementul de legătură, de el nu mai avem nevoie, iar din numele rămase formăm o pereche nouă: (Tudor, Ioana). Relația R ∘ S conține deci perechea (Tudor, Ioana). Marius mai are o soră, pe Lena, și pe ea o adăugăm în relația compusă: (Tudor, Lena). La final rămâne fiul Iacob. El are sora Lucia. Avem deci două perechi: (Petru, Iacob) și (Iacob, Lucia). Din ele formăm încă un element: (Petru, Lucia).

Rezultatul este relația: R ∘ S = {(Tudor, Ioana), (Tudor, Lena), (Petru, Lucia)}. Cum am putea numi această relație? Cel mai probabil „a fi tatăl fiicei sale”.

Încă o dată, definiția completă:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Observație: uneori se folosește scrierea inversă, adică pentru aceeași definiție s-ar scrie S ∘ R în loc de R ∘ S.