Study Guides for Discrete Mathematics
Section 6.5 - Equivalence Relations
Objects may be equivalent by virtue of many different attributes. For example, people may be considered equivalent with respect to height or weight. Students may be equated with respect to their class standing. Animals may be equated with respect the number of legs their species have. These divisions (for ex. high school freshmen, sophomores, juniors and seniors) are called equivalence classes. These classes then become the underlying objects rather than the original objects. I.e. the class ranks become the objects under discussion rather than the students.
Equivalence Relations and Equivalence Classes
A relation is an equivalence relation if it is reflexive, symmetric and transitive.
Example:
Let a relation R be defined on the positive integers such that aRb iff a and b have the same number of digits. So, for ex., 5 and 9 are related as are 1024 and 4100 but 3 is not related to 10.
aRa because a has the same number of digits as itself. Therefore R is reflexive.
aRb Þ bRa I.e. if a has the same number of digits as b then b has the same number of digits as a.
Therefore R is symmetric.
aRb /\ bRc Þ aRc. If a has the same number of digits as b and b has the same number of digits as c then a has the same number of digits as c. Therefore R is transitive.
Equivalence relations divide the members of the relation into equivalence classes. All elements that are related to each other are in the same equivalence class. In the example above the one-digit integers form an equivalence class, the two-digit integers form an intelligence class, …
If R is an equivalence class on A and a Î A then we denote the equivalence class which contains a as [a].
Partitions
Partitions are closely related to equivalence classes. In fact they are equivalent. Any set may be divided into subsets. If those subsets are disjoint then they form a partition.
More formally, let S be a set and let È Xi = S. If Xi Ç Xj = Æ (for any i,j i<> j) then the Xi form a partition of the set S.
If we define a relation, R, such that aRb iff a and b are members of the same Xi then R is an equivalence relation and the Xi are equivalence classes.
Refinement of a partition
Let {Xi} and {Yi} both form partitions of a set S. If every Yi is a subset of some Xi then {Yi} is said to be a refinement of {Xi}.
Example:
Let R1 be a relation on the animals of the world such that aR1b iff a and b have the same number of legs. Obviously this divides the animal kingdom into 0 legged, 2 legged, 4 legged, 6 legged etc. animals. Let R2 be a relation on the animals of the world such that aR2b iff a and b are of the same species. R2 subdivides the divisions of R1. For example, lions, tigers and bears are all different equivalence classes under R2 but they are all subsets of 4 legged animals, an equivalence class of R1. Therefore R2 defines a refinement of R1.