美文网首页近世代数
近世代数理论基础3:等价关系

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

作者: 溺于恐 | 来源:发表于2019-02-08 10:58 被阅读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}是双射\Leftrightarrowf是满射

    证明:

    (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:等价关系

        本文链接:https://www.haomeiwen.com/subject/pgkodqtx.html