Equivalence Relation

A binary relation that is reflexive, symmetric, and transitive, is called an equivalence relation.

An equivalence relation partitions a set of elements into disjoint sets known as equivalence classes. If R is an equivalence relation on the set S then the equivalence class of s∈S is written [s]R.

Example

Take the set {John, Mary, Paul, Anne}. Define the function

	  
sex(John)=M
sex(Mary)=F
sex(Paul)=M
sex(Anne)=F
	  
	

Now define the relation

	
same-sex={(a,b)|sex(x)=sex(b)}
	
      

This gives us

	
[John]same-sex=[Paul]same-sex={John, Paul}
[Anne]same-sex=[Mary]same-sex={Anne, Mary}
	
      

References

Derensart, Pierre, Maluszynski, Jan. A Grammatical View of Logic Programming. MIT Press, 1993.