边角情况 (Corner Cases) 和等价定义

学习数学必然要面对边角情况和等价定义 (甚至是并非等价而存在着微妙不同的定义), 这总是令我异常烦躁.

例子. 空集

\emptyset

可以被视为一个拓扑空间, 其上装备的拓扑必然是

{\emptyset}

命题. 对于群

G

的子群

H

, 如果

1_{G}

是

G

的幺元,

1_{H}

是

H

的幺元, 那么

1_{G} = 1_{H}

证明.

1_{H} 1_{H} = 1_{H} = 1_{H} 1_{G}

根据消去律,

1_{H} = 1_{G}

◻

算术

定理. 对于

a, b \in ℕ

且

b \neq 0

, 如果

r

是

a

除以

b

的余数, 那么

\gcd (a, b) = \gcd (b, r)

证明. 作带余除法,

a = q b + r

. 因为

\gcd (b, r) | b

且

\gcd (b, r) | r

, 所以

\gcd (b, r) | q b + r

, 即

\gcd (b, r) | a

. 于是,

\gcd (b, r)

是

a

和

b

的公因数, 可知

\gcd (b, r) \leq \gcd (a, b)

. 类似地,

\gcd (a, b) \leq \gcd (b, r)

. 因此,

\gcd (a, b) = \gcd (b, r)

◻

代数

定义. 给定集合

X

和一个集合上的运算

⁎

, 那么

(X, ⁎)

被称为一个熔岩 (magma).

定义. 给定熔岩

(X, ⁎)

, 对于

e \in X

, 称

e

是熔岩的单位元, 如果对于每个

x \in X

有

e ⁎ x = x ⁎ e = x

定理. 如果熔岩

(X, ⁎)

具有一个单位元, 那么熔岩的单位元是唯一的.

证明. 如果

e_{1}

和

e_{2}

是

X

的单位元, 那么

e_{1} = e_{1} ⁎ e_{2} = e_{2} .

◻

定理. 给定具有单位元的结合熔岩

(X, ⁎)

, 如果

x \in X

具有一个逆元, 那么这个逆元就是唯一的.

证明. 设

e

是

X

的单位元, 设

y

和

z

都是

x

的逆, 那么

y = y ⁎ e = y ⁎ (x ⁎ z) = (y ⁎ x) ⁎ z = e ⁎ z = z .

◻

定义. 我们称具有单位元的结合熔岩为幺半群 (monoid).

定义. 对于具有单位元的结合熔岩, 如果其每个元素均可逆, 那么就将其称为群 (group).

定理 (Cayley-Hamilton). 令

T

是有限维向量空间

V

上的一个线性算子. 如果

f

是

T

的特征多项式, 那么

f (T) = 0

. 换言之, 极小多项式整除特征多项式.

证明. 设

{α_{1}, \dots, α_{n}}

是

V

的一个有序基, 而

A

是

T

在此有序基下的矩阵表示. 令

B = x I - A

, 这是多项式环上的矩阵. 另外, 设

f

是

T

的特征多项式, 那么我们知道

\det (B) = f

, 以及

B (adj B) = f I

. 根据

A

的定义, 我们知道

\sum_{i = 1}^{n} B_{i, j} (T) α_{i} = 0, 1 \leq j \leq n .

这里的

B_{i, j}

是一个多项式. 应用一个多项式于线性算子的结果是一个线性算子. 接着, 我们可以推出对于

k = 1, \dots, n

有

\begin{array}{rcl} 0 & = & {(adj B)}_{j, k} (T) (\sum_{i = 1}^{n} B_{i, j} (T) α_{i}) \\ = & \sum_{i = 1}^{n} {(adj B)}_{j, k} (T) B_{i, j} (T) α_{i} \\ = & \sum_{i = 1}^{n} [{(adj B)}_{j, k} B_{i, j}] (T) α_{i} \\ = & \sum_{i = 1}^{n} [B_{i, j} {(adj B)}_{j, k}] (T) α_{i} \end{array}

在

j

上求和, 我们得到

