离散数学: 代数系统

Posted on Edited on In , Word count in article: 2.8k Reading time ≈ 10 mins.

代数系统

定义

  • 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→<x1∘x2,y1×y2>=<x1,y1>⊗<x2,y2>)

称 < S × T,  ⊗ >为上述两个代数的积代数；上述两个代数为该积代数的因子代数

  • 上述为两因子代数形成的积代数，多因子代数形成的积代数可递归定义
  • 积代数和因子代数是同类型的
  • 积代数的运算包含了所有因子代数的运算及其笛卡尔积顺序的信息