1.0 集合、函数与证明语言

集合与量词

集合由其元素决定。$A\subseteq B$ 表示 $A$ 的每个元素都属于 $B$；相等表示两个包含关系均成立。并集 $A\cup B$ 含至少在其中一个集合的元素，交集 $A\cap B$ 含同时在两者内的元素。相对固定全集 $X$，补集为 $A^c=X\setminus A$；差集 $A\setminus B$ 含在 $A$ 但不在 $B$ 的元素。

「对每个 $x$，存在 $y$ 使性质 $P(x,y)$ 成立」的否定是「存在 $x$，使对每个 $y$，$P(x,y)$ 都不成立」。次序很重要：同一个 $y$ 对所有 $x$ 都适用，比每个 $x$ 可选不同 $y$ 更强。一致连续及一致收敛等分析定义，正依赖这个区别。

定理

德摩根定律

对固定全集的子集，$(A\cup B)^c=A^c\cap B^c$，$(A\cap B)^c=A^c\cup B^c$。

证明

逐元素证明

$x$ 属于 $(A\cup B)^c$，当且仅当它既不在 $A$ 也不在 $B$，亦即属于 $A^c\cap B^c$。第二个等式同理，把「并非两者皆在」换成「至少不在其中一个」。每个等价关系都证明了两个包含方向。

例题

量词陷阱

对每个实数 $x$，存在实数 $y$ 使 $y>x$：取 $y=x+1$ 即可。但不存在一个实数 $y$ 大于每个实数 $x$：若存在，取 $x=y+1$ 即得矛盾。改变量词次序会改变命题。

函数、像与原像

函数 $f:X\to Y$ 为每个 $x\in X$ 指派恰好一个 $f(x)\in Y$。若相同输出必有相同输入，称为单射；若 $Y$ 中每个元素都有原像，称满射到 $Y$；两者皆成立称双射。双射有反函数 $f^{-1}:Y\to X$。

对 $A\subseteq X$，像为 $f(A)=\{f(x):x\in A\}$；对 $B\subseteq Y$，原像为 $f^{-1}(B)=\{x\in X:f(x)\in B\}$。即使反函数不存在，任何函数的原像记号仍有意义。

定理

原像保持并集及交集

对 $B,C\subseteq Y$，$f^{-1}(B\cup C)=f^{-1}(B)\cup f^{-1}(C)$，$f^{-1}(B\cap C)=f^{-1}(B)\cap f^{-1}(C)$。像总满足 $f(A\cup D)=f(A)\cup f(D)$，但一般只有 $f(A\cap D)\subseteq f(A)\cap f(D)$。

证明

用元素归属追踪逻辑

例如，$x\in f^{-1}(B\cap C)$ 当且仅当 $f(x)\in B$ 且 $f(x)\in C$，亦即 $x\in f^{-1}(B)\cap f^{-1}(C)$。对像的交集，来自 $A\cap D$ 的输出必在两个像内；但同一输出可能分别由两个不同输入产生，即使没有输入同时属于两集合。

例题

交集的像可以更小

令 $f:\mathbb R\to\mathbb R$ 为 $f(x)=x^2$，$A=\{-1\}$、$D=\{1\}$。则 $A\cap D=\varnothing$、$f(A\cap D)=\varnothing$，但 $f(A)\cap f(D)=\{1\}$。非单射造成这个差异。

可数性

本节称有限集合或可与 $\mathbb N$ 建立双射的集合为可数；有些作者用「可数」专指可数无限，故应说明惯例。整数可列为 $0,1,-1,2,-2,\ldots$，因此可数。有理数可数：按对角线列出整数分子与正整数分母的组合，再略去重复值。相反，$\mathbb R$ 不可数：对任何声称完整的列表，可用对角线法构造 $(0,1)$ 中不同于每个列表项的小数，并选用 $1$ 或 $2$ 等数字以避免末尾无穷多个九造成的表示歧义。

方法比较

集合相等可用双向包含或元素归属等价关系证明。要否定全称命题，给出一个明确反例即可。处理原像时，透过函数翻译元素归属；不要假设它是反函数。否定带量词的极限命题时，逐个反转量词，再仔细否定最后的不等式。

练习

1. 证明 $A\subseteq B$ 当且仅当 $A\cap B=A$。
2. 否定「对每个 $\varepsilon>0$，存在 $N$，使对所有 $n\ge N$ 有 $|x_n-L|<\varepsilon$」。
3. 对 $\mathbb R$ 上的 $f(x)=x^2$，求 $f^{-1}([1,4])$。
4. 给出两个不相交集合，使它们在同一函数下的像相交。

详解

1. 若 $A\subseteq B$，恰好 $A$ 的元素同时属于两者，故 $A\cap B=A$。反过来，若 $A\cap B=A$，每个 $x\in A$ 都在交集中，故属于 $B$。
2. 存在 $\varepsilon_0>0$，使对每个 $N$ 都存在 $n\ge N$，满足 $|x_n-L|\ge\varepsilon_0$。
3. $1\le x^2\le4$ 恰好在 $[-2,-1]\cup[1,2]$ 成立。
4. 取 $A=\{-1\}$、$B=\{1\}$ 和 $f(x)=x^2$。两集合不相交，但两个像都是 $\{1\}$。

总结

集合归属和量词次序是分析的语法。像、原像及反例把语法具体化；比较逐点与一致命题时，精确量词尤其重要。