\begin{array}{rcl} 0 & = & \sum_{j = 1}^{n} \sum_{i = 1}^{n} [B_{i, j} {(adj B)}_{j, k}] (T) α_{i} \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{n} [B_{i, j} {(adj B)}_{j, k}] (T) α_{i} \\ = & \sum_{i = 1}^{n} (\sum_{j = 1}^{n} [B_{i, j} {(adj B)}_{j, k}] (T)) α_{i} \\ = & \sum_{i = 1}^{n} (\sum_{j = 1}^{n} B_{i, j} {(adj B)}_{j, k}) (T) α_{i} \\ = & \sum_{i = 1}^{n} δ (i, k) (\det B) (T) α_{i} \\ = & \sum_{i = 1}^{n} δ (i, k) f (T) α_{i} \end{array}

分别令

k = 1, \dots, n

, 可得

f (T) α_{k} = 0, 1 \leq k \leq n

既然

{α_{1}, \dots, α_{n}}

是

V

的一个基, 而

f (T)

在基的每个向量上都为零, 那么

f (T)

本身肯定是一个零变换.

◻

定理. 对于域

F

的一个首项系数为一的多项式

f

, 设其素因子分解为

f = p_{1} \dots p_{k}

, 那么

p_{1}, \dots, p_{k}

互异当且仅当

f

和

