note-math

自然数 $ℕ$ 的加法

$𝑎$ 是数 $𝑎$ 次 $1$ , $𝑎 + 𝑏$ 是先数 $𝑎$ 次, 再数 $𝑏$ 次

结合律: $(𝑎 + 𝑏) + 𝑐 = 𝑎 + (𝑏 + 𝑐)$
交换律: $𝑎 + 𝑏 = 𝑏 + 𝑎$

Proof 在现实世界的直观是, 对于数数 $+ 1$ , 无论怎样把数数任务手动分成几个子任务, 都不会影响结果, 而且总的分解方式有限. 加法结合律和交换律只是其中的特殊情况. 就像我们通过数数来认识自然数一样, 我们总是可以通过数数认识交换律和结合律. 所有东西都 reduce to 完全加法分解的情况, 只有大量 $1$ 的交换律和结合律

对计算机来说似乎难以表达这种直观, 但似乎所有的有限结果一定会正确. 类似于 #link(<natural-number>)[自然数中所做的], 为了让计算机能用有限的字符和内存以及有限的时间 (以及潜在的无限时间) 去表达这种对所有自然数成立的性质, 需要定义它是 true proposition

Proof 在现实世界的直观是, 对于数数 $+ 1$ , 无论怎样把数数任务手动分成几个子任务, 都不会影响结果, 而且总的分解方式有限. 加法结合律和交换律只是其中的特殊情况

自然数 $ℕ$ 的乘法

$𝑎 \cdot 𝑏$ 是数 $𝑎$ 次的数 $𝑏$ 次

也满足交换律和结合律. 在现实世界的直观是 "二维和三维矩形", 对于数数 $+ 1$ , 无论分解成怎么样的 product 分解的子任务, 都不影响结果. 所以乘法交换律和结合律只是完全乘法分解 i.e. 素数分解的特殊情况, 而且总分解次数有限

自然数运算分配律

$(𝑎 + 𝑏) \cdot 𝑐 = 𝑎 \cdot 𝑐 + 𝑏 \cdot 𝑐$

直观是用二维矩形的边长的 sum 分解

整数 $ℤ$

数轴有两个方向

有理数 $ℚ$

$𝑛$ 等分操作, 乘法的逆 $\frac{1}{𝑛}$

不要混淆于 $ℕ, ℤ$ 的除, 余, 那是一个数 $𝑎$ 另一个数 $𝑏$ 的逐次减法, 而不是等分

实数 $ℝ$

实数的一种直观是长度

鉴于实数的直观性, 可以认为它存在, 用很多公理去定义实数 i.e. 假设 true proposition. 但也可以从有理数 "恢复" 实数

无理数的例子

代数整数 $algebraic-integer ≔ {𝑥 \in ℝ : (𝑥^{𝑛} + 𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} + \dots + 𝑎_{0} = 0) \land (𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛 - 1} \in ℤ)}$

代数整数里的 "整数" 是因为 $algebraic-integer \cap ℚ = ℤ$

Proof (p.43 of ref-8)

取 $𝑝, 𝑞 \in ℤ$ 互素. $𝑥 = \frac{𝑝}{𝑞}$ 代入方程, 乘 $𝑞^{𝑛}$

\begin{matrix} 𝑝^{𝑛} + 𝑎_{𝑛 - 1} 𝑞 𝑝^{𝑛 - 1} + \dots + 𝑎_{0} 𝑞^{𝑛} = 0 \\ 𝑝^{𝑛} = - 𝑞 (𝑎_{𝑛 - 1} 𝑝^{𝑛 - 1} + \dots + 𝑎_{0} 𝑞^{𝑛 - 1}) \end{matrix}

右边被 $𝑞$ 整除. 但 $𝑝, 𝑞$ 互素, 所以 $𝑞 = \pm 1$ 或 $𝑝 = \pm 1$ .

$𝑝 \neq \pm 1 ⟹ 𝑞 = \pm 1$

$𝑝 = \pm 1 ⟹ \pm 1 = 𝑝^{𝑛} = 𝑞 \cdot some-integer ⟹ 𝑞 = \pm 1$

