离散数学:代数系统(二)

发布时间：2025-03-06 10:24:11更新时间：2026-07-19

🕒 阅读时间：34 分钟📝 字数：13318👀 阅读量：Loading...

查看 Markdown 原文

代数系统的基本性质

同构

同构是代数系统之间的一种重要关系，用符号 $≅$ 表示。若两个代数系统 $(A, ⋆)$ 和 $(B, \circ)$ 之间存在同构，则记作 $(A, ⋆) ≅ (B, \circ)$ 。

同构的性质

1. 自反性

定理：任意代数系统与自身同构。

证明：对于任意代数系统 $(A, ⋆)$ ，存在恒等映射 $f : A \to A$ ，对于任意 $a \in A$ ，有 $f (a) = a$ 。

对任意 $a, b \in A$ ，有：

$f (a ⋆ b) = a ⋆ b = f (a) ⋆ f (b)$

所以恒等映射 $f$ 是从系统 $(A, ⋆)$ 到自身的同构，即 $(A, ⋆) ≅ (A, ⋆)$ 。

2. 对称性

定理：若 $(A, ⋆) ≅ (B, \circ)$ ，则 $(B, \circ) ≅ (A, ⋆)$ 。

证明：已知 $y = f (x)$ , $x = f^{- 1} (y)$

证明 $f^{- 1} (y_{1} \circ y_{2}) = f^{- 1} (y_{1}) ⋆ f^{- 1} (y_{2})$ 与 $f (x_{1} ⋆ x_{2}) = f (x_{1}) \circ f (x_{2})$ 等价：

用已知条件替换：

$f^{- 1} (f (x_{1}) \circ f (x_{2})) = f^{- 1} (f (x_{1})) ⋆ f^{- 1} (f (x_{2}))$
两边再套 $f$ ，消去 $f^{- 1}$ ：

$f (x_{1} ⋆ x_{2}) = f (x_{1}) \circ f (x_{2})$

更一般地，若 $(A, ⋆) ≅ (B, \circ)$ ，则存在双射 $f : A \to B$ 满足 $f (a ⋆ b) = f (a) \circ f (b)$ 。

构造 $f^{- 1} : B \to A$ ，则有 $f^{- 1} (f (a)) = a$ 对任意 $a \in A$ 成立。

对于任意 $y_{1}, y_{2} \in B$ ，设 $x_{1} = f^{- 1} (y_{1}), x_{2} = f^{- 1} (y_{2})$ ，则：

$f^{- 1} (y_{1} \circ y_{2}) = f^{- 1} (f (x_{1}) \circ f (x_{2})) = f^{- 1} (f (x_{1} ⋆ x_{2})) = x_{1} ⋆ x_{2} = f^{- 1} (y_{1}) ⋆ f^{- 1} (y_{2})$

因此 $f^{- 1}$ 是从 $(B, \circ)$ 到 $(A, ⋆)$ 的同构映射，即 $(B, \circ) ≅ (A, ⋆)$ 。

3. 传递性

定理：若 $(A, ⋆) ≅ (B, \circ)$ 且 $(B, \circ) ≅ (C, ∙)$ ，则 $(A, ⋆) ≅ (C, ∙)$ 。

证明：设 $f : A \to B$ 是 $(A, ⋆)$ 到 $(B, \circ)$ 的同构映射，即 $f (a_{1} ⋆ a_{2}) = f (a_{1}) \circ f (a_{2})$ 。设 $g : B \to C$ 是 $(B, \circ)$ 到 $(C, ∙)$ 的同构映射，即 $g (b_{1} \circ b_{2}) = g (b_{1}) ∙ g (b_{2})$ 。

构造复合映射 $h = g \circ f : A \to C$ ，对于任意 $a_{1}, a_{2} \in A$ ，有：

$h (a_{1} ⋆ a_{2}) = g (f (a_{1} ⋆ a_{2})) = g (f (a_{1}) \circ f (a_{2})) = g (f (a_{1})) ∙ g (f (a_{2})) = h (a_{1}) ∙ h (a_{2})$

由于 $f$ 和 $g$ 都是双射， $h = g \circ f$ 也是双射，因此 $h$ 是从 $(A, ⋆)$ 到 $(C, ∙)$ 的同构映射，即 $(A, ⋆) ≅ (C, ∙)$ 。

同构的保持性质

1. 保持结合律

定理：若 $(A, ⋆) ≅ (B, \circ)$ ，且 $⋆$ 在 $A$ 上具有结合律，则 $\circ$ 在 $B$ 上也具有结合律。

证明：设 $f : A \to B$ 是 $(A, ⋆)$ 到 $(B, \circ)$ 的同构映射。对于任意 $b_{1}, b_{2}, b_{3} \in B$ ，由于 $f$ 是满射，存在 $a_{1}, a_{2}, a_{3} \in A$ ，使得 $f (a_{1}) = b_{1}, f (a_{2}) = b_{2}, f (a_{3}) = b_{3}$ 。

