第工科离散数学课件 四章 4_5_等价关系(2) - 等价类.pptx

4.5.2 等价类4.5 等价关系-等价类[等价类] 设R是集合A上的等价关系，对?a ? A，称下述集合为由元素a生成的R等价类，简称为a的等价类： [a]R = {x?a ? A∧a, x?R} = [a][代表元] 如果b? [a]R ，称b为等价类的代表元。长见识(数学技巧——上下标)：符号[a]R 表明此对象与a和R有关，受a和R影响，可视为以a和R为参数的函数，函数值为集合。若将A也视为参数，记作[a]RA 、 [a]R(A)甚至f(a, R, A)均可。——因为a R a，即a?[a]R ，故任何等价类都是非空的，即[a]R ? ?。——a, x?R = a~x = x~a 4.5 等价关系-等价类例2-25：说明下述等价关系的等价类。(1) 一个年级学生集合上的“同班同学”关系。——任意一名学生s生成的等价类就是其班级所有学生的集合。(2) 字符串集合A上的关系R = {x, y?x与y的前31个字符相同}。——不超过31个字符的字符串自己构成等价类；——所有长度超过31且前31个字符相同的字符串构成等价类。(3) 整数集上的关系R = {a, b?a = b?a = -b}。 [a]R = {a, -a}。 4.5 等价关系-等价类(4) 整数集上的模3同余关系。有3个不同的等价类：[0]R = {…, -6, -3, 0, 3, 6, …}[1]R = {…, -5, -2, 1, 4, 7, …}[2]R = {…, -4, -1, 2, 5, 8, …}长见识： [a]R是a生成的，也是与该集合中任何一个元素生成的。——一个等价类是“由相互等价的元素构成的集合”，任何一个都是代表元素，都可以生成该等价类。——模m同余关系共m个“同余类” 4.5 等价关系-等价类证明：采用循环等价法。(1) ? (2)。对?x?[a]R ，有x, a?R由a, b?R 和传递性，有 x?[b]R ，知 [a]R ? [b]R 。同理， [b]R ?[a]R 。故[a]R = [b]R 。定理：设R是集合A上的等价关系，对?a, b?A，下述3个命题等价：(1) a, b?R (2) [a]R = [b]R (3) [a]R ∩[b]R ? ? (2) ? (3)。因[a]R = [b]R ，显然有[a]R ∩[b]R = [a]R ?（因为a?[a]R ） ? ?? 4.5 等价关系-等价类(3) ? (1) [a]R ∩[b]R ? ? ? a, b?R 。因 [a]R ∩[b]R ? ? ，? t ?[a]R ∩[b]R，有t ?[a]R ∧ t ?[b]R ? a, t? R ∧ b, t? R ? a, t? R ∧ t, b? R 因为R是传递的，故 a, b?R。