2.2 函数与关系

这一单元是从集合语言走向后面几乎所有主题的桥梁。函数、关系，以及商构造都从同一个想法开始：先看积集，再指定哪些有序对被允许。

重点不只是记住术语，而是要明白每个定义到底在说什么。因为后面的章节会用同一套语言去构造 $N$ 、 $Z$ 、 $Q$ ，以及各种顺序和等价类。

函数是特殊的关系

定义

函数

从 $X$ 到 $Y$ 的函数，是 $X \times Y$ 的一个子集，并且要求 $X$ 中每个 x 都只会对应 $Y$ 中唯一一个 y。

这就是本单元采用的集合论定义。

同一件事可以从几种角度来读：

$X$ 是 domain，即输入集合。
$Y$ 是 target，即可能输出的集合。
graph 是所有有序对 (x, y) 组成的集合。
image 是实际出现过的输出。
preimage 是会落入某个输出集合的输入。

常见错误

函数不能让一个输入对应多个输出

关系可以让一个输入连到多个输出，但函数不可以。每个输入都必须有且只有一个输出。

常见错误

domain 会受语境影响

$1/x$ 不是一个不加限定就完整的函数。它可以是定义在 $R \setminus \{0\}$ 上的函数，或者定义在 $Q \setminus \{0\}$ 上的函数；但无论如何都不能包含 0。

所有函数组成的集合

当函数已经被定义为有序对集合之后，我们也可以建立“以函数为元素”的集合。若 $A$ 和 $B$ 是集合，记号

B^A

表示所有从 $A$ 到 $B$ 的函数组成的集合。

这个记号不是偶然的。若 $A$ 有 n 个元素，而 $B$ 有 m 个元素，一个 $A \to B$ 的函数就是给 $A$ 的每个输入各选一个 $B$ 中的输出。因此共有 $m^n$ 个这样的函数。例如 $A = \{a,b,c\}$ 、 $B=\{0,1\}$ 时， $B^A$ 有 $2^3=8$ 个函数。这正是 $|P(A)| = 2^{|A|}$ 背后的同一个计数原理。

例题

把 $B^A$ 读成函数集合

令 $A=\{a,b\}$ 、 $B=\{0,1\}$ 。那么 $B^A$ 恰有四个函数：

\begin{array}{c|cc} & a & b \\ \hline f_1 & 0 & 0\\ f_2 & 0 & 1\\ f_3 & 1 & 0\\ f_4 & 1 & 1 \end{array}

每一行是一整个函数，而不是某一个函数的一个值。

怎么仔细读一个函数

例题

平方函数会有重复输出

考虑 $f(x) = x^2$ 。

那么 $f(-2) = 4$ 和 $f(2) = 4$ ，也就是说不同输入可以有相同输出。这是允许的。

不允许的是同一个输入有两个不同输出。

例如，把 $y^2 = x$ 当成从 x 到 y 的规则时， $x = 4$ 会有 $y = 2$ 和 $y = -2$ ，所以它不是函数。

解答

要记住的图像

像、原像和合成

对 $f : X \to Y$ ，image 这个词有三种相关但不同的用法：

f(x) 是单个输入 x 的像。
若 $A \subset X$ ，则 $f(A) = {f(x) \mid x \in A}$ 是集合的像。
f(X) 是整个函数的像，也就是实际出现过的输出。

原像定义为

f^{-1}(B) = \{x \in X \mid f(x) \in B\}.

即使 f 没有逆函数， $f^{-1}(B)$ 也仍然有意义。

合成定义为

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

次序很重要： $g \circ f$ 的意思是“先做 f，再做 g”。

例题

比较 $f(x)=x^2$ 的像与原像

设 $f : R \to R$ 由 $f(x) = x^2$ 定义，而

A = \{-2, -1, 0, 1, 2\}, \qquad B = \{0, 1, 4\}.

那么

f(A) = \{0, 1, 4\}.

而且

f^{-1}(B) = \{-2, -1, 0, 1, 2\},

因为 $A$ 里的每个元素都会落入 $B$ 。

如果改成 $C = \{4\}$ ，就有

