Equivalence Relations

Equivalence Relations

Equivalence relations are a special type of relation that allow us to group elements into classes based on a specific property. These relations are fundamental in mathematics and computer science, particularly in the study of set theory and functions.

Definition of Equivalence Relation

A relation R on a set A is called an equivalence relation if it satisfies three properties:

• Reflexivity: For every element a in A, (a, a) is in R. This means that every element is related to itself.
• Symmetry: For every pair of elements a and b in A, if (a, b) is in R, then (b, a) is also in R. This means that if one element is related to another, the second is related to the first.
• Transitivity: For any elements a, b, and c in A, if (a, b) is in R and (b, c) is in R, then (a, c) is also in R. This means that if a is related to b and b is related to c, then a is related to c.

Examples of Equivalence Relations

Example 1: Equality

The most common example of an equivalence relation is equality. Let A be the set of integers. The relation R defined by aRb if and only if a = b is an equivalence relation.

Verification of Properties:

1. Reflexivity: For any integer a, a = a is true.
2. Symmetry: If a = b, then b = a.
3. Transitivity: If a = b and b = c, then a = c.

Example 2: Congruence Modulo n

Let A be the set of integers and let n be a positive integer. We define the relation R by aRb if and only if a ≡ b (mod n). This means that a and b have the same remainder when divided by n.

Verification of Properties:

1. Reflexivity: For any integer a, a ≡ a (mod n).
2. Symmetry: If a ≡ b (mod n), then b ≡ a (mod n).
3. Transitivity: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

Equivalence Classes

When a relation is an equivalence relation, it partitions the set into disjoint subsets called equivalence classes. An equivalence class is a subset of A where all elements are equivalent to each other under the relation.

Example: Equivalence Classes for Congruence Modulo 3

Consider the equivalence relation aRb if and only if a ≡ b (mod 3). The equivalence classes are:

• Class [0] = {…, -6, -3, 0, 3, 6, …}
• Class [1] = {…, -5, -2, 1, 4, 7, …}
• Class [2] = {…, -4, -1, 2, 5, 8, …}

Each integer belongs to exactly one of these classes. This means that if you pick any integer, it will either be in class [0], class [1], or class [2], but not in more than one class.

Properties of Equivalence Classes

Equivalence classes have several important properties:

• Every element of the set belongs to exactly one equivalence class.
• Equivalence classes are disjoint; no element can belong to two different classes.
• The union of all equivalence classes gives the entire set A.

Using Equivalence Relations in Computer Science

Equivalence relations are used in various areas of computer science, such as:

• Data Structures: In data structures like hash tables, equivalence relations can help identify duplicate entries.
• Algorithms: Equivalence classes can simplify problems by reducing the number of elements to consider.
• Database Systems: Equivalence relations help in normalising data and ensuring consistency.

Common Mistakes to Avoid

Summary

• An equivalence relation is a relation that is reflexive, symmetric, and transitive.
• Equivalence classes are formed by grouping elements that are equivalent under the relation.
• Equivalence relations are useful in various fields, including computer science.

Check your understanding

1. What are the three properties that define an equivalence relation?
2. Give an example of an equivalence relation that is not equality.
3. What is an equivalence class, and how is it formed?
4. Explain how equivalence relations can be useful in computer science.