Relazioni

Una relazione in un insieme $R$, è il predicato che lega più elementi degli insiemi coinvolti.

Per esempio, considerando le seguenti proposizioni con il soggetto e il complemento in $\mathbb{N}$,

è possibile costruire una relazione che chiameremo $\ge$, tale che: $$\ge =\{(x,y)|x\text{ eˋ maggiore di }y\vee x\text{ eˋ uguale a }y\}$$

L'insieme di appartenenza del soggetto è detto dominio, mentre quello del complemento è detto codominio.

Si dice relazione binaria, la relazione $R$ che coinvolge due oggetti appartenenti ad $A$ e a $B$, per cui $$R\subseteq A\times B$$ di conseguenza, il sottoinsieme delle coppie $(a,b)\in A\times B$ sono messe in relazione da $R$, cosa che viene espressa come $aRb$, $R(a,b)$, $(a,b)\in R$ oppure "$a$ è in relazione con $b$ secondo $R$".

Proprietà

Una relazione $R\subseteq A\times A=A^2$, ha le seguenti proprietà:

• Riflessiva: $$xRx,\forall x\in A$$

• Simmetrica: $$xRy\Rightarrow yRx,\forall x,y\in A$$

• Transitiva: $$xRy\wedge yRz\Rightarrow xRz,\forall x,y,z\in A$$

Al contrario, se per ogni elemento coinvolto la proprietà non vale, la relazione potrà essere:

• Antiriflessiva (o irriflessiva) $$(x,x)\notin R,\forall x\in A$$

• Antisimmetrica $$(x,y)\in R\Rightarrow (y,x)\notin R\vee ((y,x)\in R\wedge x=y),\forall x,y\in A$$

  che significa che se $x\ne y$, $x$ sarà in relazione con $y$, ma non viceversa.

Per ogni proprietà quindi, basta un unico elemento che non la rispetti perchè non sia soddisfatta.

Confrontabilità

Due elementi $x,y\in A$, si dicono confrontabili secondo la relazione $R$ se vale: $$xRy\vee yRx$$

altrimenti, si dicono inconfrontabili se: $$\neg (xRy)\wedge \neg (yRx)$$ che è il contrario (legge di De Morgan).