【数理逻辑：证明及其限度】 1 预备知识

1 证明的必要性

数学与物理、化学等实验科学不同，不需要进行动手实验，但需要进行严格的论证并不允许有例外。

1.1 经验归纳的结果不一定正确

例 1.1.1 观察，$31, 331, 3331, 33331, 333331$都是素数，但$333333331$不是素数

例 1.1.2 Fermat注意到，对于任意整数$n \geqslant 3$，方程$x^n+y^n=z^n$没有整数解。现考虑方程$x^4+y^4+z^4=w^4$，可以验证

$$95800^4 +217519^4 +414560^4 = 422481^4$$

要验证数学猜想（如Riemann猜想），必须给出数学证明。数学证明是由公理出发，一步步根据逻辑规则列出命题，最后达到需要证明的猜想或命题的终点的过程。若猜想被成功证明，他就被称为定理。以下两个证明为反证法典型例子。

1.2 反证法

例 1.1.3 $\sqrt{2}$不是有理数。

证明 假设$\sqrt{2}$是有理数，那么它可以写成$a/b$的形式，其中$a$和$b$不全为偶数。因为$a/b=\sqrt{2}$，那么$a^2=2b^2$，于是$a$为偶数。又因为$a$为偶数，进而存在某个整数$p$使得$a=2p$，于是$a^2=4p^2$，所以$b$也为偶数。这是一个矛盾，于是$\sqrt{2}$不是有理数。

例 1.1.4 存在无穷多个素数。

证明 不妨假设只有$n$个素数：$p_1, …, p_n$。考虑整数$q=p_1\cdots p_n +1$，它不属于先前假定的任何一个素数，且不能被其中的任何一个素数整除。这是一个矛盾，于是素数有无穷多个。

习题1.1

1.1.1 是否对于所有正整数$n$，都有$q=p_1\cdots p_n +1$是素数？这里$p_i$代表第$i$个素数，特殊地，有$p_1=2$。

注意到$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 +1 = 59 \cdot 509$，因此这个猜想不正确。

使用Python语言编写的检查程序：

def primes(n:int) -> List[int]:
    """find all primes less than n"""
    ls = [2]
    for i in range(3, n):
        if not [j for j in ls if i%j==0]:
            ls.append(i)
    
    return ls

def prod(ls:list) -> int:
    """compute product of all entries of a list"""
    if len(ls) == 1:
        return ls[0]
    else:
        return ls[0] * prod(ls[1:])

ls_bk = []
for i in range(50):
    if primes(i) == ls_bk:
        continue
    else:
        ls_bk = primes(i)
    
    # check if prod(primes) + 1 can be divided by smaller primes
    ls_ = [j for j in primes(100 * i) if (prod(ls_bk) + 1) % j == 0 and (prod(ls_bk) + 1) / j > 1]
    if ls_:
        print(f"Prod({ls_bk[0]} ... {ls_bk[-1]}) can be divided by {ls_}")

输出结果为

Prod(2 ... 13) can be divided by [59, 509]
Prod(2 ... 17) can be divided by [19, 97, 277]
Prod(2 ... 19) can be divided by [347]
Prod(2 ... 23) can be divided by [317]
Prod(2 ... 29) can be divided by [331, 571]
Prod(2 ... 37) can be divided by [181]
Prod(2 ... 41) can be divided by [61]
Prod(2 ... 43) can be divided by [167]
Prod(2 ... 47) can be divided by [953]

那么在例1.1.4中看似正确的推断为什么在这个习题中变成了不正确的？注意到在例1.1.4中我们仅假设有有限个素数$p_1,…,p_n$，而在本习题中我们接受了素数是无限多个的事实。我们知道随着素数的增大，其分布是越来越稀疏的（考虑素数分布函数），于是本题中的乘积随着$n$的增大会以很快速度增长：

$$\prod_{i=1}^n p_i \gg n! \sim \sqrt{n}e^n$$

