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

代数系统的基本性质

同构

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

同构的性质

1. 自反性

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

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

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

f(a \star b) = a \star b = f(a) \star f(b)

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

2. 对称性

定理：若 (A, \star) \cong (B, \circ)，则 (B, \circ) \cong (A, \star)。

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

证明 f^{-1}(y_1 \circ y_2)=f^{-1}(y_1)\star f^{-1}(y_2) 与 f(x_1 \star x_2)=f(x_1)\circ f(x_2) 等价：

1. 用已知条件替换：

   f^{-1}(f(x_1) \circ f(x_2)) = f^{-1}(f(x_1))\star f^{-1}(f(x_2))

2. 两边再套 f，消去 f^{-1}：

   f(x_1\star x_2) = f(x_1) \circ f(x_2)

更一般地，若 (A, \star) \cong (B, \circ)，则存在双射 f: A \rightarrow B 满足 f(a \star b) = f(a) \circ f(b)。

构造 f^{-1}: B \rightarrow 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 \star x_2)) = x_1 \star x_2 = f^{-1}(y_1) \star f^{-1}(y_2)

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

3. 传递性

定理：若 (A, \star) \cong (B, \circ) 且 (B, \circ) \cong (C, \bullet)，则 (A, \star) \cong (C, \bullet)。

证明： 设 f: A \rightarrow B 是 (A, \star) 到 (B, \circ) 的同构映射，即 f(a_1 \star a_2) = f(a_1) \circ f(a_2)。 设 g: B \rightarrow C 是 (B, \circ) 到 (C, \bullet) 的同构映射，即 g(b_1 \circ b_2) = g(b_1) \bullet g(b_2)。

构造复合映射 h = g \circ f: A \rightarrow C，对于任意 a_1, a_2 \in A，有：

h(a_1 \star a_2) = g(f(a_1 \star a_2)) = g(f(a_1) \circ f(a_2)) = g(f(a_1)) \bullet g(f(a_2)) = h(a_1) \bullet h(a_2)

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

同构的保持性质

1. 保持结合律

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

证明： 设 f: A \rightarrow B 是 (A, \star) 到 (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 \star a_2) \circ f(a_3) = f((a_1 \star a_2) \star a_3)

由于 \star 满足结合律，有 (a_1 \star a_2) \star a_3 = a_1 \star (a_2 \star a_3)，因此：

f((a_1 \star a_2) \star a_3) = f(a_1 \star (a_2 \star a_3)) = f(a_1) \circ f(a_2 \star 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, \star) \cong (B, \circ)，且 \star 在 A 上具有交换律，则 \circ 在 B 上也具有交换律。

证明： 设 f: A \rightarrow B 是 (A, \star) 到 (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 \star a_2)

由于 \star 满足交换律，有 a_1 \star a_2 = a_2 \star a_1，因此：

f(a_1 \star a_2) = f(a_2 \star 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, \star) \cong (B, \circ)，则：

1. 若 e_A 是 (A, \star) 的幺元，则 f(e_A) 是 (B, \circ) 的幺元。
2. 若 z_A 是 (A, \star) 的零元，则 f(z_A) 是 (B, \circ) 的零元。
3. 若 a^{-1} 是 a 在 (A, \star) 中的逆元，则 f(a^{-1}) 是 f(a) 在 (B, \circ) 中的逆元。

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

b \circ f(e_A) = f(a) \circ f(e_A) = f(a \star e_A) = f(a) = b

f(e_A) \circ b = f(e_A) \circ f(a) = f(e_A \star a) = f(a) = b

因此 f(e_A) 是 (B, \circ) 的幺元。（零元和逆元的证明类似）

4. 保持分配率

定理：若 (A, \star, \diamond) \cong (B, \circ, \triangle)，且 \diamond 对 \star 满足分配率，则 \triangle 对 \circ 也满足分配率。

证明： 设 f: A \rightarrow B 是同构映射，满足 f(a_1 \star a_2) = f(a_1) \circ f(a_2) 和 f(a_1 \diamond a_2) = f(a_1) \triangle f(a_2)。

