Relații binare pe o mulțime

Prin relație binară pe o mulțime înțelegem o relație binară definită între două mulțimi identice.

Exemple

Relația binară pe o mulțime este un tip special de relație binară, în care ambele mulțimi suport sunt aceleași. Relația binară pe o mulțime este deci o relație R astfel încât R ⊆ M × M.

Relația „mai mare decât” este o relație binară pe o mulțime, pentru că lucrăm cu numere de ambele părți. Deci > ⊆ ℝ × ℝ. Relația „tată – număr de copii” nu este o relație binară pe o mulțime, pentru că tatăl îl alegem din mulțimea tuturor oamenilor, în timp ce numărul de copii îl alegem dintr-o mulțime de numere.

Proprietăți

O relație binară R pe o mulțime M poate avea unele proprietăți interesante. Spunem că relația R este…

• reflexivă, dacă pentru orice a ∈ M avem (a, a) ∈ R.
• simetrică, dacă pentru orice a, b ∈ M, din (a, b) ∈ R rezultă și (b, a) ∈ R.
• antisimetrică, dacă pentru orice a, b ∈ M, din (a, b) ∈ R și (b, a) ∈ R rezultă a = b.
• tranzitivă, dacă pentru orice a, b, c ∈ M, din (a, b) ∈ R și (b, c) ∈ R rezultă că și (a, c) se află în R.

Exemple de reflexivitate

Reflexivitatea înseamnă că un element se află în relație cu el însuși. Un exemplu tipic este egalitatea. Dacă avem definită egalitatea pe numerele naturale, atunci pentru orice element a avem sigur a = a. Un alt exemplu poate fi divizibilitatea. Și aici numărul a se divide cu el însuși, deci perechea (a, a) se află în relația de divizibilitate (șapte îl divide pe șapte).

Relația „mai mic decât” însă nu este reflexivă, pentru că nu avem a < a. Asta nu este posibil, șapte nu poate fi mai mic decât șapte. La fel, relația „a fi tatăl copilului său” – nu pot fi propriul meu tată. Astfel de relații nu sunt reflexive.

Important este că reflexivitatea trebuie să fie valabilă pentru toate elementele, nu ajunge să găsim doar unele. De exemplu, relația „a ține la cineva”. Pot ține la cineva, de exemplu la controlorul de bilete, dar pot ține și la mine însumi. Sigur se găsește un om care ține la sine. Dar tot așa se găsește un om care nu ține la sine. O astfel de relație nu este reflexivă – toți oamenii ar trebui să țină la ei înșiși.

Exemple de simetrie

La o relație simetrică, dacă o pereche se află în relație, atunci și perechea inversată se află în relație. De exemplu, relația „a fi frate sau soră”. Dacă Ionuț este fratele Anei, atunci și Ana este sora lui Ionuț. Dintre relațiile numerice ar putea fi relația „a fi opusul”. Mă refer la perechile 2 și −2 sau −7 și 7. Sunt două numere care adunate dau zero. O astfel de relație este simetrică, pentru că ordinea pur și simplu nu contează: (2, −2) și (−2, 2) sunt în continuare două numere opuse și suma lor este zero.

O relație care nu este simetrică este „mai mic decât” (pe numerele reale). Aceasta nu are nicio pereche simetrică, pentru că nu se poate ca a < b și în același timp b < a. Dacă 5 < 15, atunci nu poate fi 15 < 5. De asemenea, nu este simetrică relația „a fi tatăl fiului său”. Poți fi tatăl fiului tău, dar atunci fiul nu poate fi tatăl tatălui său.

Și această proprietate trebuie să fie valabilă în toate cazurile. Dacă relația „a ține la cineva” (pe mulțimea tuturor oamenilor) ar fi simetrică, atunci, dacă eu țin la Ana, o actriță cunoscută, ar trebui ca și Ana să țină la mine. Și pentru că nici nu mă cunoaște, nu pot spune că ține la mine, ceea ce e păcat, iar relația nu este simetrică. Ceea ce e tot păcat.

Exemple de antisimetrie

Un exemplu clasic de relație antisimetrică este „mai mic sau egal”. Antisimetria ne spune că, dacă perechile (a, b) și (b, a) se află amândouă în relație, atunci elementele trebuie să fie egale, a = b. Relația „mai mic sau egal” respectă asta. Când avem a ≤ b și în același timp b ≤ a? Doar dacă a = b. Dacă înlocuim: avem 3 ≤ 5 și în același timp 5 ≤ 3? Nu. Dar avem 4 ≤ 4 și în același timp 4 ≤ 4.

Un exemplu de relație care nu este antisimetrică pot fi perechile de cuvinte de aceeași lungime, de exemplu (vineri, secure). O astfel de relație nu este antisimetrică, pentru că găsim o pereche de cuvinte aflate în relație, a cărei pereche inversată se află și ea în relație, deși cele două cuvinte sunt diferite. Așadar, perechea amintită (vineri, secure) și inversa ei (secure, vineri). Evident, ambele se află în relația noastră, dar vineri ≠ secure, deci relația nu este antisimetrică.

Exemplu de tranzitivitate

Relația „mai mic decât” este tranzitivă. Tranzitivitatea ne spune că, dacă 3 < 4 și în același timp 4 < 5, atunci trebuie să avem sigur și 3 < 5. Pentru multe relații aceasta este o proprietate destul de firească. La fel și pentru exemplul cu lungimea cuvintelor. Dacă perechea (secure, vineri) se află în relație și perechea (vineri, poiană) se află în relație, atunci și cuvintele (secure, poiană) se află în relație.

Relația „a fi tatăl fiului” nu este tranzitivă. Dacă Tudor este tatăl lui Florin și Florin este tatăl lui Mircea, atunci Tudor nu este tatăl lui Mircea, ci bunicul lui. La fel, nu este tranzitivă relația „a ține la cineva”. Dacă țin la Ana și Ana ține la soțul ei, asta nu înseamnă că țin și eu la soțul Anei.

Tranzitivitatea se discută și la zarurile obișnuite. Să presupunem relația „zarul A este mai bun decât zarul B”, dacă pe zarul A cade mai des (cu o probabilitate mai mare) un număr mai mare decât pe zarul B. Este o astfel de relație tranzitivă? La asta răspunde articolul despre zaruri netranzitive.

Echivalență și ordine

Unele tipuri speciale de relații binare au și nume proprii:

• Echivalența este o relație care este reflexivă, simetrică și tranzitivă.
• Relația de ordine este o relație care este reflexivă, antisimetrică și tranzitivă.