近世代数理论基础3：等价关系

2019-02-08 本文已影响19人溺于恐

等价关系

关系

设A为一个集合,R为积集合 $A\times A=\{(a,b)|a,b\in A\}$ 的子集,则称R为集合A上的一个关系, $\forall a,b\in A$ ,若 $(a,b)\in R$ ,则称a与b具有关系R,记作aRb,否则称a与b不具有关系R

等价关系

设A为一集合,R是A上的一个关系,若R满足：

自反性： $\forall x\in A$ ,有 $(x,x)\in R$

对称性： $\forall x,y\in A$ ,若 $(x,y)\in R$ ,则 $(y,x)\in R$

传递性： $\forall x,y,z\in A$ ,若 $(x,y)\in R,(y,z)\in R$ ,则 $(x,z)\in R$

则称R为集合A上的一个等价关系,记作 $\sim$

例1

有理数域Q上所有柯西列构成的集合A,即 $A=\{\{a_n\}_{n=1}^\infty|a_n\in Q且\{a_n\}是收敛数列\}$

在A上定义关系 $\sim$ ：

$\forall \{a_n\},\{b_n\}\in A$ ,令 $\lim\limits_{n\to \infty}a_n=a,\lim\limits_{n\to \infty}b_n=b$

若 $a=b$ ,则定义 $\{a_n\}\sim \{b_n\}$

例2

设 $m\gt 1,m\in Z_+$ ,定义 $R=\{(x,y)|x,y\in Z且x-y能被m整除\}$

R是Z上的等价关系

等价类

设R为集合A上的等价关系, $\forall a\in A$ ,与a等价的所有元组成的集合为元a所属的等价类,记作 $[a]$ ,即 $[a]=\{b\in A|(a,b)\in R\}$ ,a称为这个等价类的代表元

所有等价类构成的集合称为A关于R的商集,记为 $A/R$ ,即 $A/R=\{[a]|a\in A\}$

命题

设R为集合A上的等价关系,则 $\forall a,b\in A,[a]=[b]\Leftrightarrow (a,b)\in R$

证明：

$必要性$

$若[a]=[b],则b\in [a]$

$由等价类的定义$

$(a,b)\in R$

$充分性$

$若(a,b)\in R,则\forall c\in [b],有(b,c)\in R$

$由传递性$

$(a,c)\in R$

$\therefore c\in[a]$

$\therefore [b]\subset[a]$

$由对称性$

$(b,a)\in R$

$\forall c\in [a],有(a,c)\in R$

$由传递性$

$(b,c)\in R$

$\therefore c\in [b]$

$\therefore [a]\subset [b]$

$\therefore [a]=[b]\qquad\mathcal{Q.E.D}$

(注：命题表明一个等价类可选择其中的任何一个元为代表元)

划分

设A是一个集合, $\{U_i|i\in I\}$ 是A的子集簇,其中I是某个确定的指标集,满足：

(1) $\forall i\neq j,i,j\in I$ ,有 $U_i\cap U_j=\varnothing$

(2) $\bigcup\limits_{i\in I}U_i=A$

则称 $\{U_i|i\in I\}$ 是集合A的一个划分

定理：若R是集合A上的等价关系,则商集 $A/R$ 是A上的一个划分

证明：

$对A/R中任意两个等价类[a]和[b]$

$若[a]\neq [b],则[a]\cap [b]=\varnothing$

$若不然,即[a]\cap [b]\neq \varnothing$

$\forall c\in [a]\cap [b]$

$由c\in [a]可知(a,c)\in R$

$由c\in [b]可知(b,c)\in R$

$由对称性知(c,b)\in R$

$由传递性(a,b)\in R$

$\therefore [a]=[b],矛盾$

$下证A=\bigcup\limits_{[a]\in A/R}[a]$

$\forall [a]\in A/R,有[a]\subseteq A$

$\therefore \bigcup\limits_{[a]\in A/R}[a]\subset A$