f^{-1}(C) = \{-2, 2\}.

解答

为什么这个区分很重要

单射、满射、双射

定义

三个常用词

单射：不同输入不会撞车。
满射：目标集合每个值都会被取到。
双射：同时单射和满射。

等价说法也很有用：

f 单射 iff $f(x1) = f(x2)$ 蕴含 $x1 = x2$
f 满射 iff $f(X) = Y$
f 双射 iff 每个目标值都刚好被取到一次

这里之所以经常使用这些词，是因为它们直接决定逆函数是否存在。

定理

逆函数存在当且仅当双射

对函数 $f : X \to Y$ ，逆函数存在，当且仅当 f 是双射。

证明

为什么双射会有逆

例题

单射和非单射的例子

$n \mapsto n + 1$ （定义在 $Z$ 上）既单射又满射，所以是双射。

$x \mapsto x^2$ （定义在 $R$ 上）不是单射，因为 1 和 $-1$ 有同一个像。

$x \mapsto e^x$ （定义在 $R$ 上）是单射，但不是满射到 $R$ ，因为它打不到非正数。

解答

先看什么最有效

常见错误

不要把原像和逆函数混淆

$f^{-1}(B)$ 永远有意义，只要 $B$ 是 target 的子集。真正的逆函数 $f^{-1}$ 只有在 f 是双射时才存在。

左逆和右逆

这里有一个很有用的区分。

左逆 h 表示 $h \circ f = id$
右逆 g 表示 $f \circ g = id$

一般情况下，这两个条件并不一样。

例题

一个有左逆但没有右逆的映射

设 $X = {a, b, c}$ ， $Y = {α, β, γ, δ}$ 。定义

f_1(a)=α,\qquad f_1(b)=β,\qquad f_1(c)=γ.

这个映射是单射但不是满射，因为 δ 没有被取到。所以它可以有左逆，但不可以有右逆。

例如定义 $h : Y \to X$ ：

h(α)=a,\qquad h(β)=b,\qquad h(γ)=c,\qquad h(δ)=a.

那么 $h \circ f_1 = id_X$ 。

解答

为什么缺少输出会阻止右逆

例题

一个有右逆但没有左逆的映射

定义 $f_2 : Y \to X$ 如下：

f_2(α)=a,\qquad f_2(β)=a,\qquad f_2(γ)=b,\qquad f_2(δ)=c.

这个映射是满射但不是单射，所以可以有右逆但没有左逆。

一个右逆是 $g : X \to Y$ ，令

g(a)=α,\qquad g(b)=γ,\qquad g(c)=δ.

那么 $f_2 \circ g = id_X$ 。

解答

为什么撞车会阻止左逆

定理

有限自映射：有左逆已足以推出可逆

设 $X$ 是有限集合，且 $g : X \to X$ 。如果存在 $h : X \to X$ 满足 $h \circ g = id_X$ ，那么 g 是双射，而且 h 也是 g 的右逆。

证明

证明思路

基数和运算语言

基数表示大小，但在集合论中，正确的大小比较不一定只是普通计数。两个集合 $X$ 和 $Y$ 等势，意思是它们之间存在一个双射：

|X| = |Y| \quad \text{表示存在一个双射 } X \to Y.

对有限集合而言，这和元素个数一致。对无限集合而言，这个定义会变得更微妙，后面会再次使用。

例题

$N$ 与 $Z$ 之间的第一个双射

可以用自然数指标按以下顺序列出所有整数：

0, 1, -1, 2, -2, 3, -3, \ldots

这对应到一个函数 $f : N \to Z$ ，例如

f(0)=0,\qquad f(2k+1)=k+1,\qquad f(2k+2)=-(k+1).

每个整数都恰好出现一次，所以这是一个双射枚举。

例题

从 $N \times N$ 到 $N$ 的一个单射

练习会问：能否把一个自然数有序对编码成一个自然数？一个干净答案是

F(m,n)=2^m3^n.

这确实定义了一个函数 $F : N \times N \to N$ ，因为对每个 (m,n)， $2^m3^n$ 都是自然数。

要证明 $F$ 是单射，假设

