理學(xué)圖論第七章

第七章代數(shù)結(jié)構(gòu)預(yù)備知識7.1集合與映射定義1

設(shè)和是給定的兩個集合,如果有一個規(guī)則，使對任意一個元素,在中有唯一的元素與之對應(yīng)，則稱是到的一個映射。記作和，稱為的定義域，稱為的值域，稱為的象，稱為的原像。例1設(shè)為一個非空集合。是到的一個映射，稱為上的恒等映射或單位映射。定義2

兩個映射，當(dāng)且僅當(dāng)，且對任意，都有，稱和是相等的映射，記為。3.若既是單射又是滿射,則稱它是到的雙射。定義3

設(shè)是到的一個映射。1.若對任意,都有，稱是到的單射。2.若，則稱是到的滿射。定義4

設(shè)是三個集合，有兩個映射：，則由和可確定一個到的映射,稱為與的合成，記作，亦即映射的合成一般不滿足交換律，但滿足結(jié)合律。因此中的恒等映射，則定理1

設(shè)是到的映射，和分別是與是可逆映射。定義5

設(shè)兩個映射，若成立，則稱是左可逆映射，是右可逆映射，并稱是的左逆映射，是的右逆映射。又若也成立，則稱和都定理2

到的映射是左可逆的充要條件是為單射，是右可逆的充要條件是為滿射。推論：是可逆映射,當(dāng)且僅當(dāng)是雙射。定理3

設(shè)是到的映射，且，則。7.2等價關(guān)系當(dāng)時,說與沒有關(guān)系,記作。定義1

集合和的笛卡爾積的任一子集稱為與之間的一個二元關(guān)系，它的元素是有序?qū)?，記為，其中。則稱是上的等價關(guān)系。用符號～表示。定義2

設(shè)是集合上的二元關(guān)系，如果1.對所有的,都有，即具有自反性；2.對所有的,若，則,即具有對稱性；3.對所有的，若，則，即具有傳遞性。其中是該等價類的一個代表元。這樣，對任一元素，所有與有關(guān)系的元素構(gòu)成一個集合，稱之為的一個等價類，記作，即～依據(jù)等價關(guān)系的定義，等價類具有以下性質(zhì)：1.2.若，則?！?.若且，則?！舴?，則有。定理1

設(shè)～是上的一個等價關(guān)系,對任意元素定理2

設(shè)是上由等價關(guān)系～確定的全部等價類，那么常用記號表示,并稱之為關(guān)于～的商集。等價類的集合,稱為等價類族記為～例1

設(shè)是非負整數(shù)集合，是一個正整數(shù)，令是中的模同余關(guān)系。則顯然是等價關(guān)系，因此定理3

集合的一個劃分可以確定的一個等價關(guān)系。定理4

設(shè)是到的一個滿射，則可以確定的一個等價關(guān)系。定理5

設(shè)是到的一個滿射，則存在唯一雙射，使，其中～是由～確定的等價關(guān)系，是到的自然映射。～7.3代數(shù)系統(tǒng)的概念稱為的一個二元代數(shù)運算，簡稱定義1

設(shè)是非空集合，到的一個映射二元運算。定義2

設(shè)是非空集合，是正整數(shù)，到的一個映射稱為的一個元運算,簡稱為元運算。當(dāng)是有限集合時,也稱該系統(tǒng)是有限代數(shù)系統(tǒng)。定義3

設(shè)是一個非空集合，分別是的元運算,是正整數(shù)，。稱集合和運算所組成的系統(tǒng)為一個代數(shù)系統(tǒng)（或一個代數(shù)結(jié)構(gòu)）,簡稱為一個代數(shù)，用記號表示。定理1

若對二元運算適合結(jié)合律，則對于任何正整數(shù)和，有1.。2.。若既是左單位元又是右單位元,則稱之為單位元。定義4

給定一個代數(shù)系統(tǒng)，如果存在一個元素（或者），使得對于任意元素，有（或），稱（或）是上關(guān)于運算的一個左（或右）單位元。定理2

若代數(shù)系統(tǒng)有左單位元,又有右單位元,則是的唯一的單位元。定義5

設(shè)是有單位元的代數(shù)系統(tǒng)，對于,若存在一個元素,使得，則稱是左可逆的，并稱是的一個左逆元；若存在,使得,則稱是右可逆的，并稱是的一個右逆元；若既是左可逆又是右可逆的,則說是可逆元。右逆元，則有唯一逆元，并且定理3

設(shè)代數(shù)系統(tǒng)具有單位元，且適合結(jié)合律，對于，有左逆元，又有。7.4同構(gòu)與同態(tài)定義1

設(shè)和是兩個代數(shù)系統(tǒng),若和都是元運算，是正整數(shù)，，則說代數(shù)系統(tǒng)和是同類型的。定義2

設(shè)和是兩個同類型的代數(shù)系統(tǒng)，是一個雙射。如果對任意元，恒有則稱是到的一個同構(gòu)映射，并稱與同構(gòu)，用表示。定義3

設(shè)和是兩個同類型的代數(shù)系統(tǒng)，是到一個映射。如果對任意的，都有,則稱是到的一個同態(tài)映射，簡稱同態(tài)。例1

一個代數(shù)系統(tǒng);另一個代數(shù)系統(tǒng)，其中和分別是模的加法和乘法運算，即這樣可定義映射，即則是到的一個同態(tài)，因為總有定義4

設(shè)是一個代數(shù)系統(tǒng)，是的一個非空集合，如果在運算下是封閉的，則稱是的一個子代數(shù)系統(tǒng)或子代數(shù)。子代數(shù)，并稱它是在的作用下的同態(tài)象。定理1

設(shè)映射是從代數(shù)系統(tǒng)到的一個同態(tài)，則是的一個定義5

設(shè)是從到的一個同態(tài)，如果1.是單射，稱是單一同態(tài)。2.是滿射，稱是滿同態(tài)，用表示，～并稱是的一個同態(tài)象。3.是雙射，則是同構(gòu)。則對運算，每一個元素都有逆元定理2

給定代數(shù)系統(tǒng)和，其中和都是二元運算。設(shè)是到的滿同態(tài)，則1.如果是可交換的或可結(jié)合的運算，則