从而 $𝑞 = \pm 1$ . 从而 $𝑥 = \pm 𝑝 \in ℤ$

特殊情况 ${𝑥 \in ℚ : 𝑥^{2} - 2 = 0}$ . 但是 ${(\pm 1)}^{2} = 1$ 且 $| 𝑥 | \geq 2 ⟹ | 𝑥 |^{2} \geq 4$

所以 ${𝑥 \in ℚ : 𝑥^{2} - 2 = 0} = \emptyset$ 即 $\sqrt{2}$ 不是有理数

代数数 $algebraic-number ≔ {𝑥 \in ℝ : (𝑎_{𝑛} 𝑥^{𝑛} + 𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} + \dots + 𝑎_{0} = 0) \land (𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛} \in ℤ)}$

注意不要求 $𝑎_{𝑛} = 1$ , 不限制 $𝑥 \in ℚ$ , 包含所有有理数 $\frac{𝑝}{𝑞}$ , 部分无理数 e.g. $\sqrt{2}$

代数数 $algebraic-number$ 是可数集, 实数 $ℝ$ 是不可数集

超越数 $transcendental-number ≔ ℝ ∖ algebraic-number \neq \emptyset$ . $𝑒, 𝜋$ 是超越数

十进制, 二进制 vs 区间套 vs 分割

十进制 (区间套) 似乎很直观

然而十进制并不能原生地处理 $𝑒 = \sum_{𝑛 = 0}^{\infty} \frac{1}{𝑛!}$

很多不同 $ℕ$ 区间套有相同极限, e.g. $[0, \frac{1}{𝑛}]$ vs $[- \frac{1}{𝑛}, 0]$ , 需要 limit-distance-vanish 系 quotient. let $distance (𝐴) = \sup_{𝑥, 𝑥^{'} \in 𝐴} | 𝑥 - 𝑥^{'} |$

let $𝐴_{0} \supset 𝐴_{1} \dots, 𝐵_{0} \supset 𝐵_{1} \dots$ and $lim_{𝑛 \to \infty} distance (𝐴_{𝑛}), distance (𝐵_{𝑛}) = 0$ , limit-distance-vanish 关系 (alias Cauchy 收敛)

\forall (𝜀 \in ℚ) \land (𝜀 > 0), \exists 𝑁 \in ℕ, \forall 𝑛, 𝑚 > 𝑁, distance (𝐴_{𝑛} \cup 𝐵_{𝑚}) < 𝜀

可以把 $ℕ$ 有理数区间套改为一般的长度 #link(<hom-limit>)[极限] 趋于零的有理数区间 $\subset$ #link(<maximal-linear-order>)[线序链] 或者更一般的长度趋于零的有理数区间 (极大的) #link(<net>)[网]

有理数区间是子集 $𝐴 \subset ℚ$ with property 序不中断

\underset{\begin{matrix} 𝑎, 𝑏 \in 𝐴 \\ 𝑎 < 𝑏 \end{matrix}}{⋀} \underset{\begin{matrix} 𝑐 \in ℚ \\ 𝑎 < 𝑐 < 𝑏 \end{matrix}}{⋀} 𝑐 \in 𝐴

从操作简单性来说, 应该用 Dedekind-cut. "操作简单" 是指

let $𝑥 \in ℝ$ , ${𝑥} \leftrightarrow ℝ ∖ {𝑥}$ 一一对应
$(ℝ ∖ {𝑥}) \cap ℚ = ℚ ∖ {𝑥} = ℚ_{< 𝑥} ⊔ ℚ_{> 𝑥}$
所以 $𝑥 \in ℝ$ 和 $ℚ_{< 𝑥} ⊔ ℚ_{> 𝑥}$ 一一对应

Dedekind-cut_(tag) 无理数 $ℝ ∖ ℚ$

$𝑥 \in ℝ ∖ ℚ$ 一一对应到 ${(𝐴, 𝐵) \in {Subset (ℚ)}^{2} : (ℚ = 𝐴 ⊔ 𝐵) \land (\forall (𝑎, 𝑏) \in (𝐴, 𝐵), 𝑎 < 𝑏)}$

$𝑥 ≔ (𝐴, 𝐵)$ . 将 $(𝐴, 𝐵)$ 重新记为 $(ℚ_{< 𝑥}, ℚ_{> 𝑥})$

实数 $ℝ ≔ ℚ ⊔ (ℝ ∖ ℚ)$

order-real_(tag) $ℝ$ 序 $𝑥 < 𝑦 ⟺ (ℚ_{< 𝑥} ⊊ ℚ_{< 𝑦})$

let

\begin{matrix} 𝐴 + 𝐴^{'} ≔ {𝑎 + 𝑎^{'} : (𝑎, 𝑎^{'}) \in (𝐴, 𝐴^{'})} \\ 𝐴 \cdot 𝐴^{'} ≔ {𝑎 \cdot 𝑎^{'} : (𝑎, 𝑎^{'}) \in (𝐴, 𝐴^{'})} \end{matrix}

