Binarne relacije: razlika između inačica

Izvor: Wikipedija
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja
Redak 31: Redak 31:
Binarna relacija je '''[[relacija ekvivalencije]]''', ako je refleksivna, simetrična i tranzitivna.
Binarna relacija je '''[[relacija ekvivalencije]]''', ako je refleksivna, simetrična i tranzitivna.


U slučaju kada se domena relacije podudara sa skupom na kojem je relacija zadana, dovoljan uvjet da ona bude relacija ekvivalencije je da bude simetrična i tranzitivna (refleksivnost će slijediti iz spomenutih svojstava).
U slučaju kada se domena relacije podudara sa skupom na kojem je relacija zadana, dovoljan uvjet da ona bude relacija ekvivalencije je da bude simetrična i tranzitivna (refleksivnost će slijediti iz spomenutih svojstava). Vidi [[klasa ekvivalencije]].


== Parcijalni uređaj i totalni uređaj ==
== Parcijalni uređaj i totalni uređaj ==

Inačica od 8. listopada 2019. u 21:26

Binarna relacija na skupu je svaki podskup (podskup Kartezijevog produkta skupa sa samim sobom). Ako je uređeni par onda kažemo da je u relaciji s , i pišemo ili .

Primjer:

Neka je S neprazan skup, = {1,2,3,4}, Kartezijev produkt skupa S sa samim sobom je:

 = {{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4}}

Binarna relacija ("uobičajena" relacija biti manji od nasljeđena iz skupa realnih brojeva) na skupu SxS je onaj podskup skupa SxS za kojeg vrijedi da je , tj. u ovom primjeru x<y:

 = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Ova relacija nije refleksivna jer za niti jedan uređeni par ne vrijedi da je x<x (x manji od samog sebe), npr. da bi relacija bila refleksivna za (1,2) trebao bi postojati element skupa oblika (1,1).

Također nije simetrična jer za niti jedan uređeni par ne vrijedi da je y<x, ako vrijedi da je x<y npr. ne postoji element za (2,3) oblika (3,2)

Ova relacija je tranzitivna jer za x<y i y<z vrijedi da je x<z npr. za (1,2) i (2,3) postoji element (1,3)

Nije antisimetrična jer ne vrijedi x<y i y<x iz čega bi slijedilo da je x=y.

Binarna relacija može biti:

  • refleksivna: ako je (svaki element je u relaciji sam sa sobom);
  • antirefleksivna (irefleksivna): ako je (niti jedan element ne smije biti u relaciji sam sa sobom);
  • simetrična: ako (ako je u relaciji sa onda i mora biti u relaciji sa );
  • antisimetrična: ako (ako je u relaciji sa i u relaciji sa , onda je ;
  • asimetrična: ako (ako je u relaciji sa onda ne smije biti u relaciji sa );
  • tranzitivna: ako (ako je u relaciji sa , i u relaciji sa onda je i u relaciji sa );

Relacija ekvivalencije

Binarna relacija je relacija ekvivalencije, ako je refleksivna, simetrična i tranzitivna.

U slučaju kada se domena relacije podudara sa skupom na kojem je relacija zadana, dovoljan uvjet da ona bude relacija ekvivalencije je da bude simetrična i tranzitivna (refleksivnost će slijediti iz spomenutih svojstava). Vidi klasa ekvivalencije.

Parcijalni uređaj i totalni uređaj

Binarna relacija je (strogi) parcijalni uređaj ako je antirefleksivna i tranzitivna. Ako dodatno dopustimo jednakost elemenata uz tako definiranu relaciju, novonastala relacija naziva se refleksivna relacija parcijalnog uređaja, relacija koja je refleksivna, tranzitivna i antisimetrična.

Ako dodatno vrijedi i , , za relaciju kažemo da je totalni uređaj, a navedeno svojstvo relacije nazivamo usporedivost ili potpunost.

Izvori