代数系统

二元运算常见性质

结合律推广到n个对象：$a_1*a_2*...*a_n$中任意加括号所得的积即$(...(((a_1*a_2)*a_3)*a_4)...a_{n-1})*a_n$

证明：

当n=1和n=2时命题显然成立，当n=3时由结合律可知上述式子仍然成立

假设对于少于n个元素的乘积上述式子成立：（归纳法） \[ 设a_1*a_2*...*a_n\text{任意加括号所得到的积为}\alpha\\ 在最后一次计算中是\beta、\gamma两部分相乘，即\alpha=\beta\cdot\gamma\\ \alpha=(\beta)\cdot(\gamma)=(\beta)\cdot((...)*a_n)=(\beta\cdot(...))*a_n\\ 因为\beta\cdot(...)的元素个数小于n，故等于按次序从左而右加括号所得积(...(((a_1*a_2)*a_3)*a_4)...a_{n-1})*a_n \]

代数系统

定义：一个非空集合和定义在该集合上的一个或多个运算所组成的系统成为代数系统

整环

代数系统$<J;+,\cdot>$对运算$+$和$\cdot$由性质交换律、结合律、分配律、单位元、关于加法的可逆性、消去律，则称代数系统$<J;+,\cdot>$是整环

子代数/子系统

设$<S;o_1,o_2,\sim>$是以代数系统，H是S的一个非空子集，若S上的每一个运算在H上都是封闭的，则称代数系统$<H;o_1',o_2',\sim>$是$<S;o_1,o_2,\sim>$的子代数或子系统

同态和同构

同态

设$V_1=<S_1;*_1,o_1,\sim_1>、V_2＝<S_2;∗_2,o_2,\sim_2>$是两个代数系统，h 是从 $S_1$到$S_2$ 的一个函数，若对于任意的 $x,y∈S_1$，有

$h(x∗_1 y)= h(x)*_2h(y)$，对任意 $x∈S1$，$h(\sim_1(x))=\sim_2 h(x)$，则称h是从代数系统 $V_1$到$V_2$的一个同态

如果h是内射，则称h是从$V1$到$V2$的单一同态
如果h是满射，则称h是从$V1$到$V2$的满同态
如果h是双射，则称h是从$V1$到$V2$的同构

满同态

$*_1$和$*_2$可拥有的相同性质

可结合
可交换
单位元
零元
逆元
可分配

群

半群和独异点

半群：设S是一个非空集合，$*$是S上的一个二元运算，如果运算$*$是可结合的，则称代数系统$<S;*>$为半群

独异点：若半群$<S;*>$对于运算$*$有单位元，则称半群为独异点

可交换独异点：如果独异点$<S;*>$中的运算$*$是可交换的，则称独异点$<S;*>$是可交换独异点

循环独异点：在独异点$<S;*>$中，如果存在一个元素$g\in S$，使得每一个元素$a\in S$都能写成$g^i(i\geq 0)$的形式，则称独异点$<S;*>$为循环独异点，元素g称为该循环独异点的生成元

性质

每一个循环独异点都是可交换的
设$<S;*>$是一有限独异点，则对每一$a\in S$，存在一个整数$j\geq 1$，使得$a^j$是一幂等元

子半群：设$<S;*>$是一个半群，如果$<T;*>$是$<S;*>$的子代数，则称$<T;*>$是$<S;*>$的子半群

子独异点：

定义：设$<S;*>$是一个独异点，如果$<T;*>$是$<S;*>$的子代数，且单位元$e\in T$，则称$<T;*>$是$<S;*>$的子独异点
定理：设$<S;*>$是一个可交换的独异点，则S的所有幂等元的集合形成$<S;*>$的一个子独异点

设h是从代数系统$V_1=<S_1;*>$到$V_2=<S_2;*>$的满同态，其中运算$*$和$$都是二元运算，则

若$V_1$是半群，则$V_2$也是半群
若$V_1$是独异点，则$V_2$也是独异点

群的定义

定义：设$<G;*>$是一个代数系统，如果G上的二元运算$*$满足可结合、有单位元、有逆元，则称$<G;*>$是一个群

交换群：如果群$<G;*>$的运算$*$是可交换的，则称该群为交换群或阿贝尔群

