Relazione: Una relazione tra due insiemi A e B è un sottoinsieme del prodotto cartesiano A x B.
Relazione binaria: relazione tra A e A. R ⊆ A x A (A^2)
Matrice di adiacenza: per una relazione R tra A e B (finiti) è una tabella con righe etichettate da elementi di A, colonne con gli elementi di B, e in cui le entrate sono marcate in corrispondenza degli elementi in relazione tra loro
Diagrammi di Venn (per rel. binarie): Si collegano tra di loro gli elementi il relazione usando una freccia
Relazione riflessiva: (R binaria) ogni elemento di A è in relazione con se stesso (nella matrice sono segnate tutte le caselle della diagonale, e nel diagramma di Venn ogni elemento deve avere una freccia circolare.
Relazione simmetrica: R è simmetrica se ∀x,y ∈ A se x R y allora (-->) y R x (frecce in entrambi i versi)
Proprietà transitiva: ∀x,y ∈ A se x R y e y R z allora x R z (frecce triangolari)
Una relazione che ha tutte queste tre proprietà si chiama di equivalenza.
Classe di equivalenza: se R è una relazione di equivalenza su A, per ogni x ∈ A si definisce la classe d'equivalenza di x rispetto ad R (modulo R)