【离散数学3】代数系统

代数系统概念的引入

【定义】代数系统 一个非空集合 A 以及若干定义在它上的运算 f1,f2,…,fkf1,f2,…,fk 组成的系统叫做一个代数系统，记为 <A,f1,f2,…,fk><A,f1,f2,…,fk>

【定义】运算的性质 下面默认指代一个二元运算的代数系统 (A,⋆)(A,⋆)

• 封闭性 ∀x,y∈A∀x,y∈A，有 x⋆y∈Ax⋆y∈A
• 可交换性 ∀x,y∈A∀x,y∈A，有 x⋆y=y⋆xx⋆y=y⋆x
• 可结合性 ∀x,y,z∈A∀x,y,z∈A，有 (x⋆y)⋆z=x⋆(y⋆z)(x⋆y)⋆z=x⋆(y⋆z)
• 另外还有可分配性、吸收律、等幂，等等。就不多写了。

【定义】幺元

• 对于 el∈Ael∈A，如果有 ∀x∈A→el⋆x∈A∀x∈A→el⋆x∈A，叫做 elel 是关于 ⋆⋆ 的 左幺元
• 对于 er∈Aer∈A，如果有 ∀x∈A→x⋆er∈A∀x∈A→x⋆er∈A，叫做 elel 是关于 ⋆⋆ 的 右幺元

【定理】 如果 (A,⋆)(A,⋆) 存在左幺元 elel 和右幺元 erer，那么 el=erel=er 且 A 上的幺元唯一。
（使用定义证明）

【定义】零元

• 对于 θlθl，如果有 ∀x∈A→θl⋆x=θl∀x∈A→θl⋆x=θl，叫做 θlθl 是关于 ⋆⋆ 的 左零元
• 对于 θrθr，如果有 ∀x∈A→x⋆θr=θr∀x∈A→x⋆θr=θr，叫做 θrθr 是关于 ⋆⋆ 的 右零元

【定理】 类似幺元，如果左零元和右零元都存在，那么它们相等且零元唯一。（证明方法同上）

【定理】 如果 A 中的元素个数多于1，且幺元 ee 和 零元 θθ 都存在，那么 e≠θe≠θ

【定义】逆元 如果a⋆b=ea⋆b=e，称为 a 是 b 的 左逆元，b 是 a 的 右逆元。如果既是左逆元又是右逆元，叫做 逆元
【性质】

• 逆元是相互的：如果 a 是 b 的逆元，那么 b 也是 a 的逆元。
• 一般来说，左逆元未必等于右逆元，有左逆元未必有右逆元，甚至一个元素的左/右逆元未必唯一

半群

【定义】广群 (S,⋆)(S,⋆) 是一个代数系统，⋆⋆ 是二元运算，如果 ⋆⋆ 是封闭的，称为 (S,⋆)(S,⋆) 是一个广群

【定义】半群 (S,⋆)(S,⋆) 是一个代数系统，⋆⋆ 是二元运算，如果满足以下条件，称为 (S,⋆)(S,⋆) 是一个半群:

1. ⋆⋆ 是封闭的，
2. ⋆⋆ 是可结合的，也就是说 (x⋆y)⋆z=x⋆(y⋆z)(x⋆y)⋆z=x⋆(y⋆z)

【定理1】 如果 (S,⋆)(S,⋆) 是一个半群，且B⊆SB⊆S，且 ⋆⋆ 对 B 封闭，那么，(B,⋆)(B,⋆) 也是一个半群

【定理2】 (S,⋆)(S,⋆) 是一个半群，且 SS 是一个有限集，那么 ∃a→a⋆a=a∃a→a⋆a=a
证明过程稍微绕：

1. S 是有限的，所以存在 i<ji<j 使得 ai=ajai=aj
2. 两边同时乘以 ai(j−i)−iai(j−i)−i
3. 左边 = ai(j−i)ai(j−i)，右边 = aj−iai(j−i)aj−iai(j−i)
4. 令 b=ai(j−i)b=ai(j−i)，就有这个结论：b=aj−ibb=aj−ib
5. 上式使用i次，得到 b=ai(j−j)bb=ai(j−j)b ，也就是 b=b⋆bb=b⋆b，就证完了

【定义】独异点 含有幺元的半群称为独异点

【定理】3 (S,⋆)(S,⋆) 是一个独异点，那么，⋆⋆ 的运算表中，没有不可能有相同的两行或两列。
证明：

1. 假设有相同的两列，也就是说 ∀x∈S→x⋆b1=x⋆b2∀x∈S→x⋆b1=x⋆b2
2. 令 x=ex=e，有 b1=b2b1=b2

参考文献

《离散数学》上海科学技术出版社，左孝凌