proprietà delle relazioni

Definizione

Sia $A$ un insieme, sia $\rho$ una relazione su $A$,
allora $x\rho y$

• si dice riflessiva se $\forall x\in A,x\rho x$
• si dice simmetrica se $\forall x,y\in A,x\rho y\Rightarrow y\rho x$
• si dice transitiva se $\forall x,y,z\in A,x\rho y\wedge y\rho z\Rightarrow x\rho z$

$A$ insieme, $\rho$ si dice antisimmetrica se

• $\forall x,y\in A,x\rho y\wedge y\rho x\Rightarrow x=y$

Esempi
La relazione divide è transitiva:

$x|y\wedge y|z\stackrel{?}{\Rightarrow }x|z$

$x|y\iff \exists k_1:y=k_1\cdot x$
$y|z\iff \exists k_2:z=k_2\cdot y=k_2\cdot (k_1\cdot x)=$

$x|z$ quindi è vero perché, se $k_3=k_1\cdot k_2$ allora $z=k_3\cdot x$.

$\square$

La relazione congruenza modulo m è transitiva:

$x,y,z\in \mathbb{Z}$

$x{\equiv }_{m}y\wedge y{\equiv }_{m}z\stackrel{?}{\Rightarrow }x{\equiv }_{m}z$

$\exists k_1\in \mathbb{Z}:x-y=k_1\cdot m$
$\exists k_2\in \mathbb{Z}:y-z=k_2\cdot m$

$x{\equiv }_{m}z$ quindi è vero perché, se $k_3=k_1\cdot k_2$,
allora $x-z=k_1\cdot m+k_2\cdot m=(k_1+k_2)m=k_3\cdot m$.

$\square$

Esempi
La relazione divide è antisimmetrica se e solo se

$\forall x,y\in \mathbb{N}\setminus \{0\},x|y\wedge y|x\Rightarrow x=y$

Dimostriamolo partendo da

$x|y\iff \exists k_1:y=k_1\cdot x$
$y|x\iff \exists k_2:x=k_2\cdot y\iff \exists k_2:y=\frac{x}{k_2}$

quindi

$k_1\cdot x=\frac{x}{k_2}$

che equivale a

$k_1\cdot k_2\cdot x-x=0$

quindi

$(k_1\cdot k_2-1)\cdot x=0$

per la legge dell’annullamento del prodotto

o $k_1\cdot k_2-1=0$ o $x=0$

ma poiché $x\in \mathbb{N}\setminus \{0\}$

allora

$k_1\cdot k_2=1$

poiché $k_1,k_2\in \mathbb{N}$, allora

$k=k_1=k_2=1$

e se l’unica soluzione è $k=+1$

allora $x=y$.

$\square$

Risorse