集合论——关系的闭包，等价关系与划分 - 6DAN - 博客园

集合论——关系的闭包，等价关系与划分

设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R’，且R’满足以下条件：

1)        R’是自反的（对称或传递）

2)        R R’

对A上任何包含R的自反（对称或传递）关系R’’有R’  R’’

 

闭包	标记	构造方法
自反闭包	γ(R)	将所有<x, x>R的有序对添加到R中
对称闭包	s(R)	当<a,b>∈R，而<b, a>R时，把有序对<b, a>添加到R中
传递闭包	t(R)	Warshall算法 考察MR的每列，在每列中从上到下找出取值为1的元素。对这些元素按顺序作如下操作：若第i行第j列的元素aij=1，则将矩阵的第j行元素加（布尔加）到第i行上去。对每进行一次操作后得到的矩阵再重复进行上面的操作，最后得到的矩阵就是R的传递闭包的关系矩阵。

表1 闭包的类型及构造方法

 

R是自反的、对称的和传递的，则称R为A上的等价关系。若<x, y>∈R，称x等价于y，记作x~y。

 

设R为非空集合A上的等价关系，x∈A，令

[x]_R={y |y∈A且xRy}

称[x]_R为x关于R的等价类，简记作[x]

 

以R的所有等价类作为元素的集合称为A关于R的商集，记为A/R，A/R={[x]_R |x∈A}

 

A是非空集合，A₁,A₂,…,A_m是它的非空子集，满足以下条件：

1)        任意两个集合的交集为空集

2)        所有子集的并集就是A

称п={A₁,A₂,…,A_m}为集合A的一个划分

 

参考文献：

[1] 俞瑞钊, 陈亮. 集合初步. 浙江: 浙江大学出版社.