F(m,n)=F(m',n').

也就是

2^m3^n = 2^{m'}3^{n'}.

唯一素因数分解说明，一个正整数分解成素数幂的方式只有一种。因此两边的 2 的指数必须相同，3 的指数也必须相同：

m=m', \qquad n=n'.

所以两个不同有序对不可能被送到同一个自然数。

定义

把运算读成函数

集合 $S$ 上的一个 n 元运算，是一个函数

S^n \to S.

例如加法是二元运算，因为它取一对输入，并返回同一个集合中的一个输出。

0 元运算初看可能有些奇怪。它是没有输入位置、但有一个 $S$ 中输出的函数，所以可以理解为在 $S$ 中指定一个特殊元素。

关系

定义

关系

$X$ 和 $Y$ 之间的关系，是 $X \times Y$ 的任何子集。

如果 $X = Y$ ，我们就直接叫它 $X$ 上的关系。

写 xRy 就是说 $(x, y) \in R$ 。

关系比函数更一般。函数只是带着“每个输入恰好一个输出”这条附加规则的特殊关系。

对于 $R \subset X \times Y$ ：

domain 是和至少一个 y 有关系的 x
image / range 是被至少一个 x 命中的 y

例题

关系不一定是函数

设 $X$ 是国家集合， $Y$ 是城市集合。

“y 是 x 的首都” 是 $X \times Y$ 上的关系。它是不是函数，要看时代和国家。

$y^2 = x$ （定义在 $Z \times Z$ 上）也是关系，但如果把它当成从 x 到 y 的规则，就不是函数，因为一个输入可能有多个输出。

解答

为什么关系语言仍然有用

同一个集合上的关系

$X \times X$ 上的关系尤其重要。

定理

四个常用性质

一个 $X$ 上的关系可以有以下性质：

Reflexive：每个 x 都有 xRx
Symmetric：xRy 蕴含 yRx
Antisymmetric：如果 xRy 且 yRx，那就要 $x = y$
Transitive：如果 xRy 且 yRz，那就要 xRz

两种特别重要的关系是：

partial order：reflexive + antisymmetric + transitive
equivalence relation：reflexive + symmetric + transitive

symmetric 和 antisymmetric 很容易混淆，但它们意思完全不同：

symmetric：看到单向箭头就要两边都有
antisymmetric：如果两边都有，那两个元素必须相等

例题

整除关系是偏序

在正整数上写 $a \mid b$ 表示 a 整除 b。

这个关系是 reflexive，因为每个数都整除自己。它是 antisymmetric，因为如果 $a \mid b$ 且 $b \mid a$ ，在正整数里就有 $a = b$ 。它也是 transitive，因为整除可以沿链传递。

所以整除是 partial order。

解答

为什么这个概念重要

例题

子集关系作为一个小型偏序

令 $X=\{a,b\}$ ，并考虑 P(X)，也就是 $X$ 的所有子集组成的集合。用包含关系排列 P(X)。

最底层元素是 $\varnothing$ ，最顶层元素是 \{a,b\}，中间两个元素是 \{a\} 和 \{b\}。直接相邻的 covering relations 只有

\varnothing \subset \{a\},\quad \varnothing \subset \{b\},\quad \{a\}\subset \{a,b\},\quad \{b\}\subset \{a,b\}.

Hasse 图只画这些直接覆盖关系；更长的比较则由传递性自动理解。

例题

一个简单的等价关系

模 m 同余是 $Z$ 上的等价关系。

意思是两个整数如果有相同余数，就属于同一个 class。

例如模 3，整数可以分成三类：

余 0
余 1
余 2

这些 classes 会分割整个集合。

等价类和商集

定义

等价类

设 $R$ 是 $X$ 上的等价关系。对 $x \in X$ ， x 的等价类定义为

[x]_R = \{y \in X \mid yRx\}.

定义

商集

如果 $\sim$ 是 $X$ 上的等价关系，那么所有等价类组成的集合记作 $X / \sim$ 。

等价类就是 quotient construction 的核心。与其逐个追踪代表元，不如直接把所有等价代表包成一个对象。

