Local Definition

An equivalence relation on a finite collection of objects may be described as follows: each object is related to itself and the relationship is symmetric; also, if two objects are related to the same third object, the two objects themselves must also be related.

Mathematical Definition

A binary relationship ~ between two objects is said to be an equivalence relation if:

• Each object is related to itself: a ~ a
• The relationship is symmetric: a ~ b if and only if b ~ a
• The relationship is transitive: a ~ b and b ~ c implies that a ~ c

An equivalence relation allows one to partition a set of objects into equivalence classes: that is, a collection of subsets where all entries in a given equivalence class are related to all other elements within the same equivalence class.

Given $ n $ objects which satisfy an equivalence relation, we may partition them such that all objects in the same partition are related to each other as is shown in Figure 1.

Figure 1. The partitioning of 10 objects satisfying an equivalence relation.

Implicit and Explicit Relationships

An equivalence relationship between two objects a and b may be implicitly defined through a function related(a, b) or member function a.related(b) which returns a Boolean value. The relationship is implicit to the objects.

Alternatively, the programmer can explicitly define an equivalence relation by defining the equivalence classes and where two objects are related if they fall within the same equivalence class.

Operations

Operations which may be performed on a container with objects which satisfy an equivalence relation include:

Additional Operations on Equivalence Relations

• Given an object in the container, retrieve a representative entry of the corresponding equivalence class, and
• Find all objects in the container which are equivalent to a given object, and
• Determine the size of an equivalence class.

Operations on Explicitly Defined Equivalence Relations

If the equivalence classes are explicitly defined by the programmer, there is no object-related member function which can return whether two objects are related, and therefore there is an addition operation:

• Determine if two objects in the container are related.