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。

怎么仔细读一个函数

例题

平方函数会有重复输出

考虑 $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$ 和 $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。

解答

为什么这个概念重要

例题

一个简单的等价关系

模 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 是双射时才存在。

常见错误

对称不等于反对称

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

常见错误

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

它可以让同一个输入对应多个输出，也可以让某些输入完全没有输出。

小检查

快速检查

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

先问它是不是 $R \times R$ 的子集，再问每个输入有没有唯一输出。

解答

答案

快速检查

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

分清 preimage 和 inverse function。

解答

答案

快速检查

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

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

解答

答案

为什么这一单元重要

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

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

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

MATH1090：集合论

函数是特殊的关系

函数

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

domain 会受语境影响

怎么仔细读一个函数

平方函数会有重复输出

要记住的图像

像、原像和合成

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

为什么这个区分很重要

单射、满射、双射

三个常用词

逆函数存在当且仅当双射

为什么双射会有逆

单射和非单射的例子

先看什么最有效

不要把原像和逆函数混淆

左逆和右逆

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

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

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

为什么撞车会阻止左逆

关系

关系

关系不一定是函数

为什么关系语言仍然有用

同一个集合上的关系

四个常用性质

整除关系是偏序

为什么这个概念重要

一个简单的等价关系

等价类和商集

等价类

商集

等价类会分割集合

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

常见错误

不要把原像和逆函数混淆

对称不等于反对称

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

小检查

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

答案

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

答案

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

答案

为什么这一单元重要

先备知识

本单元重点词汇

本系列更多笔记

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

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

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