$(b_{1} \circ b_{2}) \circ b_{3} = (f (a_{1}) \circ f (a_{2})) \circ f (a_{3}) = f (a_{1} ⋆ a_{2}) \circ f (a_{3}) = f ((a_{1} ⋆ a_{2}) ⋆ a_{3})$

由于 $⋆$ 满足结合律，有 $(a_{1} ⋆ a_{2}) ⋆ a_{3} = a_{1} ⋆ (a_{2} ⋆ a_{3})$ ，因此：

$f ((a_{1} ⋆ a_{2}) ⋆ a_{3}) = f (a_{1} ⋆ (a_{2} ⋆ a_{3})) = f (a_{1}) \circ f (a_{2} ⋆ a_{3}) = f (a_{1}) \circ (f (a_{2}) \circ f (a_{3})) = b_{1} \circ (b_{2} \circ b_{3})$

因此 $(b_{1} \circ b_{2}) \circ b_{3} = b_{1} \circ (b_{2} \circ b_{3})$ ， $\circ$ 在 $B$ 上具有结合律。

2. 保持交换律

定理：若 $(A, ⋆) ≅ (B, \circ)$ ，且 $⋆$ 在 $A$ 上具有交换律，则 $\circ$ 在 $B$ 上也具有交换律。

证明：设 $f : A \to B$ 是 $(A, ⋆)$ 到 $(B, \circ)$ 的同构映射。对于任意 $b_{1}, b_{2} \in B$ ，存在 $a_{1}, a_{2} \in A$ ，使得 $f (a_{1}) = b_{1}, f (a_{2}) = b_{2}$ 。

$b_{1} \circ b_{2} = f (a_{1}) \circ f (a_{2}) = f (a_{1} ⋆ a_{2})$

由于 $⋆$ 满足交换律，有 $a_{1} ⋆ a_{2} = a_{2} ⋆ a_{1}$ ，因此：

$f (a_{1} ⋆ a_{2}) = f (a_{2} ⋆ a_{1}) = f (a_{2}) \circ f (a_{1}) = b_{2} \circ b_{1}$

因此 $b_{1} \circ b_{2} = b_{2} \circ b_{1}$ ， $\circ$ 在 $B$ 上具有交换律。

3. 保持幺元、零元和逆元

定理：若 $(A, ⋆) ≅ (B, \circ)$ ，则：

若 $e_{A}$ 是 $(A, ⋆)$ 的幺元，则 $f (e_{A})$ 是 $(B, \circ)$ 的幺元。
若 $z_{A}$ 是 $(A, ⋆)$ 的零元，则 $f (z_{A})$ 是 $(B, \circ)$ 的零元。
若 $a^{- 1}$ 是 $a$ 在 $(A, ⋆)$ 中的逆元，则 $f (a^{- 1})$ 是 $f (a)$ 在 $(B, \circ)$ 中的逆元。

证明（幺元）：设 $f : A \to B$ 是从 $(A, ⋆)$ 到 $(B, \circ)$ 的同构映射， $e_{A}$ 是 $(A, ⋆)$ 的幺元。对任意 $b \in B$ ，存在唯一的 $a \in A$ 使得 $f (a) = b$ 。

$b \circ f (e_{A}) = f (a) \circ f (e_{A}) = f (a ⋆ e_{A}) = f (a) = b$

$f (e_{A}) \circ b = f (e_{A}) \circ f (a) = f (e_{A} ⋆ a) = f (a) = b$

因此 $f (e_{A})$ 是 $(B, \circ)$ 的幺元。（零元和逆元的证明类似）

4. 保持分配率

定理：若 $(A, ⋆, ⋄) ≅ (B, \circ, △)$ ，且 $⋄$ 对 $⋆$ 满足分配率，则 $△$ 对 $\circ$ 也满足分配率。

证明：设 $f : A \to B$ 是同构映射，满足 $f (a_{1} ⋆ a_{2}) = f (a_{1}) \circ f (a_{2})$ 和 $f (a_{1} ⋄ a_{2}) = f (a_{1}) △ f (a_{2})$ 。

若 $⋄$ 对 $⋆$ 满足左分配律，即 $a_{1} ⋄ (a_{2} ⋆ a_{3}) = (a_{1} ⋄ a_{2}) ⋆ (a_{1} ⋄ a_{3})$ ，则对于任意 $b_{1}, b_{2}, b_{3} \in B$ ，设 $f (a_{i}) = b_{i}$ ：

$\begin{matrix} b_{1} △ (b_{2} \circ b_{3}) & = f (a_{1}) △ (f (a_{2}) \circ f (a_{3})) \\ = f (a_{1}) △ f (a_{2} ⋆ a_{3}) \\ = f (a_{1} ⋄ (a_{2} ⋆ a_{3})) \\ = f ((a_{1} ⋄ a_{2}) ⋆ (a_{1} ⋄ a_{3})) \\ = f (a_{1} ⋄ a_{2}) \circ f (a_{1} ⋄ a_{3}) \\ = (b_{1} △ b_{2}) \circ (b_{1} △ b_{3}) \end{matrix}$