若 \diamond 对 \star 满足左分配律，即 a_1 \diamond (a_2 \star a_3) = (a_1 \diamond a_2) \star (a_1 \diamond a_3)，则对于任意 b_1, b_2, b_3 \in B，设 f(a_i) = b_i：

\begin{align}
b_1 \triangle (b_2 \circ b_3) &= f(a_1) \triangle (f(a_2) \circ f(a_3)) \\
&= f(a_1) \triangle f(a_2 \star a_3) \\
&= f(a_1 \diamond (a_2 \star a_3)) \\
&= f((a_1 \diamond a_2) \star (a_1 \diamond a_3)) \\
&= f(a_1 \diamond a_2) \circ f(a_1 \diamond a_3) \\
&= (b_1 \triangle b_2) \circ (b_1 \triangle b_3)
\end{align}

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

5. 保持吸收率

定理：若 (A, \star, \diamond) \cong (B, \circ, \triangle)，且 (A, \star, \diamond) 满足吸收律，则 (B, \circ, \triangle) 也满足吸收律。

证明： 设 f: A \rightarrow B 是同构映射，(A, \star, \diamond) 满足吸收律：a_1 \star (a_1 \diamond a_2) = a_1 和 a_1 \diamond (a_1 \star 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{align}
b_1 \circ (b_1 \triangle b_2) &= f(a_1) \circ (f(a_1) \triangle f(a_2)) \\
&= f(a_1) \circ f(a_1 \diamond a_2) \\
&= f(a_1 \star (a_1 \diamond a_2)) \\
&= f(a_1) \\
&= b_1
\end{align}

类似地：

\begin{align}
b_1 \triangle (b_1 \circ b_2) &= f(a_1) \triangle (f(a_1) \circ f(a_2)) \\
&= f(a_1) \triangle f(a_1 \star a_2) \\
&= f(a_1 \diamond (a_1 \star a_2)) \\
&= f(a_1) \\
&= b_1
\end{align}

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

同态核

定义

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

\text{Ker}(f) = \{a \in A | f(a) = e_B\}

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

同态核的性质

1. 闭包性：若 a, b \in \text{Ker}(f)，则 a \star b \in \text{Ker}(f)

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

   f(a \star b) = f(a) \circ f(b) = e_B \circ e_B = e_B

   因此 a \star b \in \text{Ker}(f)

2. 幺元属于核：若 (A, \star) 有幺元 e_A，则 e_A \in \text{Ker}(f)

   证明：由同态的性质，f(e_A) 是 (B, \circ) 的幺元，即 f(e_A) = e_B， 因此 e_A \in \text{Ker}(f)

3. 正规子群性质：若 (A, \star) 是群，则 \text{Ker}(f) 是 (A, \star) 的正规子群

   证明：

   • 由性质1和2，\text{Ker}(f) 是非空的，并且对 \star 运算封闭

   • 对任意 a \in \text{Ker}(f)，其逆元 a^{-1} 满足：

     f(a^{-1}) = f(a)^{-1} = e_B^{-1} = e_B

     因此 a^{-1} \in \text{Ker}(f)

   • 对任意 x \in A 和 a \in \text{Ker}(f)：

     f(x \star a \star 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 \star a \star x^{-1} \in \text{Ker}(f)，这证明了 \text{Ker}(f) 是正规子群

同态核与同构的关系

定理：设 f: (A, \star) \rightarrow (B, \circ) 是满同态，则 f 是同构当且仅当 \text{Ker}(f) = \{e_A\}。

证明：

• 若 f 是同构，则 f 是双射，特别是单射。对任意 a \in A，若 f(a) = e_B，则 a = e_A（因为 f(e_A) = e_B）。所以 \text{Ker}(f) = \{e_A\}。

• 反之，若 \text{Ker}(f) = \{e_A\}，则对任意 a, b \in A，如果 f(a) = f(b)，则：

  f(a \star b^{-1}) = f(a) \circ f(b)^{-1} = f(a) \circ f(a)^{-1} = e_B

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

后记

ai帮助了排版与\LaTeX{}符号查询,修正某些符号错误与渲染