Proofs in Ch 4 -
Relations
Example 2
Last modified on
In discussing Example 1, we learned to focus on 1) proof strategies from Ch 3, and 2) the main definitions in Ch 4, and 3) practice using this knowledge. Let's try another example, exercise 4.6 - 8. It is a bit trickier, and I had to experiment a bit to collect the right ideas and put them in the right order.
Example 2: If R and S are equivalence relations on A, and A/R = A/S, then R=S.
First Reactions: 1) We will probably need the definition of equivalence relation, and of A/R (unless we can use some theorem(s) in Ch 4.6 instead). Look them up now if you need to! 2) We are being asked to prove two relations are equal, and relations are sets, so we have the same choice of proof strategies as in Example 1. 3) There are no hints this time.
Second Reactions: 1) We cannot treat A/R like a fraction and "multiply by R" or whatever. No theorem in Ch 4 says we can do that. 2) If this example looks too weird, we could test it out on some examples, until we understand it better, but I will not do that here. 3) It seems harder now than at first glance. Maybe too hard to handle directly from the definitions, so we may need a little extra knowledge. Maybe some Ch 4 theorem or even a previous exercise will help. 4) Probably, we can get started using standard strategies - let's try and see.
Proof: [Again comments in brackets, like this one, are not needed in the proof. See bottom of page, for the same proof without comments] Assume that R and S are equivalence relations on A, and A/R = A/S . We'll prove that R = S. [the usual reaction to an if - then sentence. Now, let's try to prove containment both ways, which is usually a good approach to "set = set" statements. But Example 1 used two other common strategies]
First, we'll prove R is a subset of S. Assume (x,y) Î R [remember that relations are sets of ordered pairs]. We'll prove that (x,y) Î S. [The proof has been routine so far, but now we must think ! Why should (x,y) Î S ??? Looking over the section, we find some good info in the theorems and lemmas on page 207. We need to talk about equivalence classes here and will need to use different notation for the ones in A/R and the ones in A/S].
Let [x]R denote the eq. class of x in A/R. Then x Î [x]R Î A/R (by lemma 4.6.5). [remember that A/R is collection of subsets of A, and A/S is that same collection] Since A/R = A/S, [x]R Î A/S. Similarly, x Î [x]S Î A/S. [Is it true that [x]R = [x]S ?? It seems likely, but we need a reason....] By Theorem 4.6.4, A/S is a partition of A, which means its sets are pairwise disjoint.[two different sets cannot contain the same x]. Since [x]R and [x]S both contain x, we know [x]R = [x]S. [things are falling into place - now what was our goal again ?? Oh yes, we must talk about y now...] Since (x,y) Î R, y Î [x]R .So, y Î [x]S which means (x,y) Î S.
The proof that S is a subset of R is identical [just repeat the above, but switch the two letters] so we omit it [yes, you can do this in your proofs too, but be sure you aren't cheating ! ]. These two steps show R=S. Done. [This was a little harder than I expected. It might be easier (and educational) to try another strategy, such as a contrapostive approach. But after a little thought, I don't expect that would work out any easier].
What have we learned? Sometimes, prior theorems can be used instead of definitions. Having these extra options is a good thing, but then putting the proof together can get a bit trickier. When learning a new topic, study the definitions and theorems until they are common sense (if possible), and you'll find them easier to use in your proofs. In this example, a key idea was that A/R is a partition of A.
And I have learned that I can't put this much effort into explaining every step of every exercise in the book! Especially on web pages. You will have to learn a lot of your technique by trial and error or by imitation. And by talking with me or your classmates!
Proof (without all the comments).
Assume that R and S are equivalence relations on A, and A/R = A/S . We'll prove that R = S. First, we'll prove R is a subset of S. Assume (x,y) Î R. We'll prove that (x,y) Î S. Let [x]R denote the eq. class of x in A/R. Then x Î [x]R Î A/R (by lemma 4.6.5). Since A/R = A/S, [x]R Î A/S. Similarly, x Î [x]S Î A/S. By Theorem 4.6.4, A/S is a partition of A, which means its sets are pairwise disjoint. Since [x]R and [x]S both contain x, we know [x]R = [x]S. Since (x,y) Î R, y Î [x]R .So, y Î [x]S which means (x,y) Î S. The proof that S is a subset of R is identical So, R=S. Done.