可交换半群[定义]-Read.pptVIP

第四章 代数结构 4.2 半群与独异点 ——典型代数系统之一 群论的应用 群论是代数系统中研究得比较成熟的一个分支，它在 计算机形式语言 自动机理论 编码理论 …… 等方面得到广泛应用。 典型代数系统之一 1. 半群 2. 可交换半群 3. 子半群 4. 独异点 5. 子独异点 1. 半群定义 [定义]半群 设 V = S, o 是代数系统，若o为S上封闭的二元运算，如果 ? 运算是可结合的，则称 V 为半群. 实例 （1）Z+, +, N, +, Z, +, Q, +, R, +都是半群，+是普通加法. （2）P(B), ?为半群，其中?为集合的对称差运算. （3）Zn, ?n为半群，其中 Zn={0, 1, …, n?1}，?n为模 n 加法. 半群的幂运算性质 半群的幂运算定义 设V=S, *为半群，对任意 x∈S，规定：x1 = xxn+1 = xn *x,n∈Z+ 幂运算规则：xn * xm = xn+m(xn)m = xn m m, n∈Z+ 证明方法：数学归纳法。（略） 半群的等幂元存在判定 定理：设A, *是有限半群，则A, *中必存在等幂元。 证明：设|A| = n, 对任意a ? A，考察以下n + 1个元素： a, a2, a3, …, an+1 因为*运算是封闭的，所以这n + 1个元素都属于A。由鸽洞原理，在这n + 1个元素中，必定至少有2个元素相同，不妨设为： ai = ai+k (1 ≤ k ≤ n) 由i与k的关系，分三种情况讨论等幂元的取值： (1) i = k时，有 ai = ai + i = ai * ai ∴ ai是等幂元。 半群的等幂元存在判定（续） 定理：设A, *是有限半群，则A, *中必存在等幂元。 证明：设|A| = n, 在a, a2, a3, …, an+1共n + 1个元素中，必定至少有2个元素相同，不妨设为： ai = ai+k (1 ≤ k ≤ n) 由i与k的关系，需要分三种情况讨论等幂元的取值： (1) i = k (2) i k时， k – i 0, 而 ai = ai + k = ai * ak 等式左右两边同时左乘ak – i, 得 ak – i * ai = ak – i * ai * ak 化简后得： ak = ak * ak ∴ ak是等幂元。 半群的等幂元存在判定（续） 定理：设A, *是有限半群，则A, *中必存在等幂元。 证明：在a, a2, a3, …, an+1共n + 1个元素当中，必至少有2个元素相同： ai = ai+k (1 ?k ?n) (1) i = k (2) i k (3) i k时， ai = ai * ak 等式左右两边同时右乘ak, 得 ai * ak = ai * ak * ak = ai * a2k ——①式 ∵ ai = ai * ak ∴ ①式可化为 ai = ai * a2k ——②式 ∴ 如果2k – i 0, 则在②式两边同时重复右乘ak，直到使得 ai = ai * apk，pk – i 0 ——③式 时停止。对③式两边同时左乘apk – i 从而有apk – i * ai = apk – i *ai * apk——④式 将④式化简： apk = apk * apk ∴ apk是等幂元 典型代数系统之一 1. 半群 2. 可交换半群 3. 子半群 4. 独异点 5. 子独异点 可交换半群 [定义]可交换半群 设有半群S, *, 若*运算是可交换的, 则称S, *是可交换半群． 例: 给定半群P(S), ∪和P(S), ∩,其中P(S)是集合S的幂集, ∩和∪为集合上的交运算和并运算． ∩和∪是可交换运算，所以P(S), ∩和P(S), ∪是可交换半群. 可交换半群举例 例：设A, *是半群，A = {a, b, c}，且有a2 = b, b2 = c，证明： (1) A, *是可交换半群 (2) c2 = c，并写出A, *的运算表 证明： (1)只需要证明*运算在A上是可交换的 a * b = a * a2 = a * (a * a)