代数系统
定义
S上的n元运算是一个特殊的函数f : Sn → S，具有封闭性
代数系统：由非空集合S和S上的运算组成的系统，记作 < S, f1, f2, ⋯, fn>，简称代数
代数的基数等于S的基数(因为运算具有封闭性)
同类型的代数：要求一一对应的各个运算的元数相同，和S无关
子代数：给定代数 < S, f1, ⋯, fn>，若非空集合T ⊆ S，且T和f1, ⋯, fn能够组成代数(即f在T上封闭)，则 < T, f1, ⋯, fn> ⊆ < S, f1, ⋯, fn>
代数运算
代数运算的性质
设在S上的二元运算∘满足：
结合律：∀x∀y∀z(x,y,z∈S→(x∘y)∘z=x∘(y∘z))
交换律：∀x∀y(x,y∈S→x∘y=y∘x)
若同时满足结合律和交换律，则表达式可任意调换次序
分配律：设∘对S上的另一个运算×满足：
左分配律：∀x∀y∀z(x,y,z∈S→x∘(y×z)=(x∘y)×(x∘z))
右分配律：∀x∀y∀z(x,y,z∈S→(x×y)∘z=(x∘z)×(y∘z))
注意运算的对应关系，∘对×满足，则左式∘在括号外
同时满足左右分配律，才能称∘对×满足分配律
若∘满足交换律，且对×满足左或右分配律，则可证明它对×满足分配律
吸收律：类似于分配律的左右定义方式，∘对×满足左吸收律 ⇒ ∀x∀y(x,y∈S→x∘(x×y)=x)
幺元(单位元)：有左右幺元之分，若e是关于∘的左幺元，则∀x(x∈S→e∘x=x)
零元：有左右零元之分，若$\O$是关于∘的左零元，则$\forall x(x\in S\rightarrow \O\circ x=\O)$
如果一个运算的左右幺元/零元存在，则左右分别相等，且这个幺元/零元是唯一的
如果一个运算同时存在幺元和零元，则它们不相等
等幂律：∀x(x∈S→x∘x=x)，并定义x为∘的等幂元
若满足，则所有元素都为等幂元
一个运算的幺元和零元一定是等幂元
逆元：若e为∘的幺元，有左右逆元之分，且有两种对应关系
x是关于∘的左逆元：$\exist
y(y\in S\wedge x\circ y=e)$
称存在的这个y为x的右逆元，即x ∘ y = e
如果x和y互逆(x为y的左右逆元)，则x和y都是关于∘的逆元
一个运算的幺元一定是逆元
可约律：有左右可约律，若$\O$为∘的零元，则∘是左可约的$\Rightarrow\forall x\forall y\forall z((x,y,z\in
S\wedge x\ne\O\wedge x\circ y=x\circ z)\rightarrow y=z)$
定义x为∘的左可约元
如果一个运算是可约的，那么所有非零元的元素都为可约元
存在一个可约元，不代表一个运算是可约的
！如果∘满足结合律，同时$x\ne\O$且x是∘的逆元，则x是∘的可约元
一个运算的幺元一定是可约元
性质在运算表上的体现
将二元运算的左元、右元分别作为行、列，将运算结果作为表中数据，生成的运算表(方阵)中：
封闭性：表中数据一定都属于S，否则该运算不是S上的运算
可交换：该方阵是对称的
等幂：主对角线上元素和行头元素相等
左/右零元：左/右零元所在行/列元素和该元素相等
左/右幺元：左/右幺元所在行/列元素和对应的列/行元素相等
左/右逆元：左/右逆元所在行/列元素中必定有一个幺元
！两元素互为逆元：两元素所在行和列的元素都是幺元
以上冒号左右两边的描述是等价的
常见代数运算的性质
集合
运算
幺元
零元
等幂元
逆元
可约元
R
加法
0
无
0
相反数
任意元素
乘法
1
0
1和0
除0外的数的倒数
除0外的任意元素
P(S)
并集
空集
S
任意元素
空集
空集
交集
S
空集
任意元素
S
S
命题
析取
F
T
任意元素
F
F
合取
T
F
任意元素
T
T
集合上的所有关系构成集合
合成
恒等关系
空关系
恒等关系
关系矩阵可逆的所有关系
关系矩阵可逆的所有关系
f:S->S所有双射函数构成的集合
合成
恒等函数
无
恒等函数
所有元素
所有元素
最后两条：
一个集合上的所有双射函数都有其对应的反函数，且反函数也是该集合上的双射函数
一个集合上的双射函数和其反函数合成的结果是恒等函数
一个集合上的双射函数构成集合，是所有关系构成集合的子集
同类型的代数
以下关系，要求 < S, ∘ >和 < T, × >是同类型的
同态关系
记号：记 < S, ∘ > ≃ < T, × >表示前者同态于后者
定义：上式$\Rightarrow\exist f(f\in
T^S\wedge\forall x\forall y(x,y\in S\rightarrow f(x\circ y)=f(x)\times
f(y)))$，其中称f : S → T为 < S, ∘ >到 < T, × >的同态映射
即先通过运算映射再通过f映射等于先通过f映射再通过运算映射
f不唯一
在代数有多个二元运算时，要求f是同一个
由f的值域R(f) ⊆ T，易得 < R(f), × > ⊆ < T, × >
同态映射的分类
根据f的性质，对该映射进行分类：
f为满射⇒从前者到后者的满同态映射
f为单射⇒从前者到后者的单一同态映射
f为双射⇒从前者到后者的同构映射
满同态映射的运算继承性质
只要f是满射的(包括同构关系)，就有以下性质：
两代数的对应运算的结合、交换、分配、等幂律等性质是一致的
前代数中运算的幺元、零元、逆元经f后，等于后代数中对应运算的幺元、零元、逆元
同构关系
记号： < S, ∘ > ≅ < T, × > ⇒前者同构于后者
同构意味着，每个f(x)有其唯一对应的原像，因此两个代数可以互相映射，即同时存在同构关系 < T, × > ≅f−1 < S, ∘ >；而不是像同态一样，只能单向地映射系统
代数间的同构关系是等价关系
可通过同构关系，将所有代数形成的集合按其分类
同态、同构关系指的不是f这个函数关系，而是由两代数作为第一、二元素的二元关系
称从 < S, ∘ >到自身的同态、同构关系为自同态、自同构关系
代数间的运算
同余关系
定义：若E是S上的等价关系，且满足∀x1∀y1∀x2∀y2((x1,y1,x2,y2∈S∧x1Ey1∧x2Ey2)→(x1∘x2)E(y1∘y2))，则称E是 < S, ∘ >上的同余关系
称由E划分的等价类为同余类
E是特殊的等价关系，能保证元素运算后，仍能满足该关系
E的这种代换需要满足代数中的所有运算
同余关系和同态、同构不是一种概念
另一种表达：[x1]E = [y1]E ∧ [x2]E = [y2]E → [x1∘x2]E = [y1∘y2]E
商代数
若f是 < S, ∘ >到 < T, × >的同态映射，则S上的关系Ef(满足xEfy : f(x) = f(y))一定是同余关系
证明：任取x1, y1, x2, y2 ∈ S，若有x1Efy1 ∧ x2Efy2，则f(x1) = f(y1) ∧ f(x2) = f(y2)；根据同态映射的定义，有$\begin{cases}f(x_1)\times f(x_2)=f(x_1\circ
x_2)\\f(y_1)\times f(y_2)=f(y_1\circ
y_2)\end{cases}$；三式联立得f(x1∘x2) = f(y1∘y2)，即(x1∘x2)Ef(y1∘y2)，得证
称Ef为由f诱导的同余关系
商代数：给定 < S, ∘ >及其上的一个同余关系E：
以E导出的商集S/E为集合，构造满足同态定义的运算×：∀x∀y ∈ S → [x∘y]E = [x]E × [y]E，则称 < S/E, × >为它的商代数
商代数是人为构造的，满足 < S, ∘ > ≃ < S/E, × >，gE(x) = [x]E
易得gE为满同态映射，因此商代数的运算继承了本代数运算的性质
该映射被称为正则映射、自然同态
设 < S, ∘ > ≃ < T, × >，且f为满同态映射，则 < T, × > ≅ < S/Ef, * >(后者为 < S, ∘ >的商代数)
证明：构造函数$\begin{cases}h:T\rightarrow
S/E_f\\h(y)=[x]_E\end{cases}$，其中y = f(x)
证其为同态映射
h(y1×y2) = h(f(x1∘x2)) = [x1∘x2]E，由商集定义，上式 = [x1]E * [x2]E
⇒ ∀y1∀y2(y1,y2∈T→[x1]E*[x2]E=h(y1×y2))
⇒ < T, × > ≃ < S/Ef, * >，h为其同态映射
证其为满射：f、gEf为满射 ⇒ h为满射
证其为单射：若h(y1) = h(y2)
⇒ [x1]E = [x2]E ⇒ x1Efx2 ⇒ f(x1) = f(x2) ⇒ y1 = y2
得证
积代数
设有同类型的代数 < S, ∘ >和 < T, × >，则定义运算⊗：∀x1∀x2∀y1∀y2(x1,x2∈S∧y1,y2∈T→
称 < S × T, ⊗ >为上述两个代数的积代数；上述两个代数为该积代数的因子代数
上述为两因子代数形成的积代数，多因子代数形成的积代数可递归定义
积代数和因子代数是同类型的
积代数的运算包含了所有因子代数的运算及其笛卡尔积顺序的信息