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₁, A₂, …. 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 π₁ and π₂ be two partitions of a set A. Let R₁ and R₂ be the corresponding equivalence relations. We say that π₁, denoted π₁ ≤ π₂, if R₁ ⊆ R₂. In other words, if π₁ is a refinement, of π₂, then any two elements that are in the same block of π₁ must also be in the same block of π₂. We define the product of π₁ and π₂, denoted π₁. π₂ to be the partition corresponding to the equivalence relation R₁ R₂. In other words, the product of π₁ and π₂ is a partition of A such that two elements a and b are in the same block of π₁. π₂,  if a and b are in the same block of π₁ and also in the same block of π₂. Thus, π₁. π₂ is a refinement of π₁, and also a refinement of π₂.

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