理學(xué)圖論第七章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一個(gè)代數(shù)系統(tǒng);另一個(gè)代數(shù)系統(tǒng)，其中和分別是模的加法和乘法運(yùn)算，即這樣可定義映射，即則是到的一個(gè)同態(tài)，因?yàn)榭傆卸x4

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

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

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

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