add-real_(tag) $ℝ$ 加法. let $𝑥, 𝑦 \in ℝ$

\begin{matrix} 𝑥 + 𝑦 & ≔ & (ℚ_{< 𝑥} + ℚ_{< 𝑦}, ℚ_{> 𝑥} + ℚ_{> 𝑦}) & expect (ℚ_{< 𝑥 + 𝑦}, ℚ_{> 𝑥 + 𝑦}) \\ - 𝑥 & ≔ & (- ℚ_{> 𝑥}, - ℚ_{< 𝑥}) & expect (ℚ_{< - 𝑥}, ℚ_{> - 𝑥}) \end{matrix}

由于 $< 0$ 的存在, 乘法不保持序. 但是 $ℚ_{> 0}, ℝ_{> 0}$ 的乘法保持序. 先处理 $> 0$ 的情况, 再用反射 $- 𝑥$ 得到 $< 0$ 的情况

multiply-real_(tag) $ℝ$ 乘法. let $𝑥, 𝑦 > 0$

\begin{matrix} 𝑥 \cdot 𝑦 & ≔ & (ℚ_{(0, 𝑥)} \cdot ℚ_{(0, 𝑦)}, ℚ_{(𝑥, \infty)} \cdot ℚ_{(𝑦, \infty)}) & expect (ℚ_{(0, 𝑥 𝑦)}, ℚ_{(𝑥 𝑦, \infty)}) \\ \frac{1}{𝑥} & ≔ & (\frac{1}{ℚ_{(𝑥, \infty)}}, \frac{1}{ℚ_{(0, 𝑥)}}) & expect (ℚ_{(0, \frac{1}{𝑥})}, ℚ_{(\frac{1}{𝑥}, \infty)}) \end{matrix}

$ℤ, ℚ, ℝ$ 的 $+, \cdot$ 都有结合律, 交换律, 分配律

$ℝ$ 完备性 completeness-real_(tag)

exact-bound_(tag) 确界原理

let $𝐴 \subset ℝ$ 有上界

$\exists 𝑥 \in ℝ, ⋃_{𝑎 \in 𝐴} ℚ_{< 𝑎} = ℚ_{< 𝑥}$

上确界 $\sup 𝐴 ≔ 𝑥$

$\forall 𝑎 \in 𝐴, 𝑎 \leq \sup 𝐴$
$\forall 𝜀 > 0, \exists 𝑎 \in 𝐴, \sup 𝐴 - 𝜀 < 𝑎 \leq \sup 𝐴$

monotone-convergence_(tag) 单调有界 #link(<limit-sequence-real>)[收敛] Proof use 确界原理

nested-closed-interval-theorem_(tag) 闭区间套定理

无论是

ℕ

区间套还是

\subset

线序链区间套, 线序意味着区间端点单调性, 对端点用上确界

𝑎_{1}

下确界

𝑎_{0}

with

𝑎_{0} \leq 𝑎_{1}

