Relazioni
Prodotto cartesiano[modifica | modifica wikitesto]
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.
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:
- relazione universale: ogni elemento di x è associato a ogni elemento di y.
- 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 .
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:
se e e . Allora posso definire . Con questo si intende che il prodotto di relazioni è associativo.
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]
- si dice riflessiva se , è associato a se stesso e quindi contiene la relazione identica su .
- 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]
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]
Una relazione si dice di ordine se valgono le proprietà riflessiva, antisimmetrica e transitiva.
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.
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).