其中$n!$表示$n$的阶乘，$\sim$表示两函数在$n$不断增大时比值近似为常数。于是从定性角度来看很难保证在$p_n$和$q$之间不存在一个素数$p'$使得$p’|q$。

2 集合

2.1 集合及其上的运算

注意到集合并不能被定义这一事实（Russell悖论），我们以描述性语言来表述集合：在一定范围内拥有某种性质的对象全体，记作$A=\{a_1, a_2, ..., a_n\}$，自然地，也有无限集合，例如自然数集$\mathbb{N}=\{0, 1, 2, …\}$。为简便，我们通常将集合以如下形式记：

$$A = \{x:P(x)\}$$

其中$P(x)$表示对象$x$满足性质$P$。也可记为$A=\{x|P(x)\}$，为了保持与书中记号的一致性，在此一律采用冒号的记法。接下来引入集合的一些基本公理和概念。若对象$x$是集合$A$中的元素，我们称$x$属于$A$，记为$x\in A$；反之，若$x$不是$A$中的元素，我们称$x$不属于$A$，记为$x\notin A$

外延公理 两个集合相等当且仅当（if and only if，常常简记为 iff ）它们拥有相同的元素

集合的交、并、差 给定两集合$A$和$B$，定义它们的交集$A\cap B$、并集$A\cup B$和差集$A - B$如下

$$\begin{align*} A\cap B &:= \{x:x\in A~并且~x\in B\}\\ A\cup B &:= \{x:x\in A~或者~x \in B\} \\ A- B &:= \{x:x\in A~但是~x\notin B\} \\ \end{align*}$$

处于于自然语言的模糊性，在此对以上三个定义中出现的自然语言进行规定：$A$并且$B$表示$AB$同时为真；$A$或者$B$表示$AB$中至少一个为真。

子集、幂集和空集 若$A$是一个集合，其中的一部分元素可以构成新的集合$B$，称$B$是$A$的一个子集，记作$B \subset A$，显然有$A\subset A$；当存在一个$A$中的对象$x$不在子集$B$中时，称$B$是$A$的真子集，记为$B \subsetneq A$。对于一个集合$A$，可以定义其所有子集构成的集合，称为$A$的幂集，记作$\mathcal P(A)$。存在一个特殊的集合称为空集，记作$\emptyset$，它不包含任何一个元素。

注意 在证明两个集合$A$和$B$相等时，我们通常不直接采用外延公理，而是选择证明$A\subset B$并且$B\subset A$，从而得出$A=B$的结论

练习 证明：空集$\emptyset$是任意集合$A$的子集。

证明 注意到某集合$B$是集合$A$的子集的判定标准：

$$对任意的~x\in B，都有~x\in A$$

但空集中不含有任何元素，即上述推断的前提永不成立。根据 “不成立的论断可以推出一切” 的原则，我们称上述推断是虚真（Vacuously True）的。

事实上，若定义有一个从$A$到$B$的箭头$A \rightarrow B$意为$A\subset B$，空集可以是这样一个集合作为对象的范畴（Category）上的一个始对象（Initial Object）。

2.2 集族

集族 若某集合$\mathcal{F}$的元素也是集合，则称这是一个集合族，简称集族

集族的一般并和一般交 对于集族$\mathcal{F}$，定义其上的一般交$\bigcap\mathcal{F}$（非空集）和一般并$\bigcup\mathcal{F}$如下

$$\begin{align*}\\ \bigcap\mathcal{F} &:= \{x:至少存在一个~F \in \mathcal{F}，x \in F\}\\ \\ \bigcup\mathcal{F} &:= \{x:对所有~F\in \mathcal{F}，x\in F\} \\ \end{align*}$$

注意 空集的一般并还是空集，因为空集的一般并中的元素满足：对所有$F\in \emptyset$，有$x \in F$，而空集中没有元素（不存在$F\in \emptyset$），因此这是虚真的。然而空集的一般交不可定义，这是因为如果定义了空集的一般交，这意味着命题 “对所有$F\in \mathcal{F}$，$x\in F$” 永远为真，而这是不允许的，因为包含所有对象的集合是一个矛盾的概念（那么这样的集合是否包含它自己呢）。

