函数与关系

函数和关系是连接抽象数学与具体应用的重要桥梁。函数描述输入到输出的映射关系，关系则描述对象之间更一般的联系。在计算机科学中，函数是程序设计的基本概念，关系则是数据库理论、程序验证、人工智能等领域的基础工具。

函数的基本概念

函数的定义

函数（Function）是一种特殊的二元关系，它将一个集合中的每个元素唯一地映射到另一个集合中的元素。

设 $X$ 和 $Y$ 是两个集合，函数 $f: X \to Y$ 是一个规则，对于 $X$ 中的每个元素 $x$ ，都存在 $Y$ 中唯一确定的元素 $y$ 与之对应。记作 $f(x) = y$ 或 $x \mapsto y$ 。

三个核心概念：

定义域（Domain）：集合 $X$ ，即函数的输入集合
陪域（Codomain）：集合 $Y$ ，即函数可能输出的集合
值域（Range/Image）：函数实际输出的集合，即 $\{f(x) \mid x \in X\} \subseteq Y$

很多人容易混淆陪域和值域。陪域是函数定义时声明的输出集合，而值域是函数实际能取到的输出值的集合。值域是陪域的子集。

函数的形式化定义

在集合论中，函数可以形式化定义为满足特定条件的二元关系。

函数 $f: X \to Y$ 是笛卡尔积 $X \times Y$ 的一个子集，满足：

存在性：对于每个 $x \in X$ ，存在 $y \in Y$ 使得 $(x, y) \in f$
唯一性：如果 $(x, y_1) \in f$ 且 $(x, y_2) \in f$ ，则 $y_1 = y_2$

这个定义揭示了函数的本质：函数是一个有序对的集合，每个输入对应唯一的输出。

# Python 中的函数定义
def square(x):
    return x ** 2

# 函数可以看作是有序对的集合
# square = {(0, 0), (1, 1), (2, 4), (3, 9), ...}

函数的表示方法

解析式：用数学表达式描述函数，如 $f(x) = x^2 + 1$

列表法：列出定义域中每个元素及其对应的函数值。适用于定义域有限的情况。

$x$	1	2	3	4	5
$f(x)$	2	5	10	17	26

图像法：在坐标系中绘制函数图像。适用于实数域上的函数。

多元函数

多元函数是接受多个参数的函数。形式上， $f: X_1 \times X_2 \times \cdots \times X_n \to Y$ 是一个从笛卡尔积到 $Y$ 的函数。

例如，加法函数 $+: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ 接受两个实数，输出它们的和。

# 多元函数
def distance(x, y):
    return (x**2 + y**2) ** 0.5

部分函数与全函数

全函数（Total Function）：定义域中每个元素都有对应的函数值。通常所说的"函数"默认指全函数。

部分函数（Partial Function）：并非定义域中所有元素都有定义。例如， $f(x) = 1/x$ 在 $x = 0$ 处无定义。

在编程中，部分函数很常见。除法运算在除数为零时无定义，数组访问在索引越界时无定义。

# 部分函数示例：除法
def divide(a, b):
    if b == 0:
        raise ValueError("Division by zero")  # 在 b=0 处无定义
    return a / b

函数的类型

根据函数的不同性质，可以将函数分为几种重要类型。

单射（Injective Function）

单射函数保证不同的输入产生不同的输出。如果 $f(x_1) = f(x_2)$ ，则必有 $x_1 = x_2$ 。等价地说，如果 $x_1 \neq x_2$ ，则 $f(x_1) \neq f(x_2)$ 。

单射也称为"一对一"映射或内射。

判断方法：检查陪域中的每个元素是否至多有一个原像。

# 单射函数示例：f(x) = 2x + 1
def f(x):
    return 2 * x + 1
# 不同的 x 永远产生不同的 f(x)

# 非单射函数示例：f(x) = x^2
def g(x):
    return x ** 2
# g(2) = g(-2) = 4，不是单射

直观理解：想象一个电影院，如果每个座位最多坐一个人（可以有空座），这就是单射。观众到座位的映射是单射。

满射（Surjective Function）