循环群：在群$<G;*>$中，如果存在一个元素$g\in G$，使得每个元素$a\in G$都能写成$g^i(i\in I)$的形式，则称群$<G;*>$是循环群，g是该群的生成元。说群$<G;*>$由g生成。

性质：每一个循环群都是阿贝尔群

有限群/无限群：设$<G;*>$是一个群，如果G是有限集，则称$<G;*>$是一有限群。G中元素的个数称为群$<G;*>$的阶。如果G是无限集，则称$<G;*>$为无限群。

周期：对于群$<G;*>$的元素a，若存在一正整数r使得$a^r=e$，则称元素a具有有限周期；而使$a^r=e$成立的最小的正整数成为a的周期。如果对于任何正整数r，总有$a^r\neq e$，则称a的周期为无限

设$<G;*>$是一由元素g生成的循环群

若g的周期是n，则$<G;*>$是一个n阶的有限循环群
若g的周期为无限，则$<G;*>$是一个无限阶的循环群

群的特点：

群中每一个元素都是可逆的，所以在阶大于1的群中没有零元

证明：假设一个阶大于1的群中存在零元a，又因为a由逆元，所以必存在b，使得$a\circ b=e$，但是$a\circ b=a$，所以$a=e$即零元等于逆元，只有在阶为1的群中才成立。

除了单位元外，群没有任何幂等元

证明：假设$a\in G$是幂等元，则$a*a=a$，则$a=(a^{-1}*a)*a=a^{-1}*(a*a)=a^{-1}*a=e$

群的基本性质

相约性 $\color\red{\star\star\star}$：

如果$<G;*>$是一个群，则对于任意的$a,b\in G$，有

存在唯一的元素$x\in G$，则$a*x=b$
存在唯一的元素$y\in G$，则$y*a=b$

证明：

因为$a*(a^{-1}*b)=(a*a^{-1})*b=e*b=b$，所以至少存在一个元素$x=a^{-1}*b$满足$a*x=b$

现设$x'\in G$也使得$a*x'=b$，则$x'=e*x'=(a*a^{-1})*x'=a^{-1}*(a*x')=a^{-1}*b$

因此$x=a^{-1}*b$是满足$a*x=b$的唯一元素

如果$<G;*>$是一个群，则对于任意的$a,b,c\in G$，有

若$a*b=a*c$，则有$b=c$
若$b*a=c*a$，则有$b=c$

如果$<G;*>$是一个群，则对于任意的$a,b\in G$，有$(a*b)^{-1}=b^{-1}*a^{-1}$

若群的$<G;*>$的元素a具有有限周期r，则当且仅当k是r的倍数时，$a^k=e$

群中任一元素与它的逆元具有相同的周期

证明：

若a是一具有有限周期r的元素，则$a^r=e$，并由此有$(a^{-1})^r=(a^r)^{-1}=e^{-1}=e$，则$a^{-1}$必有有限周期$r'$，且$r'\leq r$

又$a^{r'}=((a^{-1})^{r'})^{-1}=e^{-1}=e$，则$r\leq r'$

所以$r'=r$

在有限群$<G;*>$中，每个元素有一有限周期，而且每个元素的周期不超过#G

子群及其陪集

子群

子群：设$<G;*>$是一个群，$<H;*>$是$<G;*>$的子代数，如果单位元$e\in H$，对任意的$a\in H$，有$a^{-1}\in H$，则称$<H;*>$是$<G;*>$的子群。如果H是G的真子集，则称子群$<H;*>$是$<G;*>$的真子群

因为可以由逆元推出单位元存在，所以：设$<H;*>$是$<G;*>$的子代数，则当且仅当对于任意的$a\in H$，有$a^{-1}\in H$时，$<H;*>$是$<G;*>$的子群

设$<G;*>$是一个有限群，若$<H;*>$是$<G;*>$的子代数，则$<H;*>$是$<G;*>$的子群

设$<G;*>$是一个群，若$<H;*>$是$<G;*>$的有限子代数，则$<H;*>$是$<G;*>$的子群

设$<G;*>$是一个群，若$<G;*>$的子代数$<H;*>$是群，则$<H;*>$是$<G;*>$的子群

子群的判定

设$<G;*>$是一个群，H是G的一非空子集

满足封闭性和可逆性
当且仅当$a,b\in H,a*b^{-1}\in H$

$<H;*>$是$<G;*>$的子群

条件2证明充分性：