对于某一些无限集族（事实上，是可数的集族）我们需要定义一个指标映射$f: \mathbb{N} \rightarrow F\in \mathcal{F}$，并将$f(i)$简记为$F_i$。这样一来，子集可以像自然数一样被排序的集族 可以表示为$\mathcal{F} = \{F_i:i\in \mathbb{N}\}$。当然，有限集族也可以像这样标注，如$\mathcal{F}=\{F_1,…, F_n\}$。像这样的有限集族中的一般并和一般交也可以表示为

$$\bigcap_{i=1}^n F_i, ~\bigcup_{i=1}^n F_i$$

类似地，上面提到的无限集族的一般并和一般交也可以写为

$$\bigcap_{i\in\mathbb{N}} F_i, ~\bigcup_{i\in\mathbb{N}} F_i$$

习题 1.2

1.2.3 找出至少$3$个性质$P$，使得$\{x\in \mathbb{R}:P(x)\}=\{1\}$；找出三个性质$P$，使得$\{x\in \mathbb{Z}:P(x)\}=\emptyset$。这里$\mathbb{R}$表示实数集，$\mathbb{Z}$表示整数集

对于第一个问题，考虑如下的$P$：

$$\begin{align*} P_1 &: x^2=-1.\\ P_2 &: 对所有~r\in \mathbb{R}，有rx = xr = x.\\ P_3 &: x~是所有正整数的因子集合的一般交的元素. \end{align*}$$

对于第二个问题，考虑如下的$P$：

$$\begin{align*} P_1 &: 2x=1.\\ P_2 &: x^2=2.\\ P_3 &: x^2=-1. \end{align*}$$

1.2.4 尝试分别寻找满足下列条件的集合，若没有这样的集合，说明理由：

1. 两个无穷集合$A$和$B$，使得$A\cap B=\{1\}$且$A\cup B=\mathbb{Z}$
2. 两个集合$C$和$D$，使得$C\cup D=\{t,h,i,c,k\}$且$C\cap D=\{t,h,i,n\}$

对于第一个问题，考虑$A = \mathbb{N}-\{0\}$和$B = \{-x:x\in \mathbb{N}\}$。

对于第二个问题，根据并集和交集的定义，注意对所有的$C$和$D$，都有$C\cap D \subset C\cup D$；而在条件中存在$i\in C\cap D$但$i \notin C\cap D$，因此不存在满足条件的$C$和$D$。

3 关系

3.1 二元关系

$n$-元组 给定集合$A$，定义函数$f:\{1,…,n\} \rightarrow A$，这样的$f$确定了$A$上的$n$个元素$f(1), f(2), …, f(n)$。将$f(i)$简记为$a_i$，这些由$f$确定的对象称之为集合$A$上的一个$n$-元组，简记为$(a_1, ..., a_n)$

两个集合的 Cartesian 积 给定两个集合$X$和$Y$，定义$X\times Y = \{(x, y):x\in X, y \in Y\}$。多数情况下，若$X = Y$，则可将$X\times Y$简记为$X^2$（需要注意的是，在一些特殊情况下，当形如$X^2$这样的集合已有其定义时，这样的简记法有时并不正确）

二元关系 集合$R$是集合$X$和$Y$的Cartesian积的子集，我们称$R$是集合$X$和$Y$之间的一个二元关系。若$(x, y)\in R$我们称元素$x$和$y$具有关系$R$，简记为$xRy$

注 若$X=Y$，我们称$R$是$X$上的一个二元关系

例 1.3.1 定义整数集合$\mathbb{Z}$上的一个整除关系$R = \{(m, n) \in \mathbb{Z} \times \mathbb{Z}: m|n\}$

3.2 关系的相关定义

定义域 一个关系$R$的定义域（Domain）定义为$\mathrm{dom}(R) = \{x:存在~y~使得~xRy\}$

