Relazioni di equivalenza

Note

Una relazione binaria si dice d'equivalenza se è riflessiva, simmetrica e transitiva.

Tip

Esiste sempre la chiusura riflessiva, simmetrica e transitiva. Questa viene detta chiusura di equivalenza:
Nel grafo di adiacenza basta completare le componenti connesse fino a renderle cliques (componenti in cui tutto è connesso con tutto).
Pasted image 20240926091812.png

Tip

Se sono d'equivalenza la loro unione non è d'equivalenza, ma l'intersezione si.

Classi d'equivalenza

Note

Sia d'equivalenza , la classe d'equivalenza con rappresentante è definita come: Il rappresentante non è unico in generale, infatti:

Data d'equivalenza, allora forma una partizione di , cioè: collezione di sottoinsiemi di tale che e .