$\forall a\in A,有a\in [a]\subseteq \bigcup\limits_{[a]\in A/R}[a]$

$\therefore A\subseteq \bigcup\limits_{[a]\in A/R}[a]\qquad\mathcal{Q.E.D}$

定理：若 $\{U_i|i\in I\}$ 是集合A的一个划分,则存在A上的一个等价关系R,使 $A/R=\{U_i|i\in I\}$

证明：

$定义A上的关系R$

$R=\{(a,b)|\exists U_i使a,b\in U_i\}$

$显然,R为A上的等价关系$

$令B=\{U_i|i\in I\}$

$\forall [a]\in A/R$

$\because B为集合A的一个划分$

$\therefore \exists U_i\in B使a\in U_i$

$由R的定义知$

$[a]=U_i$

$即[a]\in B$

$\therefore A/R\subset B$

$又\forall U_i\in B$

$取a\in U_i$

$\because [a]=U_i$

$\therefore U_i\in A/R$

$即B\subset A/R\qquad\mathcal{Q.E.D}$

(注：两个定理表明,集合的划分和等价关系是一回事)

例

令集合 $A=\{a,b,c\}$ , $U_1=\{a\}$ , $U_2=\{b,c\}$ ,则 $\{U_1,U_2\}$ 是A的一个划分,该划分对应的等价关系为 $R=\{(a,a),(b,b),(c,c),(b,c),(c,b)\}$

设 $f:A\to B$ 为一个映射,则f可诱导出A上的一个关系R, $R=\{(a,b)|f(a)=f(b),a,b\in A\}$ ,显然R是A上的等价关系,其商集为 $A/R=\{[a]|a\in A\}$

f还可诱导出一个从 $A/R$ 到B的映射 $\bar{f}:\bar{f}([a])=f(a)$

定理：(1)上述 $\bar{f}$ 是单射

(2) $\bar{f}$ 是双射 $\Leftrightarrow$ f是满射

证明：

$(1)先证\bar{f}的定义是良性的$

$\forall [a],[b]\in A/R$

$若[a]=[b],则(a,b)\in R$

$\therefore f(a)=f(b)$

$\therefore \bar{f}([a])=\bar{f}([b])$

$再证\bar{f}是单射$

$\forall [a],[b]\in A/R$

$若\bar{f}([a])=\bar{f}([b])$

$即f(a)=f(b)$

$\therefore (a,b)\in R$

$\therefore [a]=[b]$

$(2)由(1)知\bar{f}是单射$

$\therefore \bar{f}是双射\Leftrightarrow \bar{f}是满射$

$显然,\bar{f}是满射\Leftrightarrow f是满射\qquad\mathcal{Q.E.D}$

自然映射(典范映射)

$\pi:A\to A/R,\pi(a)=[a]$

例：设 $A=\{1,2,3,4\}$ , $B=\{a,b,c\}$ ,从A到B的一个映射f定义如下： $f(1)=f(2)=f(3)=a$ , $f(4)=b$ ,则由f诱导出的等价关系为

$R=\{(1,1,),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2),(4,4)\}$

它的商集为 $A/R=\{[1],[4]\}$ ,其中 $[1]=\{1,2,3\}=[2]=[3]$ , $[4]=\{4\}$

映射f诱导的从集合 $A/R=\{[1],[4]\}$ 到B的映射 $\bar{f}$ 如下： $\bar{f}([1])=f(1)=a$ , $\bar{f}([4])=c$ ,显然, $\bar{f}$ 的定义与 $A/R$ 中元的代表元选择无关,即 $\bar{f}$ 是良性定义,且 $\bar{f}$ 是单射,由于f不是满射,所以 $\bar{f}$ 也不是双射

近世代数理论基础3：等价关系

等价关系

关系

等价关系

例1

例2

等价类

命题

划分

例

自然映射(典范映射)

猜你喜欢

热点阅读