Siano X e Y due insiemi. Ogni sottoinsieme R di XxY si chiama relazione binaria (o corrispondenza) fra X e Y. Una relazione binaria è quindi una terna ordinata (X,Y,R) dove X e Y sono insiemi e R una relazione binaria fra X e Y.
Se R è una relazione binaria fra X e Y diciamo che un elemento x in X è in relazione R con un elemento y in Y, e scriviamo x R y se (x,y) appartiene ad R, sottoinsieme di XxY.
Se X=Y allora si parla di relazione binaria in X (o su X).

Definizione: Sia R sottoinsieme di XxY una relazione binaria sull'insieme X. Si dice che R è:

• Riflessiva, se per ogni x in X risulta x R x, cioè:
  
  x in X ==> x R x
  
• Simmetrica, se dati x,y in X, dall'essere x R y segue y R x, cioè:
  
  x R y ==> y R x con x,y in X
  
• Transitiva, se dati x,y,z in X, da x R y e y R z segue y R x, cioè:
  
  (x R y e y R z) ==> x R z con x,y,z in X

Si dice poi che R è una relazione di equivalenza se R è contemporaneamente riflessiva simmetrica e transitiva.

Definizione: Sia X un insieme non vuoto e sia R una relazione di equivalenza su X. Dato x in X poniamo:

[x] si chiama classe di equivalenza di x modulo R e x si dice rappresentante di tale classe.

Teorema:

Sia X un insieme non vuoto, R una relazione di equivalenza su X. Per ogni x,y in X si ha che:

• [x]=[y] <==> x R y
• [x] intersecato [y] = vuoto <==> x non è in relazione R con y

Definizione:

Sia X un insieme non vuoto e sia R una relazione di equivalenza su X. L'insieme { [x] | x in X } si chiama insieme quoziente di X modulo R e si indica con X/R.
Siano X un insieme non vuoto e R una relazione di equivalenza su X. Definiamo una applicazione p: X -> X/R ponendo per ogni x in X, p(x)=[x]. Tale applicazione è detta proiezione canonica di X sull'insieme quoziente X/R. p è una applicazione suriettiva (infatti ogni [x] in X/R ha almeno un punto nella sua controimmagine: x in [x]), ma in generale non è iniettiva. Infatti se x,y in X, con x diverso da y, e x R y allora p(x)=[x]=[y]=p(y).