1.2 Relacions

Donats dos conjunts $A$ i $B$, es diu relació entre $A$ i $B$ a tot subconjunt de $A\times B$. Si $R\subset A\times B$ és una relació entre $A$ i $B$, llavors quan es compleix que $(a,b)\in R$ diem que la relació es dona entre $a$ i $b$, o simplement, que $a$ està relacionat amb $b$.

Per ser conjunts, si $R$ i $S$ són relacions entre $A$ i $B$, llavors $R=S$ si i només si $R$ i $S$ contenen els mateixos parells ordenats. Es diu domini d’una relació $R$ entre $A$ i $B$ al conjunt denotat per $\mathcal{D}\left(R\right)$ que té per elements les primeres components dels parells ordenats de $R$. Es diu recorregut de $R$ el conjunt denotat per $\mathcal{R}\left(R\right)$ que té per elements les segones components dels parells ordenats de $R$. Així, tenim

i

Si $A$ és un conjunt, diem que $R$ és una relació binària en $A$ si $R\subset A\times A$. En tot conjunt $A$ sempre podem definir les relacions binàries següents:

1. 1.
   ​

   Relació d’identitat en $A$: $I_{A}=\left\{(x,x):x\in A\right\}$

2. 2.
   ​

   Relació nul·la en $A$: $\emptyset$

3. 3.
   ​

   Relació total en $A$: $A\times A$

Considerem un conjunt $A$ i una relació binària $R\subset A\times A$. Distingim les següents propietats de $R$:

1. 1.
   ​

   $R$ és reflexiva: per a tot $x\in A$, $(x,x)\in R$

2. 2.
   ​

   $R$ és irreflexiva: per a tot $x\in A$, $(x,x)\notin R$

3. 3.
   ​

   $R$ és simètrica: per a tot $x,y\in A$, si $(x,y)\in R$ llavors $(y,x)\in R$

4. 4.
   ​

   $R$ és asimètrica: per a tot $x,y\in A$, si $(x,y)\in R$ llavors $(y,x)\notin R$

5. 5.
   ​

   $R$ és antisimètrica: per a tot $x,y\in A$, si $(x,y)\in R$ i $(y,x)\in R$, llavors $x=y$

6. 6.
   ​

   $R$ és transitiva: per a tot $x,y,z\in A$, si $(x,y)\in R$ i $(y,z)\in R$, llavors $(x,z)\in R$

Donat un conjunt $A$ i una relació binària $R$ en $A$, diem que $R$ és una relació d’equivalència si $R$ és reflexiva, simètrica i transitiva.

Tota relació d’equivalència $R$ en un conjunt $A$ ens permet classificar els elements del conjunt en classes d’equivalència. Es diu classe d’equivalència d’un element $a\in A$ al conjunt denotat per $\left[a\right]$ que té per elements tots els elements d’$A$ que estan relacionats amb $a$. Així, tenim

De la definició de classe d’equivalència, deduïm de seguida que

o bé,

Llavors es diu conjunt quocient de $A$ per la relació $R$ al conjunt denotat per $A/R$ que té per elements les classes d’equivalència de tots els elements d’$A$ respecte de $R$. Així, tenim

Quan $R$ és d’equivalència diem que el conjunt quocient $A/R$ és una partició del conjunt $A$, això vol dir que és una col·lecció de subconjunts no buits d’$A$, disjunts dos a dos, i tals que la seva unió és $A$. Podem expressar això afirmant que en $A/R$ es compleixen les següents propietats:

1. 1.
   ​

   Per a tot $a\in A$, $\left[a\right]\neq\emptyset$.

2. 2.
   ​

   Per a tot $a,b\in A$ i $\left[a\right]\neq\left[b\right]$, $\left[a\right]\cap\left[b\right]=\emptyset$.

3. 3.
   ​

   $\mathop{\displaystyle\bigcup}A/R=A$, on $\mathop{\displaystyle\bigcup}A/R$ és la unió de totes les classes d’equivalència, doncs $A/R$ és el conjunt els elements del qual són els que pertanyen a alguna classe de $A/R$, o sigui

   $$\begin{array}[]{ccc}x\in\mathop{\displaystyle\bigcup}A/R&\Longleftrightarrow&\text{existeix alguna classe }\left[a\right]\in A/R\text{ tal que }x\in\left[a\right]\text{.}\end{array}$$

És habitual usar $\sim$ o $\equiv$ com a símbols de relacions d’equivalència sobre un conjunt.

Donat un conjunt $A$ i una relació binària $R$ en $A$, diem que $R$ és una relació d’ordre si $R$ és reflexiva, antisimètrica i transitiva. Un conjunt amb una relació d’ordre es diu un conjunt ordenat.

Una relació d’ordre $R$ en un conjunt $A$ es diu d’ordre total si per a tot $x,y\in A$ es compleix:

En aquest cas es diu que $A$ està totalment ordenat. En canvi, si existeixen $x,y\in A$ tals que $(x,y)\notin R$ i $(y,x)\notin R$, llavors la relació es diu d’ordre parcial i es diu que $A$ està parcialment ordenat. És habitual usar $\leq$ com a símbol de relació d’ordre en un conjunt.