Binarne relacije: razlika između inačica

Izvor: Wikipedija
Izbrisani sadržaj Dodani sadržaj
uklanjanje izmjene 4883251 suradnika 5.43.189.154 (razgovor)
Definicije su prilagođene modernoj ZFC teoriji skupova, odnosno usklađene su s definicijama izvedenih iz sveučilišnih udžbenika
Oznake: VisualEditor mobilni uređaj m.wiki
Redak 29: Redak 29:


== Parcijalni uređaj i totalni uređaj ==
== Parcijalni uređaj i totalni uređaj ==
Binarna relacija je '''parcijalni uređaj''', ako je refleksivna, antisimetrična i tranzitivna.
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 <math>(\forall x,y \in S)</math>, <math>(x\mathcal R y \lor y\mathcal R x)</math>, za relaciju kažemo da je '''totalni uređaj'''.
Ako dodatno vrijedi i <math>(\forall x,y \in S)</math>, <math>(x\mathcal R y \lor y\mathcal R x)</math>, za relaciju kažemo da je '''totalni uređaj''', a navedeno svojstvo relacije nazivamo usporedivost ili potpunost.





Inačica od 17. srpnja 2019. u 14:51

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 (manji od) 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);
  • simetrična: ako (ako je u relaciji sa onda i mora biti u relaciji sa );
  • tranzitivna: ako (ako je u relaciji sa , i u relaciji sa onda je i u relaciji sa );
  • antisimetrična: ako (ako je u relaciji sa i u relaciji sa , onda je ;

Relacija ekvivalencije

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

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.