等价关系、等价类与划分

等价关系的定义

定义：设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一 个等价关系，若<x,y> ∈R ，称x等价于y，记作x~y。

（即R同时满足自反性、对称性、传递性，则R为A上的等价关系）

例1：

设A={1,2...,8}，如下定义A上的关系R：
R={<x,y>|x,y≡∈A∧x≡y(mod3)}, 其中x≡y(mod3)叫做x与y模3相等（即x除以3的余数与y除以3的余数相等）

R={ <1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<8,8>,   <1,4>,<1,7>,<4,1>,<4,7>,<7,1>,<7,4>,<2,5>,<2,8>,<5,2>,<5,8>,<8,2>,<8,5>,<3,6>,<6,3>}
因为∀x∈A,有x≡x(mod3)
∀x,y∈A,有x≡y(mod3),则有y≡x(mod3)
∀x,y,z∈A,有x≡y(mod3),y≡z(mod3)则有x≡z(mod3)
同时满足自反性、对称性、传递性，所以R为A上的等价关系
以下为R的关系图

例2：

设S={a,b,c},定义S上的关系R=Is∪{<a,b>,<b,a>}，R是否是S上的等价关系？（注：Is中的s为I的下标）

正确答案：是

等价类

定义：设R为非空集合A上的等价关系, ∀x∈A，令[x]R = { y | y∈A∧xRy }
称 [x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为[x]。

例3：

求例1中等价关系的等价类。

等价类：
	[1]=[4]=[7]={1,4,7}
    [2]=[5]=[8]={2,5,8}
    [3]=[6]={3,6}

等价类的性质

设R是非空集合A上的等价关系, 则

(1) ∀x∈A, [x] 是A的非空子集

(2) ∀x, y∈A, 如果 x R y, 则 [x]=[y]

(3) ∀x, y∈A, 如果 x y, 则 [x]与[y]不交

(4) ∪{ [x] | x∈A}=A，即所有等价类的并集就是A

例4：

A={ 1, 2, … , 8 }上模 3 等价关系的等价类：
 [1]=[4]=[7]={1,4,7}，      
 [2]=[5]=[8]={2,5,8}，      
 [3]=[6]={3,6}
      以上3 类两两不交；   
       {1,4,7}∪{2,5,8}∪{3,6} = {1,2, … ,8}

例5：

设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则[a]=？[b]=？[c]=？

[a]={a,b}
[b]={a,b}
[c]={c}

集合的划分

定义 设A为非空集合, 若A的子集族π(π ⊆ P(A)) 满足下面条件：
(1) Ø ∉ π

(2) ∀x∀y (x,y∈π∧x≠y→x∩y= Ø)

(3) ∪π=A

称π是A的一个划分, 称π中的元素为A的划分块。

例6：

设A＝{a, b, c, d}, 
给定π1,π2,π3,π4,π5,π6如下：
      π1= { {a, b, c}, {d} }，
      π2= { {a, b}, {c}, {d} }
      π3= { {a}, {a, b, c, d} },
      π4= { {a, b}, {c} }
      π5= { Ø,{a, b}, {c, d} }, 
      π6= { {a, {a}}, {b, c, d} }
  
π1,π2是A的划分，其他都不是A的划分。

商集

定义：设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A }

例7：

 A={1,2,…,8},A关于模3等价关系R的商集为：
      A/R = { {1,4,7}, {2,5,8}, {3,6} }
      A关于恒等关系和全域关系的商集为：
              A/IA = { {1},{2}, … ,{8}}
              A/EA = { {1, 2, … ,8} }

例8：

设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则S/R=？

正确答案：{{a,b},{c}}

等价关系与划分的一一对应

商集 A/R 就是 A 的一个划分；

例如： A={1,2,…,8},A关于模3等价关系R的商集为：
A/R = { {1,4,7}, {2,5,8}, {3,6} }，它就是Ａ的一个划分

不同的商集对应于不同的划分；

任给 A 的一个划分π, 如下定义 A 上的关系 R：

