《大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念》由會(huì)員分享，可在線閱讀，更多相關(guān)《大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念（87頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、大學(xué)課件(第二版)()第5章 代數(shù)系統(tǒng)的基本概念 5.1 二元運(yùn)算及性質(zhì)5.2 代數(shù)系統(tǒng)5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)5.4 例題選解習(xí)題五第三篇 幅代數(shù)結(jié)構(gòu) 集合中的代數(shù)運(yùn)算實(shí)質(zhì)上是集合中的一類函數(shù)。定義5.1.1 設(shè)A是集合，函數(shù)f: AnA稱為集合A上的n元代數(shù)運(yùn)算(operators)， 整數(shù)n稱為運(yùn)算的階(order)。當(dāng)n=1時(shí)，f: AA稱為集合A中的一元運(yùn)算。當(dāng)n=2時(shí)，f: AAA稱為集合A中的二元運(yùn)算。 5.1 二元運(yùn)算及其性質(zhì) 一般地，二元運(yùn)算用算符 。，* ，等等表示，并將其寫于兩個(gè)元素之間，如ZZZ的加法： F(2，3)=+(2，3)=2+3=5注意到Ran f A，即
2、運(yùn)算結(jié)果是A中的元素，這稱為運(yùn)算的封閉性。另外，運(yùn)算是函數(shù)，要具備函數(shù)所具有的對(duì)每一個(gè)自變?cè)形ㄒ坏南竦奶匦浴?【例5.1.1】下面均是一元運(yùn)算的例子。(1) 在Z集合上(或Q，或R)，f: ZZ， x Z，f(x)=-x。(2) 在A=0，1集合上，f: AA， p A，f(p)=p，表示否定。(3) 在R+集合上，f: R+R+， x R+，f(x)= (但在R上，倒數(shù)不是一元運(yùn)算，因?yàn)?無像)。 x1 【例5.1.2】下面均是二元運(yùn)算的例子。(1) 在Z集合上(或Q，或R)，f: ZZZ，x, y Z2，f(x，y)=x+y(或f(x，y)=x-y或f(x，y)=xy)，如f(2，3)=
3、5。注意在N集合上，“減法”因其不封閉性，而不是N上的二元運(yùn)算。 (2) A為集合，P(A)為其冪集。f: P(A)P(A)P(A)。 f可以是、 、 -、 。(3) A=0，1。f: AAA。f可以是、 、 、 。(4) AA=f|f: AA?！?。(復(fù)合)”是AA上的二元運(yùn)算。當(dāng)A是有窮集合時(shí)，運(yùn)算可以用運(yùn)算表給出。如A=0，1，2，3，4，5，二元運(yùn)算“。”的定義見表5.1.1。 表5.1.1表5.1.2 事實(shí)上，對(duì)于表5.1.1，通過觀察我們可看出其運(yùn)算為(x，y )=xy(mod 3)其中，“”是普通乘法。而對(duì)于表5.1.2，此時(shí)的“*”運(yùn)算應(yīng)是在集合0，1上的 (邏輯合取運(yùn)算符)。下
4、面介紹二元運(yùn)算的性質(zhì)。 定義5.1.2設(shè)*，均為集合S上的二元運(yùn)算。(1) 若 x y z(x，y，z Sx*(y*z)=(x*y)*z)，則稱“*”運(yùn)算滿足結(jié)合律。(2) 若 x y(x，y Sx*y=y*x)，則稱“*”運(yùn)算滿足交換律。(3) 若 x y z(x，y，z Sx*(y z)=(x*y) (x*z)，則稱“*”運(yùn)算對(duì)運(yùn)算滿足左分配律； 若 x y z(x，y，z S(y z)*x=(y*x) (z*x)，則稱“*”運(yùn)算對(duì)運(yùn)算滿足右分配律。若二者均成立，則稱“*”運(yùn)算對(duì)“”運(yùn)算滿足分配律。 (4) 設(shè)*，均可交換，若 x， y A，有x*(x y)=xx (x*y)=x則稱“*”
5、運(yùn)算和“”運(yùn)算滿足吸收律。(5) 若 x(x A，x*x=x)，則稱“*”運(yùn)算滿足冪等律。 【例5.1.3】加法、 乘法運(yùn)算是自然數(shù)集上的二元運(yùn)算，減法和除法便不是。但是減法是有理數(shù)集、 實(shí)數(shù)集上的二元運(yùn)算，除法卻仍不是。加法、 乘法滿足結(jié)合律、 交換律，乘法對(duì)加法、 減法滿足分配律，減法不滿足這些定律。乘法“”對(duì)加法“+”運(yùn)算滿足分配律(對(duì)“-”也滿足)。但加法“+”對(duì)乘法“”運(yùn)算不滿足分配律。 【例5.1.4】設(shè)A是集合，在A的冪集P(A)上的二元運(yùn)算并、 交滿足交換律、 結(jié)合律、 吸收律、 冪等律且彼此滿足分配律。【例5.1.5】設(shè)A=a，b，A上的運(yùn)算*、 分別如表5.1.3和表5.1
6、.4所示。 表 5.1.3表 5.1.4 解從*運(yùn)算表可知，*是可交換的。因?yàn)?(a*a)*b=a*b=ba*(a*b)=a*b=b (a*b)*b=b*b=a a*(b*b)=a*a=a所以*是可結(jié)合的。 從運(yùn)算表可知，是可交換的。因?yàn)?(a a) b=a b=aa (a b)=a a=a (a b) b=a b=a a (b b)=a b=a 所以是可結(jié)合的。 (1) b (a*b)=b b=b (b a)*(b b)=a*b=b (2) a (a*b)=a b=a (a a)*(a b)=a*a=a b (a*a)=b a=a (b a)*(b a)=a*a=a b (b*b)=b a=
7、a (b b)*(b b)=b*b=a a (a*a)=a a=a (a a)*(a a)=a*a=a a (b*b)=a a=a (a b)*(a b)=a*a=a所以對(duì)*是可分配的。(由于運(yùn)算滿足交換律成立，因此右分配也成立。) (3) b*(a b)=b*a=b (b*a) (b*b)=b a=a故*對(duì)是不可分配的。又由a*(a b)=a*a=a 及上面(1)、 (2)、 (3)式可知和*滿足吸收律。由運(yùn)算表可知，滿足冪等律，而*不滿足冪等律。下面我們來定義與集合A中的二元運(yùn)算有關(guān)的集合A中的特異元素。 定義5.1.3設(shè)*是集合S中的一種二元運(yùn)算，如果存在er S(el S)且對(duì)任意元素
8、x S 均有x*er=x(el*x=x)，則稱元素er(el)為S中關(guān)于運(yùn)算*的右幺元(左幺元)或右單位元(左單位元)。定理5.1.1設(shè)*是S中的二元運(yùn)算且er與el分別是對(duì)于*的右幺元和左幺元，則er=el=e， 使對(duì)任意元素x S有x*e=e*x=x， 稱元素e為關(guān)于運(yùn)算*的幺元(identity elements)且唯一。 證明因?yàn)閑r和el分別是*的右幺元和左幺元，故有 el*er=el，el*er=er，所以er=el。 令其為e，有x*e=e*x=x設(shè)另有一幺元為右幺元e，那么e=e*e=e故e對(duì)*是唯一的幺元。證畢顯然，對(duì)于可交換的二元運(yùn)算來說，左幺元即為右幺元，反之亦然。因此對(duì)
9、于可交換的二元運(yùn)算，左(右)幺元即幺元。另外，我們必須強(qiáng)調(diào)是對(duì)哪一個(gè)運(yùn)算而言的幺元。 【例5.1.6】在實(shí)數(shù)集R中，對(duì)加法“+”運(yùn)算，0是幺元； 在實(shí)數(shù)集R中，對(duì)乘法“”運(yùn)算，1是幺元； 對(duì)于全集E的子集的并“”運(yùn)算，是幺元； 對(duì)于全集E的子集的交“”運(yùn)算，E是幺元;在命題集合中，對(duì)于析取“”運(yùn)算，矛盾式是幺元； 在命題集合中，對(duì)于合取“”運(yùn)算，重言式是幺元； 在AA=f|f:AA中，對(duì)于復(fù)合“”運(yùn)算，I A是幺元。 定義5.1.4設(shè)*是集合S中的一種二元運(yùn)算，如果存在r S(l S)且對(duì)任意元素x S均有x*r=r(l*x=l)，則稱元素r(l)是S中關(guān)于運(yùn)算*的右零元(左零元)。定理5.1
10、.2設(shè)*是S中的二元運(yùn)算且r 與l分別是對(duì)于*的右零元和左零元，則r=l=， 使對(duì)任意元素x S有x*=*x=， 稱元素是S中關(guān)于運(yùn)算*的零元(zero)且唯一。 證明因?yàn)閞 和l分別是*的右零元和左零元，故有 l*r=l，l*r=r，所以r=l。 令其為，有x*=*x=設(shè)另有一零元為右零元，那么=*=故對(duì)S中的*運(yùn)算是唯一的零元。證畢同樣，需強(qiáng)調(diào)零元是針對(duì)于哪個(gè)運(yùn)算的。 【例5.1.7】在實(shí)數(shù)集R中，對(duì)加法“+”運(yùn)算，沒有零元； 在實(shí)數(shù)集R中，對(duì)乘法“”運(yùn)算，0是零元； 對(duì)于全集E的子集的并“”運(yùn)算，E是零元； 對(duì)于全集E的子集的交“”運(yùn)算，是零元;在命題集合中，對(duì)于析取“”運(yùn)算，重言式是零
11、元； 在命題集合中，對(duì)于合取“”運(yùn)算，矛盾式是零元?！纠?.1.8】設(shè)Sa，b，c， S上*運(yùn)算由運(yùn)算表(如表5.1.5所示)確定，那么b是右零元， a是幺元。 表 5.1.5 我們注意到，關(guān)于同一運(yùn)算可能同時(shí)有幺元和零元，甚至可能有這樣的元素，它關(guān)于同一運(yùn)算既是左(右)幺元，又是右(左)零元，例如表5.1.5第一行(不計(jì)表頭)改為三個(gè)a時(shí)，那么*運(yùn)算有左零元a和右幺元a。 我們強(qiáng)調(diào)以下幾點(diǎn)： (1) 左、 右幺元，幺元，左、 右零元，零元都是常元。 (2) 左、 右幺元，幺元，左、 右零元，零元都是依賴于運(yùn)算的。例如，在代數(shù)結(jié)構(gòu) N，+，中，0關(guān)于數(shù)加 + 是幺元，關(guān)于數(shù)乘是零元； 1關(guān)于是
12、幺元，關(guān)于+則既非幺元又非零元。又如在P(A)中，是關(guān)于的幺元，是關(guān)于的零元； A是關(guān)于的零元，又是關(guān)于的幺元。 (3) 今后，在不致造成混淆時(shí)，特殊元素是關(guān)于什么運(yùn)算的不再一一指出，但當(dāng)有兩個(gè)或兩個(gè)以上的運(yùn)算時(shí)仍將對(duì)此作出申明。這時(shí)，常常出現(xiàn)這樣的情況，一個(gè)運(yùn)算與數(shù)加的性質(zhì)接近，另一個(gè)運(yùn)算與數(shù)乘的性質(zhì)接近，為了簡明、 直觀，我們把前一種運(yùn)算叫做加法運(yùn)算，關(guān)于它的幺元、 零元稱為加法幺元、 加法零元； 常把后一種運(yùn)算叫做乘法運(yùn)算，關(guān)于它的幺元、 零元稱為乘法幺元、 乘法零元。例如，在P(A)，中可稱為P(A)的加法幺元、 乘法零元， 稱A為P(A)的乘法幺元、 加法零元。 定義5.1.5設(shè)*是
13、集合S中的一種二元運(yùn)算，且S中對(duì)于*有e為幺元，x，y為S中元素。若x*ye，那么稱x為y的左逆元，y為x的右逆元，若x對(duì)于*運(yùn)算既有左逆元又有右逆元，則稱x是左、 右可逆的。若x左右均可逆，稱x可逆。顯然對(duì)于二元運(yùn)算*，若*是可交換的，則任何左(右)可逆的元素均可逆。 定理5.1.3設(shè)*是集合S中的一個(gè)可結(jié)合的二元運(yùn)算，且S中對(duì)于*有e為幺元，若x S是可逆的，則其左、 右逆元相等，記作x-1，稱為元素x對(duì)運(yùn)算*的逆元(inverse elements)且是唯一的。(x的逆元通常記為x-1; 但當(dāng)運(yùn)算被稱為“加法運(yùn)算”(記為+)時(shí)， x的逆元可記為-x。) 證明設(shè)xr 和xl分別是x對(duì)*運(yùn)算
14、的右逆元和左逆元，故有xl*x=x*xr=e由于*可結(jié)合，于是xl=xl*e=xl*(x*xr)=(xl*x)*xr=e*xr=xr故xl=xr。假設(shè) ， 均是x對(duì)*的逆元，則=*e=*(x*)=(*x)*=e*=由，故唯一性成立。由逆元定義知，若x -1存在，則x-1*x=x*x-1=e。證畢11x 12x11x 11x 11x 11x11x 12x12x 12x1211 xx 定理5.1.4設(shè)*是集合S中的一個(gè)可結(jié)合的二元運(yùn)算，且e為S中對(duì)于*的幺元，x有逆元x-1，則(x-1)-1=x。證明(x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x)=(x-1)-1*x-1)*x=
15、e*x=x。證畢 由以上討論可得結(jié)論： (1) e-1=e。(2) 并非每個(gè)元素均可逆。 【例5.1.9】(1) 在自然數(shù)集合N上，對(duì)于數(shù)乘“”運(yùn)算，只有數(shù) 1有逆元 1，對(duì)于數(shù)加“+”運(yùn)算，只有數(shù)0有逆元0。總之，任何代數(shù)結(jié)構(gòu)其幺元恒有逆元，逆元為其自身。 (2) 在整數(shù)集合I上(+，的定義同上)，I上每個(gè)元素均有加法逆元，但除1以外的數(shù)都沒有乘法逆元。對(duì)任意x I，x的逆元是-x。 (3) 在有理數(shù)集合Q上(+，的定義同上)，Q上每個(gè)元素x，都有加法逆元-x，除0以外的每個(gè)元素x都有乘法逆元x -1=1/x。 (4) 在P(A)中，對(duì)于運(yùn)算，其幺元為，每個(gè)元素B(B )均無逆元； 對(duì)于運(yùn)算
16、，其幺元為A，每個(gè)元素B(BA)均無逆元。 (5) 在集合AA(其中 AA f|f： AA)中，為函數(shù)的合成運(yùn)算，恒等函數(shù)IA為幺元，從而A中所有雙射函數(shù)都有逆元，所有單射函數(shù)都有左逆元， 所有滿射函數(shù)都有右逆元。定理5.1.5設(shè)*是S上的二元運(yùn)算，e為幺元，為零元，并且|S|2，那么無左(右)逆元。證明首先證 e，否則=e，則S中另有元素a，a不是幺元和零元，從而*ae*aa與a不是零元矛盾，故e得證。 再用反證法證無左(右)逆元，即可設(shè)有左(右)逆元x，那么=x*=e(=*x=e)與e矛盾，故無左(右)逆元。得證。 證畢注意逆元是對(duì)某個(gè)元素而言的，它并不是常元，它不僅依賴于運(yùn)算，而且更依賴
17、于是哪個(gè)元素的逆元。 【例5.1.10】有理數(shù)集合Q上的加法“+”運(yùn)算與乘法“”運(yùn)算，10的加法逆元是 -10， 乘法逆元是1/10; 而-10的加法逆元是10，乘法逆元是-1/10。當(dāng)一個(gè)集合中每一元素都有逆元時(shí)，可以認(rèn)為該集合上定義了一個(gè)一元求逆運(yùn)算。與逆元概念密切相關(guān)的是可約性概念。定義5.1.6設(shè)*是集合S中的一個(gè)二元運(yùn)算， a S，a，如果a滿足: 對(duì)任意x，y S 均有 a*x=a*y x=y(1) x*a=y*a x=y(2) 則稱元素a對(duì)*是可約(可消去)的(cancelable)，當(dāng)a滿足(1)式時(shí)，也稱a是左可約(左可消去)的，當(dāng)a滿足(2)式時(shí)，也稱a是右可約(右可消去)
18、的。 特別地，若對(duì)任意x，y，z S，有(x*y=x*z) x y=z (y*x=z*x) x y=z 則稱運(yùn)算*滿足消去律(可約律)。定理5.1.6若*是 S中滿足結(jié)合律的二元運(yùn)算，且元素a有逆元(左逆元，右逆元)，則a必定是可約的(左可約的，右可約的)。證明設(shè)a的逆元為a-1，對(duì)任意元素x，y S，設(shè)a*x=a*y及x*a=y*a，可得a-1*(a*x)=a-1*(a*y) (x*a)*a-1=(y*a)*a-1即(a-1*a)*x=(a-1*a)*y x*(a*a-1)=y*(a*a-1) 均可推得x=y。因此，a是可約的。 證畢 注意 定理5.1.6的逆并不成立。即a可約推不出a可逆。
19、例如整數(shù)集合I中的乘法運(yùn)算，任一非零元素a均可約，但a除1外其余元素均無逆元。 當(dāng)S是有窮集合時(shí)，其上的二元運(yùn)算?？捎眠\(yùn)算表給出，運(yùn)算的一些性質(zhì)可直接由運(yùn)算表看出。(1) 二元運(yùn)算滿足可交換性的充分必要條件是運(yùn)算表關(guān)于主對(duì)角線對(duì)稱。(2) 二元運(yùn)算滿足冪等性的充分必要條件是運(yùn)算表主對(duì)角線上的每個(gè)元素與它所在行、 列的表頭元素相同。 (3) 二元運(yùn)算有幺元的充分必要條件是該元素對(duì)應(yīng)的行和列依次與該表表頭的行、 列相一致。(4) 二元運(yùn)算有零元的充分必要條件是運(yùn)算表中該元素所對(duì)應(yīng)的行、 列元素均與該元素相同。(5) 二元運(yùn)算中a與b互為逆元素的充分必要條件是運(yùn)算表中位于a所在行、 b所在列的元素及
20、b所在行、 a所在列的元素都是幺元。 【例5.1.11】N4是整數(shù)中模4同余產(chǎn)生的等價(jià)類集合，N4=0，1，2，3， N4上運(yùn)算+4，4定義為 m+4n=(m+n)mod4 m4n=(mn)mod4其中m，n 0，1，2，3，運(yùn)算表如表5.1.6、 5.1.7所示。 表 5.1.6 表 5.1.7 解由表5.1.6可知， 0為幺元，1-1=3，2-1=2，無零元。由表5.1.7可知， 1為幺元，3-1=3，0、 2無逆元，0為零元。 什么是代數(shù)系統(tǒng)？粗略地說，代數(shù)系統(tǒng)是由一個(gè)特定的集合，以及定義于該集合上的若干“運(yùn)算”所組成的。換言之，它是一個(gè)“有組織的集合”?，F(xiàn)代科學(xué)在研究各種不同的現(xiàn)象時(shí)，
21、為了探索它們之間的共同特點(diǎn)，常常利用代數(shù)系統(tǒng)這個(gè)框架研究，以得出深刻的結(jié)果。目前，代數(shù)系統(tǒng)的理論已經(jīng)在理論物理、 生物學(xué)、 計(jì)算機(jī)科學(xué)以及社會(huì)科學(xué)中得到廣泛的應(yīng)用。5.2 代 數(shù) 系 統(tǒng) 定義5.2.1代數(shù)結(jié)構(gòu)是由以下三個(gè)部分組成的數(shù)學(xué)結(jié)構(gòu)： (1) 非空集合S。 (2) 集合S上的若干運(yùn)算。 (3) 一組刻畫集合上各運(yùn)算所具有的性質(zhì)。 代數(shù)結(jié)構(gòu)常用一個(gè)多元序組S，*， 來表示，其中 S是集合，*，為各種運(yùn)算。S稱為基集，各運(yùn)算組成的集合稱為運(yùn)算集，代數(shù)結(jié)構(gòu)也稱為代數(shù)系統(tǒng)。 【例5.2.1】 (1) 以實(shí)數(shù)集R為基集，數(shù)加運(yùn)算“”為二元運(yùn)算，組成一代數(shù)系統(tǒng)，記為R，。 (2) 以全體nn實(shí)數(shù)矩
22、陣組成的集合M為基集，矩陣加“”為二元運(yùn)算，組成一代數(shù)系統(tǒng)，記為M，。 (3) 以集合A的冪集P(A)為基集，以集合并、 交、 補(bǔ)為其二元運(yùn)算和一元運(yùn)算，組成一代數(shù)結(jié)構(gòu)，記為P(A)，。有時(shí)為了突出全集E及空集在P(A)中的特殊地位，也可將這一代數(shù)結(jié)構(gòu)記為 P(A)，A，。這個(gè)系統(tǒng)就是常說的冪集代數(shù)系統(tǒng)。 以上的(1)，(2)，(3)均稱為具體代數(shù)系統(tǒng)，其運(yùn)算滿足的性質(zhì)未列出。 (4) 設(shè)S為一非空集合，*為S上滿足結(jié)合律、 交換律的二元運(yùn)算，那么S，*為代數(shù)結(jié)構(gòu)，稱為一個(gè)抽象代數(shù)系統(tǒng)，即一類具體代數(shù)結(jié)構(gòu)的抽象。例如R，+，M， P(A)， ， P(A)， 都是S，*的具體例子。(5) R，+
23、，-，Z，+，-，均是代數(shù)系統(tǒng)，但我們不能寫Z，R， N，-，因?yàn)樗鼈儾皇谴鷶?shù)系統(tǒng)，它們的運(yùn)算不封閉。注意代數(shù)系統(tǒng)S，*， ，中的這些代數(shù)運(yùn)算可以是不同階的，但我們討論的一般是一、 二階(一元、 二元)運(yùn)算。 由上節(jié)可知，某些代數(shù)系統(tǒng)中存在著一些特異元素，它們對(duì)系統(tǒng)中的運(yùn)算起著重要的作用，如冪集代數(shù)中的和全集E，命題代數(shù)中的重言式和矛盾式，二元運(yùn)算的幺元和零元等，我們稱這些元素為該系統(tǒng)的特異元素或代數(shù)常數(shù)。有時(shí)為了強(qiáng)調(diào)它們的特殊地位，也可將它們列入這種代數(shù)系統(tǒng)的多元序組的末尾，如 P(A)，A，。定義5.2.2如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)的階數(shù)也相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱這兩
24、個(gè)代數(shù)系統(tǒng)具有相同的構(gòu)成成分，也稱它們是同類型的代數(shù)系統(tǒng)。 例如命題代數(shù)與冪集代數(shù)： P(A)， A，與R，+，-，0, 1(這里“-”指一元運(yùn)算相反數(shù))。定義5.2.3設(shè)*是S上的n元運(yùn)算(n1，2，)，T S，如果對(duì)任意元素x1，x2，xn T，*(x1，x2，xn) T，稱*運(yùn)算對(duì)T封閉(c1osed)。 【例5.2.2】設(shè)E為非負(fù)偶數(shù)集，M為非負(fù)奇數(shù)集，那么定義于N上的數(shù)加運(yùn)算對(duì)E封閉，對(duì)M不封閉，數(shù)乘運(yùn)算對(duì)E和M都封閉。定義5.2.4設(shè)S，*是代數(shù)系統(tǒng)，如果有非空集合T滿足 (1) T S, (2) 運(yùn)算*對(duì)T封閉,則稱T，*為代數(shù)系統(tǒng)S，*的子代數(shù)系統(tǒng)，或子代數(shù)(subalgebr
25、a)。根據(jù)定義，子代數(shù)必為一代數(shù)系統(tǒng)，*運(yùn)算所滿足的性質(zhì)顯然在子代數(shù)中仍能得到滿足。注意由于T只是S的子集，S中關(guān)于*運(yùn)算的特殊元素，T中未必仍然具有。 常把S，*叫做S，*的平凡子代數(shù)； 若S含幺元e，那么也把e，*叫做S，*，e 的平凡子代數(shù)。若T是S的真子集，則T構(gòu)成的子代數(shù)稱為S的真子代數(shù)?！纠?.2.3】在例5.2.2中，對(duì)N，+而言，E，+為其子代數(shù)，N，0，為其平凡子代數(shù)，M，不構(gòu)成其子代數(shù)。 本節(jié)將討論代數(shù)系統(tǒng)之間的聯(lián)系，研究兩個(gè)同類型的代數(shù)系統(tǒng)之間的關(guān)系，即同態(tài)與同構(gòu)。同態(tài)與同構(gòu)映射是研究代數(shù)系統(tǒng)的重要工具。兩個(gè)看起來似乎不同的代數(shù)系統(tǒng)，往往具有一些共同的性質(zhì)，或進(jìn)一步它們還
26、會(huì)有相同的結(jié)構(gòu)，僅僅是元素的名稱和標(biāo)記運(yùn)算用的符號(hào)不同而已。在這種情況下，對(duì)其中一個(gè)代數(shù)系統(tǒng)所得的結(jié)論，在改變符號(hào)之后，對(duì)另一個(gè)代數(shù)系統(tǒng)也有效。由于我們只討論含一元運(yùn)算、 二元運(yùn)算的代數(shù)系統(tǒng)，因此下文(直至本章末)常用 S，*表示一個(gè)一般的代數(shù)系統(tǒng)，*表示二元運(yùn)算。為簡明起見，有時(shí)也僅用基集S表示一個(gè)代數(shù)系統(tǒng)。5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 定義5.3.1設(shè)S，*及T，均為代數(shù)系統(tǒng)，如果函數(shù) f: ST對(duì)S中任何元素a，b，有f(a*b)f(a) f(b) 稱函數(shù) f為(代數(shù)系統(tǒng) S到T的)同態(tài)映射，或同態(tài)(homomorphism)，當(dāng)同態(tài)f為單射時(shí)，又稱f為單一同態(tài)； 當(dāng)f為滿射時(shí)，又稱f為
27、滿同態(tài)； 當(dāng)f為雙射時(shí)，又稱f為同構(gòu)映射，或同構(gòu)(isomorphism)。當(dāng)兩個(gè)代數(shù)系統(tǒng)間存在同構(gòu)映射時(shí)，也稱這兩個(gè)代數(shù)系統(tǒng)同構(gòu)，記為S T。當(dāng)f為S，*到S，*的同態(tài)(同構(gòu))時(shí)，稱f為S的自同態(tài)(自同構(gòu))。 f(a*b)=f(a) f(b)稱為同態(tài)f的同態(tài)方程。 【例5.3.1】 (1) 設(shè) f: RR為 f(x)=ex(R為實(shí)數(shù)集)，那么，f為R，+到R，的同態(tài)。因?yàn)閷?duì)任意實(shí)數(shù)x，y，有f(x+y)ex+y=exey=f(x)f(y)由f的定義還可知f為單一同態(tài)。 由f的定義還可知f為單一同態(tài)。 但是當(dāng)f： RR+為 f(x)ex(R+為正實(shí)數(shù)集)，那么 f為R，+到R+，的同構(gòu)映射，換
28、言之，R，+與R+，同構(gòu)。 (2) 設(shè)h: RR為h(x)=2x，那么h為R，+到R，+的自同態(tài)，因?yàn)閷?duì)任何實(shí)數(shù)x，y，有h(x+y)=2(x+y)2x + 2y=h(x)+ h(y)并且h為自同構(gòu)。 識(shí)別和證明兩個(gè)代數(shù)系統(tǒng)是否同構(gòu)是十分重要的代數(shù)學(xué)基本技能。 【例5.3.2】有代數(shù)系統(tǒng)Z，和代數(shù)系統(tǒng)B，其中是普通乘法，定義見表5.3.1，B=1，0，-1。定義映射f: ZB， n Z， 0 1 0 0 0 1)( nnnnf 表 5.3.1 則 a，b Z，有所以f(ab)=f(a) f(b)。f是Z，到B，的同態(tài)，且f(Z)=B。異號(hào)至少有一個(gè)為同正或同負(fù)ba bababaf , 1 0,
29、 0 , 1)( 0)()( 1 0)(),( 0 0)()( 1)( )(且非至少有一個(gè)為bfaf bfaf bfafbfaf 異號(hào)至少有一個(gè)為同正或同負(fù)ba baba , 1 0, 0 , 1 需要指出的是，同態(tài)映射并不是唯一的。如例5.3.1中(1)的同態(tài)映射可取不同的底數(shù)?！纠?.3.3】設(shè)A=a，b，c，d， B=0,1,2,3，*，+4定義見表5.3.2和5.3.3。證明： A，*和B，+4是同構(gòu)的。 表 5.3.2 表 5.3.3 證明設(shè) f: AB，f(a)=0，f(b)=1，f(c)=2，f(d)=3。顯然f是雙射，又*，+4均是可交換的。f(a*b)=f(b)=1 f(a)
30、+4f(b)=0+41=1f(a*c)=f(c)=2 f(a)+4f(c)=0+42=2 f(a*d)=f(d)=3 f(a)+4f(d)=0+43=3 f(a*a)=f(a)=0 f(a)+4f(a)=0+40=0 f(b*b)=f(c)=2 f(b)+4f(b)=1+41=2 f(b*c)=f(d)=3 f(b)+4f(c)=1+42=3 f(b*d)=f(a)=0 f(b)+ 4f(d)=1+43=0 f(c*c)=f(a)=0 f(c)+4f(c)=2+42=0 f(c*d)=f(b)=1 f(c)+4f(d)=2+43=1 f(d*d)=f(c)=2 f(d)+4f(d)=3+43=
31、2 故f是A，*到B，+4的同構(gòu)。證畢同構(gòu)是一個(gè)重要的概念，由上例可以說明不同形式的代數(shù)系統(tǒng)，如果它們之間存在同構(gòu)， 可以抽象地將它們看為本質(zhì)上是一樣的代數(shù)系統(tǒng)，不同之處只是所使用的符號(hào)不一樣。注意到例5.3.3中，A對(duì)于*運(yùn)算，a是幺元，b、 d互逆，a、 c均以自身為逆元；B對(duì)于+4運(yùn)算，0(=f(a)是幺元，1(=f(b)、 3(=f(d)互逆，0(=f(a)、 2(=f(c)均以自身為逆元。 由此猜想： 同態(tài)保持性質(zhì)，并把幺元映射成幺元。 為了進(jìn)一步討論同態(tài)的性質(zhì)，我們引入同態(tài)像的概念。 定義5.3.2設(shè)f為代數(shù)系統(tǒng)S，*到T，的同態(tài)映射，那么稱f(S)為f的同態(tài)像(image und
32、er homomorphism)。定理5.3.1設(shè)f為代數(shù)系統(tǒng)S，*到T，的同態(tài)，那么同態(tài)像 f(S)與構(gòu)成T，的一個(gè)子代數(shù)。證明只要證f(S)對(duì)運(yùn)算封閉即可。為此設(shè)a，b為f(S)中任意兩個(gè)元素，且f(a)=a ， f(b)=b，那么a b=f(a) f(b)=f(a*b) f(S) 故f(S)對(duì)運(yùn)算封閉，f(S)，為T的子代數(shù)。證畢很顯然， f為單射時(shí)S，*與同態(tài)像 f(S)，同構(gòu)，這使我們想到，同態(tài)像應(yīng)同S，*有許多共同的性質(zhì)。 定理5.3.2 設(shè)f是代數(shù)系統(tǒng)S，* 到 T，的滿同態(tài)(這里*， 均為二元運(yùn)算)，那么(1) 當(dāng)運(yùn)算*滿足結(jié)合律、 交換律時(shí)，T中運(yùn)算也滿足結(jié)合律、 交換律。(
33、2) 如果S，* 關(guān)于*有幺元e，那么f(e)是T，中關(guān)于的幺元。 (3) 如果x-1是S，* 中元素x關(guān)于*的逆元，那么f(x-)=(f(x)-1是T，中元素f(x)關(guān)于的逆元。(4) 如果S，* 關(guān)于*有零元，那么f()是T，中關(guān)于的零元。證明僅證(2)、 (3)。 (2) 設(shè)S，*有關(guān)于*的幺元e。考慮T中任一元素b ，因?yàn)閒是滿射，所以必存在一個(gè)元素a S使b=f(a)，那么b f(e)=f(a) f(e)=f(a*e)=f(a)=bf(e) b=f(e) f(a)=f(e*a)=f(a)=b 因此f(e)為T中關(guān)于的幺元。 (3) 設(shè)S，*中元素x有關(guān)于*的逆元x-1，考慮f(x)與
34、f(x-1)，那么f(x) f(x-1)=f(x*x-1)=f(e)f(x-1) f(x)=f(x-1*x)=f(e)這就是說，T中f(x)有關(guān)于的逆元f(x-1)，即(f(x)-1f(x-1)這表明，同態(tài)也是保持一元求逆運(yùn)算的。證畢 (4) 關(guān)于零元的證明可仿上進(jìn)行，留給讀者完成。需要強(qiáng)調(diào)指出，上述定理中滿同態(tài)的條件是必要的，否則性質(zhì)只在同態(tài)像上有效，決不能隨意擴(kuò)大到T，上，下面將舉例說明這一點(diǎn)。對(duì)于具有多個(gè)代數(shù)運(yùn)算的兩個(gè)同類型系統(tǒng)，同態(tài)是指相應(yīng)的n個(gè)同態(tài)方程均成立。一般同態(tài)無法保持消去律。因?yàn)橥瑯?gòu)映射是雙射，所以不僅保持性質(zhì)而且可逆，此時(shí)可將兩個(gè)代數(shù)系統(tǒng)視為一個(gè)，只是運(yùn)算、 元素符號(hào)不同。
35、 下面我們要討論同態(tài)核的概念。 定義5.3.3如果f為代數(shù)系統(tǒng)S ，*到T ，的同態(tài)，并且T中有幺元e，那么稱下列集合為同態(tài)f的核(kernel of homomorphism)，記為K(f)。K(f)=x|x S f(x)e 關(guān)于同態(tài)核我們有定理5.3.3。定理5.3.3設(shè)f為代數(shù)系統(tǒng)S，*到T，的同態(tài)，如果K(f)，那么 K(f)，*為S，*的子代數(shù)。證明只要證K(f)對(duì)*運(yùn)算封閉即可。設(shè)K(f)中任意元素x，y，于是f(x)=f(y)=e 。 考慮f(x*y)=f(x) f(y)=e e=e 因此x*y K(f)，故 K(f)，*為S ，*的子代數(shù)。證畢 至此我們看到，一個(gè)同態(tài)映射f可導(dǎo)
36、致兩個(gè)子代數(shù)，一個(gè)是T ，的子代數(shù)f(S) ，另一個(gè)是S，*的子代數(shù) K(f)，*。 【例5.4.1】設(shè)*和+是集合S上的兩個(gè)二元運(yùn)算，并滿足吸收律。證明： *和+均滿足冪等律。證明x，y S， 因?yàn)槲章沙闪ⅲ詘*x=x*(x+(x*y)=xx+x=x+(x*(x+y)=x因此，*和+均滿足冪等律。證畢5.4 例 題 選 解 【例5.4.2】設(shè)*和+是集合S上的兩個(gè)二元運(yùn)算， x，y S，均有x+y=x。證明： *對(duì)于+是可分配的。證明x，y，z S， 因?yàn)閤+y=x，所以x*(y+z)=x*y而 (x*y)+(x*z)=x*y故 x*(y+z)=(x*y)+(x*z) 左分配律成立。
37、又因?yàn)?(y+z)*x=y*x而 (y*x)+(z*x)=y*x故 (y+z)*x=(y*x)+(z*x)右分配律成立。 因此，*對(duì)于+是可分配的。證畢 【例5.4.3】(1) 設(shè)N4=0，1，2，3，f： N4N4定義如下:令F=f0，f1，f2，f3，其中f0為N4上的恒等函數(shù)。易證F, 為一代數(shù)系統(tǒng)，且fi fj=fi+4j， 試證F，與N 4，+4同構(gòu)。 (2) 證明代數(shù)系統(tǒng)N，+與N，不同構(gòu)。 41 0 41 1)( xxxxf當(dāng)當(dāng) 解(1) 證明： 建立雙射h: FN4，使h(fi)i(i=0，1，2，3)由于對(duì)任何fi，fj F，h(fi fj)=h(fi+4j)=i+4j=h(
38、fi)+4h(fj)故h為一同構(gòu)映射，F(xiàn)，與N4，+4同構(gòu)得證。(2) 證明： (用反證法)設(shè)N，+與N，同構(gòu)，f為任一同構(gòu)映射。 不失一般性，設(shè)有n，n2，f(n)為一質(zhì)數(shù)p。于是p=f(n)=f(n+0)=f(n)f(0) (5.4.1)p=f(n)=f(n-1+1)=f(n-1)f(1) (5.4.2)由f(n)為質(zhì)數(shù)，據(jù)式(5.4.1)，f(n)=1或f(0)=1； 據(jù)式(5.4.2)， f(n-1)=1或f(1)=1。 總之，至少在兩處f的值為1，這與f為同構(gòu)映射(雙射)沖突。因此N，+與N，不同構(gòu)。 【例5.4.4】代數(shù)系統(tǒng)0，1，是否是代數(shù)系統(tǒng)N，+的同態(tài)像？(說明理由)解是。理
39、由如下： 作映射f： N0，1，n N，令f(0)=0，f(n)=1(n0)，則 n，m N ，當(dāng)n，m0時(shí)， f(n+m)=1=1 1=f(n) f(m)當(dāng)n=0，m0時(shí)， f(n+m)=1=0 1=f(n) f(m)當(dāng)n0，m=0時(shí)， f(n+m)=1=1 0=f(n) f(m)當(dāng)n=0，m=0時(shí)， f(n+m)=0=0 0=f(n) f(m) 即 n，m N， 均有 f(n+m)=f(n) f(m)，故f是N，+到0，1，的同態(tài)，因?yàn)閒是滿射，所以0，1，是N，+的同態(tài)像。 1. 設(shè)集合S=1，2，3，4，5，6，7，8，9，10，問下面定義的二元運(yùn)算*關(guān)于集合S是否封閉？習(xí)題五 (1)
40、 x*y=x-y(2) x*y=x+y-xy(3) x*y=(4) x*y=2xy(5) x*y=min(x，y)(6) x*y=max(x，y) (7) x*y=x(8) x*y=GCD(x，y)，GCD(x，y)是x與y的最大公約數(shù)(9) x*y=LCM(x，y)，LCM(x，y)是x與y的最小公倍數(shù)(10) x*y=質(zhì)數(shù)p的個(gè)數(shù)，其中xpy2 yx 2 已知S上運(yùn)算*滿足結(jié)合律與交換律，證明： 對(duì)S中任意元素a，b，c，d有(a*b)*(c*d)(d*c)*a)*b3 設(shè)*是集合S上的可結(jié)合的二元運(yùn)算。 x，y S，若x*y=y*x，則x=y。證明：*滿足冪等律(對(duì)一切x S有x*x=x
41、)。 4 S及其S上的運(yùn)算*如下定義，問各種定義下*運(yùn)算是否滿足結(jié)合律、 交換律，S, *中是否有幺元、 零元，S中哪些元素有逆元，哪些元素沒有逆元? (1) S為I(整數(shù)集)，x*y=x-y (2) S為I(整數(shù)集)，x*y=x+y-xy (3) S為Q(有理數(shù)集)，x*y= (4) S為N(自然數(shù)集)，x*y=2xy (5) S為N(自然數(shù)集)，x*y=max(x，y)(min(x，y)(6) S為N(自然數(shù)集)，x*y=x 2 yx 5 下列說法正確嗎？為什么？ (1) 代數(shù)系統(tǒng)中的幺元與零元總不相等。 (2) 一代數(shù)系統(tǒng)中可能有三個(gè)右幺元，而只有一個(gè)左幺元。 (3) 代數(shù)系統(tǒng)中可能有一
42、個(gè)元素，它既是左零元，又是右幺元。 (4) 幺元總有逆元。6 設(shè)A0，1，S為AA，即S=f1，f2，f3，f4，諸f由表5.1給出。 (1) 給出S上函數(shù)復(fù)合運(yùn)算的運(yùn)算表。 (2) S， 是否有幺元、 零元？ (3) S，中哪些元素有逆元? 逆元是什么？ 表 5.1 7 下面各集合都是N的子集，它們能否構(gòu)成代數(shù)系統(tǒng)N，+的子代數(shù)? (1) x|x N x的某次冪可以被16整除 (2) x|x N x與5互質(zhì) (3) x|x N x是30的因子 (4) x|x N x是30的倍數(shù) 8 證明： f: R+R，f(x)=lbx為代數(shù)系統(tǒng)R+，到R，的同態(tài)(這里R+為正實(shí)數(shù)集，R為實(shí)數(shù)集，為數(shù)乘運(yùn)算
43、)。它是否為一同構(gòu)映射？ 為什么？ 9 設(shè)f: N0，1定義如下:證明： f為代數(shù)系統(tǒng)N，到0，1，的同態(tài)。它是單一同態(tài)、 滿同態(tài)嗎？ 否則是自然數(shù)當(dāng) 0 )(2 1)( knnf k 10 設(shè)A=a，b，c。問代數(shù)系統(tǒng)，A，和a，b，A，是否同構(gòu)？11 假定f是S，*到T，的同態(tài)，試舉例說明： (1) f(S)，的幺元(零元)，可能不是T，的幺元(零元)。 (2) f(S)，的成員的逆元，可能不是它在T，中的逆元。12 設(shè)f，g都是S，*到T，的同態(tài)，并且*與運(yùn)算均滿足交換律和結(jié)合律。證明: 如下定義的函數(shù)h: STh(x)=f(x) g(x)是S，*到T，的同態(tài)。 13 設(shè)f，g分別是S，*到T，的同態(tài)和T，到H，的同態(tài)。證明： f g是S，*到H，的同態(tài)。 14 設(shè)f是R，+到C，的映射(這里R為實(shí)數(shù)集，C為復(fù)數(shù)集，+為普通加法運(yùn)算，為數(shù)乘運(yùn)算)，且f: xe2ix， x R。問f是否同態(tài)？ 如果是，請(qǐng)寫出同態(tài)像和同態(tài)核。
大學(xué)課件 離散數(shù)學(xué)(第二版)(蔡英) 第5章 代數(shù)系統(tǒng)的基本概念
