离散数学笔记(7)——代数系统

离散数学笔记(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$:

  1. $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$。
  2. $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)\}$。
  3. $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}$。

规定

  1. 从 $\varnothing$ 到 $\varnothing$ 的函数只有 $f = \varnothing$。
  2. 从 $\varnothing$ 到 $Y$ 的函数只有 $f = \varnothing$。
  3. 若 $X \not = \varnothing$,则从 $X$ 到 $\varnothing$ 的函数不存在。

特殊函数

  1. 常值函数:函数 $f : X \to Y$,如果 $\exists y_0 \in Y$,使得对 $\forall x \in X$,有 $f(x) = y_0$,即 $\mathrm{ran} f = \{y_0\}$,称 $f$ 是常值函数。
  2. 恒等函数:恒等关系 $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)$。

函数的类型

  1. 满射的:$f : X \to Y$ 是函数,如果 $\mathrm{ran} f =Y$,则称 $f$ 是满射的
  2. 入射的:$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$ 是一对一的
  3. 双射的:$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$ 的左边可复合。

定理:两个函数的复合是一个函数。

43

定义:设 $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))$

复合函数的计算同复合关系。

性质

  1. (满足可结合性)$f : X \to Y,g : Y \to Z,h : Z \to W$ 是函数,则 $(h \circ g) \circ f = h \circ (g \circ f)$。

  2. $f : X \to Y,g : Y \to Z$ 是两个函数,则:

    1. 如果 $f$ 和 $g$ 是满射的,则 $g \circ f$ 也是满射的。
    2. 如果 $f$ 和 $g$ 是入射的,则 $g \circ f$ 也是入射的。
    3. 如果 $f$ 和 $g$ 是双射的,则 $g \circ f$ 也是双射的。

    44

  3. $f : X \to Y,g : Y \to Z$ 是两个函数,则:

    1. 如果 $g \circ f$ 是满射的,则 $g$ 是满射的。
    2. 如果 $g \circ f$ 是入射的,则 $f$ 是入射的。
    3. 如果 $g \circ f$ 是双射的,则 $f$ 是入射的且 $g$ 是满射的。
  4. $f : X \to Y$ 是函数,则 $f \circ I_X = f$ 且 $I_Y \circ f = f$。

逆函数

定理 1:若 $f$ 是 $X \to Y$ 的双射,则 $f^c$ 是 $Y \to X$ 的函数。

45

定义:设 $f$ 是 $X \to Y$ 的双射函数,则称 $f^c : Y \to X$ 为 $f$ 的逆函数,并记为 $f^{-1}$。

定理 2:$f^{-1}$ 是 $Y \to X$ 的双射函数。

46

性质

  1. 设 $f$ 是 $X \to Y$ 的双射函数,则 $(f^{-1})^{-1} = f$。

  2. 设 $f$ 是 $X \to Y$ 的双射函数,则 $f^{-1} \circ f = I_X$ 且 $f \circ f^{-1} = I_Y$。

    47

  3. 令 $f : X \to Y,g : Y \to X$ 是两个函数,如果 $g \circ f = I_X$ 且 $f \circ g = I_Y$,则 $g = f^{-1}$。

    48

    49

  4. 令 $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$。

二元运算的运算表

可用一个表来表示二元运算的运算规律。

50

代数系统的概念

  1. 代数系统的定义:$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)$。
  2. 有限代数系统:$U = \langle X,f_1,f_2,\cdots,f_m \rangle$ 是一个代数系统,如果 $X$ 是个有限集合,则称 $U$ 是个有限代数系统
  3. 同类型代数系统:给定两个代数系统,$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$ 是惟一的。

51

零元

设 $\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$ 的逆元是唯一的。

52

定理 2:设 $\star$ 是 $X$ 上有单位元 $e$ 且可结合的二元运算,如果 $\forall x \in X$,都存在左逆元,则 $x$ 的左逆元也是它的右逆元。

53

 

点赞 0

No Comments

Add your comment