满射函数保证陪域中的每个元素都是某个输入的输出。对于陪域 $Y$ 中的每个元素 $y$ ，都存在定义域 $X$ 中的元素 $x$ 使得 $f(x) = y$ 。

满射也称为"映上"映射。

判断方法：检查值域是否等于陪域。

# 满射函数示例：f(x) = x mod 3，定义域为 Z，陪域为 {0, 1, 2}
def mod3(x):
    return x % 3
# {0, 1, 2} 中的每个值都能被取到

# 非满射函数示例：f(x) = x^2，定义域和陪域都是 R
# 负数永远不是平方值，所以不是满射

直观理解：继续电影院比喻，如果每个座位都有人坐（没有空座），这就是满射。观众到座位的映射是满射（假设观众数等于座位数）。

双射（Bijective Function）

双射函数同时是单射和满射。陪域中的每个元素恰好有一个原像。

双射也称为"一一对应"映射。

判断方法：检查是否同时满足单射和满射的条件。

# 双射函数示例：f(x) = 2x，定义域和陪域都是 R
def double(x):
    return 2 * x
# 不同的 x 产生不同的值（单射）
# 任何实数 y 都有原像 y/2（满射）

# 另一个双射示例：将 {0, 1, 2, 3} 映射到 {a, b, c, d}
mapping = {0: 'a', 1: 'b', 2: 'c', 3: 'd'}

直观理解：电影院恰好坐满，每个座位一个人，一个人一个座位。观众到座位的映射是双射。

三种函数类型的关系

双射是最"完美"的函数，它在定义域和陪域之间建立了一一对应关系。

函数的运算

函数的复合

设有两个函数 $f: X \to Y$ 和 $g: Y \to Z$ ，它们的复合函数 $g \circ f: X \to Z$ 定义为：

$(g \circ f)(x) = g(f(x))$

注意：复合的顺序是从右到左读的。先应用 $f$ ，再应用 $g$ 。

def f(x):
    return x + 1

def g(x):
    return x * 2

# 复合函数 g ∘ f
def compose_g_f(x):
    return g(f(x))  # 先 +1，再 *2

# 测试
print(compose_g_f(3))  # (3+1)*2 = 8

# 复合函数 f ∘ g
def compose_f_g(x):
    return f(g(x))  # 先 *2，再 +1

print(compose_f_g(3))  # (3*2)+1 = 7

复合运算满足结合律： $(h \circ g) \circ f = h \circ (g \circ f)$ 。但不满足交换律： $g \circ f$ 和 $f \circ g$ 通常不相等。

恒等函数

集合 $X$ 上的恒等函数 $id_X: X \to X$ 定义为 $id_X(x) = x$ 。

恒等函数在函数复合中扮演类似于数字 1 在乘法中的角色：

$f \circ id_X = f = id_Y \circ f$

反函数

如果函数 $f: X \to Y$ 是双射，则存在反函数 $f^{-1}: Y \to X$ ，满足：

$f^{-1}(f(x)) = x, \quad f(f^{-1}(y)) = y$

只有双射函数才有反函数。单射函数可以定义部分反函数（定义域为原函数的值域）。

# 双射函数及其反函数
def f(x):
    return 2 * x + 3

def f_inverse(y):
    return (y - 3) / 2

# 验证
print(f(f_inverse(7)))    # 7
print(f_inverse(f(5)))    # 5

反函数的性质：

$(f^{-1})^{-1} = f$
$(g \circ f)^{-1} = f^{-1} \circ g^{-1}$

关系的基本概念

关系的定义

关系（Relation）描述集合元素之间的联系。设 $X$ 和 $Y$ 是两个集合，从 $X$ 到 $Y$ 的二元关系 $R$ 是笛卡尔积 $X \times Y$ 的一个子集。

如果 $(x, y) \in R$ ，记作 $xRy$ ，读作" $x$ 与 $y$ 有关系 $R$ "。

当 $X = Y$ 时， $R$ 称为 $X$ 上的二元关系。

# 关系的表示：用有序对的集合
# "小于"关系在 {1, 2, 3} 上
less_than = {(1, 2), (1, 3), (2, 3)}

