【集合论】等价关系 ( 等价关系概念 | 等价关系示例 | 等价关系与闭包 )

2023-03-28 18:05:52 浏览数 (1)

文章目录

  • 一、等价关系
  • 二、等价关系示例
  • 三、等价关系与闭包示例

一、等价关系

等价关系概念 :

A

集合是非空集合 ,

A not= varnothing

, 并且

R

关系是

A

集合上的二元关系 ,

R subseteq Atimes A

;

如果

R

关系是 自反 , 对称 , 传递 的 , 那么称

R

关系是 等价关系 ;

二、等价关系示例

1. 关系

1

:

x

与

y

年龄相同 ;

  • 自反 :
x

与

x

年龄相同 ; 自反 成立 ;

  • 对称 :
x

与

y

年龄相同 ,

y

与

x

年龄相同 ; 对称 成立 ;

  • 传递 :
x

与

y

年龄相同 ,

y

与

z

年龄相同 ,

x

与

z

年龄相同 ; 传递 成立 ;

  • 等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;

由上边可以看出 , 等价关系是用于分类的 , 同一年出生的人可以划分到一个等价类中 ;

2. 关系

2

:

x

与

y

姓氏相同 ;

  • 自反 :
x

与

x

姓氏相同 ; 自反 成立 ;

  • 对称 :
x

与

y

姓氏相同 ,

y

与

x

姓氏相同 ; 对称 成立 ;

  • 传递 :
x

与

y

姓氏相同 ,

y

与

z

姓氏相同 ,

x

与

z

姓氏相同 ; 传递 成立 ;

  • 等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;

3. 关系

3

:

x

年龄大于等于

y

;

  • 自反 :
x

年龄大于等于

x

; 自反 成立 ;

  • 对称 :
x

年龄大于等于

y

,

y

年龄大于等于

x

; 对称 不成立 ;

  • 传递 :
x

年龄大于等于

y

,

y

年龄大于等于

z

,

x

年龄大于等于

z

; 传递 成立 ;

  • 等价关系 : 该关系是 自反 , 传递 的 , 不是对称的 , 因此该关系 不是等价关系 ;

4. 关系

4

:

x

与

y

选修同一门课程 ;

  • 自反 :
x

与

x

选修同一门课程 ; 自反 成立 ;

  • 对称 :
x

与

y

选修同一门课程 ,

y

与

x

选修同一门课程 ; 对称 成立 ;

  • 传递 :
x

与

y

选修同一门课程 ,

y

与

z

选修同一门课程 ,

x

与

z

选修同一门课程 ; 上述情况不一定成立 ,

x,y

可能同时选修音乐 ,

y,z

同时选修历史 ,

x,z

没有选修相同的课程 ; 传递 不成立 ;

  • 等价关系 : 该关系是 自反 , 对称 的 , 不是传递的 , 因此该关系 不是等价关系 ;

5. 关系

5

:

x

体重大于

y

;

  • 自反 :
x

体重大于

x

; 自反 不成立 ;

  • 对称 :
x

体重大于

y

,

y

体重大于

x

; 对称 不成立 ;

  • 传递 :
x

体重大于

y

,

y

体重大于

z

,

x

体重大于

z

; 传递 成立 ;

  • 等价关系 : 该关系是 传递 的 , 不是 自反 , 对称 的 , 因此该关系 不是等价关系 ;

三、等价关系与闭包示例

A

集合是非空集合 ,

A not= varnothing

, 并且

R

关系是

A

集合上的二元关系 ,

R subseteq Atimes A

;

对

R

关系求三种闭包 , 有

6

种不同的顺序 , 讨论这些求闭包结果的性质 ;

6

种求闭包的性质 :

rts(R)

: 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;

trs(R)

: 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;

tsr(R)

: 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;

rst(R)

: 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;

srt(R)

: 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;

str(R)

: 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;

参考 : 【集合论】关系闭包 ( 关系闭包求法 | 关系图求闭包 | 关系矩阵求闭包 | 闭包运算与关系性质 | 闭包复合运算 ) 五、闭包复合运算

rs(R) = sr(R)

: 对称闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;

rt(R) = tr(R)

: 传递闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;

st(R) subseteq ts(R)

: 传递闭包 与 对称闭包 的符合运算 , 顺序不同 , 其计算结果不同 ;

因此这里分为两大类

  • ① 先求传递闭包 , 再求对称闭包
  • ② 先求对称闭包 , 再求传递闭包

先求对称闭包 , 再求传递闭包 :

rts(R)

: 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;

trs(R)

: 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;

tsr(R)

: 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;

固定 ts 运算的顺序 , 先 t 后 s , r 运算可以放在任意位置 ;

自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;

对称与传递 , 后求的传递 , 因此其结果是传递的 ;

上述三个顺序产生的结果是 自反 , 对称 , 传递 的 , 其满足等价关系 , 结果是 等价闭包 ;

先求对传递包 , 再求对称闭包 :

rst(R)

: 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;

srt(R)

: 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;

str(R)

: 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;

固定 st 运算的顺序 , 先 s ( 对称闭包 ) 后 t ( 传递闭包 ) , r ( 对称闭包 ) 运算可以放在任意位置 ;

自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;

对称与传递 , 先求的传递 , 然后求对称 , 对称会破坏传递 , 因此其结果不是传递的 ;

上述三个顺序产生的结果是 自反 , 对称 , 不传递 的 , 其不满足等价关系 ;

r t s ( R ) = t r s ( R ) = = t s r ( R ) rts(R)=trs(R)==tsr(R) rts(R)=trs(R)==tsr(R)

r s t ( R ) = s r t ( R ) = s t r ( R ) rst(R) = srt(R) = str(R) rst(R)=srt(R)=str(R)

自反

成立

成立

对称

成立

成立

传递

成立

不成立

等价关系

成立 ( 该闭包称为等价闭包 )

不成立

rts(R)=trs(R)==tsr(R)
rst(R) = srt(R) = str(R)

自反成立成立对称成立成立传递成立不成立等价关系成立 ( 该闭包称为等价闭包 )不成立

闭包 集合

0 人点赞