Equivalence Relations in Discrete Mathematics: Reflexivity, Symmetry, and Transitivity

Learn about equivalence relations in discrete mathematics, focusing on their defining properties: reflexivity, symmetry, and transitivity. This guide provides a clear definition, examples, and demonstrates how to check if a given relation is an equivalence relation.

Understanding Equivalence Relations

What is an Equivalence Relation?

An equivalence relation is a special type of relationship between elements within a set. A relation R on a set A is an equivalence relation if it satisfies three properties:

  • Reflexive: Every element is related to itself (aRa for all a in A).
  • Symmetric: If a is related to b, then b is related to a (if aRb, then bRa).
  • Transitive: If a is related to b, and b is related to c, then a is related to c (if aRb and bRc, then aRc).

Example of an Equivalence Relation

Let's say A = {1, 2, 3, 4}, and R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}. Let's check if R is an equivalence relation:

  • Reflexive: Yes, because (1,1), (2,2), (3,3), and (4,4) are all in R.
  • Symmetric: Yes, because if (a,b) is in R, then (b,a) is also in R. For example, (2,4) is in R, and (4,2) is also in R.
  • Transitive: Yes, because if (a,b) and (b,c) are in R, then (a,c) is also in R. For example, (3,1) and (1,3) are in R, and (3,3) is also in R.

Since R satisfies all three properties, it's an equivalence relation.

Notes on Equivalence Relations

Note 1: The intersection of two equivalence relations is also an equivalence relation.

Note 2: The union of two equivalence relations may or may not be an equivalence relation.

Inverse Relations

If you have a relation R between two sets A and B, the inverse relation (R-1) reverses the order of the pairs. Formally: R-1 = {(b, a) : (a, b) ∈ R}

Example of an Inverse Relation

Let A = {1, 2, 3} and B = {x, y, z}. If R = {(1, y), (1, z), (3, y)}, then the inverse relation R-1 = {(y, 1), (z, 1), (y, 3)}.

Notes on Inverse Relations

Note 1: The domain of R-1 is the range of R, and the range of R-1 is the domain of R.

Note 2: If R is an equivalence relation, then R-1 is also an equivalence relation.

Note 3: If R is a symmetric relation, then R-1 = R.

Note 4: (Composition of relations reversed): If you have relations R, S, and T, then (R∘S∘T)-1 = T-1∘S-1∘R-1

Conclusion

Equivalence relations and inverse relations are important concepts in set theory and discrete mathematics, providing a framework for understanding relationships between elements in sets. Understanding their properties helps in various areas of mathematics and computer science.