# 检查关系
print((1, 2) in less_than)  # True
print((2, 1) in less_than)  # False

关系的表示方法

集合表示法：列出所有相关的有序对。如 $R = \{(1, 2), (2, 3), (3, 4)\}$

关系矩阵：用矩阵表示关系。如果 $|X| = m$ ， $|Y| = n$ ，则关系矩阵 $M$ 是 $m \times n$ 矩阵， $M_{ij} = 1$ 当且仅当 $(x_i, y_j) \in R$ 。

例如，设 $X = \{a, b\}$ ， $Y = \{1, 2, 3\}$ ， $R = \{(a, 1), (a, 3), (b, 2)\}$ ：

$M_R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$

关系图：用有向图表示关系。顶点表示元素，有向边表示关系。

关系的性质

设 $R$ 是集合 $X$ 上的二元关系。

自反性（Reflexivity）：对于所有 $x \in X$ ，有 $xRx$ 。

例如，"等于"关系、"整除"关系（在正整数上）都是自反的。"小于"关系不是自反的。

对称性（Symmetry）：如果 $xRy$ ，则 $yRx$ 。

例如，"等于"关系、"同学"关系是对称的。"小于"关系不是对称的。

反对称性（Antisymmetry）：如果 $xRy$ 且 $yRx$ ，则 $x = y$ 。

例如，"小于等于"关系、"子集"关系是反对称的。"同学"关系不是反对称的（两个人可以互为同学但不相等）。

注意：对称性和反对称性不是互斥的。一个关系可以同时满足两者（如"等于"关系），也可以都不满足。

传递性（Transitivity）：如果 $xRy$ 且 $yRz$ ，则 $xRz$ 。

例如，"小于"关系、"祖先"关系是传递的。"同学"关系通常不是传递的。

# 检查关系的性质
def check_reflexive(relation, elements):
    """检查自反性"""
    for x in elements:
        if (x, x) not in relation:
            return False
    return True

def check_symmetric(relation):
    """检查对称性"""
    for (x, y) in relation:
        if (y, x) not in relation:
            return False
    return True

def check_antisymmetric(relation):
    """检查反对称性"""
    for (x, y) in relation:
        if x != y and (y, x) in relation:
            return False
    return True

def check_transitive(relation):
    """检查传递性"""
    for (x, y) in relation:
        for (a, b) in relation:
            if y == a and (x, b) not in relation:
                return False
    return True

关系的运算

逆关系： $R^{-1} = \{(y, x) \mid (x, y) \in R\}$

关系的复合：设 $R \subseteq X \times Y$ ， $S \subseteq Y \times Z$ ，则 $S \circ R = \{(x, z) \mid \exists y \in Y, (x, y) \in R \land (y, z) \in S\}$

# 关系复合
def compose_relations(R, S):
    """计算 S ∘ R"""
    result = set()
    for (x, y) in R:
        for (a, b) in S:
            if y == a:
                result.add((x, b))
    return result

等价关系

等价关系是一类重要的二元关系，它在数学和计算机科学中有着广泛应用。

等价关系的定义

集合 $X$ 上的关系 $R$ 称为等价关系，当且仅当 $R$ 满足：

自反性：对于所有 $x \in X$ ， $xRx$
对称性：如果 $xRy$ ，则 $yRx$
传递性：如果 $xRy$ 且 $yRz$ ，则 $xRz$

等价关系通常用符号 $\sim$ 或 $\equiv$ 表示。

等价关系的例子

等于关系： $=$ 是任何集合上的等价关系。

模 n 同余：在整数集 $\mathbb{Z}$ 上，定义 $a \equiv b \pmod{n}$ 当且仅当 $n | (a - b)$ 。这是等价关系。

验证三个性质：

自反性： $n | (a - a) = 0$ ，成立
对称性：若 $n | (a - b)$ ，则 $n | (b - a)$ ，成立
传递性：若 $n | (a - b)$ 且 $n | (b - c)$ ，则 $n | (a - c)$ ，成立

相似关系：三角形集合上的"相似"关系是等价关系。

同一天生日：人集合上的"同一天生日"关系是等价关系。