值域 一个关系$R$的值域（Range）定义为$\mathrm{ran}(R) = \{y:存在~x~使得~xRy\}$

像 集合$X$在关系$R$下的像（Image）定义为$R[X] = \{y\in \mathrm{ran}(R): 存在~x\in X~使得~xRy\}$

逆像 集合$Y$在关系$R$下的逆像（Pre-Image）定义为$R^{-1}[Y] = \{x\in \mathrm{dom}(R): 存在~y\in Y~使得~xRy\}$

关系的复合 集合$X$和$Y$之间的关系$R$和集合$Y$和$Z$之间的关系$S$可以进行复合（Composition），定义为

$$S\circ R:=\{(x, z)\in X\times Z:存在~y\in Y~使得~xRy~且~yRz\}$$

例 1.3.2 考虑一下关系

1. 相等关系 $R=\{(x, y)\in \mathbb{R}^2:x=y\}$ 有$R\circ R = R$，$R^{-1} = R$

2. 若$R=\{(x, y)\in \mathbb{R}^2:y = \sqrt x\}$，有$R^{-1} = \{(y, x)\in\mathbb{R}^2:y = x^2~并且~x\geqslant 0\}$

3. 偏序关系$\leqslant := \{(x, y)\in \mathbb{R}^2:x<y~或者~x=y\}$和$\leqslant := \{(x, y)\in \mathbb{R}^2:x>y~或者~x=y\}$，可以验证

   $$\begin{align*} \leqslant \circ \geqslant &= \{(x, z)\in\mathbb{R}:存在~y\in\mathbb{R}~使得~x \geqslant y~且~y\leqslant z\}=\mathbb{R}^2\\ \leqslant \circ \leqslant &= \{(x, z)\in\mathbb{R}:存在~y\in\mathbb{R}~使得~x \leqslant y~且~y\leqslant z\} = \leqslant \end{align*}$$

4. 同余关系。对于整数$x$，$y$和正整数$n$，如果$n|(x-y)$，则称$x$与$y$关于模$n$同余，记为$x\equiv y~(\mathrm{mod}~n)$

3.3 $n$元关系

$n$个集合的Cartesian积 给定$n$个集合$X_1,…,X_n$，定义它们的Cartesian积

$$X_1\times\cdots\times X_n := \{(x_1, ..., x_n):x_i \in X_i, i=1,...,n\},$$

通常也将$\underbrace{X\times\cdots \times X}_{n次}$记为$X^n$

$n$元关系 若集合$R\subset X_1\times\cdots\times X_n$，则称$R$是一个$n$元关系

限制和扩张 若$R$是$X$上的一个$n$元关系，集合$Y$是$X$的子集，称$R’=R\cap Y^n$是关系$R$在集合$Y$上的限制；相反地，称关系$R$是关系$R'$在集合$X$上的扩张。

习题 1.3

1.3.2 假定$a,b,c,n\in \mathbb{Z}$，且$n>0$，证明同余关系的下列性质

1. （自反性）$a\equiv a~(\mathrm{mod}~n)$
2. （对称性）若$a\equiv b~(\mathrm{mod}~n)$，则$b\equiv a~(\mathrm{mod}~n)$
3. （传递性）若$a\equiv b~(\mathrm{mod}~n)$且$b\equiv c~(\mathrm{mod}~n)$，则$a\equiv c~(\mathrm{mod}~n)$

在第五节将会看到，这样的同余关系是正整数集$\mathbb{Z}$上的一个等价关系。

对于1，显然有$n | (a - a)$

对于2，有$n | (a - b)$，所以$n | -(a-b) \Longleftrightarrow n | (b-a)$

对于3，有$n|(a-b)$，$n|(b-c)$，于是$n | (a-b) + (b-c) \Longleftrightarrow n| (a-c)$

其中$\Longleftrightarrow$是等价 (Equivalent)的意思。

