集合论-第三章1.ppt

2. 由定理可知：要想构造关系R的传递闭包，需要对R1,R2,…,Rn,…进行运算。 当A是无限集合时，这实际上是不可能实现的，但理论上的证明是必要的。 当A是有限集合时，由定理可知，在R1,R2,…,Rn,…中只有有限个不同的合成关系，所以在计算时，可以用有限个合成关系。 3.尽管A有限，但A中元素比较多时，也只能用计算机来实现。 定理7 设R是A上的一个二元关系，|A|=n，则 4.4 从一个已知的关系来构造关系R的三种闭包 定理4 设R是非空集合A上的二元关系，则 r(R)= R∪R0 =R∪IA。 定理5 设R是非空集合A上的二元关系，则 s(R)=R∪R-1。 定理6 设R是非空集合A上的二元关系，则 说明：1. t(R)也记为R+，记R*=R0∪R+—R* 称为自反传递闭包。 2. 由定理可知：要想构造关系R的传递闭包，需要对R1,R2,…,Rn,…进行运算。 当A是无限集合时，这实际上是不可能实现的，但理论上的证明是必要的。 当A是有限集合时，由定理可知，在R1,R2,…,Rn,…中只有有限个不同的合成关系，所以在计算时，可以用有限个合成关系。 3.尽管A有限，但A中元素比较多时，也只能用计算机来实现。 定理7 设R是A上的一个二元关系，|A|=n，则 例1集合A={a,b,c}，A上的关系 R={(a,b),(b,c),(c,a)}，则 r(R)=R∪IA={(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)}; s(R)=R∪R-1={(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)}; t(R)=R1∪R2∪R3={(a,b),(b,c),(c,a),(b,a), (c,b),(a,c),(a,a),(b,b),(c,c)}。 例2 集合A={a,b,c,d}，A上的关系 R={(a,b),(b,c), (c,d),(d,a)}，则 R+=全关系。 例3 集合A={a,b,c,d}，A上的关系 R={(a,b),(b,c),(c,a)}。则 R+={(a,b),(b,c),(c,a),(b,a),(c,b),(a,c), (a,a),(b,b),(c,c)} 。 对于A上的二元关系，已经会构造r(R),s(R)，t(R)，它们都是具有单一性质的闭包。但有时候希望所求的闭包具有两种或两种以上的性质，如何运算能够得到所需要的结果呢？于是有：闭包的合成运算。 4.5闭包的合成运算 一个关系R的闭包仍然是一个关系，还可以再求它的闭包，这种运算称为闭包的合成运算。例如关系的自反闭包r(R)，再求它的对称闭包s(r(R))就是闭包的合成运算。为了简化，约定s(r(R))写成sr(R)，称为自反对称闭包。tr(R)称为自反传递闭包。类似的，tsr(R)=t(s(r(R)))称为自反、对称、传递闭包。 定理8 设R是非空集合A上的关系，则 (1) rs(R)=sr(R); (2) rt(R)=tr(R); (3) st(R)?ts(R)。 说明： 1.由定理可知，若要求出R的自反、对称和传递闭包，则应先求r(R)，再求出sr(R)，最后求tsr(R)。 若先求出tr(R)，再求str(R)，则str(R)不一定是传递的。 2. 例:整数集合Ⅰ上的小于关系“＜”有这样的性质： st(＜)≠ts(＜) 因为st(＜)＝s(＜)------不等关系“≠”。而 ts(＜)＝t(≠)-------“全关系”。 4.6 例题 例1 证明：R·R*=R*·R=R+。 例2 设R是集合A上的反对称关系，则t(R)一定是反对称的吗？ R={(a,b),(b,c),(c,a)} t(R)=R1∪R2∪R3={(a,b),(b,c),(c,a),(b,a), (c,b),(a,c),(a,a),(b,b),(c,c)}。 例3 是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？ 例5 证明：如果R是对称的，则R＋也是对称的。 第三章 关系 第三章 关 系 1. 映射是关系的一种特例 映射反映的是事物之间的单值的依赖关系，而事物之间不仅仅是单值依赖关系，大部分都是多值的依赖关系。对于这种多值的依赖关系，可以用“关系”这个概念来描述。因此映射是关系的一种特殊情况。 2.在这里，所研究的关系主要是二元关系，即两个对象之间的关系，以后就不在特殊说明了。 3. 内容