等价类

设 $\sim$ 是集合 $X$ 上的等价关系，元素 $x$ 的等价类是所有与 $x$ 等价的元素组成的集合：

$[x] = \{y \in X \mid y \sim x\}$

$x$ 称为等价类的代表元。

等价类的性质：

$x \in [x]$ （自反性保证）
如果 $y \in [x]$ ，则 $[y] = [x]$ （等价类由其中任意元素唯一确定）
如果 $y \notin [x]$ ，则 $[y] \cap [x] = \emptyset$ （不同等价类不相交）

# 模 3 同余的等价类
def mod3_equivalence_class(n):
    """返回 n 所在的等价类"""
    return [x for x in range(10) if x % 3 == n % 3]

print(mod3_equivalence_class(0))  # [0, 3, 6, 9]
print(mod3_equivalence_class(1))  # [1, 4, 7]
print(mod3_equivalence_class(2))  # [2, 5, 8]

商集

集合 $X$ 关于等价关系 $\sim$ 的商集是所有等价类组成的集合，记作 $X/\sim$ ：

$X/\sim = \{[x] \mid x \in X\}$

商集是原集合的一种"压缩"或"折叠"——将等价的元素视为同一个。

例如， $\mathbb{Z}/\equiv_3 = \{[0], [1], [2]\}$ ，其中 $[0] = \{3k \mid k \in \mathbb{Z}\}$ ， $[1] = \{3k+1 \mid k \in \mathbb{Z}\}$ ， $[2] = \{3k+2 \mid k \in \mathbb{Z}\}$ 。

等价关系与分划

等价关系与集合的分划之间存在一一对应关系。

定理：集合 $X$ 上的等价关系确定 $X$ 的一个分划；反之， $X$ 的一个分划确定 $X$ 上的一个等价关系。

这个定理揭示了等价关系的本质：等价关系就是对集合进行分类。每个等价类是一个"类别"，同类元素相互等价，不同类元素不等价。

应用示例：在并查集数据结构中，我们维护一个等价关系，支持动态合并等价类和查询两个元素是否等价。

偏序关系

偏序关系是另一类重要的二元关系，它为集合引入了"顺序"的概念。

偏序关系的定义

集合 $X$ 上的关系 $R$ 称为偏序关系（Partial Order），当且仅当 $R$ 满足：

自反性：对于所有 $x \in X$ ， $xRx$
反对称性：如果 $xRy$ 且 $yRx$ ，则 $x = y$
传递性：如果 $xRy$ 且 $yRz$ ，则 $xRz$

偏序关系通常用符号 $\leq$ 或 $\preceq$ 表示。带有偏序关系的集合 $(X, \leq)$ 称为偏序集（Partially Ordered Set，简称 Poset）。

偏序关系的例子

小于等于：实数集上的 $\leq$ 是偏序关系。

整除关系：正整数集上的"整除"关系 $|$ 是偏序关系。 $a|b$ 表示 $a$ 整除 $b$ 。

验证三个性质：

自反性： $a|a$ ，成立
反对称性：若 $a|b$ 且 $b|a$ ，则 $a = b$ ，成立
传递性：若 $a|b$ 且 $b|c$ ，则 $a|c$ ，成立

包含关系：集合 $A$ 的幂集 $\mathcal{P}(A)$ 上的包含关系 $\subseteq$ 是偏序关系。

字典序：字符串集合上的字典序是偏序关系。

全序与偏序

全序（Total Order）：偏序集 $(X, \leq)$ 是全序集，如果对于任意 $x, y \in X$ ，要么 $x \leq y$ ，要么 $y \leq x$ 。

全序要求任意两个元素都可以比较，而偏序允许存在不可比较的元素对。

例子对比：

实数集上的 $\leq$ 是全序：任意两个实数都可以比较大小
幂集上的 $\subseteq$ 是偏序但不是全序： $\{1, 2\}$ 和 $\{2, 3\}$ 互不包含
整除关系是偏序但不是全序：2 不整除 3，3 也不整除 2

哈斯图

哈斯图是偏序集的图形表示，它省略了由传递性和自反性隐含的边，只保留"覆盖关系"。

