数学证明/函数

介绍

在上一章中，我们讨论了关系的概念。对关系并没有太多限制。例如，对于从集合$A$到集合$B$的关系，$A$中的每个元素都可以与$B$中的0个、1个或多个元素相关联。在本章中，我们将重点关注从集合$A$到集合$B$的一种特殊类型的关系，其中每个$A$中的元素都与$B$中的唯一一个元素相关联。

你之前应该遇到过函数的概念，例如，由$f(x)=x^{2}$定义的函数，它为你提供了每个给定$x$值的$f(x)$值。你遇到的函数很可能以上述形式出现，即方程的形式。此外，$x$和$f(x)$很可能是实数。

但我们可以将这些想法推广到更一般的情况，其中$x$和$f(x)$不一定是实数（例如，它们可以是某些集合的元素），并且函数不需要像上面那样用公式表示。因此，这里讨论的函数的概念和定义可能对你来说很陌生，并且看起来与你以前学到的函数大不相同。

定义

定义. (函数) 令 $A$ 和 $B$ 是集合。从集合 $A$ 到集合 $B$ 的一个 函数 或 映射，记为 $f:A\to B$，是一个从集合 $A$ 到集合 $B$ 的 关系，使得对于 每个 元素 $a\in A$，都 存在 一个 唯一 的 $b\in B$ 使得 $(a,b)\in f$.

备注.

• 记号 "$(a,b)\in f$" 在一开始可能看起来很奇怪。但是，当我们思考 $f$ 在这里代表什么时，它就变得更自然了：因为 $f$ 是从集合 $A$ 到集合 $B$ 的关系，它确实是 $A\times B$ 的一个子集。因此，说 $(a,b)$ 是 $f$ 的一个元素是合理的。

• 然而，更常见的是写 $f(a)=b$ 而不是 (你应该在之前见过这个记号)。

• 由于 $f$ 是一个 关系，我们可以将术语应用于函数：集合 $A$ 是函数 $f$ 的 定义域，记为 $\operatorname {dom} f$。
• 对于函数，我们还有一些其他的术语：集合 $B$ 被称为 $f$ 的 值域，$b=f(a)$ 是 $a$ 在 $f$ 下的像。同时，$a$ 被称为 $b$ 在 $f$ 下的原像。此外，我们说 $f$ 将 $a$ 映射到 $b$。

• 根据定义，每个元素 $a\in A$ 都有一个 唯一（或恰好一个）像。

• 当集合 $A$ 为空时，从集合 $A$ 到 $B$ 的唯一函数（也是唯一关系）为空集。当集合 $A$ 非空而集合 $B$ 为空时，由于从集合 $A$ 到 $B$ 的唯一关系也是空集，但这种关系不满足成为函数的要求（不存在 $b\in B$ 使得 $(a,b)\in f$ 对所有 $a\in A$ 都成立）。

练习。 写出“$f$ 不是从 $A$ 到 $B$ 的函数”的含义，即上述定义的否定。（提示：首先将唯一的 ∃ 量词分解为存在部分和唯一部分。）

解答

首先，我们使用逻辑符号来表达“$f$ 是从 $A$ 到 $B$ 的函数”的含义：$${\big (}\forall a\in A,\exists b\in B,f(a)=b{\big )}{\text{ and }}{\big (}\forall a\in A,\forall b,c\in B,{\text{if }}f(a)=b{\text{ and }}f(a)=c,{\text{ then }}b=c{\big )}.$$ 然后，“$f$ 不是从 $A$ 到 $B$ 的函数”的含义是：$${\big (}\exists a\in A,\forall b\in B,f(a)\neq b{\big )}{\text{ or }}{\big (}\exists a\in A,\exists b,c\in B,f(a)=b{\text{ and }}f(a)=c{\text{ and }}b\neq c{\big )}.$$ （LHS 表示存在性要求被违反，RHS 表示唯一性要求被违反。）换句话说，这意味着“存在某个 $a\in A$ 没有对应图像，或者存在某个 $a\in A$ 对应多个图像”。

示例. 令 $A=\{1,2,3\}$ 且 $B=\{a,b\}$。那么，$$f=\{(1,a),(2,a),(3,b)\}$$ 定义了一个函数。图形上，它看起来像

  A               B
*----*          *----*
|1*  #
|    |  #       |    |
|    |       #  |    |
|    |          |#   |
|2* # # # # # #  # *a|
|    |          |    |
|3* # # # # # #  # *b|
|    |          |    |
*----*          *----*

这里，$a$ 是 1 和 2 在 $f$ 下的像。换句话说，1 和 2 是 $a$ 在 $f$ 下的原像。类似地，$b$ 是 3 在 $f$ 下的像，而 3 是 $b$ 在 $f$ 下的原像。

示例。 令 $A=\{a,b,c,d\}$ 且 $B=\{1,2,3,4,5,6\}$。那么，$f=\{(a,1),(a,2),(b,3),(c,4),(d,5)\}$ 不是从 $A$ 到 $B$ 的函数，因为 $a$ 有两个像：1 和 2。同样，$f=\{(a,1),(b,3)\}$ 也不是从 $A$ 到 $B$ 的函数，因为 $c$ 和 $d$ 没有像。

示例。 通常我们会称 "$f(x)=x^{2}$" 为 "函数"。但严格意义上来说，当我们观察函数的定义时，这种说法实际上存在一些问题。

1. 定义域和陪域是什么呢？
2. $f(x)$ 仅仅是实数 $x$ 在 $f$ 下的像。函数 $f$ 本身应该是一个集合。

对于第一个问题，通常域和陪域被视为$\mathbb {R}$。但对于某些函数，$f(x)$ 对于某些实数 $x$ 的值变得无定义。在这种情况下，通常将域设置为 $\{x:f(x){\text{ is a real number}}\}$，被称为自然域。

对于第二个问题，实际函数 $f$ 确实是 集合 $$f=\{(x,x^{2}):x\in \mathbb {R} \}.$$。这个平面上的点集是 $f$ 的图像（抛物线）。但是，为了方便起见，这种说法是可以接受的。

练习。 一个常见的函数是指数函数，它被定义为 $g(x)=e^{x}$。另一个是自然对数函数，定义为 $h(x)=\ln x$。

(a) 找出函数 $g$ 和 $h$ 的域和陪域。

(b) 用集合表示函数 $g$ 和 $h$。

解答

(a) $g$ 的定义域和值域都是 $\mathbb {R}$。 $h$ 的定义域是 $(0,\infty )$（当 $x$ 小于或等于零时，$\ln x$ 是未定义的），$h$ 的值域是 $\mathbb {R}$。

(b) $g=\{(x,e^{x}):x\in \mathbb {R} \}$ 和 $h=\{(x,\ln x):x\in (0,\infty )\}$。

我们应该意识到函数的值域不一定与函数的值域相同。以下是函数 值域 的定义（与关系的定义相同）。

定义。 （函数的值域）函数 $f$ 的 值域，表示为 $\operatorname {ran} f$，是 $$\operatorname {ran} f=\{b\in B:b=f(x){\text{ for some }}x\in A\}=\{f(x):x\in A\}\subseteq B.$$

备注.

• 比较值域和值域的定义，我们可以注意到，对于值域，它包含值域中所有具有 至少一个 原像的元素。另一方面，值域是包含所有元素的集合，所有元素 $a\in A$ 都可能被映射到。
• 当函数 $f$ 的值域和值域最终相同，我们称这样的函数 $f$ 为 满射。稍后我们将讨论函数的更多属性。

• 我们可以观察到，实际上我们可以手动设置（或限制）函数的值域为其值域。因此，即使给定函数不是满射，我们也可以通过手动更改其值域使其成为满射。

示例。 令 $A=\{1,2\}$ 和 $B=\{3,4,5\}$。定义函数 $f$ 为 $$f=\{(1,3),(2,4)\}.$$ 那么，$\operatorname {ran} f=\{3,4\}.$

练习。 令 $A$ 和 $B$ 为集合，$b$ 为 $B$ 的一个固定元素。那么，函数 $f:A\to B$ 由 $f(a)=b$ 对所有 $a\in A$ 定义，称为从 $A$ 到 $B$ 的 常数函数。

(a) 常数函数的值域是什么？

(b) 常数函数的陪域是什么？

(c) 常数函数的值域能等于它的陪域吗？

(d) $b$ 的原像是什么？

解答

(a) 值域是 $\{b\}$。

(b) 陪域是集合 $B$。

(c) 是的，如果 $B=\{b\}$。

(d) $b$ 的原像是 $A$ 中的所有元素。

示例。 （恒等函数）设 $A$ 为一个集合。那么函数 $id_{A}$ 由 $id_{A}(a)=a$ 对所有 $a\in A$ 定义，被称为 恒等函数 of $A$。每一个 $a\in A$ 都是它自身的像。定义域、陪域和值域 of $id_{A}$ 都是 $A$。

备注.

• 此函数在关于 反函数 的部分中非常重要。

示例。 考虑函数 $f:\mathbb {R} \to \mathbb {R}$ 由 $f(x)=e^{x}$ 定义。求函数 $f$ 的值域， $\operatorname {ran} f$，并证明你的答案。

函数 $f$ 的值域是 $\operatorname {ran} f=(0,\infty )$。

证明。 为了证明 $\operatorname {ran} f=(0,\infty )$，我们将证明 (i) $\operatorname {ran} f\subseteq [0,\infty )$； (ii) $[0,\infty )\subseteq \operatorname {ran} f$。

首先，对于 $\operatorname {ran} f\subseteq (0,\infty )$：对于每个 $y$，$${\begin{aligned}y\in \operatorname {ran} f&\implies y=e^{x}{\text{ for some }}x\in \mathbb {R} \\&\implies y>0&({\text{we do not have the reverse implication for this step}})\\&\implies y\in (0,\infty ).\end{aligned}}$$ 另一方面，对于 $(0,\infty )\subseteq \operatorname {ran} f$：对于每个 $y\in (0,\infty )$，我们选择 $x=\ln y\in \mathbb {R}$。然后，$f(x)=e^{x}=e^{\ln y}=y$。所以，根据定义，我们有 $y\in \operatorname {ran} f$。

$\Box$

练习。 考虑函数 $f:\mathbb {R} \to \mathbb {R}$，定义为 $f(x)=x^{2}$。求 $\operatorname {ran} f$，并证明你的答案。

解答

我们有 $\operatorname {ran} f=[0,\infty )$。

