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

等价关系

关系

设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}$ 也不是双射

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 221,695评论 6赞 515
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,569评论 3赞 399
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 168,130评论 0赞 360
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,648评论 1赞 297
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,655评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,268评论 1赞 309
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,835评论 3赞 421
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,740评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,286评论 1赞 318
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,375评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,505评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,185评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,873评论 3赞 333
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,357评论 0赞 24
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,466评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,921评论 3赞 376
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,515评论 2赞 359

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

等价关系

关系

等价关系

例1

例2

等价类

命题

划分

例

自然映射(典范映射)

推荐阅读更多精彩内容