$a,b\in H,a*b^{-1}\in H$，则由$a\in H$知$a*a^{-1}=e\in H$，又$e*a^{-1}=a^{-1}\in H$，可逆性得证

由上述方法可知$b^{-1}\in H$，则$a*(b^{-1})^{-1}=a*b\in H$，封闭性得证

设$<G;*>$是一个有限群，H是G的一非空子集，判断H是否能构成$<G;*>$的子群，只需检验H对运算$*$是否封闭即可

$<H;*>$（H是G的非空子集）是$<G;*>$的子群的充要条件是，$<H;*>$是一个群

左右陪集

设$<H;*>$是$<G;*>$的子群，a是G的任意一个元素，则

集合$H*a=\left\{h*a|h\in H\right\}$称为子群$<H;*>$在群$<G;*>$中的右陪集
集合$a*H=\left\{a*h|h\in H\right\}$称为子群$<H;*>$在群$<G;*>$中的左陪集

正规子群

设$<H;*>$是$<G;*>$的子群，如果对于每一个$a\in G$，有$a*H=H*a$，则称$<H;*>$是$<G;*>$的正规子群，此时右陪集和左陪集简称为陪集

正规子群的判定

设$<H;*>$是$<G;*>$的子群,当且仅当对于任意的$a\in G$，有$a*H*a^{-1}=H$时，$<H;*>$是$<G;*>$的正规子群

设$<H;*>$是$<G;*>$的子群,当且仅当对于任意的$a\in G$，有$a*H*a^{-1}\subseteq H$时，$<H;*>$是$<G;*>$的正规子群（可证互相包含）

性质

设$<H;*>$是$<G;*>$的子群，a和b是G的任意两个元素，则有：

$H*a=H*b$或$(H*a)\cap (H*b)=\empty$
$a*H=b*H$或$(a*H)\cap (b*H)=\empty$

设$<H;*>$是$<G;*>$的子群，则

当且仅当$b\in H*a$时，有$H*b=H*a$
当且仅当$b\in a*H$时，有$b*H=a*H$

设$<H;*>$是$<G;*>$的子群，则

$<G;*>$中$<H;*>$的所有相异右陪集组成G的一个分划
$<G;*>$中$<H;*>$的所有相异左陪集组成G的一个分划

设$<H;*>$是$<G;*>$的子群，则对于任意的$a\in G$，有$\#(H*a)=\#(a*H)=\#H$

$<H;*>$的所有相异右陪集的个数和所有相异左陪集的个数相同

拉格朗日定理

指数：设$<H;*>$是$<G;*>$的子群，群$<G;*>$中$<H;*>$的所有相异左（右）陪集个数称为$<H;*>$在$<G;*>$中的指数

拉格朗日定理：设$<G;*>$是一具有子群$<H;*>$的有限群，且$<H;*>$在$<G;*>$中的指数为d，则$\#G=d\cdot (\#H)$

推广

任一子群的阶必为该群的阶的因子
任何素数阶的群只有平凡子群
在有限群$<G;*>$中，每个元素的周期是$\#G$的因子

格和布尔代数

偏序集

偏序关系：自反、反对称且可传递的关系

下界、最大下界(glb)、上界、最小上界(lub)、最小元素、最大元素的定义

glb、lub、最小元素、最大元素唯一

格和性质

定义：设<L；≤>是一个偏序集，如果L中任意两个元素都存在着最大下界和最小上界，则称<L；≤>是格

\[l1\wedge l2=glb(l1,l2),l1\vee l2=lub(l1,l2)\]

性质：

\[l1\wedge l2\leq l1,l1\wedge l2\leq l2\]

\[l1\vee l2\geq l1,l1\vee l2 \geq l2\]

\[l3\leq l1,l3\leq l2,l3\leq l1\wedge l2\]

\[l3\geq l1,l3\geq l2,l3\geq l1\vee l2\]

\[l1\vee l2=l2\Leftrightarrow l1\wedge l2=l1\Leftrightarrow l1\leq l2\]

格的保序性：

\[若l1\leq l3,l2\leq l4,则l1\vee l2\leq l3\vee l4 ,l1\wedge l2\leq l3\wedge l4\]

\[若l2\leq l3,则l1\vee l2\leq l1\vee l3,l1\wedge l2\leq l1\wedge l3\]

对偶原理：格上的任一真命题，其对偶亦为真。

