第三章 关系 3.5 等价关系 等价关系：广义的相等关系 把某个方面相同的对象看作是相同的

Presentation on theme: "第三章 关系 3.5 等价关系 等价关系：广义的相等关系 把某个方面相同的对象看作是相同的"— Presentation transcript:

1 第三章 关系 3.5 等价关系 等价关系：广义的相等关系 把某个方面相同的对象看作是相同的
按上述原则把对象分类（等价类），每类中的任意一个对象均可以代表整个类 例：人群按年龄划分 整数按同余（mod m）分类

2 3.5.1 等价关系 定义1 等价关系 自反、对称、传递的关系 a与b关于R等价a R b 例 1 设R是英语字母串的集合上的关系，并且aRb，当且仅当l(a)=l(b)，其中l(x)是串x的长度。R是等价关系吗？ 解: 因为l(a)=l(b),从而只要a是一个串，就有aRb，故R是自反的。其次，假设aRb，即l(a)=l(b)，那么有bRa，因为l(b)=l(a)。因此R是对称的。最后，假设aRb和bRc，那么有l(a)=l(b)和l(b)=l(c)。因此，l(a)=l(c)，即aRc。从而R是传递的。由于R是自反的、对称的和传递的，R是等价关系。

3 例 2 设R是实数集上的关系，并且aRb，当且仅当a-b是整数。R是等价关系吗？
解： 因为对所有的实数a，a-a=0是整数，即对所有的实数有aRa，因此R是自反的。现在假设aRb，那么a-b是整数，所以b-a也是整数。因此有bRa。R是对称的。如果aRb和bRc，那么a-b和b-c是整数，所以a-c=(a-b)+(b-c)也是整数。因此aRc。于是，R是传递的。综合上述，R是等价关系。 例 3 模m 同余。设m 是大于1 的正整数。证明关系 R=｛(a,b)|a≡b(mod m)｝是整数集上的等价关系。 解： a≡b(mod m)，当且仅当m 整除 a-b。注意a-a=0被m整除，因为0=0*m。因此a≡a(mod m)，从而模m同余关系是自反的。现在假设a≡b(mod m)，那么a-b被m整除，即a-b=km，其中k是整数。从而b-a=(-k)m，即b≡a(mod m)。因此模m同余关系是对称的。下面假设a≡b(mod m)和b≡c(mod m)，那么m整除a-b和b-c。因此，存在整数k和l 使得a-b=km和b-c=lm。把这两个等式加起来得a-c=(a-b)+(b-c)=km+lm=(k+l)m。于是，a≡c(mod m)。从而，模m同余关系是传递的。综合上述，模m同余关系是等价关系。

4 3.5.2 等价类 例：人群按年龄划分 整数按同余（mod m）分类 定义1 等价类 a的等价类[a]R={x︱x R a}，a是[a]R的代表元 例 4 对于模4同余关系，0和1的等价类是什么？ 解： 0的等价类包含使得a  0 (mod 4)的所有整数a。这个类中的整数是被4整除的那些整数。因此，对于这个关系0的等价类是 [0]={…,-8,-4,0,4,8…} 1的等价类包含使得a  1 (mod 4)的所有整数a。这个类中的整数是当被4除时余数为1的那些整数。因此，对于这个关系1的等价类是 [1]={…,-7,-3,1,5,9,…}

5 问题： (1)不同的等价类是否有公共元素？ (2)若[x]R=[a]R，那么同一个等价类就有多个代表元 定理1 下列3个命题等价 (1)a R b (2)[a]R=[b]R (3)[a]R∩[b]R≠ 证明：首先证明(1)推出(2)。假设aRb，我们将通过[a]R [b]R 和[b]R [a]R 来证明[a]R=[b]R 。假设c[a]R ,那么aRc。因为aRb和R的对称性，有bRa。又由于R是传递的，以及bRa和aRc，就得到bRc，因而有c[b]R .这就证明了[a]R [b]R 。类似地可证明[b]R [a]R，证明留给读者作为练习。 其次，我们将证明(2)推出（3）。假设[a]R=[b]R。这就证明了[a]R∩[b]R≠，因为[a]R是非空的（由于R的自反性，a[a]R）。 （接下页）

