Relazioni

Prodotto cartesiano

Definizione (6)

Nell'universo presi due insiemi $X,Y\in P(U)$$X,Y\in P(U)$. Definiamo prodotto cartesiano$X\times Y=$$X\times Y=$$\{(x,y)\,x\in X\,y\in Y\}$$\{(x,y)\,x\in X\,y\in Y\}$.

 

Se $X\neq Y$$X\neq Y$, allora segue $X\times Y\neq Y\times X$$X\times Y\neq Y\times X$.

Se $X=Y$$X=Y$, allora $X\times X=X^{2}$$X\times X=X^{2}$ è il quadrato cartesiano.

Presa una $n$$n$-upla ordinata $(X_{1},X_{2},...,X_{n})$$(X_{1},X_{2},...,X_{n})$ di insiemi contenuti in U, ad essa si può associare il prodotto cartesiano $X_{1}\times X_{2}\times ...\times X_{n}=\{(x_{1},x_{2},...,x_{n}),x_{1}\in X_{1},x_{2}\in X_{2},...,x_{n}\in X_{n}\}$$X_{1}\times X_{2}\times ...\times X_{n}=\{(x_{1},x_{2},...,x_{n}),x_{1}\in X_{1},x_{2}\in X_{2},...,x_{n}\in X_{n}\}$

Si può definire la potenza cartesiana $X^{Y}$$X^{Y}$ come l'insieme delle funzioni da Y a X.

Relazioni binarie

Prendiamo due insiemi X e Y non vuoti.

Definizione (7)

Si dice relazione fra X e Y ogni sottoinsieme R del prodotto cartesiano $X\times Y$$X\times Y$.

 

Se ho una funzione reale di variabile reale $f(x)$$f(x)$, posso definire una relazione data dalle coppie $x,f(x)$$x,f(x)$ che rappresenta il grafico della funzione.

Se la coppia $(x,y)$$(x,y)$ appartiene a R, si può scrivere $xRy$$xRy$, cioè x è associato a y nella relazione R.

Ci sono due casi banali da considerare:

1. relazione universale: ogni elemento di x è associato a ogni elemento di y.
2. relazione vuota: nessun x è associato ad alcun y.

Le relazioni fra X e Y sono gli elementi che costituiscono gli insiemi delle parti di $X\times Y$$X\times Y$.

Se $(x,y)\notin R$$(x,y)\notin R$, si scrive $x\not Ry$$x\not Ry$ (cioè x non è associato a y mediante R).

Caso particolare: Una relazione di X con se stesso è un sottoinsieme di $X^{2}$$X^{2}$.

Oltre alla relazione universale e a quella vuota, una relazione particolare è la relazione identità: $\{(x,x)\}$$\{(x,x)\}$ (associa ad ogni elemento solamente se stesso).

Composizione di relazioni

Si può definire il prodotto di relazioni. Nel caso di funzioni reali di variabile reale, si possono fare due prodotti: $(f*g)(x)=f(x)*g(x)$$(f*g)(x)=f(x)*g(x)$ oppure $(f\circ g)(x)=f\circ g(x)$$(f\circ g)(x)=f\circ g(x)$.

Definizione (8)

Supponiamo di avere tre insiemi non vuoti $X,Y,I$$X,Y,I$ e supponiamo di avere una relazione $R\subset X\times Y$$R\subset X\times Y$ e $S\subset Y\times I$$S\subset Y\times I$.

Per definire il prodotto di R e S lo indico con $S\circ R(X\to I)=\{(x,i)\in X\times I,\,t.c.\,\exists y\in Y\,t.c.\,(x,y)\in R,\,(y,i)\in S\}$$S\circ R(X\to I)=\{(x,i)\in X\times I,\,t.c.\,\exists y\in Y\,t.c.\,(x,y)\in R,\,(y,i)\in S\}$.

In questo caso non posso definire $R\circ S$$R\circ S$.

 

$R\circ S$$R\circ S$ è definibile se e solo se $I$$I$ coincide con $X$$X$.

Se questo è vero si può definire $R\circ S$$R\circ S$ e $S\circ R$$S\circ R$ ma le due relazioni sono definite su insiemi diversi: la prima è un sottoinsieme di $X^{2}$$X^{2}$, mentre la seconda è definita su Y ed è un sottoinsieme di $Y^{2}$$Y^{2}$.

Se $X=Y=I$$X=Y=I$, in generale $S\circ R\neq R\circ S$$S\circ R\neq R\circ S$.

La composizione di relazioni $X^{2}$$X^{2}$ è non commutativa, tranne nel caso in cui X è costituita da un solo oggetto. Il prodotto di relazioni in generale è associativo.

Associatività della composizione di relazioni

Se $X=Y$$X=Y$, l'insieme delle relazioni binarie fra $X$$X$ e $Y$$Y$ è l'insieme delle parti di $X^{2}$$X^{2}$.

Se considero $P(X^{2})$$P(X^{2})$ (insieme delle relazioni binarie su $X$$X$), abbiamo una struttura algebrica con un'operazione binaria (composizione di relazioni). L'operazione non è commutativa, tranne nel caso in cui l'insieme $X$$X$ sia costituito da un unico oggetto.

Nel caso generale:

Teorema (9)