1.3.3 判断下列命题是否对任意的集合$A,B,C,D$均成立。若成立，给出证明；若不成立，给出反例

1. $$A\times(B \cup C) = (A \times B) \cup (A \times C)$$
2. $$(A\times B) \cap (C\times D) = (A \cap C) \times (B \cap D)$$
3. $$(A\times B) \cup (C\times D) = (A \cup C) \times (B \cup D)$$

对于1，左侧有$A\times (B \cup C) = \{(x, y) : x\in A~并且~y \in (B \cup C)\}$，而右侧$(A \times B) \cup (A \times C) = \{(x, y) | (x \in A~并且~y \in B)~或者~(x\in A~并且~y \in C)\}$容易看出这两个集合中元素所满足的性质$P$相同，因此这两个集合相等

对于2，类似的方法也可以判定两个集合相同

对于3，考虑$A =B = \{0\}, C = D = \{1\}$，则有$(A\times B) \cup (C\times D) = \{(0, 0), (1, 1)\}$而$(A \cup C) \times (B \cup D) = \{(0, 0), (0, 1), (1, 0), (1, 1)\}$。从而两个集合并不相等。通过使用1的结论，我们也可以直接计算：

$$\begin{align*} (A \cup C) \times (B \cup D) &= \Big( (A \cup C) \times B\Big) \bigcup \Big((A \cup C) \times D\Big)\\ &= (A\times B) \cup (C\times B) \cup (A\times D) \cup (C\times D) \end{align*}$$

可以看出右侧的结果相比于左侧多出了两项，类似的现象也出现在双线性函数 (Bi-linear Functions)中：

$$f(a+b, c+d) = f(a, c) + f(a, d) + f(b, c) + f(b, d)$$

而不是$f(a+b, c+d) = f(a, c) + f(b, d)$。

4 函数

4.1 函数的定义

考虑二元关系的一个特例$f$，它满足若$(x, y) \in f, (x, z)\in f$则$y = z$，也即一个$x$不能对应两个$y$。我们称这样的关系是一个函数 (Function)。对于关系中的$(x, y)$，我们常常将其写为$f(x) = y$或者$f: x\mapsto y$，并称$y$为$f$在$x$处的值。如果$\text{dom}(f) = X$，$\text{ran}(f) \subset Y$，称$f$是$X$到$Y$的函数，记为

$$f: X\rightarrow Y$$

例 1.4.1

1. 实数集上的不与$\mathrm{y}$轴垂直的直线表示一个函数，而实数集上的序关系$\leqslant$不是函数。

2. 对于任意集合$X$，定义其上的恒同函数 (Identity Function)

   $$\begin{align*} \mathrm{id}_X : X &\rightarrow X\\ x &\mapsto x \end{align*}$$

定理 1.4.2 两个函数$f$和$g$相等，当且仅当两函数的定义域相等，且对于定义域中的每一个元素，函数值都相等。

我们当然可以将函数定义在有有限个集合的Cartesian积得到的集合之上，得到多元函数 (Multi-variable Functions)：

$$\begin{align*} f: X_1\times X_2 \times \cdots \times X_n &\rightarrow Y\\ (x_1, x_2, ..., x_n) &\mapsto f(x_1, x_2, ..., x_n) \end{align*}$$

我们也可以将函数的像所在的集合写为多个集合的Cartesian积，从而定义更加复杂的函数。一个典型的例子就是复数域上的恒同函数：

$$\begin{align*} \mathrm{id}_\mathbb{C}: \mathbb{C} &\rightarrow \mathbb{C}\\ x + y\,\mathrm{i} & \mapsto x + y\,\mathrm{i} \end{align*}$$

在此复数域$\mathbb{C}$可以看作是在$\mathbb{R}^2$上赋予复数加法和乘法运算的结构。

定理 1.4.3 若$f$和$g$是函数，则他们的复合$g \circ f$也是函数，其定义域为$f^{-1}\big[\text{dom}(g)\big]$，且对于其定义域中所有的$x$，有$(g\circ f)(x) = g(f(x))$