得到闭区间套交集是闭区间

[𝑎_{0}, 𝑎_{1}] \neq \emptyset

[𝑎_{0}, 𝑎_{1}]

可以理解为

\subset

线序链区间套的最小元

closed-interval-net-theorem_(tag) 闭区间 #link(<net>)[网] $B$ 交集非空 $⋂ B \neq \emptyset$

Proof

对网 $B$ 补充所有的有限交集

取一个 #link(<maximal-linear-order>)[极大线序链] $C$ . 由闭区间套定理, 其交集是非空闭区间 $⋂ C \neq \emptyset$

由 $C$ 的线序极大性, 直觉上, 闭区间 $⋂ C$ 将小于所有 $B$ 的闭区间, 从而 $⋂ C \subset ⋂ B$

$\forall 𝐵 \in B$ , 我们证明 $⋂ C \subset 𝐵$

定义闭区间线序链 $C_{𝐵} = {𝐵 \cap 𝐶 \in B : 𝐶 \in C}$ . $𝐵 \cap 𝐶 \subset 𝐵$ . 我们证明 $⋂ C_{𝐵} = ⋂ C$

反证法. 假设 $⋂ C_{𝐵} ⊊ ⋂ C$ . 那么 $⋂ C_{𝐵}$ 的小/大端点大/小于 $⋂ C$ 的小/大端点

$\subset$ 线序链满足 $⋂_{𝐴 \supset 𝐴_{0}} 𝐴 = 𝐴_{0}$

如果闭区间 $⋂ C_{𝐵} \notin B$ , 那么对端点使用 $ℝ$ 确界原理

\begin{matrix} \exists 𝐵 \cap 𝐶_{0} \in C_{𝐵} \\ 𝐵 \cap 𝐶_{0} \in B \\ 𝐵 \cap 𝐶_{0} = ⋂_{𝐵 \cap 𝐶 \supset 𝐵 \cap 𝐶_{0}} 𝐵 \cap 𝐶 ⊊ ⋂ C \end{matrix}

存在 $𝐵 \cap 𝐶_{0} \in B$ 属于 $⋂ C$ , 矛盾于 $⋂ C$ 是 $\subset$ 极大线序链

如果闭区间 $⋂ C_{𝐵} \in B$ , 同理矛盾

let $𝑎_{𝑛} : ℕ \to ℝ$

def $ℕ \to ℝ$ 序列 $𝑘 ⇝ \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}}$ 单调递减, $𝑘 ⇝ \inf_{𝑘 \geq 𝑛} {𝑎_{𝑘}}$ 单调递增

limsup_(tag) 上极限

\underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} ≔ lim_{𝑛 \to \infty} \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}} = \inf_{𝑛 \in ℕ} \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}}

liminf_(tag) 下极限

\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} ≔ lim_{𝑛 \to \infty} \inf_{𝑛 \geq 𝑘} {𝑎_{𝑘}} = \sup_{𝑛 \in ℕ} \inf_{𝑛 \geq 𝑘} {𝑎_{𝑘}}

Example

$𝑎_{𝑘} = 1 + \frac{1}{𝑘}$
$\begin{matrix} \sup_{𝑛 \in ℕ} {𝑎_{𝑛}} & = & 2 \\ \sup_{𝑛 \geq 𝑘} {𝑎_{𝑘}} & = & 1 + \frac{1}{𝑘} \\ lim_{𝑛 \to \infty} \sup_{𝑛 \geq 𝑘} {𝑎_{𝑘}} & = & 1 \end{matrix}$
$𝑎_{𝑘} = 1 + {(- 1)}^{𝑘}$
$\underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} = 2$

对于 $ℕ$ 序列定义 $distance {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} ≔ \sup_{𝑚, 𝑚^{'} \geq 𝑛} | 𝑎_{𝑚} - 𝑎_{𝑚^{'}} |$