R = {<x,y> | x,y∈A∧x 与 y 在π的同一划分块中}，则 R 为 A上的等价关系, 且该等价关系确定的商集是π。

例9：

求出A＝{1,2,3}上所有的等价关系
求解思路：先求出A的所有划分, 然后根据划分写出对应的等价关系。(如下图)

π1对应于全域关系 EA
π2对应等价关系 R2={<2,3>,<3,2>}∪IA
π3对应等价关系 R3 ={<1,3>,<3,1>}∪IA
π4对应等价关系 R4={<1,2>,<2,1>}∪IA
π5  对应于恒等关系 IA
(注：以上所出现的IA，A为I的下标)

等价关系

等价关系的定义

定义：设$R$为非空集合$A$上的关系，若$R$是自反的、对称的和传递的，则称$R$为$A$上的等价关系。对任何$x,y\in A$，若$<x,y>\in R$，则记作$x\sim y$

例：

1. 若有 A = { 1 , 2 , . . . , 8 } A=\{1,2,...,8\} A={1,2,...,8}， R = { &lt; x , y &gt; ∣ x , y ∈ A ∧ x ≡ y ( m o d 3 ) } R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\} R={<x,y>∣x,y∈A∧x≡y(mod3)}。则$R$为$A$上的等价关系。
2. 动物按种属进行分类后，“具有相同种属”的关系是动物集合上的等价关系。
3. 集合上的恒等关系和全域关系都是等价关系。

等价类

设$R$是非空集合$A$上的等价关系，则$A$上互相等价的元素构成了$A$的若干个子集，称作等价类。

等价类的一般定义：设$R$是非空集合$A$上的等价关系，对任意的$x\in A$，令 [ x ] R = { y ∣ y ∈ A , x R y } [x]_R=\{y|y\in A, x\text{R}y\} [x]R​={y∣y∈A,xRy}则称$[x{]}_R$为$x$关于$R$的等价类，简称$x$的等价类，简记为$[x]$

例如：若有 A = { 1 , 2 , . . . , 8 } A=\{1,2,...,8\} A={1,2,...,8}， R = { &lt; x , y &gt; ∣ x , y ∈ A ∧ x ≡ y ( m o d 3 ) } R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\} R={<x,y>∣x,y∈A∧x≡y(mod3)}，有等价类： [ 1 ] = [ 4 ] = [ 7 ] = { 1 , 4 , 7 } [1]=[4]=[7]=\{1,4,7\} [1]=[4]=[7]={1,4,7} [ 2 ] = [ 5 ] = [ 8 ] = { 2 , 5 , 8 } [2]=[5]=[8]=\{2,5,8\} [2]=[5]=[8]={2,5,8} [ 3 ] = [ 6 ] = { 3 , 6 } [3]=[6]=\{3,6\} [3]=[6]={3,6}等价类具有如下性质：
设$R$是非空集合$A$上的等价关系，对任意的$x,y\in A$，下面的结论成立。

1. $[x]̸=\varnothing$，且$[x]\subseteq A$；
2. 若$x\text{R}y$，则$[x]=[y]$；
3. 若$x̸\text{R}y$，则$[x]\cap [y]=\varnothing$；
4. ${\bigcup }_{x\in A}[x]=A$.

其中，(1)表明任何等价类都是集合$A$的非空子集；(2)和(3)表明在$A$中任取两个元素，它们的等价类或是相等，或是不交；(4)表示所有等价类的并集就是$A$.

商集

定义：设$R$是非空集合$A$上的等价关系，以$R$的不交等价类为元素的集合称作$A$在$R$下的商集，记作$A/R$： A / R = { [ x ] R   ∣   x ∈ A } A/R=\{[x]_R\ |\ x\in A\} A/R={[x]R​ ∣ x∈A}例如：
1、若有 A = { 1 , 2 , . . . , 8 } A=\{1,2,...,8\} A={1,2,...,8}， R = { &lt; x , y &gt; ∣ x , y ∈ A ∧ x ≡ y ( m o d 3 ) } R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\} R={<x,y>∣x,y∈A∧x≡y(mod3)}，有商集： A / R = { { 1 , 4 , 7 } , { 2 , 5 , 8 } , { 3 , 6 } } A/R=\{\{1,4,7\},\{2,5,8\},\{3,6\}\} A/R={{1,4,7},{2,5,8},{3,6}}