交换律：\[l1\vee l2=l2\vee l1,l1\wedge l2=l2\wedge l1\]

结合律：\[l1\vee (l2\vee l3)=(l1\vee l2)\vee l3,l1\wedge(l2\wedge l3)=(l1\wedge l2)\wedge l3\]

等幂律：\[l\vee l=l,l\wedge l=l\]

吸收率：\[l1\vee (l1\wedge l2)=l1,l1\wedge(l1\vee l2)=l1\]

分配不等式：

\[l1\vee (l2\wedge l3)\leq (l1\vee l2)\wedge(l1\vee l3)\]

\[l1\wedge(l2\vee l3)\geq (l1\wedge l2)\vee (l1\wedge l3)\]

在格$<L;*>$中，$l1\wedge l2\wedge...\wedge ln$就是元素$l1,l2,...,ln$的最大下界；$l1\vee l2\vee ...\vee ln$就是元素$l1,l2,...,ln$的最小上界

格是一种代数系统

定义：设$<L;\vee,\wedge>$是一格代数系统，$\vee$和$\wedge$是L上的二元运算，如果这两个运算满足交换律、结合律和吸收率，则称$<L;\vee,\wedge>$是一个格

子格：设$<L,\vee,\wedge>$是一个格，如果$<A;\vee,\wedge>$是$<L;\vee,\wedge>$的子代数，则称$<A;\vee,\wedge>$是$<L;\vee,\wedge>$的子格

分配格和有补格

分配格

定义：设$<L;\vee,\wedge>$是一个格，若对于任一的$l1,l2,l3\in L$，有\[l1\wedge (l2\vee l3)=(l1\wedge l2)\vee(l1\wedge l3)\] \[l1\vee(l2\wedge l3)=(l1\vee l2)\wedge (l1\vee l3)\]

性质1：在格中如果交运算对并运算是可分配的，那么并运算对交运算也是可分配的；反之同理。

性质2：设$l1,l2,l3$是分配格$<L;\vee,\wedge>$中任意三个元素，则$(l1\vee l2=l1\vee l3,l1\wedge l2=l1\wedge l3)\Leftrightarrow (l2=l3)$

判定：格$<L; ≤>$是分配格的充要条件是$<L; ≤>$不含与钻石格或五角格同构的子格

有补格

有界格：具有最小元素和最大元素的格，最大元素1，最小元素0

补元素：设$<L;\vee,\wedge>$是一个含有元素1和0的格，对于L中的一个元素l，若有元素$\overline{l}$使得$l\vee\overline{l}=1,l\wedge\overline{l}=0$，则称元素$\overline{l}$是l的补

有补格：设$<L;\vee,\wedge>$是一个含有元素1和0的格，如果L中的每一个元素都有补，则称$<L;\vee,\wedge>$为有补格

有补分配格

对合律：在有补分配格$<L;\vee,\wedge>$中，对于任一元素$l\in L$，有$\overline{\overline{l}}=l$

德摩根定律：在有补分配格$<L;\vee,\wedge>$中，对于任意的$l1,l2\in L$，有$\overline{l1\vee l2}=l1\wedge l2,\overline{l1\wedge l2}=\overline{l1}\vee\overline{l2}$

\[(l1\leq l2)\Leftrightarrow (l1\wedge \overline{l2}=0)\Leftrightarrow (\overline{l1}\vee l2=1)\]

布尔代数

定义：如果一个格既是分配格又是有补格，而称其为一个布尔代数

设代数系统中$<B;-，\vee,\wedge>$的运算满足交换律、分配律、同一律和互补律，则它也必定满足其他的集合定律，则称$<B;-，\vee,\wedge>$是布尔代数

性质：

布尔代数的每一子代数仍是布尔代数。

一个布尔代数的每一满同态像都是布尔代数。

有限布尔代数的同构

设$< B ;－，∨，∧>$是布尔代数，如果元素a≠0，且对任意的x ∈B，有x ∧a＝a或x ∧ a＝0，则称a是原子。

设$< B ;－，∨，∧>$是一有限布尔代数，则对任意的x ∈B 且 x ≠ 0，一定存在一个原子a ，使得x ∧ a＝a（或a ≤x）。

如果a1和a2是布尔代数$< B ;－，∨，∧>$的原子，且a1 ∧ a2 ≠ 0 ，则a1 ＝a2。