Relazioni

Prodotto cartesiano[modifica | modifica wikitesto]

Definizione (6)

Nell'universo presi due insiemi . Definiamo prodotto cartesiano.

 



Se , allora segue .


Se , allora è il quadrato cartesiano.


Presa una -upla ordinata di insiemi contenuti in U, ad essa si può associare il prodotto cartesiano

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

Relazioni binarie[modifica | modifica wikitesto]

Prendiamo due insiemi X e Y non vuoti.


Definizione (7)

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

 



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


Se la coppia appartiene a R, si può scrivere , 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 .


Se , si scrive (cioè x non è associato a y mediante R).


Caso particolare: Una relazione di X con se stesso è un sottoinsieme di .


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

Composizione di relazioni[modifica | modifica wikitesto]

Si può definire il prodotto di relazioni. Nel caso di funzioni reali di variabile reale, si possono fare due prodotti: oppure .

Definizione (8)

Supponiamo di avere tre insiemi non vuoti e supponiamo di avere una relazione e .


Per definire il prodotto di R e S lo indico con .


In questo caso non posso definire .

 



è definibile se e solo se coincide con .


Se questo è vero si può definire e ma le due relazioni sono definite su insiemi diversi: la prima è un sottoinsieme di , mentre la seconda è definita su Y ed è un sottoinsieme di .


Se , in generale .


La composizione di relazioni è 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[modifica | modifica wikitesto]

Se , l'insieme delle relazioni binarie fra e è l'insieme delle parti di .


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


Nel caso generale:

Teorema (9)

se e e . Allora posso definire . 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 che è una coppia ordinata con , . Allora per la definizione di composizione di relazioni esiste .


A sua volta, dire che è associato a w significa che esiste tale che e .


D'altronde e implica che . A sua volta dire che e implica che .


Ho provato che qualunque coppia .


Similmente si prova che vale l'inclusione opposta.


Allora possiamo scrivere 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[modifica | modifica wikitesto]

Definizione (10)
  1. si dice riflessiva se , è associato a se stesso e quindi contiene la relazione identica su .
  2. si dice simmetrica se , se è associato a , allora è associato ad .


relazione trasposta: se , e viceversa. Quindi se è simmetrica.

3. si dice antisimmetrica se , e , allora (solo se a e b coincidono). In termini delle relazioni, l'intersezione tra e è contenuta nell'identità

4. si dice transitiva se presi tre elementi , se e implica .

 

relazioni di equivalenza[modifica | modifica wikitesto]

Definizione (11)

si dice di equivalenza se è riflessiva, simmetrica e transitiva, cioè se valgono le proprietà .

 



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[modifica | modifica wikitesto]

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 , o , altrimenti si parla di ordinamento parziale.

 


Per esempio, preso l'insieme delle parti di un insieme X prendo la relazione di inclusione, se e solo se (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 .

 



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

 PrecedenteSuccessivo