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