等价关系
关系
设A为一个集合,R为积集合的子集,则称R为集合A上的一个关系,,若,则称a与b具有关系R,记作aRb,否则称a与b不具有关系R
等价关系
设A为一集合,R是A上的一个关系,若R满足:
自反性:,有
对称性:,若,则
传递性:,若,则
则称R为集合A上的一个等价关系,记作
例1
有理数域Q上所有柯西列构成的集合A,即
在A上定义关系:
,令
若,则定义
例2
设,定义
R是Z上的等价关系
等价类
设R为集合A上的等价关系,,与a等价的所有元组成的集合为元a所属的等价类,记作,即,a称为这个等价类的代表元
所有等价类构成的集合称为A关于R的商集,记为,即
命题
设R为集合A上的等价关系,则
证明:
(注:命题表明一个等价类可选择其中的任何一个元为代表元)
划分
设A是一个集合,是A的子集簇,其中I是某个确定的指标集,满足:
(1),有
(2)
则称是集合A的一个划分
定理:若R是集合A上的等价关系,则商集是A上的一个划分
证明:
定理:若是集合A的一个划分,则存在A上的一个等价关系R,使
证明:
(注:两个定理表明,集合的划分和等价关系是一回事)
例
令集合,,,则是A的一个划分,该划分对应的等价关系为
设为一个映射,则f可诱导出A上的一个关系R,,显然R是A上的等价关系,其商集为
f还可诱导出一个从到B的映射
定理:(1)上述是单射
(2)是双射f是满射
证明:
自然映射(典范映射)
例:设,,从A到B的一个映射f定义如下:,,则由f诱导出的等价关系为
它的商集为,其中,
映射f诱导的从集合到B的映射如下:,,显然,的定义与中元的代表元选择无关,即是良性定义,且是单射,由于f不是满射,所以也不是双射
网友评论