Equivalence Relations Partitions
A binary relation might have one or more of the following properties: reflexivity, symmetry, anti symmetry and transitivity. A binary relation on a set is said to be an equivalence relation if it is reflexive, symmetric, and transitive. For example, the binary relation on the set {a, b, c, d, e, f} is an equivalence relation. Let A be a set of students and R be a binary relation of A such that (a, b) is in R if and only if a lives in the same dormitory as b. Since everybody lives in the same dormitory as himself or herself, R is a reflexive relation. Note that if a lives in the same dormitory as b, then b lives in the same dormitory as a. Thus, R is a symmetric relation. Note that if a lives in the same dormitory as b and b lives in the same dormitory as c, then a lives in the same dormitory as c. Thus, R is a transitive relation. Also, let A be a set of strings of 0s and 1s the lengths of which are at least three. Let R be a binary relation on A such that for two strings a and b, (a, b) is in R if and only if the last three digits in a are the same as the last three digits in b. Again, we leave it to the reader to check that R is an equivalence relation. Intuitively, in an equivalence relation two objects are related if they share some common properties or satisfy some common requirements, and are thus “equivalent” with respect to these properties or requirements.
We define now the notion of a partition of a set. A partition of a set A is a set of nonempty subsets of A denoted {A_{1}, A_{2}, …. A_{k}} such that the union of A_{i}’s is equal to A and the intersection of A_{i} and A_{j} is empty for any distinct A_{i} and A_{j}. In other words, a partition of a set is a division of the elements in the set into disjoint subsets. These subsets are also called blocks of the partition. For example, let A = {a, b, c, d, e, f, g}, then {{a}, {b, c, d}, {e, f}, {g}} is a partition of A.
Let π_{1} and π_{2} be two partitions of a set A. Let R_{1} and R_{2} be the corresponding equivalence relations. We say that π_{1}, denoted π_{1} ≤ π_{2}, if R_{1} ⊆ R_{2}. In other words, if π_{1} is a refinement, of π_{2}, then any two elements that are in the same block of π_{1} must also be in the same block of π_{2}. We define the product of π_{1} and π_{2}, denoted π_{1}. π_{2} to be the partition corresponding to the equivalence relation R_{1} R_{2}. In other words, the product of π_{1} and π_{2} is a partition of A such that two elements a and b are in the same block of π_{1}. π_{2}, if a and b are in the same block of π_{1} and also in the same block of π_{2}. Thus, π_{1}. π_{2} is a refinement of π_{1}, and also a refinement of π_{2}.
Services: - Equivalence Relations Partitions Homework | Equivalence Relations Partitions Homework Help | Equivalence Relations Partitions Homework Help Services | Live Equivalence Relations Partitions Homework Help | Equivalence Relations Partitions Homework Tutors | Online Equivalence Relations Partitions Homework Help | Equivalence Relations Partitions Tutors | Online Equivalence Relations Partitions Tutors | Equivalence Relations Partitions Homework Services | Equivalence Relations Partitions