证明。 首先，对于每个 $y$，$${\begin{aligned}y\in \operatorname {ran} f&\implies y=x^{2}{\text{ for some }}x\in \mathbb {R} \\&\implies y\geq 0\\&\implies y\in [0,\infty ).\end{aligned}}$$ 这表明 $\operatorname {ran} f\subseteq [0,\infty )$。

另一方面，对于每个 $y\in [0,\infty )$，我们选择 $x={\sqrt {y}}\in \mathbb {R}$。 然后，$f(x)=x^{2}=\left({\sqrt {y}}\right)^{2}=y$ 。所以，我们有 $y\in \operatorname {ran} f$。 这表明 $[0,\infty )\subseteq \operatorname {ran} f$，我们就完成了。

$\Box$

由于定义域和值域，以及映射的“方式”，都影响着函数的“行为”和性质，因此将所有这些特征纳入函数的相等定义是自然的。

定义。 （函数相等） 令 $A$ 和 $B$ 是集合，并且令 $f:A\to B$ 和 $g:A\to B$ 是从 $A$ 到 $B$ 的两个函数（注意它们的定义域和值域必须相同）。 那么，函数 $f$ 和 $g$ 被称为相等，记为 $f=g$，如果对于每个 $a\in A$，$f(a)=g(a)$。

练习。 写下两个函数 $f$ 和 $g$ 不相等的含义。

解答

($f$ 和 $g$ 具有不同的定义域) 或 ($f$ 和 $g$ 具有不同的陪域) 或 (存在 $a\in A$ 使得 $f(a)\neq g(a)$ )。

例。 考虑函数 $f:\mathbb {R} \to \mathbb {R}$ 和 $g:\mathbb {R} \to (0,\infty )$，它们由 $f(x)=e^{x}$ 和 $g(x)=e^{x}$ 定义。尽管它们的“公式”相同，但它们并不相等，因为它们的陪域不同。

练习。 考虑函数 $f$ 和 $g$，它们由 $f(x)=x$ 和 $g(x)={\frac {x^{2}}{x}}$ 定义。函数 $f$ 和 $g$ 相等吗？为什么？

解答

不。

请注意 $g(x)$ 当 $x=0$ 时未定义（但在其他所有实数 $x$ 上都定义），而 $f(x)$ 对所有实数 $x$ 都定义。因此，$f$ 的定义域为 $\mathbb {R}$，$g$ 的定义域为 $\mathbb {R} \setminus \{0\}$。因此，$f$ 和 $g$ 不 相等。

单射、满射和双射函数

在本节中，我们将讨论函数可能具有的某些重要性质，即单射性、满射性和双射性。

定义。（单射函数）函数 $f:A\to B$ 是 单射 或 一一对应 的，如果对于每个 $x,y\in A$，$f(x)=f(y)\implies x=y$，或等效地（逆否命题），对于每个 $x,y\in A$，$x\neq y\implies f(x)\neq f(y)$。

备注.

• 定义告诉我们，从 $A$ 到 $B$ 的单射函数将 不同 的 $A$ 元素映射到 不同 的 $B$ 元素。
• 为了证明一个函数是单射的，通常使用直接证明：对于每一个 $x,y\in A$，假设 $f(x)=f(y)$，然后继续证明 $x=y$。

练习。 写下 “函数 $f:A\to B$ 不是 单射的” 的含义。

解答

存在 $x,y\in A$ 使得 $f(x)=f(y)$ 且 $x\neq y$。

示例。 函数 $f:\mathbb {R} \to \mathbb {R}$ 定义为 $f(x)=2x+5$。证明 $f$ 是单射的。

证明。 对于每一个 $x,y\in \mathbb {R}$，$$f(x)=f(y)\implies 2x+5=2y+5\implies 2x=2y\implies x=y.$$ 因此，$f$ 是单射的。

$\Box$

示例. 函数 $f:\mathbb {R} \to \mathbb {R}$ 由 $f(x)=x^{2}$ 定义。证明或反驳 $f$ 是单射的。

反驳. 由于 $f(-1)=f(1)=1$, $f$ 不是单射的。

$\Box$

练习. 函数 $g:[0,\infty )\to \mathbb {R}$ 由 $g(x)=x^{2}$ 定义。 证明 $g$ 是单射的。

证明

证明. 对于所有 $x,y\in [0,\infty )$, $$g(x)=g(y)\implies x^{2}=y^{2}\implies {\sqrt {x^{2}}}={\sqrt {y^{2}}}\implies |x|=|y|\implies x=y.$$

$\Box$

备注.

• 这表明在判断一个函数是否单射时，函数的定义域很重要。我们不应该只关注函数的公式。

示例. 函数 $f:\mathbb {R} \to \mathbb {R}$ 由 $f(x)=x^{2}-3x+5$ 定义。证明或反驳 $f$ 是单射的。

这次，并不立即清楚这个函数是否是一对一的。所以，我们首先可以尝试证明$f$是一对一的，看看会得到什么：对于每一个$x,y\in \mathbb {R}$，$$f(x)=f(y)\implies x^{2}-3x+5=y^{2}-3y+5\implies x(x-3)=y(y-3).$$ 注意，为了使最后一个等式推导出$x=y$，我们需要$x\neq 3$ 以及 $y\neq 3$。然而，$x$ 和 $y$ 可以取任何实数值。因此，这提示我们考虑 $f(3)$ 并 反驳 $f$ 是一对一的。另一个观察是，当 $x=3$ 时，$x(x-3)=0$。但是为了使它等于零，我们也可以取 $x=0$。因此，这给了我们一个反例来反驳$f$是一对一的。

反驳。 由于 $f(0)=f(3)=5$，$f$ 不是一对一的。

$\Box$

练习. 定义函数 $f:[-1,1]\to [0,1]$ 为 $f(x)={\sqrt {1-x^{2}}}$。证明或反驳 $f$ 是单射。

解答

反证. 由于 $f(-1)=f(1)=0$，$f$ 不是单射。

$\Box$

备注.

• 该函数的图像是一个位于 $x$ 轴上方的半圆。

定义. (满射函数) 函数 $f:A\to B$ 是 满射 或 映上 的，如果对于每一个 $y\in B$，存在 $x\in A$ 使得 $f(x)=y$。

备注.

• 定义告诉我们，$f$ 是满射的，如果 所有 陪域 $B$ 中的元素都是 $A$ 中 某些 元素的像。换句话说，$\operatorname {ran} f=B$。

练习. 写下 "$f:A\to B$ 是 非 满射的" 的含义。

解答

存在 $y\in B$ 使得对于每一个 $x\in A$，$f(x)\neq y$。

换句话说，某些 余域元素 $B$ 不是 $A$ 的每个元素的像。换句话说，$\operatorname {ran} f\neq B$（由于$\operatorname {ran} f\subseteq B$ 由定义，我们也可以写成$\operatorname {ran} f\subset B$）。

例子。 函数 $f:\mathbb {R} \to \mathbb {R}$ 被定义为$f(x)=2x+5$。证明 $f$ 是满射。

为了证明 $f$ 是满射的，我们需要证明对于任意的 $y\in \mathbb {R}$，都存在一个 $x\in \mathbb {R}$ 使得 $f(x)=y$，也就是说 $y=2x+5$。为了证明这一点，我们可以看到对于不同的 $y$ 值，满足要求的 $x\in \mathbb {R}$ 的选择是不同的。事实上，$x$ 的选择取决于 $y\in \mathbb {R}$ 的值。但对于给定的 $y\in \mathbb {R}$ 值，选择这样的 $x\in \mathbb {R}$并不难：我们可以简单地将上面的方程重新排列，使 $x$ 成为方程的解：$$x={\frac {y-5}{2}}\in \mathbb {R}$$

证明：对于任意的 $y\in \mathbb {R}$，选择 $x={\frac {y-5}{2}}\in \mathbb {R}$。那么，$$f(x)=f\left({\frac {y-5}{2}}\right)=2\left({\frac {y-5}{2}}\right)+5=y-5+5=y.$$

$\Box$

例： 证明或反驳由 $f(x)=x^{2}$ 定义的函数 $f:\mathbb {R} \to \mathbb {R}$ 是满射的。

反证法。 取 $y=-1$. 那么，不存在 $x\in \mathbb {R}$ 使得 $$x^{2}=f(x)=-1$$ 因为 $x^{2}=-1$ 没有实数解。 因此，$f$ 不是满射。

$\Box$

练习。 证明 函数 $g:\mathbb {R} \to [0,\infty )$ 由 $g(x)=x^{2}$ 定义是满射。

证明

证明。 对于每一个 $y\in [0,\infty )$， 选择 $x={\sqrt {y}}\in \mathbb {R}$（可以选择这样的 实数 $x$ 因为 $y\in [0,\infty )$）。 那么， $$f(x)=f\left({\sqrt {y}}\right)=\left({\sqrt {y}}\right)^{2}=y$$

$\Box$

备注.

• 这表明函数的 陪域 在确定函数是否为满射时很重要。 所以，我们应该 不 只看函数的公式。

定义。（双射函数）一个函数 $f:A\to B$ 是 双射 或 一一对应 如果它既是单射又是满射。

备注.

• 我们应该意识到 "一一对应"（即双射）与 "一对一"（即单射）不同。
• 换句话说，$f$ 是双射的，如果对于每一个 $y\in B$，都存在一个 唯一 的 $x\in A$ 使得 $f(x)=y$（存在性对应着满射，唯一性对应着单射）。

• 然而，我们通常仍然通过分别证明单射和满射来证明双射，类似于证明“存在唯一...”时，我们分别证明存在性和唯一性部分。

练习。 写下“$f:A\to B$ 不是 双射 ”的含义。

解答

$f$ 不是单射或 $f$ 不是满射。

例子。 我们已经证明了函数 $f:\mathbb {R} \to \mathbb {R}$ 由 $f(x)=2x+5$ 定义，它既是单射又是满射。因此，它是双射的。