在哈斯图中：

较小的元素画在下方
如果 $x < y$ 且不存在 $z$ 使得 $x < z < y$ ，则在 $x$ 和 $y$ 之间画一条边

例如，集合 $\{1, 2, 3\}$ 的幂集按包含关系排序的哈斯图：

特殊元素

在偏序集 $(X, \leq)$ 中：

最大元和最小元：

$a$ 是最大元，如果对所有 $x \in X$ ，都有 $x \leq a$
$a$ 是最小元，如果对所有 $x \in X$ ，都有 $a \leq x$

最大元和最小元如果存在则唯一。

极大元和极小元：

$a$ 是极大元，如果不存在 $x$ 使得 $a < x$
$a$ 是极小元，如果不存在 $x$ 使得 $x < a$

极大元和极小元可能不唯一。

上界和下界：设 $A \subseteq X$ ：

$u$ 是 $A$ 的上界，如果对所有 $a \in A$ ，都有 $a \leq u$
$l$ 是 $A$ 的下界，如果对所有 $a \in A$ ，都有 $l \leq a$

最小上界（上确界）和最大下界（下确界）：

$A$ 的最小上界 $\sup(A)$ 是 $A$ 所有上界中的最小元
$A$ 的最大下界 $\inf(A)$ 是 $A$ 所有下界中的最大元

格

格（Lattice）是一种特殊的偏序集，其中任意两个元素都有最小上界和最大下界。

设 $(L, \leq)$ 是偏序集，如果对于任意 $a, b \in L$ ：

$a$ 和 $b$ 的最小上界存在，记作 $a \vee b$ （称为"join"）
$a$ 和 $b$ 的最大下界存在，记作 $a \wedge b$ （称为"meet"）

则 $(L, \leq)$ 称为格。

例子：

幂集 $\mathcal{P}(S)$ 在包含关系下构成格： $A \vee B = A \cup B$ ， $A \wedge B = A \cap B$
正整数在整除关系下构成格： $a \vee b = \text{lcm}(a, b)$ ， $a \wedge b = \gcd(a, b)$

小结

本章介绍了函数与关系的基础知识：

函数：定义、定义域、陪域、值域；单射、满射、双射；复合与反函数
关系：定义与表示；自反性、对称性、反对称性、传递性
等价关系：定义、等价类、商集、与分划的对应
偏序关系：定义、全序与偏序、哈斯图、特殊元素、格

函数是特殊的关系——每个输入对应唯一输出的关系。等价关系用于分类，偏序关系用于排序，它们在算法设计、数据结构、程序验证等领域都有重要应用。

练习

设 $f: \mathbb{R} \to \mathbb{R}$ ， $f(x) = x^2$ 。判断 $f$ 是否为单射、满射或双射。如果改变陪域为 $\mathbb{R}^+$ （非负实数），结论有何变化？
证明：如果 $f: X \to Y$ 是双射，则 $f$ 有唯一的反函数 $f^{-1}: Y \to X$ 。
设关系 $R = \{(1,1), (1,2), (2,1), (2,2), (3,3)\}$ 在集合 $\{1, 2, 3\}$ 上。判断 $R$ 是否为等价关系。
画出集合 $\{1, 2, 3, 4, 6, 12\}$ 在整除关系下的哈斯图，并找出所有极大元和极小元。
证明：等价关系确定一个分划，分划确定一个等价关系。

函数的基本概念​

函数的定义​

函数的形式化定义​

函数的表示方法​

多元函数​

部分函数与全函数​

函数的类型​

单射（Injective Function）​

满射（Surjective Function）​

双射（Bijective Function）​

三种函数类型的关系​

函数的运算​

函数的复合​

恒等函数​

反函数​

关系的基本概念​

关系的定义​

关系的表示方法​

关系的性质​

关系的运算​

等价关系​

等价关系的定义​

等价关系的例子​

等价类​

商集​

等价关系与分划​

偏序关系​

偏序关系的定义​

偏序关系的例子​

全序与偏序​

哈斯图​

特殊元素​

格​

小结​

练习​