Equivalence Relations

What Are Equivalence Relations?

Reflexivity: $$ \forall \ a \ \in A \:\: a\rho a $$
Symmetry: $$ \forall \ a,b \ \in A \:\: a\rho b \Rightarrow b\rho a $$
Transitivity: $$ \forall \ a,b,c \ \in A \ | \ a\rho b \land b\rho c \Rightarrow a\rho c $$

Whenever a relation aρb holds, the elements a and b in the set are said to be equivalent.

$$ a\rho b $$

A classic example is equality (=), which is an equivalence relation because it satisfies all three properties:

Reflexivity: $$ \forall \ a \ \in A \ \Rightarrow \: a = a $$
Symmetry: $$ \forall \ a,b \ \in A \ | \: a = b \Rightarrow b = a $$
Transitivity: $$ \forall \ a,b,c \ \in A \ | \ a = b \land b = c \Rightarrow a = c $$

Equivalence vs. Order Relations: Both equivalence and order relations are reflexive and transitive. The key difference lies in the third property: equivalence relations are symmetric, whereas order relations are antisymmetric.

A Practical Example
Equivalence Classes

A Practical Example

Consider the set of lines in the Cartesian plane and the relation R:

$$ R: \ \text{x is parallel to y} $$

To determine whether R is an equivalence relation, we examine each of the three defining properties:

Reflexive: Every line is parallel to itself, as it has the same direction.
Symmetric: If line x is parallel to line y, then line y is parallel to line x.
Transitive: If x is parallel to y and y is parallel to z, then x is also parallel to z.

Since all three conditions are satisfied, R qualifies as an equivalence relation.

Example 2

Now consider the same set of lines, but with a different relation:

$$ R: \ \text{x is perpendicular to y} $$

Let’s check whether this is an equivalence relation:

Not reflexive: A line cannot be perpendicular to itself.

Therefore, this is not an equivalence relation.

Note: Since the relation fails the reflexivity test, there’s no need to check the other properties. A single violation is enough to disqualify it as an equivalence relation - even if the other properties hold.

Other Simple Examples

The relation "x is the same age as y" is an equivalence relation.
The relation "x lives in the same house as y" is an equivalence relation.
The relation "x has the same weight as y" is an equivalence relation.
The relation "x is the same color as y" is an equivalence relation.

Equivalence Classes

An equivalence relation naturally partitions a set into equivalence classes, which are non-empty, disjoint subsets whose union is the entire set.

A partition is a way of dividing a set into separate, non-overlapping parts such that every element belongs to exactly one part.

Each of these subsets is called an equivalence class.

The collection of all equivalence classes forms what is known as the quotient set.

Example: Consider the finite set of integers $$ X = \{ -5, -2, -1, 3, 4 \} $$ Define the relation "x has the same sign as y". This is an equivalence relation because it is reflexive, symmetric, and transitive. It partitions X into two distinct equivalence classes: $$ C_1 = \{ 3, 4 \} $$ $$ C_2 = \{ -5, -2, -1 \} $$ These classes are non-empty and mutually exclusive. Their union covers the entire original set: $$ C_1 \cup C_2 = X $$ Thus, the quotient set is the set of these equivalence classes: $$ Q = \{ C_1, C_2 \} = \{ \{3, 4\}, \{-5, -2, -1\} \} $$ Notice that each element of the quotient set Q is itself a set.

A given set can have many different partitions.

Each distinct partition corresponds to a different equivalence relation.

For instance, a set of objects might be grouped based on color, weight, price, and so on.

And so on.