6 （接上页证明） 下面证明(3)推出(1)。假设[a]R∩[b]R≠。那么存在元素c满足c[a]R和c[b]R，换句话说，aRc和bRc。有对称性有cRb，再根据传递性，就有aRb。 因为(1)推出(2)，(2)推出(3)，(3)推出(1)，所以这三个问题是等价的。 结论： (1)等价类中的元素都等价，与等价类中的元素等价的元素都在等价类中， 不与等价类中的元素等价的元素都不在等价类中 (2)对同一个等价类中的任意两个元素a, b，[a]R=[b]R (3)等价类要么完全，要么不交

7 3.5.3 划分 定义1 划分 集合A的划分是A的非空子集组成的集合族，且集合族中的子集两两不交，其并恰为A。 ={Y∣YA}，且 (1)Y，Y (2)Y, Z，YZ Y∩Z= (3)∪= A 划分块：中的元素 图3-5 集合的划分

8 例 5 假设S={1,2,3,4,5,6}，一族集合A1={1，2，3 }, A2={4, 5} 和A3={6} 构成S的一个划分，因为这些集合是不相交的，且他们的并是S。
定义1 商集 R是X上的等价关系，R的等价类组成的集合族，X/R。 X/R={[x]R∣xX} 例：人群中的年龄相同关系 整数集上的同余关系

9 定理2 商集是划分 R是X上的等价关系，X/R是X的一个划分R 证明：我们知道R的所有等价类的并集就是X的全部，因为X的每个元素x都在它自己的等价类即[x] R中。这也就是说， ∪[x] R =X (x∈X) 又由定理1，这些等价类或是相等或是不相交，因此当x≠y时， [x]∩[y]=Ф 这就说明了这些等价类将X分成不相交的子集，所以等价类构成X的划分。又因为商集是R的等价类组成的集合族，所以商集是划分。

10 定理3 是X的划分，R={(x, y) ∣x,yX，且x和y在的同一块中} 是等价关系
证明：要证明等价关系，必须证明是自反的、对称的、传递的。 (1)对于每一个x∈X，有(x,x)∈R，因为x与它自己是在的同一块中的。因此是自反的。 (2)若(x,y)∈R，即x和y在的同一块中，也就是说y和x在的同一块中，所以(y,x)∈R。因此是对称的。 (3)若(x,y)∈R，(y,z)∈R，即x和y在的同一块中，且y和z在的同一块中，那么x和z也在的同一块中，即(x,z)∈R，所以是传递的。 R是自反的、对称的、传递的，所以是等价关系。

11 RR  R 等价关系和划分本质上描述了同一个事物，是这个事物的两个不同的方面 例 设A={1，2，3}，求出A上的所有等价关系。 先求所有的划分，再从划分求对应的等价关系。 只有1个划分块的划分有一个、具有两个划分块的划分有三个、具有3个划分块的划分有一个 （接下页）

12

13 习题 1.下面是所有人集合上的关系，其中哪些是等价关系？确定一个等价关系中为其他等价关系中所缺少的性质。 a) {(a,b)|a与b有相同的年龄} b) {(a,b)|a与b有相同的父母} c) {(a,b)|a与b有一个相同的父亲或一个相同的母亲} d) {(a,b)|a与b相识} e) {(a,b)|a与b说同一种语言} 2.设R是正整数的有序对集合上的关系((a,b),(c,d))R，当且仅当ad=bc。证明R是等价关系。 3. a) 对于上面的等价关系，（1,2）的等价类是什么？ b) 对于上面的等价关系，解释等价类的含义。

14 4.下面哪些子集族是整数集合的划分？ a)偶数集于奇数集合。 b)正整数集合与负数集合。 c)被3整除的整数集合，当被3除时余数为1的整数集合，当被3除时余数为2的整数集合。 d)小于-100的整数集合，绝对值不超过100的整数集合，大于100的整数集合。 e)不能被3整除的整数集合，偶数集合，当被6除时余数为3的整数集合。 5.假设R1和R2是集合S上的等价关系。确定下面R1与R2的每个组合是否一定为等价关系。 a)R1R b)R1R2