2、非空集合$A$上的全域关系$E_A$是$A$上的等价关系，对任意$x\in A$有$[x]=A$，商集 A / E A = { A } A/E_A = \{A\} A/EA​={A}

划分与划分块

设$A$是非空集合，若存在一个$A$的子集族$\pi (\pi \subseteq P(A))$满足以下条件：

1. $\varnothing \notin \pi$
2. $\pi$中任意两个元素不交
3. $\pi$中所有元素的并集等于$A$，则称$\pi$为$A$的一个划分，且称$\pi$中的元素为划分块

例：考虑集合 A = { a , b , c , d } A=\{a,b,c,d\} A={a,b,c,d}，则：

1. { { a } , { b , c } , { d } } \{\{a\}, \{b,c\},\{d\}\} {{a},{b,c},{d}}
2. { { a , b , c , d } } \{\{a,b,c,d\}\} {{a,b,c,d}}
3. { { a , b } , { c } , { a , d } } \{\{a,b\}, \{c\},\{a,d\}\} {{a,b},{c},{a,d}}
4. { ∅ , { a , b } , { c , d } } \{\varnothing, \{a,b\}, \{c,d\}\} {∅,{a,b},{c,d}}
5. { { a } , { b , c } } \{\{a\},\{b,c\}\} {{a},{b,c}}

中(1)、(2)是$A$的划分；(3)不是$A$的划分，因为子集 { a , b } \{a,b\} {a,b}与 { a , d } \{a,d\} {a,d}有交；(4)不是$A$的划分，因为$\varnothing$在其中；(5)不是$A$的划分，因为所有子集的并集不为$A$.

由商集和划分的定义不难看出若有$A$上的二元关系 R = { &lt; x , y &gt;   ∣   x , y ∈ π } R=\{&lt;x,y&gt;\ |\ x,y \in\pi\} R={<x,y> ∣ x,y∈π}，则可证明$R$是$A$上的等价关系，称为有划分$\pi$所诱导的等价关系，且该等价关系的商集为$\pi$。所以集合$A$上的等价关系与集合$A$的划分是一一对应的。

偏序关系

在介绍偏序关系之前先了解一下什么是全序关系：
全序集的定义： 设$<A,\preccurlyeq >$为偏序集，若对任意的$x,y\in A$，$x$和$y$都可比，则称$\preccurlyeq$为$A$上的全序关系，且称$<A,\preccurlyeq >$为全序集。

例如： { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5}上的$⩽$关系就是全序关系，而整除关系就不是全序关系。

偏序关系的定义

设$R$为非空集合$A$上的关系，若$R$是自反的、反对称的、传递的，则称$R$为$A$上的偏序关系。简称偏序，记作$\preccurlyeq$

设$\preccurlyeq$为$A$上的偏序关系，若有有序对$<x,y>$属于偏序$\preccurlyeq$，可记作$x\preccurlyeq y$，读作$x$小于等于$y$，不过这里的“小于等于”不是指数的大小，而是指它们在偏序中的位置先后。

例如在集合 A = { 1 , 2 , 3 } A=\{1,2,3\} A={1,2,3}中，偏序$\preccurlyeq$是$A$上的大于等于关系,则： ≼ = { &lt; 3 , 3 &gt; , &lt; 3 , 2 &gt; , &lt; 3 , 1 &gt; , &lt; 2 , 2 &gt; , &lt; 2 , 1 &gt; &lt; 1 , 1 &gt; } \preccurlyeq = \{&lt;3,3&gt;,&lt;3,2&gt;,&lt;3,1&gt;,&lt;2,2&gt;,&lt;2,1&gt;&lt;1,1&gt;\} ≼={<3,3>,<3,2>,<3,1>,<2,2>,<2,1><1,1>}那么就有$3\preccurlyeq 2$、$3\preccurlyeq 1$等，它们分别表示$<3,2>\in \preccurlyeq$、$<3,1>\in \preccurlyeq$

