Let R be an equivalence relation on a set A.

Chapter 8, Problem 41E

(choose chapter or problem)

Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem.TheoremSuppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An,where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.)Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.]To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown].To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union.But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown].Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An.Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3,either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown].ExerciseFor all a and b in A, if a ? [b] then [a] = [b].

Unfortunately, we don't have that question answered yet. But you can get it answered in just 5 hours by Logging in or Becoming a subscriber.

Becoming a subscriber
Or look for another answer

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back