这个定理显然成立。

4.2 函数的一般性质

单射、满射和一一对应

• 若函数$f: X \rightarrow Y$满足对于不同的$x_1, x_2$，有$f(x_1) \ne f(x_2)$，或者$f(x_1) = f(x_2)$时只有$x_1=x_2$，则称函数$f$是单射 (Injective) 或一一的 (One-one)
• 若函数$f:X\rightarrow Y$满足对于所有的$y \in Y$，其逆像$f^{-1}[\{y\}] \ne \emptyset$，即每一个$Y$中的元素都有一个$X$中的元素与之对应，则称函数$f$是满射 (Surjective)的
• 若函数$f$既是单射又是满射，则称函数$f$是一个双射 (Bijective)或一一对应 (One-one correspondence)

拓展和限制

• 给定函数$f: X\rightarrow Y$，若$A\subset X$，我们定义$f$在$A$上的限制

  $$\begin{align*} f|_A: A &\rightarrow Y\\ a &\mapsto f(a) \end{align*}$$

• 若$g$为$f$的一个限制，我们称$f$是$g$的一个扩展

习题 1.4

1.4.1 若$A$的元素个数为$m$，$B$的元素个数为$n$，$A$到$B$的函数有多少个？

1.4.4 给定函数$f: X\rightarrow Y$，判断下列命题是否正确

1. $f$是满射当且仅当任何一个$Y$中的元素都是某个$X$中元素的像
2. $f$是满射当且仅当任何一个$X$中的元素都有某个$Y$中的元素是它的像
3. $$f$$是满射当且仅当对任何$$y \in Y$$都存在$$x \in X$$使得$$f(x)=y$$
4. $$f$$是满射当且仅当对任何$$x \in X$$都存在$$y \in Y$$使得$$f(x)=y$$
5. $$f$$是满射当且仅当存在$$y \in Y$$对任意$$x \in X$$都有$$f(x) = y$$
6. $$f$$是满射当且仅当$$\text{ran}(f) = Y$$

1.4.5 $f$和$g$是$\mathbb{R}$上的函数，判断下列命题是否正确

1. $$\{x|f(x)=0\} \cap \{x|g(x) = 0\} = \{x|f^2(x) +g^2(x) = 0\}$$
2. $$\{x|f(x)=0\} = \{x|f^2(x)=0\}$$
3. 若$f$和$g$都是双射，则$f+g: x \mapsto f(x)+g(x)$也是双射

1.4.6

1. 证明对任意$\mathbb{R}$上的函数$f$和$g$，若$f\circ g$是单射，则$g$也是单射
2. 找出函数$f,g: \mathbb{R} \rightarrow \mathbb R$，使得$f\circ g$是单射，但$f$不是单射

1.4.7 给定函数$f: X\rightarrow Y$，定义函数

$$\begin{align*} F: \mathcal{P}(X) &\rightarrow \mathcal{P}(Y)\\ A\subset X &\mapsto f(A)\\\\ G: \mathcal{P}(X) &\rightarrow \mathcal{P}(Y)\\ B\subset Y &\mapsto f^{-1}(B)\\ \end{align*}$$

判断下列说法是否正确：

1. 若$f$是单射，则$F$也是单射
2. 若$f$是满射，则$G$也是满射

1.4.11

1. 找出实数域上的开区间$(0, 1) := \{x \in \mathbb{R}|0 <x <1\}$和$\mathbb{R}$之间的一个双射
2. 找出有理数域上的开区间$(0, 1)$到有理数域上的闭区间$[0,1] := \{x \in \mathbb{Q}|0 \leqslant x \leqslant 1\}$上的一个双射
3. 找出$\mathbb{N}$到$\mathbb{N}\times\mathbb{N}$上的一个双射

5 等价关系与划分

5.1 等价关系

5.2 划分

6 序

6.1 全序

6.2 偏序

7 结构的例子

7.1 域

7.2 环

7.3 Peano公理