等价关系与序关系.ppt

等价关系与序关系笛卡尔积集合A与集合B的笛卡儿积为一个集合,记为A×BA×B={(X,y)X∈A且y∈B(x,y)是有序对关系·集合A到集合B的关系是笛卡儿积A×B的个子集如果R是集合A到集合B的一个关系,且(Xy是R的一个元素,那么称关于R与y关联(有关系,般记作xRy集合S到其自身的关系称为集合S上的关系S={草,树,猪,牛,LYC}T={植物,动物,人}·定义R为S到T的一个关系草R植物为真,草R动物为假猪R动物为真,猪R人为假·LYCR人为真,LYCR植物假等价关系·若集合S上的关系R具备以下三个性质1、自反性:对S的任意元素X,XRx为真2、对称性:只要xRy为真,yRx就为真3、传递性:只要ⅹRy为真,yRz为真,XRz就为真等于关系·一个符号集合S定义S上的关系R:如果S中的两个符号x,y代表同一个事物的话,那么XRy就为真容易证明,R是等价关系整除关系设S是正整数的集合,定义xRy为xy。于是,3R6、7R35为真,但8R4,6R9为假。R是S上的一个关系。R有自反性,传递性,但没有对称性其他例子·设S是一些集合组成的集合族,定义ARB为A∩B≠空集显然,R有自反性和对称性,但没传递性定义R为:只要两个人x和y的姓相同,xRy就为真。这是一个等价关系等价类如果R是S上的等价关系,ⅹ∈S,则S中与x相关联的元素的集合称为包含x的等价类,记为x]。所以x={y∈SyRx}自反性保证了X∈[×等价类的性质1、如果ⅹ和y是集合S的元素,那么ⅹ与y相关联,当且仅当x]=y]2、关系R的两个等价类要么相等,要么互不相交