北京郵電大學(xué)計算機學(xué)院--離散數(shù)學(xué)-9.5-relations

1、9.5 Equivalence Relations,,2,2024/3/21,College of Computer Science & Technology, BUPT,Definition,A relation R on a set A is an equivalence relation (等價關(guān)系) iff R isreflexivesymmetrictransitiveIt is easy to recogn

2、ize equivalence relations using digraphs.,3,2024/3/21,College of Computer Science & Technology, BUPT,Equivalence relations,The subset of all elements related to a particular element forms a universal relation (contai

3、ns all possible arcs) on that subset. The (sub)digraph representing the subset is called a complete (sub)digraph. All arcs are present. The number of such subsets is called the rank of the equivalence relation.,4,2024/3

4、/21,College of Computer Science & Technology, BUPT,Examples: A has 3 elements,,,,,,,,,5,2024/3/21,College of Computer Science & Technology, BUPT,Equivalence class,Each of the subsets is called an equivalence clas

5、s.A bracket around an element means the equivalence class in which the element lies.[x] = {y | (x, y) is in R}The element in the bracket is called a representative (代表元) of the equivalence class. We could have chosen

6、any one.,6,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let A be the set of all triangles in the plane and let R be the relation on A defined as follows:R = {(a, b) ? A ? A | a is congruent to b}

7、.It is easy to see that R is an equivalence relation.,7,2024/3/21,College of Computer Science & Technology, BUPT,An interesting counting problem,Count the number of equivalence relations on a set A with n elements.

8、Can you find a recurrence relation?The answers are1 for n = 12 for n = 25 for n = 3How many for n = 4?,8,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let A = Z and letR = {(a, b) ? A x A | a

9、 and b yield the same remainder when divided by 2}.Showcongruence mod 2 is an equivalence relationnote2 is called the modulus a ? b (mod 2)“a is congruent to b mod 2.“(模2同余),9,2024/3/21,College of Computer Science

10、& Technology, BUPT,Solution, a typical way,Firstclearly a ? a (mod 2). Thus R is reflexive.Secondif a ? b (mod 2), then a and b yield the same remainder when divided by 2, so b ? a (mod 2). R is symmetric.Final

11、lysuppose that a ? b (mod 2) and b ? c (mod 2). Then a, b, and c yield the same remainder when divided by 2. Thus, a ? c (mod 2). R is transitive.Hence congruence mod 2 is an equivalence relation.,10,2024/3/21,Colleg

12、e of Computer Science & Technology, BUPT,Equivalence Relations and Partitions,If P is a partition of a set A, then P can be used to construct an equivalence relation on A.,11,2024/3/21,College of Computer Science &am

13、p; Technology, BUPT,Theorem 1,Let P be a partition of a set A. Define the relation R on A as follows:a R bIf and only ifa and b are members of the same block.Then R is an equivalence relation on A.,12,2024/3/21,Colle

14、ge of Computer Science & Technology, BUPT,Proof,If a ? A, then clearly a is in the same block as itself; so a R a.If a R b, then a and b are in the same block; so b R a.If a R b and b R c, then a, b, and c must all

15、 lie in the same block of P. Thus a R c.Since R is reflexive, symmetric, and transitive, R is an equivalence relation.R will be called the equivalence relation determined by P.QED,13,2024/3/21,College of Computer Scie

16、nce & Technology, BUPT,Example,Let A = {1, 2, 3, 4} and consider the partition P = {{1, 2, 3}, {4}} of A. Find the equivalence relation R on A determined by P.SolutionThe blocks of P are {l, 2, 3} and {4}. Each el

17、ement in a block is related to every other element in the same block and only to those elements.Thus R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, l), (3, 2), (3, 3), (4, 4)}.,14,2024/3/21,College of Computer

18、 Science & Technology, BUPT,Lemma,Let R be an equivalence relation on a set A, and let a ? A and b ? A. Thena R bif and only ifR(a) = R(b),15,2024/3/21,College of Computer Science & Technology, BUPT,Proof of

19、lemma,First suppose that R(a) = R(b)Since R is reflexive, b ? R(b) = R(a), so a R b.Conversely, suppose that a R b, show that R(a) = R(b)choose x ? R(b)x R ba R b, so b R a (symmetric)x R a (transitive)x ? R(a).

20、Thus R(b) ? R(a)A completely similar argument shows that, R(a) ? R(b)so R(a) = R(b)QED,16,2024/3/21,College of Computer Science & Technology, BUPT,Theorem,Let R be an equivalence relation on A, and let P be the co

21、llection of all distinct relative sets R(a) for a in A. Then P is a partition of A, and R is the equivalence relation determined by P.,17,2024/3/21,College of Computer Science & Technology, BUPT,Proof,P = {R(a) | a

22、? A}Every element of A belongs to some relative set.Since reflexivity of R, a ? R(a)If R(a) and R(b) are not identical, then R(a) ? R(b) = ?If R(a) ? R(b) ? ? , then R(a) = R(b).Contrapositive(換質(zhì)位命題、對換式、逆反式),18,202

23、4/3/21,College of Computer Science & Technology, BUPT,Proof :If R(a) ? R(b) ? ? , then R(a) = R(b),Let c ? R(a) ? R(b)a R c, b R cc R b, since R is symmetrica R b, since R is transitiveR(a) = R(b) by Lemma lSo,

24、 P is a partitiona R b iff a and b belong to the same block of P, Thus P determines R.QED,19,2024/3/21,College of Computer Science & Technology, BUPT,Equivalence classes,If R is an equivalence relation on A, then t

25、he sets R(a) are traditionally called equivalence classes of R, denoted by [a]The partition P consists of all equivalence classes of R is denoted by A/R and calledthe quotient set, orthe partition of A induced by R, o

26、r,A modulo R.,20,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let A = {1, 2, 3, 4}R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)}.Determine A/R.SolutionR(1) = {1, 2} = R

27、(2)R(3) = {3, 4} = R(4).Hence A/R = {{1, 2}, {3, 4}},21,2024/3/21,College of Computer Science & Technology, BUPT,Determining partitions A/ R,STEP 1: Choose any element of A and compute the equivalence class R(a).S

28、TEP 2: if R(a) ? A, choose an element b, not included in R(a), and compute the equivalence class R(b).STEP 3: If A is not the union of previously computed equivalence classes, then choose an element x of A that is not i

29、n any of those equivalence classes and compute R(x).STEP 4: Repeat step 3 until all elements of A are included in the computed equivalence classes. If A is countable, this process could continue indefinitely. In that ca

30、se, continue until a pattern emerges that allows you to describe or give a formula for all equivalence classes.,22,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let R be the equivalence relation de

31、fined in example 2, determine A/R.SolutionR(0)={…, -6, -4, -2, 0, 2, 4, 6, …}R(1)={…, -5, -3, -1, 1, 3, 5, 7, …}Hence A/R consists of the set of even integers and the set of odd integers.,23,2024/3/21,College of Comp