wzf2000 离散数学笔记（7）——代数系统
Contents
代数结构（代数系统）
函数
定义
对于集合 $X$ 与 $Y$，$f$ 是从 $X$ 到 $Y$ 的关系，如果 $x \in X$，都存在唯一 $y \in Y$，使得 $\langle x,y \rangle \in f$，则称 $f$ 是从 $X$ 到 $Y$ 的函数（变换、映射），记作 $f : X \to Y$ 或 $X \stackrel{f}{\longrightarrow} Y$，$\langle x,y \rangle \in f$ 可记为 $y = f(x)$。
如果 $f : X \to X$ 是函数，也称 $f$ 是 $X$ 上的函数。
定义域、值域和陪域（共域）
设 $f : X \to Y$：
- $f$ 的定义域，记作 $\mathrm{dom} f$ 或 $D_f$，即 $D_f = \mathrm{dom} f = \{x | x \in X \land \exists y(y \in Y \land \langle x,y \rangle \in f)\} = X$。
- $f$ 的值域，记作 $\mathrm{ran} f$ 或 $R_f$ 或 $f(X)$，即 $R_f = \mathrm{ran} f = f(X) = \{y|y \in Y \land \exists x (x \in X \land \langle x,y \rangle \in f)\}$。
- $f$ 的陪域，即 $Y$。
函数的表示方法
枚举法、关系图、关系矩阵、谓词描述法。
从 $X$ 到 $Y$ 的函数的集合 $Y^X$
$Y^X = \{f | f : X \to Y\}$
$Y^X$：它是由所有的从 $X$ 到 $Y$ 的函数构成的集合。
结论：若 $X$、$Y$ 是有限集合，且 $|X| = m,|Y| = n$，则 $|Y^X| = |Y|^{|X|} = n^m$。从 $X$ 到 $Y$ 的关系 $= |P(X \times Y)| = 2^{nm}$。
规定：
- 从 $\varnothing$ 到 $\varnothing$ 的函数只有 $f = \varnothing$。
- 从 $\varnothing$ 到 $Y$ 的函数只有 $f = \varnothing$。
- 若 $X \not = \varnothing$，则从 $X$ 到 $\varnothing$ 的函数不存在。
特殊函数
- 常值函数：函数 $f : X \to Y$，如果 $\exists y_0 \in Y$，使得对 $\forall x \in X$，有 $f(x) = y_0$，即 $\mathrm{ran} f = \{y_0\}$，称 $f$ 是常值函数。
- 恒等函数：恒等关系 $I_X$ 是 $X$ 到 $X$ 的函数，即 $I_X : X \to X$，称之为恒等函数。显然对于 $\forall x \in X$，有 $I_X(x) = x$。
两个函数相等
设有两个函数 $f : A \to B,g : A \to B$，$f = g$ 当且仅当，对任何 $x \in A$，有 $f(x) = g(x)$。
函数的类型
- 满射的：$f : X \to Y$ 是函数，如果 $\mathrm{ran} f =Y$，则称 $f$ 是满射的。
- 入射的：$f : X \to Y$ 是函数，如果对于任何 $x_1,x_2 \in X$，如果 $x_1 \not = x_2$ 有 $f(x_1) \not = f(x_2)$，则称 $f$ 是入射的，也称 $f$ 是单射的，也称 $f$ 是一对一的。
- 双射的：$f : X \to Y$ 是函数，如果 $f$ 既是满射的，又是入射的，则称 $f$ 是双射的，也称 $f$ 是一一对应的。
特别地，$\varnothing : \varnothing \to Y$ 是单射，$\varnothing : \varnothing \to \varnothing$ 是双射。
在 $X$ 有限的情况下，$f : X \to X$ 是入射的，则 $f$ 必是满射的。
函数的复合
设 $f : X \to Y$, $g : W \to Z$是函数，若 $f(X) \subseteq W$，则 $g \circ f = \{\langle x,z \rangle | x \in X \land z \in Z \land \exists y(y \in Y \land \langle x,y \rangle \in f \land \langle y,z \rangle \in g)\}$ 称为 $g$ 在 $f$ 的左边可复合。
定理：两个函数的复合是一个函数。
定义：设 $f : X \to Y$, $g : Y \to Z$是函数，则定义 $g \circ f = \{\langle x,z \rangle | x \in X \land z \in Z \land \exists y(y \in Y \land \langle x,y \rangle \in f \land \langle y,z \rangle \in g)\}$，则称 $g \circ f$ 为 $f$ 与 $g$ 的复合函数（左复合）。
结论：$(g \circ f) (x) = g(f(x))$
复合函数的计算同复合关系。
性质：
- （满足可结合性）$f : X \to Y,g : Y \to Z,h : Z \to W$ 是函数，则 $(h \circ g) \circ f = h \circ (g \circ f)$。
$f : X \to Y,g : Y \to Z$ 是两个函数，则：
- 如果 $f$ 和 $g$ 是满射的，则 $g \circ f$ 也是满射的。
- 如果 $f$ 和 $g$ 是入射的，则 $g \circ f$ 也是入射的。
- 如果 $f$ 和 $g$ 是双射的，则 $g \circ f$ 也是双射的。
$f : X \to Y,g : Y \to Z$ 是两个函数，则：
- 如果 $g \circ f$ 是满射的，则 $g$ 是满射的。
- 如果 $g \circ f$ 是入射的，则 $f$ 是入射的。
- 如果 $g \circ f$ 是双射的，则 $f$ 是入射的且 $g$ 是满射的。
- $f : X \to Y$ 是函数，则 $f \circ I_X = f$ 且 $I_Y \circ f = f$。
逆函数
定理 1：若 $f$ 是 $X \to Y$ 的双射，则 $f^c$ 是 $Y \to X$ 的函数。
定义：设 $f$ 是 $X \to Y$ 的双射函数，则称 $f^c : Y \to X$ 为 $f$ 的逆函数，并记为 $f^{-1}$。
定理 2：$f^{-1}$ 是 $Y \to X$ 的双射函数。
性质：
- 设 $f$ 是 $X \to Y$ 的双射函数，则 $(f^{-1})^{-1} = f$。
设 $f$ 是 $X \to Y$ 的双射函数，则 $f^{-1} \circ f = I_X$ 且 $f \circ f^{-1} = I_Y$。
令 $f : X \to Y,g : Y \to X$ 是两个函数，如果 $g \circ f = I_X$ 且 $f \circ g = I_Y$，则 $g = f^{-1}$。
令 $f : X \to Y,g : Y \to X$ 是两个双射函数，则 $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$。
代数结构（系统）的概念
$n$ 元运算
设 $X,Y$ 是集合，$f : X^n \to Y$ 是个映射，则称 $f$ 是 $X$ 上的一个 $n$ 元运算。
主要讨论二元运算，一般用 $x \star y = z$ 表示 $f(\langle x,y \rangle) = z$。
二元运算的运算表
可用一个表来表示二元运算的运算规律。
代数系统的概念
- 代数系统的定义：$X$ 是非空集合，$f_1,f_2,\cdots,f_m$ 分别是 $X$ 上 $k_1,k_2,\cdots,k_m$ 元运算，$k_i$ 为整数，称集合 $X$ 和运算 $f_1,f_2,\cdots,f_m$ 所构成的系统为一个代数系统 $U$（或一个代数结构），简称一个代数，记作 $U = \langle X,f_1,f_2,\cdots,f_m \rangle(m \ge 1)$。
- 有限代数系统：$U = \langle X,f_1,f_2,\cdots,f_m \rangle$ 是一个代数系统，如果 $X$ 是个有限集合，则称 $U$ 是个有限代数系统。
- 同类型代数系统：给定两个代数系统，$U = \langle X,f_1,f_2,\cdots,f_m \rangle,V = \langle Y,g_1,g_2,\cdots,g_m \rangle$，若对应的运算 $f_i$ 和 $g_i$ 的元数相同，则称 $U$ 与 $V$ 是同类型代数系统。
封闭性
设 $\star$ 是 $X$ 上的二元运算，如果对任何 $x,y \in X$，有 $x \star y \in X$，则称二元运算 $\star$ 在 $X$ 上是封闭的。
交换性
设 $\star$ 是 $X$ 上的二元运算，如果对任何 $x,y \in X$，有 $x \star y = y \star x$，则称 $\star$ 是可交换的。
从运算表看交换性：是个以主对角线为对称的表。
等幂元、等幂性
设 $\star$ 是 $X$ 上的二元运算，如果存在 $a \in X$，使得 $a \star a = a$，则称 $a$ 是等幂元，如果对任何 $x \in X$，都有 $x \star x = x$，则称 $\star$ 有等幂性。
从运算表看等幂元、等幂性：主对角线的元素与上表头（或左表头）元素相同。
单位元（幺元、恒等元）
设 $\star$ 是 $X$ 上的二元运算，如果存在 $e_L \in X$，使得对任何 $x \in X$，有 $e_L \star x = x$，则称 $e_L$ 是相对 $\star$ 的左单位元。如果存在 $e_R \in X$，使得对任何 $x \in X$，有 $x \star e_R = x$，则称 $e_R$ 是相对 $\star$ 的右单位元。如果 $e_L = e_R = e$，对任何 $x \in X$，有 $e \star x = x \star e = x$，称 $e$ 是相对 $\star$ 的单位元。
从运算表中找左单位元 $e_L$：$e_L$ 所在行的各元素均与上表头元素相同。
从运算表中找右单位元 $e_R$：$e_R$ 所在列的各元素均与左表头元素相同。
定理 1：设 $\star$ 是 $X$ 上的二元运算，如果有左单位元 $e_L \in X$，也有右单位元 $e_R \in X$，则 $e_L = e_R = e$，且单位元 $e$ 是惟一的。
零元
设 $\star$ 是 $X$ 上的二元运算，如果存在 $\theta_L \in X$，使得对任何 $x \in X$，有 $\theta_L \star x = \theta_L$，则称 $\theta_L$ 是相对 $\star$ 的左零元。如果存在 $\theta_R \in X$，使得对任何 $x \in X$，有 $x \star \theta_R = \theta_R$，则称 $\theta_R$ 是相对 $\star$ 的右零元。如果 $\theta_L = \theta_R = \theta$，对任何 $x \in X$，有 $\theta \star x = x \star \theta = \theta$，称 $\theta$ 是相对 $\star$ 的零元。
从运算表找左零元 $\theta_L$：$\theta_L$ 所在行的各元素均与左表头元素相同。
从运算表找右零元 $\theta_R$：$\theta_R$ 所在列的各元素均与上表头元素相同。
定理 2：设 $\star$ 是 $X$ 上的二元运算，如果有左零元 $\theta_L \in X$，也有右零元 $\theta_R \in X$，则 $\theta_L = \theta_R = \theta$，且零元 $\theta$ 是惟一的。
定理 3：$\langle A,\star \rangle$ 是代数系统，且集合 $A$ 中元素个数大于 $1$，如果该代数系统中存在单位元 $e$ 和零元 $\theta$，则 $e \not = \theta$。
可结合性
设 $\star$ 是 $X$ 上的二元运算，如果对任何 $x,y,z \in X$，有 $(x \star y) \star z = x \star (y \star z)$，则称 $\star$ 是可结合的。
$\star$ 是可结合的运算，则相同元素 $x$ 的 $\star$ 运算一般可以写成乘幂的形式：$x \star x = x^2,x \star x^{n - 1} = x^n$。
定理：设 $A$ 是非空集合，$\star$ 是 $A$ 上的二元运算且满足结合律，则对任意的正整数 $m$ 和 $n$ ，有 $x^m \star x^n = x^{m+n},(x^m)^n = x^{mn}$。
逆元
设 $\star$ 是 $X$ 上有单位元 $e$ 的二元运算，$x \in X$，如果存在 $x_L^{-1} \in X$，使得 $x_L^{-1} \star x = e$，则称 $x_L^{-1}$ 是 $x$ 相对 $\star$ 的左逆元。如果存在 $x_R^{-1} \in X$，使得 $x \star x_R^{-1} = e$，则称 $x_R^{-1}$ 是 $x$ 相对 $\star$ 的右逆元。如果 $x_L^{-1} = x_R^{-1} = x^{-1}$，使得 $x^{-1} \star x = x \star x^{-1} = e$，称 $x^{-1}$ 是 $x$ 相对 $\star$ 的逆元，并称 $x$ 可逆。也称 $x^{-1}$ 与 $x$ 互为逆元。
从运算表找左逆元 $x_L^{-1}$：在 $x$ 列向下找到单位元 $e$ 后，再向左到左表头元素即是 $x_L^{-1}$。
从运算表找右逆元 $x_R^{-1}$：在 $x$ 行向右找到单位元 $e$ 后，再向上到上表头元素即是 $x_R^{-1}$。
定理 1：设 $\star$ 是 $X$ 上有单位元 $e$ 且可结合的二元运算，如果 $x \in X$，$x$ 的左、右逆元都存在，则 $x$ 的左、右逆元必相等，且 $x$ 的逆元是唯一的。
定理 2：设 $\star$ 是 $X$ 上有单位元 $e$ 且可结合的二元运算，如果 $\forall x \in X$，都存在左逆元，则 $x$ 的左逆元也是它的右逆元。
No Comments