对于一般 net 定义 $distance (𝐵) = \sup_{𝑎, 𝑎^{'} \in 𝐵} | 𝑎 - 𝑎^{'} |$

limit-distance-vanish-sequence_(tag) := $lim_{𝑛 \to \infty} | {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} | = 0$ . i.e. tail distance vanish

limit-distance-vanish-net_(tag) := $\forall 𝜀 > 0, \exists 𝐵 \in B, distance (𝐵) < 𝜀$

Cauchy-completeness-real_(tag) limit-distance-vanish 序列 or net 收敛

Proof

无界 ==> $\forall 𝜀 > 0, \forall 𝑁 \in ℕ, \exists 𝑛 > 𝑁, | {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} | \geq 𝜀$

==> limit-distance-vanish 序列有界

==> 单调增减有界序列 $𝑛 ⇝ \inf_{𝑚 \geq 𝑛} {𝑎_{𝑚}}, \sup_{𝑚 \geq 𝑛} {𝑎_{𝑚}}$ 有极限 $\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} \leq \underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}}$

limit-distance-vanish 性质 ==> $\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} = \underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} = 𝑎$

从而 $𝑎_{𝑛}$ 收敛到 $𝑎$

对网, 由闭区间网定理, let $𝑎 \in ⋂_{𝐵 \in B} 𝐵 \neq \emptyset$ . 使用 limit-distance-vanish-net 得到 net 收敛 $lim_{𝐵 \in B} \sup_{𝑎_{𝐵} \in 𝐵} | 𝑎_{𝐵} - 𝑎 | = 0$

反过来, 收敛序列是 limit-distance-vanish 的. by 三角不等式 $| 𝑎_{𝑚} - 𝑎_{𝑚^{'}} | \leq | 𝑎_{𝑚} - 𝑎 | + | 𝑎_{𝑚^{'}} - 𝑎 |$

序列 $ℕ \to ℝ$ or net $B$ 收敛到 $𝑎$ <==> limit-distance-vanish

uncountable-real_(tag) 实数不可数 $| ℕ | < | ℝ |$

已经证明了 $| ℕ | < | Subset (ℕ) |$ . cf. #link(<cardinal-increase>)[]

recall ${0, 1}^{ℕ} ≃ (ℕ \to bool) ≃ Subset (ℕ)$

$| Subset (ℝ) | = | ℕ \to ℕ | = | ℝ |$

Proof

根据区间套定理, 实数的二进制小数点表示: $𝑎_{0} . 𝑎_{1} 𝑎_{2} \dots$ 第 $𝑛$ 位取 $0 ⇝ 0 \cdot \frac{1}{2^{𝑛}}$ 或 $1 ⇝ 1 \cdot \frac{1}{2^{𝑛}}$

==> ${0, 1}^{ℕ} ≃ [0, 1]$ . 其中, 把二进制中可能的两种等价的选择 quotient

$[0, 1] ≃ (- 1, 1)$ by 线性映射 or 仿射映射

$(- 1, 1) ≃ ℝ$ by $𝑥 ⇝ \frac{𝑥}{1 - 𝑥^{2}}$

$(ℕ \to ℕ) ≃ (0, 1]$

Proof

(𝑛_{1}, 𝑛_{2}, \dots) ⇝ \frac{1}{2^{𝑛_{1}}} + \frac{1}{2^{𝑛_{1} + 𝑛_{2}}} + \dots

它代表二进制中, $1$ 出现的第一个位置是 $𝑛_{1}$ , 第二个位置是 $𝑛_{2}$ …

对比 ${0, 1}^{ℕ}$ , $\frac{1}{2^{𝑚_{1}}} + \frac{1}{2^{𝑚_{2}}} + \dots$ vs $\frac{1}{2^{𝑛_{1}}} + \frac{1}{2^{𝑛_{1} + 𝑛_{2}}} + \dots$

\begin{matrix} 𝑚_{1} & = & 𝑛_{1} \\ 𝑚_{2} & = & 𝑛_{1} + 𝑛_{2} \\ \dots \end{matrix}

距离 $𝑛_{𝑖 + 1} = 𝑚_{𝑖 + 1} - 𝑚_{𝑖}$