因此 $△$ 对 $\circ$ 满足左分配律。右分配律的证明类似。

5. 保持吸收率

定理：若 $(A, ⋆, ⋄) ≅ (B, \circ, △)$ ，且 $(A, ⋆, ⋄)$ 满足吸收律，则 $(B, \circ, △)$ 也满足吸收律。

证明：设 $f : A \to B$ 是同构映射， $(A, ⋆, ⋄)$ 满足吸收律： $a_{1} ⋆ (a_{1} ⋄ a_{2}) = a_{1}$ 和 $a_{1} ⋄ (a_{1} ⋆ a_{2}) = a_{1}$ 。

对于任意 $b_{1}, b_{2} \in B$ ，存在 $a_{1}, a_{2} \in A$ ，使得 $f (a_{1}) = b_{1}, f (a_{2}) = b_{2}$ 。

$\begin{matrix} b_{1} \circ (b_{1} △ b_{2}) & = f (a_{1}) \circ (f (a_{1}) △ f (a_{2})) \\ = f (a_{1}) \circ f (a_{1} ⋄ a_{2}) \\ = f (a_{1} ⋆ (a_{1} ⋄ a_{2})) \\ = f (a_{1}) \\ = b_{1} \end{matrix}$

类似地：

$\begin{matrix} b_{1} △ (b_{1} \circ b_{2}) & = f (a_{1}) △ (f (a_{1}) \circ f (a_{2})) \\ = f (a_{1}) △ f (a_{1} ⋆ a_{2}) \\ = f (a_{1} ⋄ (a_{1} ⋆ a_{2})) \\ = f (a_{1}) \\ = b_{1} \end{matrix}$

因此 $(B, \circ, △)$ 也满足吸收律。

同态核

定义

设 $f : (A, ⋆) \to (B, \circ)$ 是一个同态映射，则 $f$ 的同态核（也称为核）定义为：

$Ker (f) = {‘{’} a \in A | f (a) = e_{B} {‘}’}$

其中 $e_{B}$ 是代数系统 $(B, \circ)$ 的单位元（幺元）。

同态核的性质

闭包性：若 $a, b \in Ker (f)$ ，则 $a ⋆ b \in Ker (f)$

证明：因为 $a, b \in Ker (f)$ ，所以 $f (a) = e_{B}, f (b) = e_{B}$

$f (a ⋆ b) = f (a) \circ f (b) = e_{B} \circ e_{B} = e_{B}$

因此 $a ⋆ b \in Ker (f)$
幺元属于核：若 $(A, ⋆)$ 有幺元 $e_{A}$ ，则 $e_{A} \in Ker (f)$

证明：由同态的性质， $f (e_{A})$ 是 $(B, \circ)$ 的幺元，即 $f (e_{A}) = e_{B}$ ，因此 $e_{A} \in Ker (f)$
正规子群性质：若 $(A, ⋆)$ 是群，则 $Ker (f)$ 是 $(A, ⋆)$ 的正规子群

证明：
- 由性质1和2， $Ker (f)$ 是非空的，并且对 $⋆$ 运算封闭
- 对任意 $a \in Ker (f)$ ，其逆元 $a^{- 1}$ 满足：
  
  $f (a^{- 1}) = f {(a)}^{- 1} = e_{B}^{- 1} = e_{B}$
  
  因此 $a^{- 1} \in Ker (f)$
- 对任意 $x \in A$ 和 $a \in Ker (f)$ ：
  
  $f (x ⋆ a ⋆ x^{- 1}) = f (x) \circ f (a) \circ f (x^{- 1}) = f (x) \circ e_{B} \circ f {(x)}^{- 1} = f (x) \circ f {(x)}^{- 1} = e_{B}$
  
  因此 $x ⋆ a ⋆ x^{- 1} \in Ker (f)$ ，这证明了 $Ker (f)$ 是正规子群

同态核与同构的关系

定理：设 $f : (A, ⋆) \to (B, \circ)$ 是满同态，则 $f$ 是同构当且仅当 $Ker (f) = {e_{A}}$ 。

证明：

若 $f$ 是同构，则 $f$ 是双射，特别是单射。对任意 $a \in A$ ，若 $f (a) = e_{B}$ ，则 $a = e_{A}$ （因为 $f (e_{A}) = e_{B}$ ）。所以 $Ker (f) = {e_{A}}$ 。
反之，若 $Ker (f) = {e_{A}}$ ，则对任意 $a, b \in A$ ，如果 $f (a) = f (b)$ ，则：

$f (a ⋆ b^{- 1}) = f (a) \circ f {(b)}^{- 1} = f (a) \circ f {(a)}^{- 1} = e_{B}$

因此 $a ⋆ b^{- 1} \in Ker (f) = {e_{A}}$ ，即 $a ⋆ b^{- 1} = e_{A}$ ，所以 $a = b$ 。这证明了 $f$ 是单射，结合 $f$ 是满射的条件， $f$ 是双射，即同构。

后记

ai帮助了排版与 $L A T E X$ 符号查询,修正某些符号错误与渲染