偏序集

偏序集定义：一个集合$A$与$A$上的偏序关系$R$一起称作偏序集，记作$<A,R>$。

可比与盖住：
设$<A,\preccurlyeq >$为偏序集，对于任意的$x,y\in A$，若果$x\preccurlyeq y$或$y\preccurlyeq x$成立，则称$x$与$y$是可比的，若$x\prec y$(即$x\preccurlyeq y\wedge x̸=y$)，且不存在$z\in A$使得$x\prec z\prec y$，则称$y$盖住$x$。

例如：$<A,\preccurlyeq >$是偏序集，其中 A = { 1 , 2 , 3 , 4 , 5 } A=\{1,2,3,4,5\} A={1,2,3,4,5}，$\preccurlyeq$是整除关系。

那么对任意$x\in A$都有$1\preccurlyeq x$，所以1和1,2,3,4,5都是可比的；但是2与3相互不能整除，所以2和3是不可比的:。

对于1和2来说，$1\prec 2$，并且不存在$z\in A$使得1整除$z$并且$z$整除2，所以2盖住1，同样的有4盖住2，但4不盖住1因为有$1\prec 2\prec 4$。

显然的，若$x$与$y$不可比，则一定不会有$x$盖住$y$或反之。

哈斯图

对于又穷的偏序集$<A,\preccurlyeq >$可以用哈斯图来描述。在哈斯图中，每一个节点表示$A$中的一个元素，节点位置按它们在偏序集中的次序从低向上排列。若$y$盖住$x$则在$xy$之间连一条直线。

例如：$<A,\preccurlyeq >$是偏序集，其中 A = { 1 , 2 , 3 , 4 , 5 } A=\{1,2,3,4,5\} A={1,2,3,4,5}，$\preccurlyeq$是整除关系，则该偏序集的哈斯图为：

由哈斯图不能看出全序集的哈斯图是一条直线，因此，全序集也称做线序集

元与界

设$<A,\preccurlyeq >$为偏序集，$B\subseteq A$

1. 若$\exists y\in B$，使得$\forall x(x\in B\to y\preccurlyeq x)$成立，则称$y$是$B$的最小元。
2. 若$\exists y\in B$，使得$\forall x(x\in B\to x\preccurlyeq y)$成立，则称$y$是$B$的最大元。
3. 若$\exists y\in B$，使得$\neg \exists x(x\in B\wedge x\prec y)$成立，则称$y$是$B$的极小元。
4. 若$\exists y\in B$，使得$\neg \exists x(x\in B\wedge y\prec x)$成立，则称$y$是$B$的极大元。

设$<A,\preccurlyeq >$为偏序集，$B\subseteq A$

1. 若$\exists y\in A$，使得$\forall x(x\in B\to x\preccurlyeq y)$成立，则称$y$为$B$的上界。
2. 若$\exists y\in A$，使得$\forall x(x\in B\to y\preccurlyeq x)$成立，则称$y$为$B$的下界。
3. 令 C = { y   ∣   ∀ x ( x ∈ B → x ≼ y ) } C=\{y\ |\ \forall x(x\in B\to x\preccurlyeq y)\} C={y ∣ ∀x(x∈B→x≼y)}，则称$C$的最小元为$B$的上确界(最小上界)
4. 令 C = { y   ∣   ∀ x ( x ∈ B → y ≼ x ) } C=\{y\ |\ \forall x(x\in B\to y\preccurlyeq x)\} C={y ∣ ∀x(x∈B→y≼x)}，则称$C$的最大元为$B$的下确界(最大下界)