定理

等价类会分割集合

如果 $R$ 是 $X$ 上的等价关系，那么等价类会覆盖整个集合，而且任意两个等价类只会相等或者互不相交。

证明

为什么等价类不会部分重叠

这就是后面用等价类构造整数和有理数的原因。

常见错误

不要把原像和逆函数混淆

$f^{-1}(B)$ 永远有意义，只要 $B$ 是 target 的子集。真正的逆函数 $f^{-1}$ 只有在 f 是双射时才存在。

常见错误

对称不等于反对称

$≤$ 是反对称但不是对称。等号既对称又反对称，而整除是反对称但不是对称。

常见错误

回想会把集合分成 class 的那种关系。

解答

答案

为什么这一单元重要

后面的章节会不停用到这些概念：

$N$ 会通过集合语言和 induction 构造
$Z$ 和 $Q$ 会通过等价类构造
数字上的 $≤$ 是 partial order
quotient set 解释了为什么同一个对象可以有很多代表元

如果这一单元清楚，后面的构造会容易很多，因为符号不再在暗中做事。

2.2 函数与关系

MATH1090：集合论

函数是特殊的关系

函数

函数不能让一个输入对应多个输出

domain 会受语境影响

所有函数组成的集合

把 BAB^ABA 读成函数集合

怎么仔细读一个函数

平方函数会有重复输出

要记住的图像

像、原像和合成

比较 f(x)=x2f(x)=x^2f(x)=x2 的像与原像

为什么这个区分很重要

单射、满射、双射

三个常用词

逆函数存在当且仅当双射

为什么双射会有逆

单射和非单射的例子

先看什么最有效

不要把原像和逆函数混淆

左逆和右逆

一个有左逆但没有右逆的映射

为什么缺少输出会阻止右逆

一个有右逆但没有左逆的映射

为什么撞车会阻止左逆

有限自映射：有左逆已足以推出可逆

证明思路

基数和运算语言

NNN 与 ZZZ 之间的第一个双射

从 N×NN \times NN×N 到 NNN 的一个单射

把运算读成函数

关系

关系

关系不一定是函数

为什么关系语言仍然有用

同一个集合上的关系

四个常用性质

整除关系是偏序

为什么这个概念重要

子集关系作为一个小型偏序

一个简单的等价关系

等价类和商集

等价类

商集

等价类会分割集合

为什么等价类不会部分重叠

常见错误

不要把原像和逆函数混淆

对称不等于反对称

关系做不成函数有两种方式

小检查

x≤yx ≤ yx≤y 在实数上是关系吗？是函数吗？

答案

f−1(B)f^{-1}(B)f−1(B) 在 f 不是双射时还有意义吗？

答案

如果 AAA 有三个元素，而 BBB 有两个元素，BAB^ABA 中有多少个函数？

答案

若 g:X→Xg : X \to Xg:X→X 有左逆且 XXX 是有限集合，证明 g 可逆时第一步应证明 g 有什么性质？

答案

为什么 F(m,n)=2m3nF(m,n)=2^m3^nF(m,n)=2m3n 定义了从 N×NN \times NN×N 到 NNN 的单射？

答案

如果一个关系是 reflexive、symmetric、transitive，它叫什么？

答案

为什么这一单元重要

本节掌握 checkpoint

先备知识

本单元重点词汇

Premium learning add-ons

本系列更多笔记

把 $B^A$ 读成函数集合

比较 $f(x)=x^2$ 的像与原像

$N$ 与 $Z$ 之间的第一个双射

从 $N \times N$ 到 $N$ 的一个单射

$x ≤ y$ 在实数上是关系吗？是函数吗？

$f^{-1}(B)$ 在 `f` 不是双射时还有意义吗？

如果 $A$ 有三个元素，而 $B$ 有两个元素， $B^A$ 中有多少个函数？

若 $g : X \to X$ 有左逆且 $X$ 是有限集合，证明 `g` 可逆时第一步应证明 `g` 有什么性质？

为什么 $F(m,n)=2^m3^n$ 定义了从 $N \times N$ 到 $N$ 的单射？