CMPU-145, Spring 2013 Proof from class Feb. 20, 2013 Theorem 1. Let R be an equivalence relation over the set A = {a1,a2,...,an}. Let P = {B1,B2,...,Bn} be a collection of subsets of A where for each i, Bi = {a | (ai,a) is in R}. For example, B1 is the set of a's that are related to a1; B2 is the set of a's that are related to a2; and so on. Then P is a partition of A. Proof of Theorem 1. Let R, A and P be as in the statement of the theorem. Goal: Show that P is a partition over A. Thus, we must show that: (1) Each Bi is a non-empty subset of A. (2) The collection {B1,B2,...,Bn} exhaust A. (3) The Bi's are pairwise disjoint. Proof of (1). Since R is an equivalence relation, it is reflexive. Thus, for each ai in A, (ai,ai) is in R. But in that case, each set Bi contains at least one element, namely, ai. Thus, each Bi is non-empty. Furthermore, each Bi is a subset of A since R is a relation over A; thus, the only things that can be related to ai are elements of A. Proof of (2). Let U be the UNION of all the Bi's. We seek to show that A = U (i.e., that U is a subset of A; and A is a subset of U). Since each Bi is a subset of A, it follows that U is a subset of A. Thus, we need only show that A is a subset of U. In other words, we need to show that for any x, if x is in A, then x is in U. Let ai be any element of A. By definition of Bi, ai is an element of Bi. Hence ai is an element of U. Proof of (3). We seek to show that for any sets, Bi and Bj, in P, if Bi INTERSECT Bj is non-empty, then Bi = Bj. Let Bi and Bj be any sets in P such that Bi INTERSECT Bj is non-empty. We must show that Bi = Bj (i.e., Bi is a subset of Bj, and vice-versa). Proof that Bi is a subset of Bj. Let x be any element of Bi. We must show that x is also in Bj. Now, by assumption, Bi INTERSECT Bj is non-empty. Thus, there must be some y in both Bi and Bj. By definition of the sets Bi and Bj, it follows that (ai,y) and (aj,y) are in R. Okay, here we go: Since (ai,x) is in R, and R is symmetric, it follows that (x,ai) must also be in R. Thus, (x,ai) and (ai,y) are both in R. Thus, since R is transitive, it follows that (x,y) is in R. Since (aj,y) is in R, and R is symmetric, it follows that (y,aj) must be in R. Thus, both (x,y) and (y,aj) are in R. Thus, since R is transitive, it follows that (x,aj) is in R. And by symmetry, (aj,x) must be in R. But then, by definition of Bj, it follows that x is in Bj. That's the end of the proof. ----- Notice that we used all three properties of an equivalence relation. If R is not an equivalence relation, then the proof will not work. ================================================== Theorem 2. Let A be any non-empty set. Let P = {K1,K2,...,Km} be any partition of A. Let R be the following relation: R = {(a,b) | there is a set Ki such that a and b both belong to Ki } Note: We don't assume that there is only *one* such Ki. But it will turn out to be true. Then R is an equivalence relation. Proof of Theorem 2. Let P, A and R be as in the statement of the theorem. We seek to show that R is an equivalence relation (i.e., that it is reflexive, symmetric and transitive). Proof that R is reflexive (i.e., that for all a in A, (a,a) is in R). Let x be any element of A. Since P is a partition of A, the sets Ki must exhaust A. Thus, A is a subset of the union of the Ki. Thus, x must be an element of the union of the Ki. That implies that x must be an element of at least one of the Ki. (Definition of a union.) Thus, there is some Ki such that both x and x belong to Ki. Thus, (x,x) is in R. (Recall the definition of R.) Proof that R is symmetric (i.e., that for all (x,y) in R, (y,x) is also in R. Let (x,y) be any pair in R. By the definition of R, it must be that there is some Ki to which both x and y belong. But then y and x both belong to Ki. Thus, (y,x) is also in R. Proof that R is transitive (i.e., that for all (x,y), (y,z) in R, (x,z) is also in R. Let (x,y) and (y,z) be any pairs in R. By the definition of R, there must be some Ki to which both x and y belong. Similarly, there must be some Kj to which both y and z belong. Now, y belongs to both Ki and Kj. Thus, Ki INTERSECT Kj is non-empty. Thus, by the definition of pairwise disjointness (part of the defn. of a partition), it follows that Ki = Kj. Thus, x, y and z all belong to Ki. (They also all belong to Kj, since Ki = Kj.) But then (x,z) must be in R. That's the end of the proof! ------------ Notice that we used the requirements that the sets of a partition be pairwise disjoint and that they exhaust A. However, we did not use the fact that the sets in a partition must be NON-EMPTY. Consider the following example. A = {1,2} P = {{1,2}, EMPTY_SET} Now, the sets in P satisfy all the requirements of a partition *except* that one of the sets is empty. Nonetheless, we can define a relation R by: R = {(a,b) | there is some set in P that contains both a and b} In this case, we get: R = {(1,1), (1,2), (2,2), (2,1)} which is indeed an equivalence relation. This example does not invalidate the above theorems in any way. It just shows that the requirement that the sets in a partition be non-empty is not really relevant for those theorems. In a couple of seconds of searching on the web, I found this page: http://www.abstractmath.org/MM/MMEquivalenceRelations.htm It highlights a good reason why empty sets are excluded from partitions. Here's an example: Suppose A = {1,2,3}. Then there are 5 possible ways of partitioning A into non-empty subsets: P1 = {{1},{2},{3}} P2 = {{1},{2,3}} P3 = {{1,2},{3}} P4 = {{1,3},{2}} P5 = {{1,2,3}} There are also 5 possible equivalence relations over A: Q1 = {(1,1), (2,2), (3,3)} Q2 = {(1,1), (2,2), (2,3), (3,2), (3,3)} Q3 = {(1,1), (1,2), (2,1), (2,2), (3,3)} Q4 = {(1,1), (1,3), (3,1), (3,3), (2,2)} Q5 = {(1,1), (1,2), (1,3), (2,3), (2,1), (3,1), (3,2), (2,2), (3,3)} Notice that the corresponding partitions and equivalence relations are those that are constructed in the above theorems. Thus, we can define a function, f, from partitions to equivalence relations, where: f(Pi) = Qi. This function is a bijection! Its inverse is the function g, where g(Qi) = Pi.