se $R\in X\times Y$$R\in X\times Y$ e $S\in Y\times V$$S\in Y\times V$ e $T\in V\times W$$T\in V\times W$. Allora posso definire $(T\circ S)\circ R=T\circ (S\circ R)$$(T\circ S)\circ R=T\circ (S\circ R)$. Con questo si intende che il prodotto di relazioni è associativo.

 

Dimostrazione

Per verificare che i due sottoinsiemi coincidono, faremo vedere che uno sia contenuto nell'altro e viceversa.

Prendiamo un elemento di $T\circ (S\circ R)$$T\circ (S\circ R)$ che è una coppia ordinata $(x,w)$$(x,w)$ con $x\in X$$x \in X$, $w\in W$$w\in W$. Allora per la definizione di composizione di relazioni esiste $y\in Yt.c.(x,y)\in R,\,(y,w)\in T\circ S$$y\in Yt.c.(x,y)\in R,\,(y,w)\in T\circ S$.

A sua volta, dire che $y$$y$ è associato a w significa che esiste $v\in V$$v \in V$ tale che $(y,v)\in S$$(y,v)\in S$ e $(v,w)\in T$$(v,w)\in T$.

D'altronde $ySv$$ySv$ e $xRy$$xRy$ implica che $(x,v)\in S\circ R$$(x,v)\in S\circ R$. A sua volta dire che $(x,v)\in S\circ R$$(x,v)\in S\circ R$ e $(v,w)\in T$$(v,w)\in T$ implica che $(x,w)\in T\circ S\circ R$$(x,w)\in T\circ S\circ R$.

Ho provato che qualunque coppia $(T\circ S)\circ R\subset T\circ (S\circ R)$$(T\circ S)\circ R\subset T\circ (S\circ R)$.

Similmente si prova che vale l'inclusione opposta.

Allora possiamo scrivere $t\circ s\circ r$$t\circ s\circ r$ senza mettere le parentesi.

 

Ci occuperemo in particolare di relazioni binarie definite su un insieme X e di applicazioni, che sono relazioni particolari definite tra X e Y.

Tra le relazioni su un insieme X non vuoto ci sono le relazioni di equivalenza.

Proprietà importanti delle relazioni

Definizione (10)

1. $R$$R$ si dice riflessiva se $\forall a\in X$$\forall a\in X$, $a$$a$ è associato a se stesso e quindi $R$$R$ contiene la relazione identica su $X$$X$.
2. $R$$R$ si dice simmetrica se $\forall a,b\in X$$\forall a,b\in X$, se $a$$a$ è associato a $b$$b$, allora $b$$b$ è associato ad $a$$a$.

relazione trasposta: se $x\,R^{t}\,y$$x\,R^{t}\,y$, $y\,R\,x$$y\,R\,x$ e viceversa. Quindi $R=R^{t}$$R=R^{t}$ se $R$$R$ è simmetrica.

3. $R$$R$ si dice antisimmetrica se $\forall a,b\in X$$\forall a,b\in X$, $aRb$$aRb$ e $bRa$$bRa$, allora $a=b$$a=b$ (solo se a e b coincidono). In termini delle relazioni, l'intersezione tra $R$$R$ e $R^{t}$$R^{t}$ è contenuta nell'identità

4. $R$$R$ si dice transitiva se presi tre elementi $a,b,c\in X$$a,b,c\in X$, se $aRb$$aRb$ e $bRc$$bRc$ implica $aRc$$aRc$.

 

relazioni di equivalenza

Definizione (11)

$R$$R$ si dice di equivalenza se è riflessiva, simmetrica e transitiva, cioè se valgono le proprietà $1,2,4$$1,2,4$.

 

Ad esempio, la relazione di equivalenza fra poligoni di avere la stessa area è di equivalenza in senso generale. Lo stesso vale per la relazione di sovrapponibilità e similitudine tra poligoni, il parallelismo tra rette. La relazione di ortogonalità non lo è, perché non è riflessiva ne transitiva.

Relazioni d'ordine

Definizione (12)

Una relazione si dice di ordine se valgono le proprietà riflessiva, antisimmetrica e transitiva.

 

Definizione (13)

Una relazione d'ordine si dice totale se presi due elementi $a,b\in X$$a,b\in X$, $a\leq b$$a\leq b$ o $b\leq a$$b\leq a$, altrimenti si parla di ordinamento parziale.

 

Per esempio, preso l'insieme delle parti di un insieme X prendo la relazione di inclusione, $X\leq Y$$X\leq Y$ se e solo se $X\subset Y$$X\subset Y$ (relazione d'ordine). Non è una relazione d'ordine totale, perché presi due elementi distinti, considerati gli insiemi che hanno come oggetto i due elementi, non sono confrontabili.

Esercizio (14)

se ho un insieme finito di cardinalità n, i suoi sottoinsiemi sono $2^{n}$$2^n$.

 

Considerati commutatività, associatività e proprietà di assorbimento, si può provare che se ho un reticolo e chiamo $a,b,c$$a,b,c$ i suoi elementi, allora si può definire una relazione d'ordine dicendo che $a\leq b$$a\leq b$ e $A\cap B=A$$A\cap B=A$ o $A\cup B=B$$A\cup B=B$. Questa relazione d'ordine, non totale, ha la proprietà che ogni coppia di oggetti ha un estremo superiore (unione) e un estremo inferiore (intersezione).