f^{'}

互素.

证明. 设

p_{1}, \dots, p_{k}

互异. 若

f

和

f^{'}

不互素, 存在

i

使得

p_{i}

整除

f

和

f^{'}

. 令

f_{j} = f / p_{j}

, 那么

f^{'} = p_{1}^{'} f_{1} + \dots + p_{k}^{'} f_{k} .

对于

j \neq i

, 我们知道

p_{i}

整除

f_{j}

. 又因为

p_{i}

整除

f^{'}

, 所以

p_{i}

整除

p_{i}^{'} f_{i}

, 这等价于

p_{i}

整除

p_{i}^{'}

或

f_{i}

. 但是,

p_{i}

不可能整除

p_{i}^{'}

, 鉴于

p_{i}^{'}

的次数小于

p_{i}

的次数. 而且,

p_{i}

也不可能整除

f_{i}

, 鉴于

p_{1}, \dots, p_{k}

是互异的. 这就推导出了一个矛盾, 于是

f

和

f^{'}

必然是互素的.
反过来, 设

f

和

f^{'}

互素. 若

f

的素因子分解中出现重复的因子

p

, 那么存在多项式

h

使得

f = p^{2} h

, 于是

f^{'} = p^{2} h^{'} + 2 p p^{'} h = p (p h^{'} + 2 p^{'} h) .

因此,

p

也整除

f^{'}

, 但这与

f

和

f^{'}

矛盾. 换言之,

p_{1}, \dots, p_{k}

互异.
证明的最后, 我们想要澄清一下

f = 1

的极端情况. 此时,

f

的素因子分解应该理解为"空积", 因而互异的条件得到满足. 鉴于

1^{'} = 0

\gcd (1, 0) = 1

f

和

f^{'}

也是互素的. 我们看到, 即便是

f = 1

, 定理也是成立的.

◻

分析

定义.

ℝ

是具有最小上界性的有序域.

定义. 对于域

F

和其上的一个全序关系

\leq

, 如果

对于所有的 $x, y, z \in F$ , $x \leq y$ 可以推出 $x + z \leq y + z$ ;
对于所有的 $x, y \in F$ , $0 \leq x$ 和 $0 \leq y$ 可以推出 $0 \leq x y$ .

那么称带有这个序关系的域是一个有序域.

定理. 对于有序域

F

0 < 1

定理. 不能为

ℂ

赋一个序关系使其成为有序域.

定理. 对于

x, y \in ℝ

, 如果

x > 0

, 那么总存在

n \in ℕ

满足

n \cdot x > y

. 此即所谓的Archimedes公理.

证明. 对于集合

X = {n \cdot x | n \in ℕ}

, 若对于每个

n \in ℕ

有

n \cdot x \leq y

, 那么

y

就是集合

X

的上界. 显然

X

是非空的, 所以

X

有最小上界

y_{0}

. 对于每个

n \in ℕ

, 我们知道

(n + 1) \in ℕ

, 于是

(n + 1) \cdot x \leq y_{0}

, 即

n \cdot x \leq y_{0} - x

. 那么,

y_{0} - x

也是一个上界, 这与

y_{0}

是最小上界矛盾.

◻

定理. 嵌套区间公理.

定义. 给定集合

X

, 称

d : X \times X \to ℝ

是

X

上的度量, 如果

对于任意的 $x, y \in X$ , $d (x, y) \geq 0$ ;
对于任意的 $x, y \in X$ , $d (x, y) = 0 \Leftrightarrow x = y$ ;
对于任意的 $x, y \in X$ , $d (x, y) = d (y, x)$ ;
对于任意的 $x, y, z \in X$ , $d (x, y) + d (y, z) \geq d (x, z)$ .

如果

d

是

X

上的度量, 那么就称序对

(X, d)

是一个度量空间.

X

的子集继承了自然的度量结构而成为子空间. 在度量可以从上下文中推断出来的时候, 我们也说度量空间

X

而不是

(X, d)

定理. 给定度量空间

(X, d)

, 对于任意的

x_{1}, \dots, x_{n} \in X

d (x_{1}, x_{2}) + \dots + d (x_{n - 1}, x_{n}) \geq d (x_{1}, x_{n})

证明. 根据归纳即得.

◻

定理. 给定度量空间

(X, d)

, 对于任意的

x, y, z \in X

d (x, z) \geq | d (x, y) - d (y, z) |

定义. 给定度量空间

(X, d)

, 对于

x \in X

和

r > 0

, 定义开球

𝔹 (x, r) ≔ {y \in X | d (x, y) < r}

, 闭球

\overline{𝔹} (x, r) ≔ {y \in X | d (x, y) \leq r}

定义. 给定度量空间

(X, d)

, 对于

x \in X

, 称

U \subseteq X

是

x

的邻域, 如果存在

r > 0

满足

𝔹 (x, r) \subseteq U

定义. 给定集合

X

X

中的一个序列是一个类型为

ℕ \to X

的映射. 对于序列

x : ℕ \to X

, 对于

n \in ℕ

, 我们也将

x (n)

记作

x_{n}

定义. 给定度量空间

(X, d)

, 对于

X

中序列

x : ℕ \to X

, 如果存在

y \in X

满足对于每个

ε > 0

, 存在

N \in ℕ

, 对于每个自然数

n \geq N

有

d (x_{n}, y) < ε

, 那么就称

x

在

X

中收敛, 并以

y

为极限, 记作

lim_{n \to \infty} x_{n} = y

. 换言之, 序列

x : ℕ \to X

收敛于

y

当且仅当以

y

为中心的每个开球都包含序列的几乎所有项.

定义. 给定度量空间

(X, d)

, 对于

X

中序列

x : ℕ \to X

, 称其为Cauchy序列, 如果对于每个

ε > 0

, 存在

N \in ℕ

, 对于任意的

m, n \geq N

d (x_{m}, x_{n}) < ε

定理. 给定度量空间

(X, d)

, 对于

X

中序列

x : ℕ \to X

, 如果它收敛, 那么它是Cauchy序列.

定义. 对于序列

x : ℕ \to X

和严格单调递增映射

φ : ℕ \to ℕ

, 序列

x \circ φ : ℕ \to X

被称为序列

x : ℕ \to X

的子序列.

定理. 给定度量空间

(X, d)

, 对于序列

x : ℕ \to X

, 如果

lim_{n \to \infty} x_{n} = y

, 那么对于每个严格单调递增映射

φ : ℕ \to ℕ

有

lim_{k \to \infty} (x \circ φ) (k) = y

证明. 注意到对于每个

k \in ℕ

φ (k) \geq k

◻

定义. 对于序列

x : ℕ \to ℝ

, 我们将其称为实序列. 对于序列

x : ℕ \to ℂ

, 我们将其称为复序列.

定理. 对于单调递增的实序列

x : ℕ \to ℝ

, 如果其像

img (x)

有界, 那么该序列收敛, 并以

\sup img (x)

为极限.

定理. 对于实序列

x, y : ℕ \to ℝ

, 如果

lim_{n \to \infty} x_{n} = a

且

lim_{n \to \infty} y_{n} = b

, 那么序列

x + y : ℕ \to ℝ

收敛, 并且

lim_{n \to \infty} (x + y) (n) = a + b

定理. 对于实序列

x : ℕ \to ℝ

, 如果

lim_{n \to \infty} x_{n} = a

, 那么对于每个

k \in ℝ

, 序列

k x : ℕ \to ℝ

收敛, 并且

lim_{n \to \infty} (k x) (n) = k a

定理. 对于实序列

x, y : ℕ \to ℝ

, 如果

lim_{n \to \infty} x_{n} = a

且

lim_{n \to \infty} y_{n} = b

, 那么序列

x y : ℕ \to ℝ

收敛, 并且

lim_{n \to \infty} (x y) (n) = a b

定义. 对于实序列

x : ℕ \to ℝ

, 定义序列如下

S : ℕ \to ℝ, n \mapsto {\begin{matrix} x_{0} & , n = 0 \\ S (n - 1) + x_{n} & , n \geq 1 \end{matrix} .

序列

S

被称为序列

x

的部分和. 如果

S

收敛, 那么我们就称级数

\sum_{n = 0}^{\infty} x_{n}

收敛. 如果

lim_{n \to \infty} S_{n} = s

, 那么记

\sum_{n = 0}^{\infty} x_{n} = s

定理. 对于实序列

x, y : ℕ \to ℝ

, 如果对于每个

n \in ℕ

有

0 \leq x_{n} \leq y_{n}

并且级数

\sum_{n = 0}^{\infty} y_{n}

收敛, 那么

\sum_{n = 0}^{\infty} x_{n}

亦收敛, 并有

\sum_{n = 0}^{\infty} x_{n} \leq \sum_{n = 0}^{\infty} y_{n} .

证明. 级数

\sum_{n = 0}^{\infty} y_{n}

收敛的话, 说明其部分和有上界, 并且当然收敛至最小上界. 可以看出, 对于级数

\sum_{n = 0}^{\infty} x_{n}

而言, 有

\sum_{n = 0}^{k} x_{n} \leq \sum_{n = 0}^{k} y_{n} \leq \sum_{n = 0}^{\infty} y_{n}, k \in ℕ .

于是, 其部分和亦有上界, 且以

\sum_{n = 0}^{\infty} y_{n}

为一个上界. 而

\sum_{n = 0}^{\infty} x_{n}

又是最小上界, 故

\sum_{n = 0}^{\infty} x_{n} \leq \sum_{n = 0}^{\infty} y_{n}

◻

定义. 指数函数定义如下:

\exp : ℝ \to ℝ, x \mapsto \sum_{n = 0}^{\infty} \frac{x^{n}}{n!} .

定义. 给定度量空间

(X, d_{X})

和

(Y, d_{Y})

, 对于函数

f : X \to Y

, 称

f

于点

a \in X

连续, 如果对于每个以

f (a)

为中心的开球

B_{Y}

存在以

a

为中心的开球

B_{X}

满足

f (B_{X}) \subseteq B_{Y}

. 等价地, 把开球替换成开集或者邻域也可以.

良基关系

定义. 一个偏序集被称为良基 (well-founded) 的, 如果其每个非空子集都有极小元. 对于良基的偏序集, 我们可以施行良基归纳. 对于良基的偏序集

(X, \leq)

和性质

P

, 如果对于每个

x \in X

, 我们可以根据

\forall y \in X . y < x \Rightarrow P (y)

推出

P (x)

, 那么性质

P

对于每个

x \in X

均成立. 一种证明良基归纳正确性的方式是反证法. 对于满足良基归纳条件的性质

P

, 假设

X

中存在不满足

P

的元素, 那么这些元素构成了

X

的一个非空子集, 即

{x \in X | \neg P (x)}

. 根据良基的定义, 这个集合具有一个极小元. 对于所有小于这个极小元的元素, 我们知道其必然满足性质

P

, 因为这是极小的定义. 根据良基归纳的条件, 我们可以推出这个极小元也必然满足性质

P

, 那么这就导出了一个矛盾.

接下来抄一抄nlab, 这和传统意义上的良基关系还不太一样.

1. 想法

一个集合 $S$ 上的一个二元关系 $≺$ 是良基的, 如果在 $S$ 上我们可以对于 $≺$ 做归纳.

2. 定义

未归类

定理. 给定集合

A

和

B

以及函数

f : A \to B

, 那么

$f$ 左可逆当且仅当 $f$ 是单射且 $A$ 为空可以推出 $B$ 为空. (许多书籍的表述并不正确)
$f$ 右可逆当且仅当 $f$ 是满射. (这条需要选择公理)

定理. 在选择公理下, 升链条件等价于极大条件, 降链条件等价于极小条件 (良基关系).

定理. 对于函数

f : X \to Y

和

Y

中的集族

{(A_{i})}_{i \in I}

, 我们有

f^{- 1} (⋃_{i \in I} A_{i}) = ⋃_{i \in I} f^{- 1} (A_{i}) .

证明. 对于

x \in X

, 我们知道

x \in f^{- 1} (⋃_{i \in I} A_{i})

等价于

f (x) \in ⋃_{i \in I} A_{i}

等价于

\exists i \in I, f (x) \in A_{i}

等价于

\exists i \in I, x \in f^{- 1} (A_{i})

等价于

x \in ⋃_{i \in I} f^{- 1} (A_{i})

◻

命题. 对于实数

a > 0

, 定义序列

x_{0} = 1; x_{n + 1} = \frac{x_{n} + a / x_{n}}{2}

那么

lim_{n \to \infty} x_{n} = \sqrt{a} .

证明. 首先, 易知对于

n \in ℕ

x_{n} > 0

. 那么, 根据基本不等式, 我们有对于

n \in ℕ

x_{n + 1} \geq \sqrt{a}

. 对于

n \geq 1

, 现在

\begin{array}{rcl} x_{n + 1} - x_{n} & = & \frac{x_{n} + a / x_{n}}{2} - x_{n} \\ = & \frac{a - x_{n}^{2}}{2 x_{n}} \\ \leq & 0 \end{array}

换言之, 从第

1

项起, 序列单调递减. 既然序列单调递减有下界, 那么其就收敛于它的最大下界. 设这个序列收敛于

y

, 那么

lim_{n \to \infty} x_{n} = y = lim_{n \to \infty} x_{n + 1} = \frac{y + a / y}{2}

由此可知

y^{2} = a

. 另外, 我们知道

y \geq \sqrt{a}

, 故

y = \sqrt{a}

◻

吉米多维奇习题集

完全出于玩票的心态写一写, 鉴于对本科时期的怀念. 当时发现书上有很多错误, 这使我对于分析这一学科缺乏信心.

练习1.

1 + 2 + \dots + n = \frac{n (n + 1)}{2} .

证明.

对于正整数 $1$ , 命题平凡地成立, 即 $1 = \frac{1 (1 + 1)}{2} .$
如果命题对于正整数 $n$ 成立, 那么对于 $n + 1$ , 我们有 $\begin{array}{rcl} 1 + 2 + \dots + n + (n + 1) & = & \frac{n (n + 1)}{2} + (n + 1) \\ = & \frac{n (n + 1)}{2} + \frac{2 (n + 1)}{2} \\ = & \frac{(n + 2) (n + 1)}{2} \\ = & \frac{(n + 1) ((n + 1) + 1)}{2} \end{array}$ 换言之, 命题对于 $n + 1$ 也成立.

命题的成立可由归纳得到.

◻

练习2.

1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .

证明.

对于正整数 $1$ , 命题平凡地成立, 即 $1^{2} = \frac{1 (1 + 1) (2 \cdot 1 + 1)}{6} .$
如果命题对于正整数 $n$ 成立, 那么对于 $n + 1$ , 我们有 $\begin{array}{rcl} 1^{2} + 2^{2} + \dots + n^{2} + {(n + 1)}^{2} & = & \frac{n (n + 1) (2 n + 1)}{6} + {(n + 1)}^{2} \\ = & \frac{(n + 1) (2 n^{2} + n)}{6} + \frac{(n + 1) (6 n + 6)}{6} \\ = & \frac{(n + 1) (2 n^{2} + 7 n + 6)}{6} \\ = & \frac{(n + 1) (n + 2) (2 n + 3)}{6} \\ = & \frac{(n + 1) ((n + 1) + 1) (2 (n + 1) + 1)}{6} \end{array}$ 换言之, 命题对于 $n + 1$ 也成立.

命题的成立可由归纳得到.

◻

练习3.

1^{3} + 2^{3} + \dots + n^{3} = {(1 + 2 + \dots + n)}^{2} .

证明.

对于正整数 $1$ , 命题平凡地成立, 即 $1^{3} = 1^{2} .$
如果命题对于正整数 $n$ 成立, 那么对于 $n + 1$ , 我们有 $\begin{array}{rcl} 1^{3} + 2^{3} + \dots + n^{3} + {(n + 1)}^{3} & = & {(1 + 2 + \dots + n)}^{2} + {(n + 1)}^{3} \\ = & \frac{{(n + 1)}^{2} n^{2}}{4} + {(n + 1)}^{3} \\ = & \frac{{(n + 1)}^{2} n^{2}}{4} + \frac{{(n + 1)}^{2} (4 n + 4)}{4} \\ = & \frac{{(n + 1)}^{2} {(n + 2)}^{2}}{4} \\ = & {[\frac{(n + 1) ((n + 1) + 1)}{2}]}^{2} \\ = & {(1 + 2 + \dots + n + (n + 1))}^{2} \end{array}$ 换言之, 命题对于 $n + 1$ 也成立.

命题的成立可由归纳得到.

◻

练习5.

证明. 这题还挺有趣的, 因为我每次看到都要想一想, 但是只要动笔就会发现很简单.

◻

读书的地图

大致上记录了我读书的痕迹, 然而不甚完整. 仅是为了备忘.

分析学
1. Principles of Mathematical Analysis (Baby Rudin)
2. 微积分学教程 (菲赫金哥尔茨)
3. 数学分析习题集 (吉米多维奇)
4. Amann & Escher
5. Godement
6. An Introduction to Manifolds
7. Stein
8. Exercises in Analysis (Part I)
9. Treatise on Analysis (Dieudonné)
10. 无穷小计算 (Dieudonné)
代数学
1. Hoffman & Kunze
2. 代数学方法 (李文威)
3. Algebra: Chapter 0
4. Algebra (Bourbaki)
5. Godement
6. Introduction to Commutative Algebra
逻辑学
1. 集合论导引 (冯琦)
2. Set Theory (Kunen)
3. Beginning Mathematical Logic (Peter Smith)
4. Gödel Without (Too Many) Tears
5. Structural Proof Theory
6. An Introduction to Formal Logic (Peter Smith)
7. An Introduction to Inductive Definitions (Peter Aczel)
范畴论
1. Category Theory (Steve Awodey)
2. Category Theory in Context
3. Abstract and Concrete Categories
4. Topoi: The Categorial Analysis of Logic
编程语言
1. 程序设计
  1. SICP
  2. HtDP
  3. Concepts, Techniques, and Models of Computer Programming (我挺讨厌这本书的)
  4. ML for the Working Programmer
  5. Programming in Standard ML
  6. CMU 15-122 (Principles of Imperative Computation)
2. 一般性入门导引
  1. Essentials of Programming Languages
  2. Programming Languages: Application and Interpretation
  3. Lisp in Small Pieces
3. 一般性严肃导引
  1. TaPL
  2. PFPL
  3. Software Foundations
  4. PLFA
  5. The Formal Semantics of Programming Languages
  6. Semantics Engineering with PLT Redex (讲义形式为Programming Languages and Lambda Calculi)
  7. Domain-Theoretic Foundations of Functional Programming
4. 编译器构造
  1. Three Implementation Models for Scheme
  2. Compiling with Continuations
  3. P423 Assignments
  4. Essentials of Compilation
5. 证明助手
  1. The Little Typer
  2. Proofs and Types
  3. Lectures on the Curry-Howard Isomorphism
  4. HoTT
  5. The Little Prover
6. 部分求值
  1. Partial Evaluation and Automatic Program Generation
7. 抽象解释
8. 计算理论
  1. Computability and Complexity (Neil Jones)
9. (自然)语言学
  1. Continuations and Natural Language
10. 形式语言学(和句法分析)
  1. Parsing with Derivatives
  2. Parsing with Zippers
计算机硬件
1. Computation Structures
2. Foundations of Analog and Digital Electronic Circuits
物理学
1. 力学概论 (方励之)
2. Structure and Interpretation of Classical Mechanics