例子。 我们已经证明了函数 $g_{1}:[0,\infty )\to \mathbb {R}$ 由 $g_{1}(x)=x^{2}$ 定义是单射的，函数 $g_{2}:\mathbb {R} \to [0,\infty )$ 由 $g_{2}(x)=x^{2}$ 定义是满射的。然后，使用基本上相同的证明，我们可以证明函数 $g_{3}:[0,\infty \to [0,\infty )$ 由 $g_{3}(x)=x^{2}$ 定义既是单射又是满射，因此是双射的。

例子。 证明函数 $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ 由 $f(x)={\frac {3x+1}{x-1}}$ 定义是双射的。

为了证明满射部分，我们需要将 $x$ 作为方程 $y={\frac {3x+1}{x-1}}$ 的主元：$$y={\frac {3x+1}{x-1}}\iff xy-y=3x+1\iff (y-3)x=y+1\iff x={\frac {y+1}{y-3}}.$$

证明。

单射：对于每个 $x,y\in \mathbb {R} \setminus \{1\}$，$$f(x)=f(y)\implies {\frac {3x+1}{x-1}}={\frac {3y+1}{y-1}}\implies 3x+1=3y+1\implies 3x=3y\implies x=y.$$ 满射：对于每个 $y\in \mathbb {R} \setminus \{3\}$，选择 $x={\frac {y+1}{y-3}}$。然后我们需要证明 $x\in \mathbb {R} \setminus \{1\}$。由于 $x\in \mathbb {R}$ ($y\neq 3$，所以 $x$ 是定义的)，我们只需要证明 $x\neq 1$。我们用反证法来证明

假设与结论相反，$x=1$。那么，${\frac {y+1}{y-3}}=1\implies y+1=y-3\implies 1=-3$。因此我们得到矛盾。

然后，我们有 $$f(x)=f\left({\frac {y+1}{y-3}}\right)={\frac {3\left({\frac {y+1}{y-3}}\right)+1}{{\frac {y+1}{y-3}}-1}}={\frac {3y+3+y-3}{y+1-y+3}}={\frac {4y}{4}}=y.$$

$\Box$

练习。 令 $A$ 为一个集合。证明恒等函数 $id_{A}:A\to A$ 是双射的。

证明

证明。

单射：对于每一个 $x,y\in A$，$id_{A}(x)=id_{A}(y)\implies x=y$.

满射：对于每一个 $y\in A$，选择 $x=y\in A$。然后，$id_{A}(x)=id_{A}(y)=y$.

$\Box$

练习。 一个函数 $f:\mathbb {Z} \times \mathbb {Z} \to \mathbb {Z} \times \mathbb {Z}$ 定义为 $$f(m,n)=(n,m).$$ 证明或反驳 $f$ 是双射的。

解答

证明。

单射：对于每一个 $(m_{1},n_{1}),(m_{2},n_{2})\in \mathbb {Z} \times \mathbb {Z}$，$$f(m_{1},n_{1})=f(m_{2},n_{2})\implies (n_{1},m_{1})=(n_{2},m_{2})\implies n_{1}=n_{2}{\text{ and }}m_{1}=m_{2}\implies (m_{1},n_{1})=(m_{2},n_{2}).$$

满射：对于每个$(x,y)\in \mathbb {Z} \times \mathbb {Z}$，选择$(y,x)\in \mathbb {Z} \times \mathbb {Z}$。那么，$$f(y,x)=(x,y).$$

$\Box$

练习。考虑一个函数$f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$，定义为$f(m,n)=m+n$，以及另一个函数$g:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$，定义为$g(m,n)=mn$.

(a) 证明或反驳$f$是 (i) 单射；(ii) 满射。

(b) 证明或反驳$g$是 (i) 单射；(ii) 满射。

解答

(a) (i)

反证。 由于$f(1,2)=f(2,1)=3$，$f$不是单射。

$\Box$

(ii)

反证。取$y=1$。那么，对于每个$(m,n)\in \mathbb {N} \times \mathbb {N}$，$m+n\neq y=1$.

$\Box$

(b) (i)

反证。 由于$f(1,2)=f(2,1)=2$，$f$不是单射。

$\Box$

(ii)

证明。 对于每个 $y\in \mathbb {N}$，选择 $(m,n)=(1,y)\in \mathbb {N} \times \mathbb {N}$。 那么，$f(m,n)=1(y)=y$.

$\Box$

函数的复合

令 $A,B$ 和 $C$ 是非空集，并令 $f:A\to B$ 和 $g:B\to C$ 是两个函数。 在本节中，我们将讨论一种通过“组合”两个函数 $f$ 和 $g$ 来创建一个新函数的方法，称为它们的 复合

定义。 (复合) 令 $f:A\to B$ 和 $g:B\to C$ 是两个函数，其中 $A,B$ 和 $C$ 是非空集。 那么，$f$ 和 $g$ 的 复合，记为 $g\circ f$（读作“g-circle-f”），是从 $A$ 到 $C$ 的函数，由下式定义： $$(g\circ f)(a)=g(f(a)){\text{ for every }}a\in A.$$

备注.

• 我们可以看到，复合函数 $g\circ f$ 是先应用 $f$，然后再应用 $g$ 得到的。

例子： 令 $A=\{1,2,3\},B=\{a,b,c,d\}$ 以及 $C=\{4,5\}$。考虑函数 $f:A\to B$ 和 $g:B\to C$，它们定义为 $$f=\{(1,a),(2,b),(3,b)\}{\text{ and }}g=\{((a,4),(b,5),(c,5),(d,5)\}.$$ 那么，我们有 $(g\circ f)(1)=4,(g\circ f)(2)=5$ 和 $(g\circ f)(3)=5$。因此，函数 $g\circ f:A\to C$ 由 $$g\circ f=\{(1,4),(2,5),(3,5)\}.$$ 然而，$f\circ g$ 是 未定义的，因为 $g$ 的陪域 ($C$) 与 $f$ 的定义域 ($A$) 不同。

备注.

• 为了使 $g\circ f$ 和 $f\circ g$ 都被定义，我们需要有 $f:A\to B$ 和 $g:B\to A$，也就是说，$f$ 的定义域（陪域）必须等于 $g$ 的陪域（定义域）。
• 在这种情况下，$g\circ f$ 是一个从 $B$ 到 $B$ 的函数，而 $f\circ g$ 是一个从 $A$ 到 $A$ 的函数。因此，为了使它们 可能 相等，我们需要进一步有 $A=B$。

• 但是，即使 $A=B$，仍然有可能 $f\circ g\neq g\circ f$。考虑以下例子。

示例. 令 $A=\{1,2\}$. 考虑函数 $f:A\to A$ 和 $g:A\to A$ 定义为 $$f=\{(1,2),(2,2)\}{\text{ and }}g=\{(1,1),(2,1)\}.$$ 那么，$g\circ f=\{(1,1),(2,1)\}$ 和 $f\circ g=\{(1,2),(2,2)\}$. 由于，例如，$(g\circ f)(1)=1\neq 2=(f\circ g)(1)$，因此 $g\circ f\neq f\circ g$.

备注.

• 这个例子表明函数的复合运算不是 交换的. 也就是说，改变复合运算的顺序后，结果可能不同。

虽然函数的复合运算不是交换的，但它是 结合的.

定理. (函数复合运算的结合性) 对于任何非空集 $A,B,C,D$，以及对于任何函数 $f:A\to B,g:B\to C$ 和 $h:C\to D$，我们有 $$h\circ (g\circ f)=(h\circ g)\circ f.$$

证明。 首先，由于 $g\circ f$ 是从 $A$ 到 $C$ 的函数，所以 $h\circ (g\circ f)$ 是从 $A$ 到 $D$ 的函数。类似地，由于 $h\circ g$ 是从 $B\to D$ 的函数，所以 $(h\circ g)\circ f$ 是从 $A$ 到 $D$ 的函数。

现在，剩下的就是要证明这两个函数将每个元素 $a\in A$ 映射到 $D$ 中的同一个像。对于每个 $a\in A$，$${\big (}h\circ (g\circ f){\big )}(a)=h{\big (}(g\circ f)(a){\big )}=h{\big (}g(f(a)){\big )}.$$ ($g\circ f$ 的括号表示“分组” $g$ 和 $f$ 首先，也就是说，我们首先将 $g\circ f$ 视为一个函数。为了更方便地理解，可以将上面的 $g\circ f$ 写成 $f_{1}$ 。）

同时，$${\big (}(h\circ g)(f(a)){\big )}=h{\big (}g(f(a)){\big )}.$$

$\Box$

示例。 令 $A=\{1,2,3\},B=\{a,b,c,d\},C=\{4,5\}$ 且 $D=\{\alpha ,\beta ,\gamma \}$。考虑函数 $f:A\to B$，$g:B\to C$ 和 $h:C\to D$，其定义如下：$$f=\{(1,a),(2,b),(3,b)\},g=\{((a,4),(b,5),(c,5),(d,5)\}{\text{ and }}h=\{(4,\beta ),(5,\gamma )\}.$$ 回想一下，我们已经证明了 $g\circ f=\{(1,4),(2,5),(3,5)\}$。我们还可以进一步证明 $h\circ g=\{(a,\beta ),(b,\gamma ),(c,\gamma ),(d,\gamma )\}$。因此，$h\circ (g\circ f):A\to D$ 和 $(h\circ g)\circ f:A\to D$ 由以下给出：$$h\circ (g\circ f)=(h\circ g)\circ f=\{(1,\beta ),(2,\gamma ),(3,\gamma )\}.$$

现在，让我们研究一些与合成、单射性、满射性和双射性相关的结果。

命题。 对于任何非空集 $A,B,C$ 以及任意函数 $f:A\to B$ 和 $g:B\to C$,

(a) 如果 $f$ 和 $g$ 是单射，那么 $g\circ f$ 也是单射。

(b) 如果 $f$ 和 $g$ 是满射，那么 $g\circ f$ 也是满射。

证明。 对于 (a)，假设 $f$ 和 $g$ 是单射函数。那么，对于任意 $x,y\in A$ $${\begin{aligned}g\circ f(x)=g\circ f(y)&\implies g(f(x))=g(f(y))\\&\implies f(x)=f(y)&(g{\text{ is injective}})\\&\implies x=y.&(f{\text{ is injective}})\\\end{aligned}}$$ 对于 (b)，假设 $f$ 和 $g$ 是单射函数。那么，对于任意 $c\in C$，由于 $g$ 是满射函数，存在 $b\in B$ 使得 $g(b)=c$。对于 该 $b\in B$，也一定存在 $a\in A$ 使得 $f(a)=b$，因为 $f$ 是满射函数。因此，对于任意 $c\in C$，存在 $a\in A$ 使得 $$c=g(b)=g(f(a))=(g\circ f)(a).$$

$\Box$

推论。 对于每个非空集 $A,B,C$，以及对于每个函数 $f:A\to B$ 和 $g:B\to C$，如果 $f:A\to B$ 和 $g:B\to C$ 是双射的，那么 $g\circ f$ 是双射的。

证明。 假设 $f$ 和 $g$ 是双射的，即它们是单射的 并且 满射的。由上面的命题可知，$g\circ f$ 是单射的 并且 满射的，即它是双射的。

$\Box$

在了解了这些结果后，自然会问上述命题的 逆命题 是否成立。实际上，逆命题不成立，我们有以下结果

命题。 对于任何非空集 $A,B,C$ 以及任意函数 $f:A\to B$ 和 $g:B\to C$,

(a) 如果 $g\circ f$ 是单射的，那么 $f$ 是单射的。

(b) 如果 $g\circ f$ 是满射的，那么 $g$ 是满射的。

证明。 对于 (a)，假设 $g\circ f$ 是单射。那么，对于每个 $x,y\in A$，$${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&({\text{函数定义}})\\&\implies x=y.&(g\circ f{\text{ 是单射}})\\\end{aligned}}$$ 对于 (b)，假设 $g\circ f$ 是满射。那么，对于每个 $c\in C$，存在 $a\in A$ 使得 $g(f(a))=c$。因此，我们现在可以证明 $g$ 是满射：对于每个 $c\in C$，我们可以选择 $f(a)\in B$，然后我们有 $g(f(a))=c$。

$\Box$

备注.

• 由此可知，如果 $g\circ f$ 是双射，那么 $f$ 是单射，而 $g$ 是满射。
• 对于 (a)，在假设下，$f$ 可能或不可能是满射。同样，对于 (b)，$g$ 可能或不可能是单射。

为了总结结果，我们有以下表格

总结

$g\circ f$ (给定)	$f$	$g$
单射	单射	单射/非单射
满射	满射	满射/非满射
双射	单射	满射

练习。 反驳 对于任意非空集合 $A,B,C$ 以及任意函数 $f:A\to B$ 和 $g:B\to C$，

(a) 如果 $g\circ f$ 是单射的，那么 $g$ 是单射的。

(b) 如果 $g\circ f$ 是满射的，那么 $f$ 是满射的。

解答

(a)

反证。 取 $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$，并取函数 $f:A\to B$ 和 $g:B\to C$，它们定义如下：$f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$。

那么，函数 $g\circ f:A\to C$ 由 $g\circ f=\{(1,1),(2,2)\}$ 给出，它是单射的，因为对于任意 $x,y\in A$，$(g\circ f)(x)=(g\circ f)(y)\implies x=y$。但是，函数 $g$ 不是单射的，因为 $g(1)=g(3)=1$。

$\Box$

(b)

反证。 取 $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$，并取函数 $f:A\to B$ 和 $g:B\to C$，它们定义如下：$f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$。

然后，函数 $g\circ f:A\to C$ 由 $g\circ f=\{(1,1),(2,2)\}$ 给出，这是满射，因为对于每个 $c\in C$，都存在 $a\in A$ 使得 $(g\circ f)(a)=c$。然而，函数 $f$ 不是满射，例如，取 $c=3$。那么，对于每个 $a\in A$，$f(a)\neq c=3$.

$\Box$

示例。 考虑两个任意函数 $f:\mathbb {R} \to \mathbb {R}$ 和 $g:\mathbb {R} \to \mathbb {R}$，使得函数 $g\circ f:\mathbb {R} \to \mathbb {R}$ 由 $$g\circ f(x)=x^{3}.$$ 给出。函数 $f$ 和 $g$ 具有哪些性质？

解。首先，我们断言 $g\circ f$ 是双射的。

证明。

单射：对于每个 $x,y\in \mathbb {R}$，$(g\circ f)(x)=(g\circ f)(y)=x^{3}=y^{3}\implies x=y$.

满射: 对于每个 $y\in \mathbb {R}$，选择 $x=y^{1/3}\in \mathbb {R}$。那么，$(g\circ f)(x)=(y^{1/3})^{3}=y$.

$\Box$

然后，我们可以得出结论，$f$ 是单射的，而 $g$ 是满射的，根据上述命题。

练习。 考虑函数 $f:\mathbb {R} \to \mathbb {R}$ 满足 $(f\circ f)(x)=x$ 对于每个 $x\in \mathbb {R}$。证明或反驳 $f$ 是 (i) 单射的；(ii) 满射的。

解答

(i) 和 (ii)

证明。 首先，注意到 $f\circ f=id_{\mathbb {R} }$，我们已经证明了 $id_{\mathbb {R} }$ 是双射的。所以，根据上述命题，$f$ 是单射的和满射的。

$\Box$

反函数

回顾一下，函数 $f:A\to B$ 是集合 $A$ 到集合 $B$ 的一种特殊关系，它需要满足一些条件。同时，还记得从 $A$ 到 $B$ 的关系中， 反关系 $R^{-1}$ 的定义为 $$R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$$ 我们知道，反关系本身始终是一种关系。但是，函数 f:A→B 的反关系是否始终是 函数 从 $B$ 到 $A$ 本身呢？答案是，不，不是。考虑下面的例子。

示例. 假设 $A=\{1,2,3\}$ 且 $B=\{a,b\}$. 考虑函数 $f:A\to B$，由 $$f=\{(1,a),(2,a),(3,b)\}.$$ 定义。 那么，反关系（我们不称之为反函数） of $f$，记为 $f^{-1}$，是 $$f^{-1}=\{(a,1),(a,2),(b,3)\}.$$ 我们可以看到，这个反关系 $f^{-1}$ 不是 从 $B$ 到 $A$ 的函数，因为元素 $a\in B$ 有两个像：1 和 2。

当然，当函数 $f:A\to B$ 的反关系正好是 $B$ 到 $A$ 的函数时，很自然地将它定义为 $f$ 的 反函数

定义。（逆函数）令 $A$ 和 $B$ 为集合，且令 $f:A\to B$ 为函数。函数 $f$ 的 逆函数 是函数 $f$ 的 逆关系，用 $f^{-1}$ 表示，前提是 $f^{-1}$ 是从 $B$ 到 $A$ 的函数。

备注.

• 由于给定从 $A$ 到 $B$ 的关系，它具有从 $B$ 到 $A$ 的唯一（或正好一个）逆关系（根据定义），因此，函数 $f$ 的逆函数，如果存在，是唯一的。

那么我们感兴趣的是了解在什么条件下逆关系 $f^{-1}$ 是从 $B$ 到 $A$ 的函数，以便 逆函数存在。

首先，为了使 $f^{-1}$ 成为从 $B$ 到 $A$ 的函数，我们必须有 $\operatorname {dom} f^{-1}=B$。所以，我们需要确保 每个 $B$ 中的元素都与 $A$ 中的一些元素相关联，这样当我们 "反转" $f$ 中的有序对以获得 $f^{-1}$ 时，每个 $b\in B$ 至少有一个像。这意味着 $\operatorname {ran} f=B$，即 $f$ 需要是满射的。

当然，我们还需要确保每个 $b\in B$ 都有一个 唯一 的像。在 $f$ 是满射的条件下，每个 $b\in B$ 已经至少有一个像了。所以，剩下的要确保每个 $b\in B$ 最多 只有一个像。

为了确保这一点，我们需要函数 $f$ 是单射的，因为如果 $f$ 是单射的，那么 $B$ 中的每个元素最多只有一个原像。因此，当我们“反转” $f$ 中的有序对得到 $f^{-1}$ 时，$B$ 中的每个元素最多只有一个 像。

从这段讨论中，我们知道，如果 $f^{-1}$ 是从 $B$ 到 $A$ 的函数，那么 $f$ 必须是单射和满射的，即双射的。这表明 $f$ 的双射性是逆函数存在的必要条件。它也是充分条件吗？事实证明，$f$ 的双射性实际上是逆函数存在的 充要 条件。

定理。 令 $f:A\to B$ 为一个函数。那么它的逆关系 $f^{-1}$ 是从 $B$ 到 $A$ 的函数（即，$f$ 的逆函数存在） 当且仅当 函数 $f$ 是双射的。

证明。

"$\Rightarrow$" 假设 $f^{-1}$ 是一个从 $B$ 到 $A$ 的函数。然后我们将证明 $f$ 是单射和满射的。

单射：对于每个 $x,y\in {\color {darkgreen}A}$，首先假设 $z=f(x)=f(y){\color {blue}\in B}$。然后，$(x,z),(y,z)\in f$。根据逆关系的定义，我们有 $(z,x),(z,y)\in f^{-1}$。由于 $f^{-1}$ 是一个从 ${\color {blue}B}$ 到 ${\color {darkgreen}A}$ 的函数，根据定义我们有 $x=y$。

满射：对于每个$b\in B$，由于$f^{-1}$ 是从$B$ 到$A$ 的函数，存在唯一的$a\in A$ 使得$(b,a)\in f^{-1}$。根据逆关系的定义，这意味着$(a,b)\in f$，即$f(a)=b$。

"$\Leftarrow$" 方向：假设$f$ 是双射的。接下来我们将证明$f^{-1}$ 是从$B$ 到$A$ 的函数。也就是说，我们需要确保对于每个元素$b\in B$，存在唯一的$a\in A$ 使得$(b,a)\in f^{-1}$。

存在性：对于每个 $b\in B$，因为 $f$ 是满射的，存在一个 $a\in A$ 使得 $f(a)=b$，即 $(a,b)\in f$。因此，$(b,a)\in f^{-1}$。这表明对于每个 $b\in B$，存在一个 $a\in A$ 使得 $(b,a)\in f^{-1}$。

唯一性：假设除了 $(b,a)\in f^{-1}$，还有 $(b,a')\in f^{-1}$。因此，我们有 $(a,b),(a',b)\in f$，即 $f(a)=f(a')=b$。由于 $f$ 是单射的，我们有 $a=a'$。

$\Box$

因此，从这个定理中，我们知道只有当 $f$ 是双射时，谈论 $f$ 的逆函数才有意义。如果 $f$ 不是双射的，那么它的逆函数根本不存在，谈论它就没有意义。下面的定理进一步表明，逆函数也必须是双射的。

定理。 如果函数 $f:A\to B$ 是双射的，那么它的逆函数 $f^{-1}:B\to A$ 也是双射的。

证明。 假设 $f:A\to B$ 是双射的。那么，$f^{-1}$ 是一个从 $B$ 到 $A$ 的函数。然后，我们将证明它是单射的和满射的。

单射：对于每一个 $b,b'\in B$，首先假设 $a=f^{-1}(b)=f^{-1}(b')$。然后，$(b,a),(b',a)\in f^{-1}$。因此，$(a,b),(a,b')\in f$。由于 $f$ 是一个函数，因此有 $b=b'$。

满射：对于每一个 $a\in A$，由于 $f$ 是一个函数，因此存在一个唯一的 $b\in B$ 使得 $f(a)=b$，即 $(a,b)\in f$，因此有 $(b,a)\in f^{-1}$，即 $f^{-1}(b)$。

$\Box$

备注.

• 请注意，在证明中，我们没有使用 $f$ 的双射性来证明 $f^{-1}$ 的单射性和满射性。事实上，我们只是使用函数的定义来证明它们。$f$ 的双射性只有一个目的：确保逆函数的存在。

另一个常见的逆函数定义是，函数 $f$ 的逆函数，记为 $f^{-1}$，是一个满足 $$f^{-1}\circ f=id_{A}{\text{ and }}f\circ f^{-1}=id_{B}.$$ 的函数。 事实证明，这两个逆函数定义确实是（逻辑上）等价的。 考虑以下定理。

定理。 设 $f:A\to B$ 和 $g:B\to A$ 是两个满足 $f\circ g=id_{A}$ 和 $g\circ f=id_{B}$ 的函数。 那么，$f$ 是双射的，并且 $g$ 等于 $f$ 的逆函数，$f^{-1}$.

证明。 首先证明 $f$ 是双射的。

单射: 对于每一个 $x,y\in A$，$${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&(g{\text{ is a function}})\\&\implies (g\circ f)(x)=(g\circ f)(y)\\&\implies id_{A}(x)=id_{A}(y)&({\text{assumption}})\\&\implies x=y.\end{aligned}}$$ 满射: 对于每一个 $y\in B$，选择 $x=g(y)\in A$。 然后，$$f(x)=f(g(y))=id_{B}(y)=y.$$

现在，让我们证明$g=f^{-1}$。由于$f$ 是双射的，因此存在逆函数 $f^{-1}$。然后，根据定义，逆函数$f^{-1}$ 的定义域和值域分别是 $B$ 和 $A$，$g$ 和 $f^{-1}$ 具有相同的定义域和值域。现在剩下要证明的是，对于每个 $b\in B$，$g(b)=f^{-1}(b)$。由于$f$ 是满射的，对于每个 $b\in B$，都存在$a\in A$ 使得 $f(a)=b$。这意味着 $a=f^{-1}(b)$。现在，我们有对于每个 $b\in B$，$$g(b)=g(f(a))=id_{A}(a)=a=f^{-1}(b).$$

$\Box$

上述定理的逆命题也成立。更准确地说，如果 $f$ 是双射函数，那么它的逆函数 $f^{-1}$ 存在，则有 $f\circ f^{-1}=id_{A}$ 和 $f^{-1}\circ f=id_{B}$。（细节留给以下练习。）因此，这两个定义实际上在逻辑上是等价的，因为

• 根据上述定理，备选定义中的条件意味着我们定义中的条件。
• 根据上述说明，我们定义中的条件意味着备选定义中的条件。

因此，满足 $f\circ g=id_{A}$ 和 $g\circ f=id_{B}$ 的函数 $g$ 是唯一的，因为逆函数是唯一的。

练习。 假设 $f:A\to B$ 是一个函数。证明如果 $f$ 是双射函数，那么它的逆函数 $f^{-1}$ 存在，则有 $f\circ f^{-1}=id_{A}$ 和 $f^{-1}\circ f=id_{B}$。

证明。 首先，由于 $f^{-1}$ 是从 $B$ 到 $A$ 的函数，因此 $f\circ f^{-1}$ 是从 $A$ 到 $A$ 的函数，并且 $f^{-1}\circ f$ 是从 $B$ 到 $B$ 的函数。

然后，对于每一个 $a\in A$，存在唯一的 $b\in B$ 使得 $f(a)=b$，因此 $a=f^{-1}(b)$。所以，$$(f^{-1}\circ f)(a)=f^{-1}(f(a))=f^{-1}(b)=a.$$ 同样，对于每一个 $b\in B$，$$(f\circ f^{-1})(b)=f(f^{-1}(b))=f(a)=b.$$

$\Box$

这里，我们将介绍一种寻找逆函数公式的方法。但是这种方法并 不总是 有效。

示例。 回忆我们已经证明了函数 $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ 由 $f(x)={\frac {3x+1}{x-1}}$ 定义的双射函数。因此，它的逆函数 $f^{-1}$ 存在。确定逆函数 $f^{-1}$。

解. 对于任意 $x\in \mathbb {R} \setminus \{3\}$，我们有 $(f\circ f^{-1})(x)=x$。因此，$$x=(f\circ f^{-1})(x)=f(f^{-1}(x))={\frac {3f^{-1}(x)+1}{f^{-1}(x)-1}}\implies xf^{-1}(x)-x=3f^{-1}(x)+1\implies f^{-1}(x)={\frac {x+1}{x-3}}.$$ 因此，逆函数 $f^{-1}:\mathbb {R} \setminus \{3\}\to \mathbb {R} \setminus \{1\}$ 由以下公式给出: $$f^{-1}(x)={\frac {x+1}{x-3}}.$$

在这个方法中，我们使用一些代数运算来求解逆函数。然而，这种方法并不总是可行的。例如，函数 $f:\mathbb {R} \to (0,\infty )$ 定义为 $f(x)=e^{x}$ 是双射的，但是它的逆函数 $f^{-1}:(0,\infty )\to \mathbb {R}$ 由（实际上，被定义为）$f^{-1}(x)=\ln x$ 给出。在这种情况下，无法通过代数运算来求解逆函数。

习题. 考虑函数 $f:[0,1]\to [0,1]$ 定义为 $$f(x)={\sqrt {1-x^{2}}}.$$ (a) 证明 $f$ 是双射的。

(b) 求解逆函数的公式，即 $f^{-1}(x)$。

解答

(a)

证明。

单射：对于每个 $x,y\in [0,1]$，$${\begin{aligned}f(x)=f(y)&\implies {\sqrt {1-x^{2}}}={\sqrt {1-y^{2}}}\\&\implies 1-x^{2}=1-y^{2}\\&\implies x^{2}=y^{2}\\&\implies x=y.&(x,y\geq 0)\end{aligned}}$$ 满射：对于每个 $y\in [0,1]$，选择 $x={\sqrt {1-y^{2}}}\in [0,1]$。然后，$$f(x)=f\left({\sqrt {1-y^{2}}}\right)={\sqrt {1-\left({\sqrt {1-y^{2}}}\right)^{2}}}={\sqrt {1-(1-y^{2})}}={\sqrt {y^{2}}}=|y|=y.$$

$\Box$

(b) 由于对于每个 $x\in [0,1]$，有 $f(f^{-1}(x))=x$，我们有 $$x={\sqrt {1-(f^{-1}(x))^{2}}}\implies x^{2}=1-(f^{-1}(x))^{2}\implies f^{-1}(x)=\pm {\sqrt {1-x^{2}}}.$$ 但反函数 $f^{-1}$ 的陪域是 $[0,1]$。所以我们应该选择正平方根作为公式，即 $$f^{-1}(x)={\sqrt {1-x^{2}}}.$$

备注.

• 事实证明，在这种情况下，函数 $f$ 等于它的反函数 $f^{-1}$。

图像集和原像集

本节讨论的概念是对图像和原像概念的推广。

定义。 （图像（集）和原像（集））令$A$ 和 $B$ 是集合，令$f:A\to B$ 是一个函数。

(a) 假设$X\subseteq A$. $X$ 的图像（集）是集合$$f(X)=\{y\in B:y=f(x){\text{ for some }}x\in X\}\subseteq B.$$ (b) 假设$Y\subseteq B$. $Y$ 的原像（集）是集合$$f^{-1}(Y)=\{x\in A:f(x)\in Y\}\subseteq A.$$

备注.

• 注意，原像集符号中使用的 "$f^{-1}$" 不是 指代逆函数。即使函数$f$ 不是双射函数，$Y$ 的原像集 $f^{-1}(Y)$ 仍然有意义。但是，如果函数$f$ 不是双射函数，则逆函数 $f^{-1}$ 不存在。
• 换句话说，图像集包含每个元素$x\in X$ 的图像。因此，它是一个图像的集合，因此得名。
• 另一方面，原象集包含每个元素 $y\in Y$ 的原象。也就是说，原象集 $f^{-1}(Y)$ 是 $A$ 中被 $f$ 映射到 $Y$ 的元素的集合。
• 特殊情况：假设 $a\in A$ 且 $b\in B$。然后，$\{a\}$ 的像集是包含 $a$ 在 $f$ 下的像的集合：$\{f(a)\}$，而集合 $\{b\}$ 的原象是包含 $b$ 在 $f$ 下的原象（如果有）的集合。

从图形上看，像集看起来像

   A              B
*------*       *------*
|      |       |      |
|  . X |       | f(X) |
|.###. |       |  .   |
|.###.--------->.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

原象集看起来像

   A              B
*------*       *------*
|f-1(Y)|       |      |
|  .   |       |  Y   |
|.###. |       |  .   |
|.###.<---------.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

示例。 令 $A=\{1,2,3,4,5,6,7\}$ 且 $B=\{a,b,c,d,e\}$。考虑函数 $f:A\to B$，由 $$f=\{(1,a),(2,a),(3,b),(4,b),(5,d),(6,d),(7,a)\}.$$ 定义。然后，

• $f(\{1,3\})=\{a,b\}$
• $f^{-1}(\{a,b\})=\{1,2,3,4\}$
• $f(\{1,2,3,4\})=\{a,b\}$
• $f(\{1,2,3,4,5,6,7\})=\{a,b,d\}$
• $f^{-1}(\{c\})=\varnothing$
• $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$
• $f(\{1,2,5,6,7\})=\{a,d\}$

备注.

• 注意 $f$ 不是双射，但考虑 $f$ 的原像集仍然是有意义的。例如，我们有 $f^{-1}(\{a\})=\{1,2\}$，但“$f^{-1}(a)$” 没有意义，因为 $f^{-1}$ 本身就不存在。
• 我们可以观察到 $f(\{1,3\})=\{a,b\}$，但 $f^{-1}(\{a,b\})=\{1,2,3,4\}$。所以，一般情况下 $f^{-1}(f(X))\neq X$。另外，我们可以注意到，在对集合 $X$ “应用”了像集和原像集之后，我们可能得到一些比 $X$ 更大的集合。
• 另一方面，我们可以看到 $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$，但 $f(\{1,2,5,6,7\})=\{a,d\}$。因此，$f(f^{-1}(Y))\neq Y$ 通常不成立。此外，似乎我们得到了一些比 $X$ 更小的集合。
• 事实证明，这种结果通常成立（见下面的定理）。

练习。 考虑一个函数 $f:A\to B$。求解 (a) $f(A)$；(b) $f^{-1}(B)$；(c) $f(\varnothing )$；(d) $f^{-1}(\varnothing )$。

解答

(a) $f(A)=\{y\in B:y=f(x){\text{ for some }}x\in A\}=\operatorname {ran} f$.

(b) $f^{-1}(B)=\{x\in A:\underbrace {f(x)\in B} _{\text{always true}}\}=A$.

(c) $f(\varnothing )=\{y\in B:\underbrace {y=f(x){\text{ for some }}x\in \varnothing } _{\text{always false}}\}=\varnothing$.

(d) $f^{-1}(\varnothing )=\{x\in A:\underbrace {f(x)\in \varnothing } _{\text{always false}}\}=\varnothing$.

命题。 令 $A$ 和 $B$ 是集合，并令 $f:A\to B$ 是一个函数。那么，

(a) $X\subseteq f^{-1}(f(X))$ 对于所有子集 $X\subseteq A$ 成立。

(b) $f(f^{-1}(Y))\subseteq Y$ 对于所有子集 $Y\subseteq B$ 成立。

证明： (a) 对于任意子集 $X\subseteq A$，我们有 $f^{-1}(f(X))=\{x\in A:f(x)\in f(X)\}$。因此，对于任意 $x$，$$x\in X\implies f(x)\in f(X)\implies x\in f^{-1}(f(X)).$$ (b) 对于任意子集 $Y\subseteq B$，我们有 $f(f^{-1}(Y))=\{y\in B:y=f(x){\text{ for some }}x\in f^{-1}(Y)\}$。因此，对于任意 $y$，假设 $y\in f(f^{-1}(Y))$。那么，$y=f(x)$，其中 $x\in f^{-1}(Y)$。但 $x\in f^{-1}(Y)$意味着 $f(x)\in Y$。因此，我们有 $y=f(x)\in Y$.

$\Box$

练习. 针对函数 $f$，提出一个额外的假设，使得 (a) 在此假设下，$X=f^{-1}(f(X))$ 成立； (b) 在此假设下，$Y=f(f^{-1}(Y))$ 成立。 然后，证明它们。 (提示: 这个假设要么是 "$f$ 是单射的"，要么是 "$f$ 是满射的"。 构造一些简单的单射/满射函数的例子，来帮助你做出选择。）

解答

(a) 假设是 "$f$ 是单射的"。

证明. 由于另一个子集包含关系在上面的命题中是直接的，所以只需证明 $f^{-1}(f(X))\subseteq X$。 对于每一个 $x$，$${\begin{aligned}x\in f^{-1}(f(X))&\implies f(x)\in f(X)\\&\implies f(x)=f(x'){\text{ for some }}x'\in X\\&\implies x=x'&({\text{injective}}).\end{aligned}}$$

$\Box$

(b) 假设是 "$f$ 是满射的"。

证明。 只要证明 $Y\subseteq f^{-1}(f(Y))$。对于任意 $y$，假设 $y\in Y$。然后，因为 $f$ 是满射，存在 $x\in A$ 使得 $y=f(x)$。这意味着 $x\in f^{-1}(Y)$，因为 $f(x)\in Y$。将此与前面的等式结合起来，我们有 $y=f(x)$，其中 $x\in f^{-1}(Y)$。因此，根据像集的定义，$y\in f(f^{-1}(Y))$。

$\Box$

练习。 证明或反驳以下命题：(a) 如果 $x\in X$，则 $f(x)\in f(X)$；(b) 如果 $f(x)\in f(X)$，则 $x\in X$。

解答

(a)

证明。 假设 $x\in X$。根据像集的定义，$f(x)\in f(X)$。

$\Box$

(b)

反证法。 考虑 $A=\{1,2\}$，$B=\{1\}$，以及由 $f=\{(1,1),(2,1)\}$ 定义的函数 $f:A\to B$。然后，取 $x=2$ 和 $X=\{1\}$。之后，我们有 $f(x)=1\in \{1\}=f(X)$，但 $x=2\notin \{1\}=X$。

$\Box$

集合的基数

回想一下，一个集合 $S$ 是 有限的，如果它包含有限个元素，即 $S=\varnothing$ 或对某个 $n\in \mathbb {N}$ 有 $|S|=n$。另一方面，如果一个集合不是有限的，那么它是无限的。之前，我们已经研究了有限集合的基数，并且我们把 无限 集合的基数留作未定义。但是，事实证明，我们可以用更复杂的方法定义无限集合的基数，使用 双射函数。

现在可能看起来我们可以像 $|S|=\infty$ 一样写无限集合 $S$ 的基数。但事实证明这并不完全有意义，正如我们将看到的，无限集合可以有不同的基数，或者不同的“大小”。也就是说，有不同大小的无穷大！（在某种意义上）。

为了激发对无限集合基数定义的理解，让我们首先考虑一个简单的 有限 集合的例子。

示例： 令 $A=\{a,b,c\}$ 和 $B=\{1,2,3\}$。我们可以很明显地观察到 $|A|=|B|=3$，只需计算每个集合中包含的元素数量。或者，我们可以将 $A$ 和 $B$ 的元素配对，如下所示： $${\begin{array}{c|ccc}A&a&b&c\\&\updownarrow &\updownarrow &\updownarrow \\B&1&2&3\\\end{array}}$$ 更准确地说，这种配对定义了一个 双射 函数 $f:A\to B$，表示为 $$f=\{(a,1),(b,2),(c,3)\}.$$

这个例子表明，对于两个有限的（非空）集合 $A$ 和 $B$，如果存在一个从 $A$ 到 $B$（或从 $B$ 到 $A$ 的双射函数，那么它们具有 相同基数。其中一个这样的函数是由 $A$ 到 $B$ 的双射函数的 逆函数 给出。这将我们引向了以下定义。

定义。 两个（有限或无限）集合 $A$ 和 $B$ 具有 相同基数（或 数值等价），记作 $|A|=|B|$，如果 $A$ 和 $B$ 都是空集，或者存在一个从 $A$ 到 $B$ 的双射函数。

备注.

• 如果两个集合具有不同的基数，那么我们记作 $|A|\neq |B|$。具有不同的基数意味着（$A$ 非空或 $B$ 非空）并且（对于从 $A$ 到 $B$ 的每个函数，该函数 不是 双射）。（换句话说，后者意味着不存在从 $A$ 到 $B$ 的双射函数。）
• 双射函数是从 $A$ 到 $B$，还是从 $B$ 到 $A$，都没有关系。由于其中一个的存在意味着另一个的存在，通过考虑逆函数。
• 对于有限集（包括空集），这个定义有点多余，因为我们只需要简单地计算有限集中元素的数量。但是对于无限集，这个定义是比较它们基数或“大小”的基础。
• 根据这个定义，我们也知道有限集和无限集不能具有相同的基数，因为从有限集到无限集不存在双射函数（可以使用反证法证明这一点）。

示例。 令 $E$ 是所有偶数整数的集合，即 $E=\{2x:x\in \mathbb {Z} \}$。证明 $\mathbb {Z}$ 和 $E$ 是数值等价的。

证明。 定义一个函数 $f:\mathbb {Z} \to E$ 由 $f(x)=2x$ 定义。现在，只需要证明它是双射的。

单射：对于每一个 $x,y\in \mathbb {Z}$，$f(x)=f(y)\implies 2x=2y\implies x=y$。

满射：对于每一个 $y\in E$，选择 $x={\frac {y}{2}}\in \mathbb {Z}$。那么，$f(x)=2(y/2)=y$。

$\Box$

练习。 令 $O$ 为所有奇数的集合。

(a) 证明 $\mathbb {Z}$ 和 $O$ 是等势的。

(b) 证明 $E$ 和 $O$ 是等势的。

解答

(a)

证明。 定义一个函数 $f:\mathbb {Z} \to O$ 由 $f(x)=2x+1$ 定义。现在，只需要证明它是双射的。

单射：对于每一个 $x,y\in \mathbb {Z}$，$f(x)=f(y)\implies 2x+1=2y+1\implies x=y$。

满射：对于每一个 $y\in O$，选择 $x={\frac {y-1}{2}}\in \mathbb {Z}$。那么，$f(x)=2\left({\frac {y-1}{2}}\right)+1=y-1+1=y$。

$\Box$

(b)

证明： 定义一个函数 $f:E\to O$，其中 $f(x)=x+1$。现在，我们只需要证明它是一个双射函数。

单射： 对于任意 $x,y\in \mathbb {Z}$，$f(x)=f(y)\implies x+1=y+1\implies x=y$。

满射： 对于任意 $y\in O$，选择 $x=y-1\in E$。那么，$f(x)=y-1+1=y$。

$\Box$

这个例子中的结果可能看起来很奇怪，也很不直观，因为 $\mathbb {Z}$ 似乎是 $E$ 的两倍大，而 $E$ 是 $\mathbb {Z}$ 的一个真子集，但它们的基数却相同。当我们处理 无限集 的基数时，这种现象实际上很常见。

幸运的是，数值等价具有一些很好的性质：自反性、对称性和传递性

定理： 对于任意集合 $A,B,C$，

• (自反性) $A$ 与 $A$ 数值等价。
• (对称性) 如果 $A$ 与 $B$ 数值等价，那么 $B$ 与 $A$ 数值等价。
• (传递性) 如果 $A$ 在数值上等价于 $B$，并且 $B$ 在数值上等价于 $C$，那么 $A$ 在数值上等价于 $C$.

证明。

自反性:

情况 1: $A$ 为空。那么，$|A|=|A|=0$.

情况 2: $A$ 非空。那么，考虑恒等函数 $id_{A}:A\to A$。我们已经证明它是双射的。

对称性:

情况 1: $A$ 和 $B$ 都是空的。那么，$B$ 必须在数值上等价于 $A$.

情况 2: $A,B$ 之一为空，另一个非空。那么，$A$ 必须 不 在数值上等价于 $B$，结果随之而来。

情况 3：$A$ 和 $B$ 都非空。然后，假设 $A$ 在数值上等价于 $B$。这意味着存在一个双射函数 $f:A\to B$。现在，考虑它的逆函数 $f^{-1}:B\to A$，它也是双射的。因此，$B$ 在数值上等价于 $A$。

传递性:

情况 1：$A,B,C$ 为空。那么，$A$ 必须在数值上等价于 $C$。

情况 2：$A,B,C$ 中有些为空，有些非空。那么，$A$ 不可能在数值上等价于 $B$ 并且 $B$ 在数值上等价于 $C$。结果随之而来。

情况 3：$A,B,C$ 是非空的。那么，假设 $A$ 与 $B$ 数值上等价，且 $B$ 与 $C$ 数值上等价。那么，存在双射函数 $f:A\to B$ 和 $g:B\to C$。因此，它们的复合函数 $g\circ f:A\to C$ 是双射的。因此，$A$ 和 $C$ 数值上等价。

$\Box$

现在，让我们关注集合 $\mathbb {N}$，并考虑与 $\mathbb {N}$ 具有相同基数的（无限）集合。我们给这类集合一个特殊的名称

定义。 （可数集合）如果集合 $A$ 与 $\mathbb {N}$ 数值上等价，即存在一个双射函数 $f:\mathbb {N} \to A$，则称集合 $A$ 是 可数 的。

备注.

• 同样地，双射函数可以是从 $A$ 到 $\mathbb {N}$，这并不重要。
• 根据数值等价的自反性，$\mathbb {N}$ 本身是可数的。
• 由于$\mathbb {N}$ 是一个无限集，为了与之数值等价，集合$A$ 必须是无限集。也就是说，作为无限集是可数的必要条件（但不是充分条件）。
• 这种双射函数 $f:\mathbb {N} \to A$ 的存在，使我们可以将可数集$A$ 列成一个无限列表$f(1),f(2),f(3),\dotsc$。因此，我们可以将$A$ 的元素列为$a_{1},a_{2},a_{3},\dotsc$，即 $A$ 可以表示为$\{a_{1},a_{2},a_{3},\dotsc \}$。

• 反过来，假设$a_{i}\neq a_{j}$ 对于每个$i\neq j$ （为了确保单射性），那么我们可以定义一个函数$f:\mathbb {N} \to A$，通过$f(n)=a_{n}$，它基于上述无限列表是双射的。

• $\mathbb {N}$ 的基数用 $|\mathbb {N} |$ 或 $\aleph _{0}$（读作“aleph-zero”或“aleph-naught”）表示。因此，每个可数集的基数都是$\aleph _{0}$。

利用这个定义，我们可以进一步定义集合的另一个性质。

定义。 （可数集）如果一个集合 $A$ 是有限的或可数无限的，那么它就是 可数 的。不可数的集合被称为 不可数 的。

备注.

• 直观地，我们仍然可以“数”出一个可数无限集合中的元素。同样地，我们可以清楚地数出一个有限集合中的元素。因此，我们称它们为可数集。
• 根据这个定义，我们知道 可数无限集 与 可数无限集 是一样的。在其他一些地方，人们会使用“可数无限集”来代替“可数无限集”。
• 同样地，根据这个定义，我们知道一个不可数集必然是无限的。

示例。 证明集合 $\mathbb {Z}$ 是可数无限的。

为了证明这一点，我们需要构造一个双射函数 $f:\mathbb {N} \to \mathbb {Z}$。因此，我们应该有一对一的对应关系，将正整数与整数配对。

思路：我们可以将整数标记为一个无限的“队列”：$${\begin{array}{ccccccc}{\text{Label}}&5&3&1&2&4\\\hline \cdots &-2&-1&0&1&2&\cdots \end{array}}$$ 从中，我们得到一个无限的整数“队列”：$0,1,-1,2,-2,\dotsc$。

证明。 以下配对表明了一种构造双射函数 $f:\mathbb {N} \to \mathbb {Z}$ 的方法：$${\begin{array}{c|cccccc}\mathbb {N} &1&2&3&4&5&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Z} &0&1&-1&2&-2&\cdots \\\end{array}}$$ 更准确地说，我们可以定义函数 $f:\mathbb {N} \to \mathbb {Z}$ 为 $$f(n)={\begin{cases}{\frac {n}{2}},&{\text{ if }}n{\text{ is even}};\\{\frac {1-n}{2}},&{\text{ if }}n{\text{ is odd}}.\end{cases}}$$ 然后，剩下的就是证明这个函数是双射的。

单射：对于每个 $m,n\in \mathbb {N}$，

情况 1: $m$ 和 $n$ 都是偶数。那么，$f(m)=f(n)\implies {\frac {m}{2}}={\frac {n}{2}}\implies m=n$.

情况 2: $m$ 和 $n$ 都是奇数。那么，$f(m)=f(n)\implies {\frac {1-m}{2}}={\frac {1-n}{2}}\implies 1-m=1-n\implies m=n$.

情况 3: $m$ 和 $n$ 的奇偶性不同。那么，不可能出现 $f(m)=f(n)$，因为 $f(m)$ 是非负数，而 $f(n)$ 是负数。结果成立。

满射: 对于任何 $y\in \mathbb {Z}$，

情况 1: $y$ 是非负数。那么，选择 $n=2y\in \mathbb {N}$，它是偶数。因此，我们有 $f(n)={\frac {2y}{2}}=y$.

情况 2: $y$ 为负数。然后，选择 $n=1-2y\in \mathbb {N}$，它是奇数。因此，我们有 $f(n)={\frac {1-(1-2y)}{2}}={\frac {2y}{2}}=y$.

$\Box$

备注.

• 上面的函数也可以用一个公式来定义

$$f(n)={\frac {1+(-1)^{n}(2n-1)}{4}}.$$

• 这个结果有点奇怪，因为 $\mathbb {N} \subset \mathbb {Z}$，但 $|\mathbb {N} |=|\mathbb {Z} |$.
• 根据数值等价的传递性和对称性，所有偶数的集合和所有奇数的集合也是可数的。

练习。 设 $S_{3}$ 是所有 3 的倍数的集合。证明或反驳 $S_{3}$ 是可数的。

解答

证明。 首先证明 $\mathbb {Z}$ 数值等价于 $S_{3}$。定义函数 $f:\mathbb {Z} \to S_{3}$ 为 $f(n)=3n$。现在证明 $f$ 是双射的

单射: 对于每个 $m,n\in \mathbb {Z}$，$f(m)=f(n)\implies 3m=3n\implies m=n$.

满射：对于每个 $y\in S_{3}$，选择 $n={\frac {y}{3}}\in \mathbb {Z}$。然后，$f(n)=3(y/3)=y$。

然后，由于 $\mathbb {Z}$ 在数量上等价于 $\mathbb {N}$，因此 $S_{3}$ 在数量上等价于 $\mathbb {N}$。因此，$S_{3}$ 是可数的。

$\Box$

我们现在知道 $\mathbb {N}$ 和 $\mathbb {Z}$ 具有相同的基数。然后自然地考虑所有有理数的集合，$\mathbb {Q}$。看起来 $\mathbb {Q}$ 比 $\mathbb {Z}$ 大得多，因此似乎 $\mathbb {Q}$ 不再是可数的，而是不可数的。但事实证明 $\mathbb {Q}$ 也是可数的。

例子。

(a) 证明所有正有理数的集合，$\mathbb {Q} ^{+}$ 是可数的。

(b) 因此，证明所有有理数的集合，$\mathbb {Q}$ 是可数的。

解答.

(a) 首先，考虑以下图表：

此图将所有有理数排列在一个无限的数组中。然后，我们按照图中的箭头，得到所有有理数的无限列表：$${\frac {1}{1}},{\frac {2}{1}},{\frac {1}{2}},{\frac {1}{3}},{\color {red}{\frac {2}{2}}},{\frac {3}{1}},{\frac {4}{1}},\dotsc$$

证明。 利用上述的无限列表，我们可以定义一个双射函数$f:\mathbb {N} \to \mathbb {Q} ^{+}$：$$f(1)={\frac {1}{1}},f(2)={\frac {2}{1}},f(3)={\frac {1}{2}},f(4)={\frac {1}{3}},{\cancel {f(5)={\color {red}{\frac {2}{2}}},}}f(5)={\frac {3}{1}},\dotsc$$ 换句话说，一对一的对应配对是$${\begin{array}{c|ccccccc}\mathbb {N} &1&2&3&4&5&6&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Q} ^{+}&{\frac {1}{1}}&{\frac {2}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&{\frac {3}{1}}&{\frac {4}{1}}&\cdots \end{array}}$$ 特别地，我们跳过${\color {red}{\frac {2}{2}}}$，因为这个数字与${\frac {1}{1}}$相同。所以，为了确保函数$f$的单射性，我们需要跳过这些重复的有理数。（上图中红色数字是重复的有理数，我们必须在函数定义中跳过它们。）这样的函数$f$是双射的（因为对于每一个$n\in \mathbb {N}$，都存在唯一的$y\in \mathbb {Q} ^{+}$ 使得$f(n)=y$），因此$\mathbb {Q} ^{+}$是可数的。

$\Box$

(b)

Proof. Since $\mathbb {Q} ^{+}$ is denumerable, we are allowed to write $\mathbb {Q} ^{+}=\{q_{1},q_{2},q_{3},\dotsc \}$. Similarly, we can write the set of all negative rational numbers as $\mathbb {Q} ^{-}=\{-q_{1},-q_{2},-q_{3},\dotsc \}$. Hence, we can write the set of all rational numbers as $$\mathbb {Q} =\mathbb {Q} ^{+}\cup \{0\}\cup \mathbb {Q} ^{-}=\{q_{1},q_{2},q_{3},\dotsc \}\cup \{0\}\cup \{-q_{1},-q_{2},-q_{3},\dotsc \}=\{0,q_{1},-q_{1},q_{2},-q_{2},\dotsc \}.$$ More precisely, we can define a function $f:\mathbb {N} \to \mathbb {Q}$ by $$f(1)=0,f(2)=q_{1},f(3)=-q_{1},f(4)=q_{2},f(5)=-q_{2},\dotsc$$ (similar to the function for proving that $\mathbb {Z}$ is denumerable) In other words, the one-to-one corresponding pairing is $${\begin{array}{c|cccccc}\mathbb {N} &1&2&3&4&5&\cdots \\&\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow \\\mathbb {Q} &0&q_{1}&-q_{1}&q_{2}&-q_{2}&\cdots \end{array}}$$ This function $f$ can be proved to be bijective (very similar proof as in the proof for $\mathbb {Z}$ is denumerable, but we now consider the indexes of "$q$"), and hence $\mathbb {Q}$ is denumerable.

$\Box$

因此，我们已经证明了$|\mathbb {N} |=|\mathbb {Z} |=|\mathbb {Q} |$。事实证明，即使$\mathbb {Q}$看起来比$\mathbb {N}$和$\mathbb {Z}$大得多，它仍然与它们具有相同的基数。然后自然会产生一个问题：是否存在任何不可数集？答案是肯定的，最著名的例子是所有实数的集合，$\mathbb {R}$。换句话说，不存在从$\mathbb {N}$到$\mathbb {R}$的双射函数。由于$\mathbb {R}$是不可数的，这表明$\mathbb {R}$的“大小”与$\mathbb {N}$的“大小”不同，即存在不同大小的无穷大（在某种意义上）。

例子。

(a) 令$a,b\in \mathbb {R}$，其中$b>a$。构造一个双射函数$f:(0,1)\to (a,b)$

(b) 使用 (a) 中的双射函数，证明对于所有 $a,b,c,d\in \mathbb {R}$，满足 $b>a$ 和 $d>c$，有 $|(a,b)|=|(c,d)|$。

(c) 证明开区间 $(0,1)$ 是不可数的。

(d) 证明对于所有 $a,b\in \mathbb {R}$，满足 $b>a$，有 $|(a,b)|=|\mathbb {R} |$。 (提示: 你可以不用证明就使用正切函数 $\tan :(-\pi /2,\pi /2)\to \mathbb {R}$ 是双射这个事实。）

解答.

(a) 定义一个函数 $f:(0,1)\to (a,b)$，由 $$f(x)=a+(b-a)x.$$ 现在，我们证明 $f$ 是双射。

证明。

单射: 对于所有 $x,y\in (0,1)$，$$f(x)=f(y)\implies a+(b-a)x=a+(b-a)y\implies (b-a)x=(b-a)y\implies x=y$$.

满射：对于每个 $y\in (a,b)$，选择 $x={\frac {y-a}{b-a}}\in (0,1)$。然后，$$f(x)=a+(b-a)\cdot {\frac {y-a}{b-a}}=a+y-a=y.$$

$\Box$

(b)

证明。 由 (a)，我们可以构造一个双射函数 $f:(0,1)\to (a,b)$，以及一个双射函数 $g:(0,1)\to (c,d)$。这意味着 $|(0,1)|=|(a,b)|$ 且 $|(0,1)|=|(c,d)|$。然后，根据数值等价的对称性和传递性，我们有 $|(a,b)|=|(c,d)|$。

$\Box$

(c) 可以使用 康托尔对角线论证 来证明它。

(d)

证明。 由于正切函数 $\tan :(-\pi /2,\pi /2)\in \mathbb {R}$ 是双射的，我们有 $|(-\pi /2,\pi /2)|=|\mathbb {R} |$。此外，根据 (b)，对于每个 $a,b\in \mathbb {R}$ 且 $b>a$，$|(a,b)|=|(-\pi /2,\pi /2)|$。结果根据数值等价的传递性而来。

$\Box$

备注.

• 特别地，部分 (d) 表明 $|(0,1)|=|\mathbb {R} |$。因此，这意味着 $\mathbb {R}$ 是不可数的，因为如果它是可数的（在本例中是可枚举的）并且 $|(0,1)|=|\mathbb {R} |$，那么这意味着 $(0,1)$ 是可枚举的，这导致了矛盾。

以下结果可能有助于比较可枚举或不可数的集合。

命题。 可枚举集的任何无限子集都是可枚举的。

示例。 令 $P$ 是所有素数的集合。证明 $P$ 是可枚举的。

证明。 回想一下，我们已经证明了存在无限多个素数。那么，因为 $P$ 是 $\mathbb {N}$ （它是可枚举的）的 无限 子集，因此 $P$ 是可枚举的。

$\Box$

练习。 证明集合 $S=\{2^{n}:n\in \mathbb {Z} \}=\left\{\dotsc ,{\frac {1}{8}},{\frac {1}{4}},{\frac {1}{2}},1,2,4,8,\dotsc \right\}$ 是可枚举的。

证明

证明。 因为集合 $S$ 是 $\mathbb {Q}$ 的无限子集，并且 $\mathbb {Q}$ 是可枚举的，因此 $S$ 是可枚举的。

$\Box$

示例。 证明对于自然数集 $\mathbb {N}$ 的任何有限子集 $S$，都有 $|\mathbb {N} \setminus S|=|\mathbb {N} |$。(这意味着无论我们从 $\mathbb {N}$ 中 "去掉" 多少个元素，只要去掉的元素数量是有限的，那么集合的基数就不会受到影响。)

证明。 首先，我们有 $\mathbb {N} \setminus S\subseteq \mathbb {N}$，而 $\mathbb {N}$ 是可数的。因此，我们只需要证明 $\mathbb {N} \setminus S$ 是无限的。我们用反证法来证明。

假设 $\mathbb {N} \setminus S$ 是有限的。由于 $S$ 也是有限的，我们有 $$S\cup (\mathbb {N} \setminus S)=\mathbb {N}$$ 是有限的，这与 $\mathbb {N}$ 是无限的这个事实相矛盾。

$\Box$

命题。 令 $A$ 和 $B$ 是满足 $A\subseteq B$ 的集合。如果 $A$ 是不可数的，那么 $B$ 是不可数的。

备注.

• 利用这个结果，我们可以给出一个$\mathbb {R}$ 不可数的另一种证明（我们有$(0,1)$ 不可数，且$(0,1)\subseteq \mathbb {R}$）。

示例。 证明对于所有 $a,b\in \mathbb {R}$ 且 $b>a$，$[a,b]$ 不可数。

证明。 由于$(a,b)\subseteq [a,b]$ 且 $(a,b)$ 不可数，我们得出结论：$[a,b]$ 不可数。

$\Box$

备注.

• 注意，这只是说明$[a,b]$ 不可数，并不意味着$|[a,b]|=|(a,b)|$。正如我们即将看到，两个不可数的集合可能具有不同的基数。

命题。 如果$A$ 和$B$ 是可数集合，那么$A\times B$ 是可数的。

命题。 如果$A$ 和$B$ 是可数集合，那么$A\cup B$ 是可数的。

练习。 证明或反驳：如果$A$ 和$B$ 是可数集合，那么$A\cap B$ 是可数的。

解答

反证。 设 $A$ 为所有偶数的集合， $B$ 为所有奇数的集合。那么， $A\cap B=\varnothing$，它不是可数的。

$\Box$

例子。

• $\mathbb {N} \times \mathbb {N}$ 是可数的。
• $\mathbb {Q} \times \mathbb {Z}$ 是可数的。

练习。 证明或反驳以下每个语句

(a) 对于任何非空集 $A,B$， $|A\times B|=|B\times A|$.

(b) 所有无理数的集合， $\mathbb {I}$ 是不可数的。(提示: 使用反证法)

(c) $\mathbb {I}$ 的每个无限子集都是不可数的。

(d) 对于任何集合 $A,B,C$，如果 $A\subseteq B\subseteq C$，并且 $A,C$ 是可数的，那么 $B$ 是可数的。

(e) $\{{\sqrt {2}}\}\times \mathbb {Q}$ 是不可数的。

(f) 集合 $S=\{(x,y)\in \mathbb {Z} \times \mathbb {R} :x+y=1\}$ 是可数的。

解答

(a)

证明。 定义一个函数 $f:A\times B\to B\times A$ 如下：$$f(a,b)=(b,a).$$ 现在只需要证明 $f$ 是双射的。

单射：对于每个 $(a_{1},b_{1}),(a_{2},b_{2})\in A\times B$，$$f(a_{1},b_{1})=f(a_{2},b_{2})\implies (b_{1},a_{1})=(b_{2},a_{2})\implies b_{1}=b_{2}{\text{ and }}a_{1}=a_{2}\implies (a_{1},b_{1})=(a_{2},b_{2}).$$ 满射：对于每个 $(x,y)\in B\times A$，选择 $(a,b)=(y,x)\in A\times B$。那么，$$f(a,b)=(b,a)=(x,y).$$

$\Box$

(b)

证明。 假设相反，$\mathbb {I}$ 是可数的。由于 $\mathbb {I}$ 是无限的，这意味着 $\mathbb {I}$ 是可数无限的。同时，由于 $\mathbb {Q}$ 是可数无限的，由此得出 $$\mathbb {I} \cup \mathbb {Q} =\mathbb {R}$$ 是可数无限的，与 $\mathbb {R}$ 是不可数的事实相矛盾。

$\Box$

(c)

反证。 考虑集合 $S=\{k+{\sqrt {2}}:k\in \mathbb {N} \}\subseteq \mathbb {I}$。然后，定义函数 $f:\mathbb {N} \to S$ 为 $$f(n)=n+{\sqrt {2}}.$$ 现在需要证明 $f$ 是双射的。

单射：对于任意 $m,n\in \mathbb {N}$，$f(m)=f(n)\implies m+{\sqrt {2}}=n+{\sqrt {2}}\implies m=n$。

满射：对于任意 $y\in S$，选择 $n=y-{\sqrt {2}}\in \mathbb {N}$。那么，$f(n)=y-{\sqrt {2}}+{\sqrt {2}}=y$。

$\Box$

(d)

证明。 假设 $A\subseteq B\subseteq C$ 且 $A,C$ 可数。由于 $B\subseteq C$ 且 $C$ 可数，则只需证明 $B$ 是无限的。由于 $A$ 可数，因此是无限的，并且 $A\subseteq B$，$B$ 必须是无限的。证毕。

$\Box$

(e)

反证。 令 $S$ 为集合 $\{{\sqrt {2}}\}\times \mathbb {Q}$。定义函数 $f:\mathbb {Q} \to S$，使得 $$f(q)=({\sqrt {2}},q).$$ 现在需要证明 $f$ 是双射的。

单射：对于每个 $q_{1},q_{2}\in \mathbb {Q}$，$f(q_{1})=f(q_{2})\implies ({\sqrt {2}},q_{1})=({\sqrt {2}},q_{2})\implies q_{1}=q_{2}$.

满射：对于每个 $(x,y)\in S$，选择 $q=y\in \mathbb {Q}$。然后，$f(q)=({\sqrt {2}},y)=(x,y)$ ($x$ 必须是 ${\sqrt {2}}$）。

$\Box$

(f)

证明。 对于每个 $x\in \mathbb {Z}$，唯一的实数 $y$ 使得 $x+y=1$ 是 $y=1-x$。因此，我们可以将集合 $S$ 表示为 $$S=\{(x,1-x)\in \mathbb {Z} \times \mathbb {R} :x\in \mathbb {Z} \}.$$ 然后，我们可以定义一个函数 $f:S\to \mathbb {Z}$，其中 $$f(x,y)=x.$$ 现在需要证明 $f$ 是双射的。

单射: 对于每个 $(x_{1},y_{1}),(x_{2},y_{2})\in S$，$f(x_{1},y_{1})=f(x_{2},y_{2})\implies x_{1}=x_{2}\implies (x_{1},1-x_{1})=(x_{2},1-x_{2})\implies (x_{1},y_{1})=(x_{2},y_{2})$.

满射: 对于每个 $z\in \mathbb {Z}$，选择 $(x,y)=(z,1-z)\in S$。然后，$f(x,y)=z$.

$\Box$