数的定义的三种视角

陶哲轩"实分析"中从自然数到实数的 python 定义

2024-04-30 二 22:27 2024-07-16 二 22:01

本文依托陶哲轩实分析第 2,4,5,6 章，主要梳理自然数、整数、有理数、实数定义在以下三个视角中异同：

自然语言：这是最为灵活的层面，可以描述数的意义、模型、定义语法等等一切可以谈论的对象。

实际整本书都是用这种语言所写，只不过在需要的时候混合了用自然语言描写的逻辑语言，也就是说，这种逻辑语言写出来是给人理解的，人的大脑是自然语言和这部分 latex 形式的逻辑语言的解释器
逻辑语言：然而，逻辑语言还有完全机械的一面，数理逻辑被发明的目的之一正是使数学可以被纯机械地进行推理。因此用公理系统去精确地对数进行描述之后，理论上是可以被机器直接执行的，本文中会比原书稍微突出这一点，但并不会比原书严格多少，即不会真的把 latex 写成可以自动推理的定理证明代码，而更多是对这种描述添加一些自己的理解。
编程语言：基于计算模型去构建数（过程性编程语言）。这与描述性的逻辑语言很不一样，比如要构建出无限精度的实数是不可能的，但用数理逻辑的语言描述起来则相对简单，本文基于 python ，按照书本中公理所描述的数的性质，给出一种具体的数的实现。

为什么公理化

实分析书本里是用公理系统的方式构建（或描述）数系的，为什么用这种方式？

在注 2.1.15 中作者写到:

从历史的角度来说，实现对数的公理化处理是近代才发生的事情，距今只有一百多年。在那之前，数一般被认为不可避免地与某些外部概念密切关联，例如：计算集合的势、测量线段的长度或者计算物体的质量等。

在人们的认知不得不从一个数系转向另一个数系之前，上面这种对数的理解是合理且有效的。比如，通过数珠子的方式去理解数，对数的概念化是很有好处的（例如通过数珠子很容易就形成 3 和 5 的概念）, 但是对于 -3、1/3, $ \sqrt{2} $ 或 3 + 4i 这样的数来说，数珠子的方法就不怎么起作用了。

因此，数论中每一次伟大的进步——负数、无理数、复数甚至是数字 0 ——都会带来大量不必要的哲理烦恼。

数可以通过公理来抽象地理解而不需要借助任何实物模型，这是 19 世纪后期的一个伟大发现。

当然，在方便的情况下，数学家可以使用任何实物模型来帮助自己更好地展现直观认识并加深理解，但是当这些模型开始对研究造成阻碍的时候，它们也会被轻易地抛弃。

注 2.1.15

个人对此的理解是：

这种公理化构建或者描述数系的方法不是绝对的，它甚至是很新的一个"技术发展", 距今只有 100 多年。
但微积分、概率论等 "典型的数学" 是至少 300 年前的知识。也就是说，没有这种描述数的方法，并不影响数学家发明微积分、概率原理等等。只不过近一百年里数学家又把微积分和概率等重新用形式化语言来表达，并基于此获得了更大的扩展。

此外在实数一节中提到：

即便像欧拉和牛顿这样伟大的数学家在研究极限时也感到困难，直到 19 世纪，像柯西和戴德金这些数学家才弄清楚如何严格地处理极限。

.

这反映出，欧拉即便不理解什么是严格意义上的极限，也不影响他做出那么多伟大的数学发现。

这至少说明，数学研究和严格定义底层的对象不是强相关的，或者说数学内部是分层的，就像做 web 开发不要求一定精通操作系统或者汇编一样。
将数学形式化实际是为了避免不再出现一些 "哲理烦恼", 比如虚数的意义、"无理数不存在", "无穷小的幽灵", 人们想去做一种"避免深刻" 或者 "悬置意义" 的事情，只想纯粹地用机械化、可复现的手段来发展和研究数学，这样一切都可以按规则办事，不会陷入"形而上" 的纠纷。
然而，从结果来看，"形式化" 本身似乎带来了更多的 "哲理烦恼", 比如现在正在讨论的 "为什么要形式化", 还有就是不完备性等。

但它的核心目的也确实实现了，现代的数学大部分是用这一套形式化语言来继续发展起来的。

这种机械化做法类似对数学对象进行了抽象层划分，数学家多了选择的自由，可以继续依托外部直觉，还可以依托符号所描述的抽象层面的直觉，而这抽象可以分层，当某一层探索的差不多了，又可以再加一个抽象层？

此外还催生出了计算机科学，去完成真正可以机械化的那部分，并把抽象分层的理念也带到了计算机科学中。

自然数

完整代码见： numbers/analysis/natural.py at main · metaescape/numbers

2.1 Peano 公理

公理 2.1： 0 是一个自然数

有时候会写成： \[ 0 \in \mathbb{N} \]

不过要知道的是，这个 latex 表达式里已经预设了集合论中的对象（所对应的语法），比如 "属于" 关系 $ \in $，这就好比写代码中，实现某个功能的时候用到了额外第三方库里的函数。

从以上 latex 公式表达的意思来看，它可以拆分为命题和定义两个部分：

命题部分（论断真假）：存在某个特定的非空的集合
定义部分（取名字）：给这个非空的集合取名为自然数 N，从这个非空集合中取出一个元素，取名为 0 或者任何名字，比如 "零"

但 Peano 公理可以不依赖于集合论，比如可以说：

命题部分：世界上存在一个对象，它符合自然数性质
定义部分：我们给这个对象取名为 0

问题是，我们没法直接用数理逻辑单独地、无条件地表达出 "存在一个对象", 比如，假设 E 是存在量词， E(x)x 不是一个合法命题，因为 x 没有对应的真值。一般情况下，只要能写出指代那个希望存在的对象的符号，就表示了它的存在性。因此能写出 0 这个符号，就能表示 0 的存在性（只要后续不去论断它不存在）。

因此命题核心的部分实际是论断 0 是一个自然数，这是一种谓词，因此不依赖集合论的话，这个公理直接可以写成：

is_natural(0)

is_natural 的意义还需要更多别的公理来支撑，也就是单独这个命题并没有说清楚自然数是什么。

另外，如果当前我们只谈论自然数，而不讨论其他类型的对象，那么不需要明确用一条单独的语句来表达该公理，它可以在其他出现了符号 0 的公理里被隐含地表达出来。

从构建视角上，可以随意选择某种对象表示 0，只要这个对象能够符合公理，比如以下定义一个类来表示集合（也可以用 python 中 dict 对象，但之后我们要给集合里的元素添加方法，用类型来表示会更加方便），无条件初始化之后，它就是 0:

class NaturalNumber:
    def __init__(self, predecessor=None):
        self.is_zero = True

NaturalNumber().is_zero

True

公理 2.2：每个自然数有一个唯一的后继数

每个自然数有一个唯一的后继数，该后继数也是自然数。

一种借助集合论的写法如下： \[ \forall n (n \in \mathbb{N} \rightarrow s(n) \in \mathbb{N}) \]

本文里有些地方会用 s(n) 表示书本里的 n++ ，二者是一样的意思。

该公式是不全面的，要完整表达出本公理，需要引入 "等于关系", 才能够刻画出 "唯一性" ，而描述等于关系的公理一般被认为是数理逻辑内部的公理，类似 A(x)[P(x)]->P(0) 。它不属于 Peano 公理（尽管 Peano 最初提出的自然数公理中包含了对等于关系刻画的公理，但后来大家认为等于关系比自然数更加普遍，因此将其抽取成单独的一套公理，并且内置到了一般一阶逻辑的公理系统中，就像 python 解释器内置了对字符串处理的一些函数一样)

但如果不依赖集合论，可以写成：

A(x)[is_natural(x)->is_natural(s(x))]

和 2.1 一样，如果当前只讨论自然数的话，is_natural 是恒真的，这个公理也就不用显式地写出来。

实现层面，可以个给 NaturalNumber 添加一个后继方法：

class NaturalNumber:
    def __init__(self, predecessor=None):
        self.is_zero = True
        self.predecessor = predecessor

    def successor(self):
        return NaturalNumber(self)

以上实现中维护了一个 self.predecessor, 用于找到前继，它实际类似 n– 操作，因为后继的唯一性，我们可以定义该索引。

这时候可以生成更多的自然数：

def generate_nats(n=30):
    nat = [NaturalNumber()]
    for i in range(n):
        nat.append(nat[-1].successor())
    return nat

不过问题很快出现了，所有自然数对象都是 0:

nat=generate_nats()
print(nat[0].is_zero, nat[1].is_zero)

True True

于是引出下一条公理：

公理 2.3： 0 不是任何自然数的后继

基于集合论的写法： \[ \forall n (n \in \mathbb{N} \rightarrow s(n) \neq 0) \]

继续用到了"等于关系", 不基于集合论的逻辑实现：

A(x)[s(x)!=0]

实现上的修改是，只有 predecessor 是 None 的时候，这个对象才会被判断为 0:

class NaturalNumber:
    def __init__(self, predecessor=None):
        self.is_zero = True if not predecessor else False
        self.predecessor = predecessor

    def successor(self):
        return NaturalNumber(self)

nat=generate_nats()

print(nat[0].is_zero, nat[1].is_zero, nat[2].is_zero)

True False False

有了这个公理，才能说明 0!=1 ，因为数理逻辑里全称命题可以变成特称命题，即

A(x)[s(x)!=0]->s(c)!=0

这里 c 可以替换成任何合法的常量，而到目前位置，合法的常量只有公理 1 中定义的 0, 因此从纯机械规则上（类似宏替换），我们就可以得到

s(0)!=0

而如果我们（在逻辑之外）把 s(0) 用 1 来指代, 就得到了 1!=0 。

不过，该公理没有解决 nat[1] 和 nat[3] 是否相等的问题，当然，由于 python 底层自己有一套判断对象是否相等的"公理", 它主要是基于内存中地址，因此会得到以下结果：

nat[1] == nat[3]

False

但它也会导致逻辑上相同的对象被判断为不同：

NaturalNumber() == nat[0]

False

因此引入以下公理

公理 2.4: 不同自然数的后继也不同

如果两个自然数的后继数相等，那么这两个自然数相等。

依赖集合论的写法是： \[ \forall n, m (n \in \mathbb{N} \land m \in \mathbb{N} \land s(n) = s(m) \rightarrow n = m) \]

不依赖集合论且所有对象都是自然数的情况下的写法：

A(x)[A(y)[(x!=y)->(s(x)!=s(y))]]

实现上看，这里实际是一个递归的相等判断，要判断 x 和 y 是否相等，得去找它们的前继是否相等，而根据公理 2.3, 一旦前继递归到 None 了，说明它是 0, 这时候另外一个元素如果不是 0 那么 x 和 y 就不相等，否则相等。

def __eq__(self, other):
    return eq(self, other)

def eq(x, y):
    if x is None or y is None:
        return x is y
    return eq(x.predecessor, y.predecessor)

NaturalNumber.__eq__=__eq__

nat=generate_nats()

print(nat[0]==nat[1], nat[1]==nat[1], NaturalNumber()==nat[0])

False True True

公理 2.5: 数学归纳法

如果某个性质 $P$ 对 0 成立，且假设对某个自然数 $n$ 成立时，也对其后继 $S(n)$ 成立，则 $P$ 对所有自然数都成立。

这是谓词逻辑中的公理模板，因为可以替换其中的关系 P 而生成无限条公理，基于集合论写法如下： \[ P(0) \land \forall n (n \in \mathbb{N} \land P(n) \rightarrow P(S(n))) \rightarrow \forall n (n \in \mathbb{N} \rightarrow P(n)) \]

这个公理不直接定义一个具体的数学概念，而是提供了一个证明自然数属性的方法。

比如，用该公理可以证明自然数是有限的（假设这里有限的概念是一般直觉的，而非形式的），0 是有限的，假设 n 是有限的，那么 n++ 也是有限的，因此所有自然数都是有限的。然而自然数的集合是无限的

这条公理没有具体对应的某个具体实现，这是一个证明技术，可以看作纯解释或描述行为。

但另一方面，所有递归算法都可以看作是本公理模板实例化结果的某种体现。

假设 2.6: 自然数数集合的存在性

(非正式) 存在一个数系 N，我们称 N 中的元素为自然数，且满足以上五条公理。

命题 2.1.16: 递归定义

可以通过某个起点值，重复应用一系列函数而得到不同的值：每个自然数对应了一个函数 $f_n$, 接着从 0 映射出一个对应的元素 c, 而对该元素 c, 可以不断用 $f_n$ 去变换生成 n 次得到 $a_n$, 例如 $a_3 = f_2(f_1(f_0(c))$

如果自然数出现循环，递归定义是失效的，因为某个 a_n 会被重复定义，其值可能是不唯一，因此是不确定的，只有在以上五个公理情况下，我们才能说清递归定义的性质，比如如果没有公理 4 而出现环， a[3] 可能被定义为 f3(f2(f1(c))), 又可能被定义为 f2(f1(c))。

2.2 加法

定义 2.2.1: 自然数上加法的定义

根据递归定义，对任何自然数 m, 可以对应一个关于 m 的加法函数+m，定义加法 $a_n$, 首先 $a_0 = 0 + m = m$ ，且 $a_{n++} = (n++) + m = a_n ++$

因此 n+1 定义了一个 $ a_n $ 序列，n+3 定义了另一个序列。

为什么这是一种定义，而非命题？

因为这里引入了一个额外的符号 "+" ，并且用之前已经存在的自然数对象以及等于关系组成新的命题：

0+m=m

(n++)+(m)=(n+m)++

符号定义实际只是给已有的符号的组合取了一个新的名字，考虑 3+2, 它实际是对某个自然数的另一种表示, 这里为了方便书写，用 s(x) 表示 x++:

3+2
s(s(s(0))) + s(s(0))
s(s(s(s(0))) + s(0))
s(s(s(s(s(0))) + 0))  ;; 假设已经证明了 m+0=m, 那么继续得到:
s(s(s(s(s(0)))) 
5

最终 3+2 被规约到了 5 上，而 3,2,5 这些也都是对 s 函数和 0 的组合的一个“标签”

s(x) 或者 x++ 被认为是“函数”，也就一种计算方法（从编程的角度看），但也可以用关系（从逻辑描述的视角看）来描述函数，这种关系返回真和假而不是具体的数学对象（因此关系可以称为真值函数，或真值函项）。

比如，可以定义 S(0, 1) 是真命题， S(2,3) 或者 S(n,n+1) 都被认为是真命题， S(1,3) 是假。

同样， 3+2 可以写成 Add(3,2,x), Add 是一个关系函数，它返回的是真和假，这个命题由于包含一个自由变量 x, 因此真值未定，如果 x 是 5 ，那么就得到一个真命题 Add(3,2,5), 而 Add(3,2,4) 是一个假命题。

Add 关系的定义是，Add(x,0,x) 为真，注意这可以看作一个公理模板，x 可以是任何整数对象，可以用 $ \forall x$ is_natural(x) 来限制 x 的范围，而以下是把递归定义部分从函数计算形式改写成关系逻辑形式：

a+s(b)=s(a+b)
Add(a, s(b), s(a+b)) # 写成 Add 关系
Add(a, s(b), s(c))&& Add(a,b,c) # 把 a+b 提取成关系
Add(a, s(b), s(c))&& Add(a,b,c) # 把 s(c) 运算写成 S(c,d) 关系
Add(a, s(b), d) && Add(a,b,c) && S(c,d) # 把 s(c) 运算写成 S(c,d) 关系
Add(a, e, d) && Add(a,b,c) && S(c,d) && S(b,e) # 把 s(b) 运算写成 S(c,e) 关系
A(a,b,c,d,e)[Add(a, e, d) && Add(a,b,c) && S(c,d) && S(b,e)] # 添加全称量词

以上最后一句是一个只包括关系，而没有函数的真命题，这里是用纯关系的形式来定义“加法”，从第一行到最后一行体现了“函数计算”和“逻辑描述”的区别，这是可计算性问题为什么会从逻辑中出现的一点线索。

在 python 中，执行 a+b 时，实际调用的是 a.__add__(b), 如果该函数返回 NotImplemented, 则会调用 b.__radd__(a), 但我们只对相同类型的 NaturalNumber 实施加法，因此不会出现类似 1+NaturalNumber() 的场景，也就不会触发 radd, 因此只实现 __add__:

def __add__(self, other):
    if self.is_zero:
        return other
    return (self.predecessor + other).successor()

NaturalNumber.__add__=__add__
nat=generate_nats()

print(nat[0]+nat[10]==nat[10], nat[10]+nat[1]==nat[11])

True True

注意这种实现天然有结合律：

((nat[1]+nat[2])+nat[3]) == (nat[1]+(nat[2]+nat[3]))

True

因为根据定义就可以证明：

命题 2.2.5; 习题 2.2.1: 加法结合律

为了证明结合率，需要先证明以下两个引理

引理 2.2.2: 加法定义初始条件的交换律

对任意的自然数 n，n + 0 = n 恒成立。
引理 2.2.3: 加法定义递归部分的交换律

对任意的自然数 n 和 m，有 n + (m + +) = (n + m) + + 成立。

用归纳法，可以证明 n+(m++) = (n+m)++ ，这个定理打通了 n+1,n+3,n+0 序列之间的界限，在它们之间建立了 shortcut ，比较 n+1 和 n+3 时，不再需要递归地回到原点，而直接建立的 ((n+1)++)++ = n+3 这层关系，使得真正意义上我们所熟悉的加法出现了。从这开始，就可以证明加法的结合律和交换律

最终结合律 (a+b)+c = a + (b+c) 的证明：
- 对 b 归纳，b =0 时， (a+0)+c = a+c = a + (0+c); (根据引理 2.2.2 and 定义 2.2.1)
- 假设 b=n 时 (a+n)+c=a+(n+c) 成立
  
  要证明： (a+(n++))+c=a+((n++)+c)
  
  根据引理 2.2.3 和定义 2.2.1, 左边等于 ((a+n)++) + c = ((a+n)+c)++;
  
  根据定义 2.2.1 和引理 2.2.3, 右边等于 a+((n+c)++) = (a+(n+c))++;
  
  因此两边相等

命题 2.2.6: 加法消去律

令 a、b、c 为任意三个自然数并且满足 a + b = a + c，那么 b = c 成立。

写成谓词逻辑为（以下命题中省略了全称量词，默认就是全称）：

(a+b)=(a+c)->(b=c)

这一命题与公理 2.4 很类似，公理 2.4 规定，如果 a++=b++ 那么 a=b, 相当于是对 ++ 或者 +1 操作的消去，而该定理是对更一般的 +m 操作的消去。

证明细节

对 c 进行归纳（如果对 a 或者 b 归纳会遇到麻烦）

a=0 时， 0+b=0+c, 根据 0 上的加法定义得到 b=c
假设 a+b=a+c->b=c, 那么 (a++)+b=(a++)+c 得到 (a+b)++=(a+c)++, 根据公理 2.4 得到 a+b=a+c, 根据归纳假设，得到 b=c

这个定理没有对应的操作上的实现，因为它没有描述一种计算规则，后文定义减法并出现整数后再一同实现。

定义 2.2.7 正自然数的定义

不等于 0 的自然数就是正自然数

命题 2.2.8 : 正数加法性质

如果 a 是正，b 是自然数，a+b 也是正

这部分也不需要额外实现，它都是加法定义所蕴含的，用类似以下方式进行验证即可

(nat[1]+nat[2]).is_zero

False

推论 2.2.9: a+b=0 的性质

如果 a 和 b 是自然数并且满足 a + b = 0，那么 a = 0 且 b = 0。

引理 2.2.10: 正数 a 有唯一前继

令 a 表示一个正自然数，那么恰存在一个自然数 b 使得 b++ = a。

写成逻辑语言：

A(x)[x!=0->E(b)[(b++=a)&唯一性]]

这里唯一性是通过等于关系刻画的，即如果存在另一个 c 那么 b=c.

习题 2.2.2: 正数唯一前继的证明

对 a 进行归纳：

a=0 时，前提就是错误的，因此这是一个恒为真的空推断
归纳假设：恰存在一个自然数 b 使得 b++ = a。
那么 a++ = (b++)++, 因此 b++ 就是使得 x++=a++ 中的 x, 如果有其他的自然数 c 也满足, a++=c++, 根据公理 2.4, a=c=b++. 因此二者是相同的，这说明了唯一性。

定义 2.2.11: 自然数的序

定义 <= 的符号，它等价于一种存在量词修饰的等于关系命题，即 a<=b 等价于 E(c)[a=b+c]

可以用等价关系来表述这种定义：

(a<=b)<->E(c)[a=b+c]

在具体实现上，由于加法本身是通过递归来构建的，而小于等于是基于加法的，因此小于等于也可以递归实现：

def __le__(self, other):
      if self == other:
          return True
      elif self.is_zero:
          return True  # 任何数都大于或等于零
      elif other.is_zero:
          return False  # 非零数不可能小于零
      else:
          return self.predecessor.__le__(other.predecessor)

NaturalNumber.__le__ = __le__

nat=generate_nats()
nat[0]<= nat[20]

True

它自动也能支持大于等于：

nat[1] >= nat[0]

True

命题 2.2.12: 序的性质

根据定义，对于序关系的证明，在逻辑上最终转换为对存在量词、加法、等于关系的处理。

习题 2.2.3: 序性质的证明

prove substition propperty of order a<=b, then b = a + c, then b+n = a+n+c, then b+n >= a+n

order(小于等于)符合自反性，传递性和*反对称性* (a) reflexive: a = a+0 so a >= a

(b) transitive: if a >= b and b >= c then a=b+x,b=c+y, by substitution, a = c+y+x，then a >= c

(c) anti-symmetric: if a >= b , b >= a, then a=b+x, b = a+y，by substitution a=a+x+y, by prop 2.2.6, x+y=0, by cor 2.2.9 x=y=0， so a=b

(d) addition preserves order: a >= b iff a+c >= b+c from left to right，a=b+x，a+c=b+c+x by addition substitution, then a+c >= b+c from right to left, a+c=b+c+x，by 2.2.6 cancellation law, a=b+x, a>=b

(e) a < b iff a++ <= b from left to right: a<b then a+x=b and a != b, we cannot use proof by contradiction because we have not defined what the negation of a <= b is. we can prove that x != 0, because if x=0, then a=b, this means x is a positive number, by lemma 2.2.10, there exists exactly one natural number c such that x = c++, so a+(c++) = b by 2.2.3, a+(c++) = (a+c)++ =(a++)+c, by defintion, so (a++)+c=b, and we know (a++)<=b

from right to left, a++ <= b, then b = (a++) + c, so b >= a, then we prove a != b , if a = b , then a=a+(c++), (c++)=0 , this is conflict with axiom3

(f) 证明$a<b iff ∃ d≠ 0, b=a+d $ left to right, this have been proved in (e) right to left, b = a + d, d!=0, then a <= b by definition, now we prove a != b by contradiction, if a = b, then a = a + d, d = 0, this is conflict with the fact that d is positive.

命题 2.2.13: 三歧性

a>b, a=b, a<b 三个命题只有一个成立

我们需要额外加入 < 关系：

def __lt__(self, other):
    return self<=other and not self==other

NaturalNumber.__lt__ = __lt__

nat=generate_nats()
print(nat[0]< nat[20], nat[1]<nat[1])

True False

习题 2.2.4: 三歧性证明

书本已经给出了证明框架，在此描述其思路：

首先要证明两两之间不可能同时成立，这样最多就只有一个为真，只要说明两两不能同时为真即可
接着证明至少有一个为真，竟然可以用归纳法，保持 b 不变，a 进行归纳：
- a=0 的时候可以知道 0<=b 成立，这就足够了，因为我们只需要证明至少有一个为真，而 0<=b 表达了两种可能。
- 然后分情况讨论 a++ 的情况，需要讨论三种不同的可能，并证明在每个可能下，a++>b, a++=b, a++<b 至少有一个成立

命题 2.2.14: 强归纳法、逆向归纳法

令 m0 表示一个自然数，P(m) 表示与任意自然数 m 有关的性质。假设对任意满足 m >= m0 的自然数 m，均有如下内容成立：若 P(m0) 对任意满足 m0<= m' < m 的自然数 m' 均为真，那么 P(m) 也为真。于是我们能够断定，对于任意满足 m > m0 的自然数 m，P(m) 为真。

.

注意这仍然是一个公理模板，证明时我们可以将 P 当作特定的性质。

要证明这种比较复杂的命题是比较难的，这里的核心在于把归纳法的语言映射到强归纳法上去。

注意这里写成数理逻辑语言是：

A(m)[A(x)[(m0<=x<m)->P(x)]->P(m)]->A(m)[(m>=m0)->P(m)]

归纳法公理的写法是：

((R(0)&Ax[(R(x)->R(s(x)))])->Ax[R(x)])

我们有两种证明思路，一个是把强归纳当作一个普通定理，用数学归纳法去证明这个定理，另一个是把强归纳直接写成数学归纳法形式。但因为强归纳法命题本身复杂，实际比较难对这样一个公式做归纳法。

于是我们用第二种，我们需要改写这个归纳法命题使得它能够和一般归纳法同构起来，或者替换一般归纳法模板里的 R 就能得到强归纳法的公式。

习题 2.2.5: 强归纳法证明

这里我们先重新拆分强归纳法： A(m)[A(x)[(m0<=x<m)->P(x)]->P(m)]->A(m)[(m>=m0)->P(m)], 定义：

P1(m) := A(x)[(m0<=x<m)->P(x)]
P2(m) := (m>=m0)->P(m)

那么式子可以写成：

A(m)[P1(m)->P(m)]->A(m)[P2(m)]

这里可以看到的问题：

x 要替换成 m
但是 P1 P2 和 P 的形式都不是统一的，我们需要一个 R 可以同时表示这三个命题
P1(m)->P(m) 要能写成 R(m)->R(s(m))
实现 R 后要补上 R(0)

我们首先来看 P1(m)->P(m) ， P1(m) 论述的是，如果一个范围内的自然数具有某个性质 P, 那么该范围右侧端点加一的自然数 m 也满足性质 P 。而由于 P1(m)->P1(m), 因此我们实际可以改写成 P1(m)->P1(m)&P(m), P1(m)&P(m) 表示的是在 m0<x<m++ 范围内，P(x) 也成立。这么看，似乎可以把归纳这一步写成 P1(m)->P1(s(m)), 整个强归纳法就是：

A(m)[P1(m)->P1(s(m))]->A(m)[P2(m)]

这体现出一种明显的把 P1 替换成 R 的倾向, 但如果我们把归纳法模板里的 R 都用 P1 替换, 得到的结果是：

A(m)[P1(m)->P1(s(m))]->A(m)[P1(m)]

结论 A(m)[P1(m)] 部分展开就是

A(m)[A(x)[(m0<=x<m)->P(x)]]

它需要能够推出强归纳法里原始的结论部分：

A(m)[(m>=m0)->P(m)]

这部分语义上看是明显的，因为对任意大的 m, 在 m0 到 m 之间的数都满足性质 P, 那么说明比 m0 大的数都应该满足性质 P 。

最后补充上 R(0), 也就是 A(x)[(m0<=x<0)->P(x)], 这是恒成立的，因为前提为 False （证明方法是对任意自然数 x 有 x=x+0, 因此根据序的定义， 0<=x, 根据三歧性， 0>x 不成立）

习题 2.2.6 逆向归纳法

令 n 表示一个自然数，令 P(m) 是关于自然数的一个性质并且满足：只要 P(m++) 为真，P(m) 就为真。假设 P(n) 也为真，证明：P(m) 对任意满足 m <= n 的自然数 m 均为真；这被称为逆向归纳法原理。

base case: n=0 的时候，P(0)成立，则对 m<=n 的 m 只有 m=0，此时所有 P(m) 都成立
归纳假设：n=k 的时候逆向归纳法成立，这里把完整的逆向归纳假设，即"如果 P(n)成立，且 P(m++) 成立能推出 P(m) 成立，则所有 n<=m 都有 P(n) 成立"作为条件。
接着要证明的是，“如果 P(k++)成立并且 P(m++)成立能推出 P(m)也成立，则对所有$m\le k++$,P(m)都成立“。
"如果 P(k++)成立并且 P(m++)成立能推出 P(m)也成立"这句话表明，如果 P(k) 在这个条件下也是成立的，再由归纳假设可知所有$m\le k$,P(m)都成立，因此所有$m\le k++$,P(m)都成立。这证明了逆向归纳法。

2.3 乘法

定义 2.3.1: 自然数的乘法

对于乘法来说： \[ a_{n} = n\times m; a_{0} = 0\times m=0; f_{n}(a_{n})=a_{n}+m \]

对比加法递归定义的描述:

对于加法来说： \[ a_{n} = n+m ;a_{0} = 0+m =m; f_{n}(a_{n})=a_{n}++ \]

def __mul__(self, other):
    if self.is_zero:
        return self
    return (self.predecessor * other) + other

NaturalNumber.__mul__ = __mul__

nat=generate_nats()
print(nat[0]*nat[3] == nat[0])
print(nat[2]*nat[9] == nat[18])

True
True

引理 2.3.2: 乘法交换律

m*n=n*m

习题 2.3.1: 乘法交换律证明

仿造加法交换率：

先证明在 0 可以交换，mx0=0. 对 m 进行归纳

由乘法定义可知 0x0=0，归纳假设 mx0=0,则 (m++)x0= mx0+0=0，因此归纳法可知 mx0=0
再证明 m++ 的可以交换： nx(m++)=(nxm)+n

对 n 进行归纳，由乘法定义可知左边 0x(m++)=0 ,右边 0xm+0=0 ，因此 base case 成立，归纳假设 n 时成立，要证明 n++ 时成立，

左边 (n++)x(m++) = nx(m++)+(m++) = (nxm)+n+(m++)

右边 (n++)xm+(n++) = nxm + m + (n++)

因此左边=右边，因此 mx(n++) = mxn+m
最后证明 nxm = mxn:

根据乘法定义和本题第一条的结论可知 base case 成立，归纳假设 nxm=mxn 成立，则 n++时

左边=(n++)xm = (nxm)+m = mxn + m

右边 mx(n++) = (mxn)+m

因此左边等于右边，因此证明结束。

引理 2.3.3: 正自然数没有 0 因子

如果 n，m 是自然数且 nxm=0,则 n 和 m 至少有一个为 0

习题 2.3.2: 正自然数没有 0 因子证明

反证法，如果 n,m 都是正数，那么由引理 2.2.10 可知，存在一个自然数 a 使得 (a++)=n, 因此 nxm = (a++)xm = axm+m。
由于 m 为正，根据命题 2.2.8, 那么 axm+m 也为正，因此 nxm 为正。这与前提矛盾，故 n 和 m 中至少有一个是 0.
在反证法过程中也说明了，如果 n 和 m 都是正数，那么 nm 也是正数。

注意以上证明某数为正时，完全用的是正的定义以及 peano 公理的直接推论 – 引理 2.2.10: 只要某个数能写成 a++ 形式，这个数就是正的。而在引入自然数的序之后，可以用比较的方式来说明某自然数为正：

即对任意自然数 a ，如果 b>a，则 b 为正。根据定理 2.2.12 (f), b>a 意味着 b=a+(k++)=(a+k)++，因此 b 为正(还是写成 x++的形式)。

命题 2.3.4: 乘法对加法的分配律

对于任意自然数 a、b、c，a(b + c) = ab + ac 和 (b + c)a = ba + ca 均成立。

固定 a,b 对 c 进行归纳即可证明

加法和乘法的实现上蕴含了这个性质：

nat[3]*(nat[2]+nat[3]) == nat[3]*nat[2]+nat[3]*nat[3]

True

乘法和加法的运算优先级

到目前为止我们已经有了乘法交换律、乘法对加法的分配率，根据这些定律，实际可以以此来推导出乘法和加法的运算优先级。

我们目前是用括号来区分优先级的，比如对于 (axb)+c 和 ax(b+c) 是不一样的，现在考虑不添加括号，得到 axb+c, 那么它有两种解释：

(axb)+c
ax(b+c), 根据分配律等于 axb+axc, 也就是 axb+c=axb+axc, 因此 c=axc, 因此 a=1

第二个式子只有在 a=1 的时候才合理，并不通用，于是当写成 axb+c 时，可以自然推导出乘法的优先级高于加法。

于是我们可以用 ab 来简写 axb, 这样 ab+c 看上去 ab 是更加紧密需要先计算的，因此乘法对加法分配律的性质使得视觉上有两层优化：

减少了括号的使用
乘法符号 x 可以省略

命题 2.3.5: 乘法结合律

对于任何自然数 a,b,c 有(axb)xc = ax(bxc), 固定 a，b，对 c 归纳。

习题 2.3.3: 乘法结合律证明

base case: (axb)x0 = ax(bx0)，按照乘法定义以及引理 2.3.2 乘法交换律可以证明左右都是 0
归纳假设 (axb)xc = ax(bxc) 成立
左边 = (axb)x(c++)=(axb)xc+(axb), 右边 = ax(bx(c++))=ax(bxc+b)=ax(bxc)+(ab), 这里用了命题 2.3.4 的乘法分配律。根据归纳假设，左边=右边，证明完毕。

nat[5]*(nat[2]*nat[3]) == (nat[5]*nat[2])*nat[3]

True

命题 2.3.6: 乘法保持序不变

如果 a、b 是满足 a<b 的自然数，并且 c 是正的，那么 ac<bc 。

核心数是把 a<b 转成存在命题，即存在 k 使得 b=a+(k++), 两边乘以 c, 用上分配律后： bc=ac+(k++)c = ac+kc+c, 根据命题 2.2.8 可知 kc+c 是正的，因此 ac<bc

nat[2]*nat[3] < nat[4]*nat[3]

True

推论 2.3.7: 虚拟除法：乘法消去律

设 a、b、c 是自然数，满足 ac = bc 且 c 不为零，那么 a = b。

证明细节

两种证明：

一是归纳法，对 c 归纳：

c=0, 因为空推断而成立
归纳假设成立情况下，如果 a(c++)=b(c++), 那么根据引理 2.3.2 的乘法交换律和乘法定义得到， ac+a=bc+b, 由于 ac=bc, 根据等式替换规则，可以写成 ac+a=ac+b, 根据命题 2.2.6 加法消去律得到 a=b

另一种是用反证法结合命题 2.2.13 里三歧性：

如果最终 a>b, 那么根据命题 2.3.6, ac>bc ，根据三歧性，它与 ac=bc 矛盾
同样如果 a<b 也会得到矛盾，因此 a=b

和加法消去律一样，需要等到除法定义了才能实现

命题 2.3.9: 欧几里得算法

对于自然数 n 和正数 q，存在自然数 m，r 符合 0 <= r < q 且 n = mq + r.

习题 2.3.5: 欧几里得算法证明

固定 q，对 n 进行归纳，n=0 时，等式右侧必须是 0+0 的形式，因此找到 m=0，r=0 使得 0=0q + 0
归纳假设为 n = mq+r, 需要证明 n++ = Mq + R,0 <= R <= q
由于 n++ = mq+r+1，根据三歧性:
- 如果 r+1 < q, 则 n++ = mq + R;
- 如果 r+1 = q, 则 mq+q = (m+1)q + 1, 因此 M=m+1, R=0
- 如果 r+1 > q, 根据命题 2.2.12 可知 r < q 等价于 r++ <= q, 因此这是不可能的。
所以在所有情况下，都能找到符合要求的 m 和 r

由于当前我们只定义了乘法和加法，因此没法用每次从 n 中减去 q 的方式来实现该算法，也可以用递归的方式，每次去模拟出虚拟减法，但这里不做实现。

定义 2.3.11 自然数的指数运算

设 m 是一个自然数。我们定义 pow(m,0):=1 来表示把 m 升到 0 次幂；

特别地，定义 pow(0,0):=1 。现在递归地假设对于某个自然数 n，pow(m,n) 已经被定义了，那么我们定义 pow(m,n++) := mn × m。

.

def __pow__(self, other):
    if other.is_zero:
        return NaturalNumber(NaturalNumber())
    return self*other.predecessor*self

NaturalNumber.__pow__ = __pow__

nat=generate_nats()
print(nat[0]**nat[0] == nat[1])
print(nat[2]**nat[3] == nat[8])

True
True

习题 2.3.4: 和的平方展开公式

对于所有自然数 a,b 都有 $ (a+b)^2 = a^2 + 2ab+b^2$

这里不需要用归纳法，直接计算 (a+b)(a+b):

根据分配律得到 (a+b)a+(a+b)b
继续分配得到 aa+ba+ab+bb
交换律得到 aa+2ab+bb

和的平方展开公式展示：

(nat[1]+nat[2])**nat[2]==nat[1]**nat[2]+nat[2]*nat[1]*nat[2]+nat[2]**nat[2]

True

注意这里指数和底都需要是 NaturalNumber 对象

十进制和其他进制的编码

到目前为止，打印出的 NaturalNumber 如下：

nat[2]**nat[3]

<__main__.NaturalNumber at 0x75af85cd8580>

我们只能用自然数之间的相等关系来确认运算是否正确：

nat[2]**nat[3]==nat[8]

True

但为了更方便阅读，本章对自然数添加十进制等其他进制的表示法，这里主要想说明的是，从分析的角度，十进制只是数的一种表示方法，它只是一种表征规则。

在《实分析》附录 B 中，作者主要定义了十进制下的数字 – 字符 "0" 到 "9", 对应的是自然数 0 到 9, 也就是 0,s(1),s(s(1)),…, 并且定义符号 "10" ，它对应 s(9), 这就是进制的基。

而任意自然数的十进制表示就是由于数字符号组成的一个字符串 a[n]…a[0], 其中第一字符 a[n] 不为 "0",且这个字符串对应的自然数是： \[ \sum_{i=0}^{n} a[i] * 10 \]

为了体现数字不是很重要，我们用以下符号来表示数字，以下也给出了更多符号，用于最高支持 16 进制

digits =["0️⃣", "1️⃣", "2️⃣", "3️⃣", "4️⃣", "5️⃣", "6️⃣", "7️⃣", "8️⃣", "9️⃣", "A", "B", "C", "D", "E", "F"]

同时为了能够打印出不同机制的表征，这里实现一个函数，它能够将某个自然数转为任意进制，这里我直接用 python 里 cnt 方式数出该变量有多少个前继，然后把 cnt 转为不同进制

def notation(self, n):
    assert 2<=n<=16
    cnt = 0
    p = self.predecessor
    while p:
        cnt += 1
        p = p.predecessor

    result = []
    while cnt:
        result.append(digits[cnt%n])
        cnt //= n
    
    return "".join(result[::-1])

print(notation(nat[27], 10))
print(notation(nat[27], 16))
print(notation(nat[27], 9))
print(notation(nat[27], 8))
print(notation(nat[27], 2))

2️⃣7️⃣
1️⃣B
3️⃣0️⃣
3️⃣3️⃣
1️⃣1️⃣0️⃣1️⃣1️⃣

默认用十进制显示，这样我们可以比较方便地显示出不在 nat 里数

NaturalNumber.__repr__=lambda self: notation(self, 10)
nat=generate_nats()
print(nat[17]*nat[19])

3️⃣2️⃣3️⃣

本节也体现出了逻辑（理论）和计算的区别，我们从小是先从计算角度学习数学的，先是计数，然后是竖式加法、减法、乘法除法等。从分析的角度它们都可以看做是一种计算的技巧，它是为了方便计算，或者说，是针对人的眼睛和人与环境的交互习惯进行效率优化的计算方法。正如我们在计算机上，用二进制的补码等规则来实现加减法，这是针对 cpu 进行效率优化的计算方法。

而以上根据逻辑角度写下的公理、命题等，以及用 python 实现的 NaturalNumber 类中也提供了计算方法（都是通过递归到 0 来完成），但这种计算是针对人类对逻辑推理的效率进行优化的结果，这里面可以包括多个目标：比如追求公理的简洁性，从而可以使得推理变得更精炼；追求抽象度，从而可以覆盖更多领域；或者追求解释的清晰性。因此它不考虑人眼计算的效率或者 cpu 计算的效率。

集合论的说明

《实分析》一书中在介绍完自然数之后引入了集合论，但由于在数系构成部分，对集合论的公理化描述不是很重要（对后续无限集可能比较重要），只需要有对集合一般的认识就可以理解实数构建，因此本文不讨论。

但这里要说明的是：集合论和 Peano 公理所对应的模型差不多是相同层次的理论，都是接近最底层，甚至集合论更加底层一点。

它们都可以用数理逻辑语言来描述，但它们的现实或者直觉模型是很不一样的，一个是对计数的严格的刻画（有点类似时间的单向性），另一个是对类似空间容器概念的建模。

在 python 中，有两种与集合很相似的具体计算对象（或特性）：

自带的 set: 比如并集，交集 python set 都默认支持，但 python set 只能描述有限的对象。
类型系统：对于无限的对象，python 中的类型系统反倒更接近集合。集合论使得我们可以谈论某个对象是属于某个集合，正如可以在 python 中谈论某个对象是属于整数还是浮点数，同样，数学里集合论不单单谈论其中元素的个体，还会谈论在该元素上的关系、函数等。因此 python 中定义一个类，并给这个类添加函数与之是比较相似的。

Lean4 是一种混合了逻辑证明和编程属性的语言，它把类型看作是可以操作的对象，用"可执行的"类型论来近似"描述层面的"集合论。参考 Lean perfectoid spaces

整数和有理数

本章的证明看上去更多是在代数运算层面，连归纳法公理都很少用上，这是因为，当构建出整数上的交换环或有理数上的域之后，实际已经建立了一个比较完整的对于整数和有理数的抽象层。

在此抽象层中，与人打交道的大部分是自定义的关系或函数符号，比如 "<=", "-", "+", "*", 它们不是数理逻辑语言里内置的对象（内置语法主要包括 &,| 以及 A,E 两个存在量词），同样，我们对不同的对象定义了它们各自的 "=" 关系，使得它们满足等于关系的替换公理。

因此证明中，大部分时候不需要打破抽象层，进入到底层数理逻辑的原语层面，而仅用已经证明的等式和不等式去证明新的等式和不等式，大部分等式或不等式的变换，实际都是在本层抽象层里应用替换公理的结果。

比如证明整数加法交换律：x + y = y + x, 先根据定义展开，我们要证明 (a+c–b+d)=(a+c–b+d), 而它又规约到了形式差相等的证明，根据定义要继续证明 a+c+b+d=a+c+b+d, 而它是恒真的。每次新的等式的产生都来自于"等于关系"的替换公理，所以这也是一种依据公理和命题进行的逻辑推理，尽管看上去似乎就是显然的"纯等式"变换。

类比到编程：

当已经实现了某个框架后，比如用 vue 或 react 进行前端开发，那么大部分时候都不需要写原生的 javascript.
当用底层语言实现了某个语言解释器的核心部分之后，就可以用新的语言继续实现该语言的其他特性。

之后会看到，当要引入实数时，当前建立的抽象层就不太够用的，这时又需要用底层的逻辑原语去定义更多的关系，造新的轮子，设计出 $ \epsilon-\delta $ 语言，并与当前抽象层结合，再定义出实数。

当实数构建完了，又可以抛开一阵子底层语言，谈论新的抽象层上的代数变换，比如洛必达法则等（这也是工科微积分里不太需要介绍实数是如何构造的，正如基于 pytorch 的开发很少要去写 cuda 代码）。

4.1 整数

引入 a–b 这种形式差来表示整数，尽管这导致了每个整数都有大量的等价类，比如 1–0, 5–4, 7–6 都表示 1, 但形式上的统一使得证明过程变得简单，我们常用的整数 1,2,-2 只被看作一种 "语法糖" 。

完整代码见： numbers/integer.py at main · metaescape/numbers

定义 4.1.1: 整数的形式差别定义

整数是形如 a–b 的表达式，a 和 b 都是自然数，，a–b = c–d，当且仅当 a + d = c + b。令 Z 表示由全体整数构成的集合。

这个定义主要是凸显整数可以用一种数对形式来表示，其中 – 符号和笛卡尔积有序对 (a,b) 中的逗号作用类似。但以上不完善，因为单个自然数 a 还不是整数

习题 4.1.1: 整数相等的自反和对称性

自反：a–b=a–b, 因为 a+b=a+b
对称性：a–b=c–d 则 a+d=c+b, 那么 c+b=a+d, 所以 c–d=a–b

新定义一个整数类型：

class Integer:
    def __init__(self, a: NaturalNumber, b: NaturalNumber = NaturalNumber()):
        self.a = a
        self.b = b

    def __eq__(self, other):
        return self.a + other.b == self.b + other.a

    def __repr__(self) -> str:
        return f"({self.a}--{self.b})"

这里我们不支持直接用 Integer 和 NaturalNumber 类型比较，因为如果 init 第二个参数不显式传入，那么就相当于把一个自然数"包装提升"成整数，因此，如果需要和自然数对比，那么只和被包装的自然数进行对比

定义生成整数函数，以下函数中参数 n=30 表示会生成 -30 到 30 的整数，每个整数中具体的 a,b 值是随机产生的，但返回的结果是一个字典，ints[i] 返回的是一个 a–b 整数，满足 a-b=i

def generate_ints(n=30):
    import random

    nat = [NaturalNumber()]
    for i in range(n * 3):
        nat.append(nat[-1].successor())

    ints = {}

    for i in range(-n, n + 1):
        a = random.randint(n, 2 * n)
        b = a - i
        ints[i] = Integer(nat[a], nat[b])

    return ints

ints = generate_ints()

assert Integer(nat[0],nat[10]) == Integer(nat[2],nat[12])
print(Integer(nat[2],nat[12]))
print(ints[-10], ints[30], ints[0], ints[-30])

(2️⃣--1️⃣2️⃣)
(3️⃣6️⃣--4️⃣6️⃣) (5️⃣2️⃣--2️⃣2️⃣) (4️⃣2️⃣--4️⃣2️⃣) (3️⃣1️⃣--6️⃣1️⃣)

定义 4.1.2: 整数加法和乘法

(a–b) + (c–d) := (a + c)–(b + d) (a–b) × (c–d) := (ac + bd)–(ad + bc)

def __add__(self, other):
    return Integer(self.a + other.a, self.b + other.b)

def __mul__(self, other):
    first = self.a * other.a + self.b * other.b
    second = self.a * other.b + self.b * other.a
    return Integer(first, second)

Integer.__add__ = __add__
Integer.__mul__ = __mul__

Integer(nat[4],nat[2])*Integer(nat[6],nat[2]) == Integer(nat[9],nat[1])

True

Integer(nat[4],nat[2])+Integer(nat[0],nat[2]) == Integer(nat[0],nat[0])

True

注意，由于计算效率，以下两个整数相乘已经需要非常多递归，稍微再大一点的数则容易导致栈溢出：

print(ints[5]*ints[8])

(4️⃣1️⃣4️⃣0️⃣--4️⃣1️⃣0️⃣0️⃣)

定义 4.1.4: 整数的负运算

如果 (a–b) = (a'–b')，那么 -(a–b)=-(a'–b'), 因此相等的整数有相等的负数。

习题 4.1.2: 整数的负运算证明

根据定义 -(a–b)=(b–a), -(a'–b')=(b'–a'), 要证明 (b–a)=(b'–a'), 需要证明 b+a'=b'+a, 而 (a–b) = (a'–b') 意味着 a+b'=a'+b, 根据加法交换律可以得到 b+a'=b'+a.

def __neg__(self):
    return Integer(self.b, self.a)

Integer.__neg__ = __neg__

-Integer(nat[1],nat[2])

2️⃣–1️⃣

引理 4.1.5: 整数的三歧性

设 x 是一个整数，那么下述三个命题中恰好有一个为真：

(a) x 是零；(b) x 是正自然数 n；(c) x 是正自然数 n 的负数 -n

.

习题 4.1.3: (−1) * a = −a

(−1) * a=−a 对任意整数 a 均成立。

a 可以写成 (a–0), -1 写成 -(1–0), 因此 (−1) * a =(0–1)(a–0) = (0*a+1*0)–(0*0+1*a) = 0–a = -a

命题 4.1.6: 整数的代数定律

x + y = y + x:

(x + y) + z = x + (y + z):

x + 0 = 0 + x = x:

x + (−x) = (−x) + x = 0

xy = yx

(xy)z = x(yz)

x1 = 1x = x

x(y + z) = xy + xz

(y + z)x = yx + zx

交换环性质

习题 4.1.4: 代数定律的证明

假设 (a–b),(c–d),(e–f) 表示 x,y,z

x + y = y + x:

要证明 (a+c–b+d)=(a+c–b+d), 因为 a+c+b+d=a+c+b+d
(x + y) + z = x + (y + z):

归约到自然数加法结合律 ((a+c)+e–(b+d)+f) = (a+(c+e)–b+(d+f))
x + 0 = 0 + x = x:

要证明 (a–b)+(0–0)=(0–0)+(a–b)=(a+b), 归约到 a+0=0+a=a 和整数相等自反性上。
x + (−x) = (−x) + x = 0

要证明 (a–b) +(b–a)=(b–a) + (a–b), 这规约到 a+b=b+a 上

接着证明 (a+b–b+a)=(0–0), 因为 a+b+0=0+b+a.
xy = yx

要证明 (a–b)(c–d)=(c–d)(a–b)

(ac+bd–ad+bc)=(ca+db–cb+da), 根据自然数乘法和加法交换律右侧可以变换成与左侧一样
(xy)z = x(yz): 书本已证
x1 = 1x = x

xy=yx 可知 x1=1x, x1 = (a–b)(1–0) = (a+b*0–b*1+a*0) =(a–b) = x
x(y + z) = xy + xz

要证明 (a–b)(c+e–d+f)=(ac+bd–ad+bc) + (ae+bf–af+be)

左边等于 (a(c+e)+b(d+f)–(b(c+e)+a(d+f))) =(ac+ae+bd+bf–bc+be+ad+af)

右边等于 (ac+bd+ae+bf–ad+bc+af+be), 根据自然数加法乘法交换律可知与左边相等
(y + z)x = yx + zx: 根据 x(y + z) = xy + xz 和 xy = yx 可以得到

对形式差的抛弃：整数的稀疏表征到紧凑表征

一旦我们定义了减法操作，即 a-b = a+(-b), 可以看到：它在语义上和形式差所定义的整数是完全一样的，因为

a-b=a+(-b)=(a–0)+(0–b)=(a–b)

也就是说，我们完全可以用 a-b 来替代 a–b, 这是什么意思呢？

在数学上：根本不用在乎整数是用什么方式具体构造的，a–b 只是一种临时的表示方法，用 a&&b, a7b, 或者 a&&b–000 都是无所谓的。数学在乎的是命题 4.1.6 中的代数定律，前文只是用 a–b 形式说明确实有一种具体的数据结构是可以符合交换环这种运算性质的，然而这并不代表只有 a–b 形式的对象才能叫作整数。数学并不在乎整数底层是由两个自然数组成的还是无数个自然数组成的，它在乎的是这种对象的性质。这种性质构造出了一个稳定且比较完备的抽象层，之后我们只需要用这些性质去继续证明其他定理或者定义新的数学对象，而不需要打破抽象进入到 a–b 的数据结构层面。因为抽象的 a-b 运算就可以替代整数的一切具体实现形式。
在编程上，前文我们用了包含两个属性的的类去实现了整数，但同样的，这并不是必须的：
- 一旦我们有了代数定律，只要所实现的对象的运算满足这些代数定律即可。
- 与数理逻辑不同的是，编程实现上不能不在乎数据结构，因为编程是构造性的，必须要有一个具体东西才能基于此继续定义其他的对象和运算。
- 根据三歧性，整数可以分为正自然数、0 、负自然数，因此我们完全可以只在自然数的基础上，扩展出带符号的自然数，并保证其运算符合交换环性质即可。
- 用三歧性定义出来的自然数，当要整数 5 的时候，它就是被包装后的自然数 5, 而不要考虑等价类里的 (5–0),(8–3),(9–4) 各种对象。因此这可以看作是一种从稀疏表征到紧凑表征的转换。
- 当然，从更高效的角度，由于整数性质覆盖了自然数性质，可以完全对整数重新"造轮子"，比如从二进制层面去重新定义整数（包括自然数），也就是用 python 自带的整数实现，它的底层是基于二进制的逻辑运算，与 peano 公理构建数的思路完全不同（也不同于一般小学生学习的十进制算数方式），它只是在交换环这一抽象层上提供了和 peano 公理所定义的整数相同的接口而已。
- 可以小声地说，数学里，接口即本质。

命题 4.1.8: 非 0 整数没有零因子

设 a 和 b 是整数，并且满足 ab =0 。那么 a =0 或 b =0 （或 a = b =0 ）。

习题 4.1.5: 非 0 整数没有零因子证明

反证法：如果 a b 都不等于 0, 那么它们可以表示为 (x–0) 和 (y–0), 其中 x 和 y 都是正自然数：

ab = (x–0)(y–0) = (xy+0–0) =(xy–0), 根据引理 2.3.3, xy 不等于 0, 因此 (xy–0) 不等于 (0–0), 与前提矛盾。

推论 4.1.9: 整数消去律

如果 a、b、c 是整数，并且满足 ac = bc 以及 c 不为零，那么 a = b.

习题 4.1.6: 整数消去律证明

(a–b)(c–0)=(ac–bc), 由于 ac=bc 因此 (ac–bc)=(0–0)

因此 (a–b)(c–0)==(0–0), 根据整数没有 0 因子性质以及 c–0 不为 0 ，那么 a–b 就一定是 0, 那么 a=b 就必须成立。

引理 4.1.11: 整数序的性质

建立关于 <,> 符号的代数抽象层

整数 x 小于等于整数 y 的定义是，存在一个自然数 z 使得 x=y+z, 不过在以下实现上，我们可以把整数小于等于规约到自然数的小于等于：

a–b<=c–d 等价于 a+d<=b+c:

def __le__(self, other):
    return self.a + other.b <= self.b + other.a

def __lt__(self, other):
    return self <= other and not self == other

Integer.__le__ = __le__
Integer.__lt__ = __lt__
assert ints[-30] <= ints[30]
assert ints[0] <= ints[0]
assert ints[6] < ints[15]

习题 4.1.7: 整数序的性质证明

设 a、b、c 是整数。 (a) a>b 当且仅当 a − b 是一个正的自然数。

根据整数序的定义， a>=b 等价于存在自然数 m 使得 a=b+m, 如果 m 是 0 那么 a=b, 但 a>b 的定义是 a!=b, 因此此时 b 只能是正自然数。

根据对 a=b+m 两边加上 -b 得到 a-b=m, 因此 a-b 是一个正自然数

(b) （加法保持序不变）如果 a>b ，那么 a + c>b + c。

a>b 意味着 a-b=m, m 为正自然数。

由于 c+(-c)=0, 因此 a-b+c+(-c)=m, 因此 a+c-b+(-c)=m

两边加上 b+c 得到 a+c=b+c+m, 因此 a+b>b+c

a>b 意味着 a-b=m, m 为正自然数。

两边乘以正数 c, 根据分配律： ac-bc=mc, 两边加上 bc 得到 ac=bc+mc

由于 m 和 c 都是正的，mc 为正，因此 ac>bc.

(d) （负运算反序）如果 a > b，那么 −a < −b。

a>b 意味着 a-b=m, m 为正自然数。那么 -b+a=m, -b-(-a)=m

两边加 -a 得到 -b=-a+m, 因此 -b>-a

(e) （序是可传递的）如果 a > b 且 b > c，那么 a > c。

a=b+m, b=c+n, 则 a=c+m+n, m,n 为正，因此 a>c

(f) （序的三歧性）命题 a > b、a < b 和 a = b 中恰有一个为真。

对于任意整数 a 和 b, a-b 是整数，因此根据引理 4.1.5（整数的三歧性）， a-b>0,a-b=0,a-b<0 只有一个成立，而它们分别对应了 a>b, a<b, a=b

习题 4.1.8: 归纳法原理对整数失效

一个反例是 P(n) 是 n>=0, 首先 P(0) 为真，而对于所有正数，P(n)->P(n++) 前后件命题都为真。

对于小于 0 的整数，则是空推断，恒为真。

4.2 有理数

有理数(比例数)和整数是类似的，这里用 a//b 来表示，而 a b 是整数，如果要完全展开形式，它是： (a–b)//(c–d) 的形式，a,b,c,d 是 Peano 公理中的自然数对象。

但有理数的出现使得我们可以描述无限接近的概念，开始把离散推向连续，极限的概念越来越凸显。

完整代码见： numbers/rational.py at main · metaescape/numbers

定义 4.2.1: 有理数定义

有理数是形如 a//b 的表达式，其中 a 和 b 是整数，并且 b 不为零，a//0 不是有理数。两个有理数被看作是相等的，即 a//b = c//d, 当且仅当 ad = cb。全体有理数构成的集合记作 Q。

class Rational:
    zero = Integer(NaturalNumber())
    one = Integer(NaturalNumber().successor())

    def __init__(self, a, b=1):
        if isinstance(b, int):
            assert b != 0
        else:
            assert b != Rational.zero
        self.a = a
        self.b = b

    def __eq__(self, other):
        return self.a * other.b == self.b * other.a

    def __repr__(self) -> str:
        return f"{self.a} // {self.b}"

print(Rational(ints[2],ints[3]))

(5️⃣2️⃣--5️⃣0️⃣) // (4️⃣0️⃣--3️⃣7️⃣)

在实现上，目前我们按照逻辑角度来构建的 NaturalNumber, Integer ，由于计算效率太低，很小数值内的对比或者乘法就会栈溢出，因此我们要抛弃这种实现，因此以上 Rational 的 init 函数中可以支持传入 python 内置的整数：

Rational(1,2)

1 // 2

显然 python 实现整数的目的就不再是为了遵照逻辑规则，或者为了面向逻辑解释进行设计，而是为了面向机器的执行效率而设计。有了高效的整数，我们至少可以在有理数抽象层面走得更远一点，往哪个方向走呢？

我们想要的是能够用模拟的方式，用有理数去逼近另外的数，从而（近似）构造出实数，因此我们需要更高效的实现以支持这种模拟。

习题 4.2.1: 有理数等于关系性质

注意相等关系和整数的也非常"对偶", 整数 a–b=c–d 等价于 a+d=c+b, 把 + 换成乘法把 – 换成 // 就是比例数了。

验证有理数上“相等”符合等于关系公理：

自反： a//b=a//b 因为 ab=ab

对称：

a//b=c//d <-> ad=cb <-> cb=ad <-> c//d=a//b

可传递的： a//b=b//c, b//c=e//f 则 a//b=e//f

a//b=c//d <-> ad=cb <-> adf=cbf
c//d=e//f <-> cf=ed <-> cfb=edb
<-> adf=edb
<-> ;; 推论 4.1.9 ac = bc ->a=b
<-> af=eb
<-> a//b=e//f

定义 4.2.2: 和、乘积以及负运算

果 a//b 和 c//d 是有理数，我们定义它们的和为：

(a//b) + (c//d) := (ad + bc)//(bd)

它们的乘积为：

(a//b) ∗ (c//d) := (ac)//(bd)

以及负运算为： −(a//b) := (−a)//b

.

def __neg__(self):
    return Rational(-self.a, self.b)

def __add__(self, other):
    return Rational(self.a * other.b + self.b * other.a, self.b * other.b)

def __mul__(self, other):
    return Rational(self.a * other.a, self.b * other.b)

def __sub__(self, other):
    return self + (-other)

Rational.__neg__ = __neg__
Rational.__add__ = __add__
Rational.__mul__ = __mul__
Rational.__sub__ = __sub__

这样可以进行"比较大"的数值的计算：

print(Rational(30,100)+Rational(9,130))
print(Rational(30,100)*Rational(9,130))
print(Rational(30,100)-Rational(9,130))

4800 // 13000
270 // 13000
3000 // 13000

习题 4.2.2: 运算符合替代公理的证明

证明乘积和负运算是良好定义的，即证明两个操作符合替代公理：

假设有 (a'//b') = (a//b)

证明 (a//b) * (c//d)=(a'//b') * (c//d)

也就是证明： (ad+bc)//bd = (a'd+b'c)//b'd

即证明： (ad+bc)b'd=(a'd+b'c)bd

根据整数乘法分配律，要证明： (adb'd+bcb'd)=(a'dbd+b'cbd)

根据整数替换性质，该式子成立
证明 -(a//b)=-(a'//b')

也就是证明： (-a)//b=(-a')//b'

即证明： (-a)b'=b(-a')

根据整数乘法交换律和替换性质，该等式成立。

命题 4.2.4: 有理数的代数运算定律

x + y = y + x

(x + y) + z = x + (y + z)

x + 0 = 0 + x = x

x - (−x) = (−x) + x =0

xy = yx

(xy)z = x(yz)

x1 = 1x = x

x(y + z)= xy + xz

(y + z)x = yx + zx

$ xx^{-1} = x^{-1}x =1 $

有理数域（比交环环多了最后一条）

额外定义 truediv, 这是支持 "/" 操作，div 操作是有理数特有的，在整数上执行 div 会得到未定义的数，而正是这些未定义的数作为扩充将整数延伸到了有理数。

def __reverse__(self):
    assert self.a != 0
    return Rational(self.b, self.a)

def __truediv__(self, other):
    return self * other.__reverse__()

Rational.__reverse__ = __reverse__
Rational.__truediv__ = __truediv__

print(Rational(30,100)/Rational(9,130))

3900 // 900

习题 4.2.3: 有理数的代数定律

记 x = a//b ，y = c//d 以及 z = e//f ，其中 a、c、e 是整数， b、d、f 是不为零的整数。

x + y = y + x

a//b+c//d = (ad+bc)//bd = (cb + da)//db = c//d + a//b
(x + y) + z = x + (y + z)
x + 0 = 0 + x = x
x - (−x) = (−x) + x =0
xy = yx
(xy)z = x(yz)
x1 = 1x = x

根据 xy=yx 可以得到 x1=1x
x(y + z)= xy + xz
(y + z)x = yx + zx

根据 x(y + z)= xy + xz 和交换律可以得到。

引理 4.2.7: 有理数的三歧性

设 x 是一个有理数，那么下述三个命题中恰好有一个为真： (a) x 等于 0；(b) x 是一个正有理数；(c) x 是一个负有理数。

习题 4.2.4: 有理数的三歧性证明

首先证明其中必有一个为真，根据定义，存在整数 a 和 b, 且 b 不为 0, 使得 x 表示成 a//b 形式，根据整数三歧性，b 要么是正，要么是负，如果 b 是正，那么可以讨论 a 的三歧性：

如果 a 是正，根据定义 x 就是正
如果 a 是 0 那么 x 为 0;
如果 a 为负，那么 a 就是某个正自然数 m 的负数，即 a=-m, x=(-m) //b, 根据定义 x 就是负的。

如果 b 是负的，那么存在一个正数使得 b=-n, 继续讨论 a 的三歧性

如果 a 是正，x=a//(-n), 根据定义可以得知它等于 (-a)//n = -(a//n), 因此 x 是负的。

这里要说明 (-a)(-n)=an, a,n 都是整数，因此左侧可以写成 (0–a)(0–n)=(0+an–0)=an
如果 a 是 0 那么 x 为 0;
如果 a 为负，那么 a 就是某个正自然数 m 的负数，即 a=-m, x=(-m) //(-n), 它等于 m//n, 因此 x 是正的。

注意以上每个分支都是互斥的，因为都是根据三歧性的到的。

命题 4.2.9: 有理数上序的基本性质

定义大于小于关系

def __le__(self, other):
    return lesseq0(self + (-other))

def __lt__(self, other):
    return self <= other and not self == other

def lesseq0(self):
    return (self.a >= 0 and self.b <= 0) or (self.a <= 0 and self.b >= 0)

Rational.__le__ = __le__
Rational.__lt__ = __lt__

assert Rational(10,100) <= Rational(11,101)
assert Rational(10,100) < Rational(20,122)

习题 4.2.5: 有理数上序的基本性质;

(a) （序的三歧性）命题 x = y、x < y 和 x > y 中恰有一个为真。 (b) （序是反对称的）我们有 x < y 当且仅当 y > x。 (c) （序是可传递的）如果 x < y 且 y < z，那么 x < z。 (d) （加法保持序不变）如果 x < y，那么 x + z < y + z。 (e) （正的乘法保持序不变）如果 x < y 且 z 是正的，那么 xz < yz。

.

(a) （序的三歧性）命题 x = y、x < y 和 x > y 中恰有一个为真。

x-y 根据定义展开后它是有理数，根据有理数三歧性，它有 =0,>0,<0 三种状态，根据序的定义，就说明了以上三个命题恰有一个为真。

(b) （序是反对称的）我们有 x < y 当且仅当 y > x。

x<y 意味着 x-y 是小于 0 的，那么 -(x-y) 就是大于 0 的，它等于 y-x, 因此 y>x

x<y, y<z 意味着 y=x+m , z-y=n, 其中 m,n 都是正有理数

那么 z-(x+m)=n, z=x+m+n, m+n 为正有理数，因此 z>x, 根据 (b) x<z

(d) （加法保持序不变）如果 x < y，那么 x + z < y + z。

x<y 意味着 y=x+m, m 为正有理数，那么 y+z=x+z+m, 因此 x+z<y+z

(e) （正的乘法保持序不变）如果 x < y 且 z 是正的，那么 xz < yz。

x<y 意味着 y=x+m, m 为正有理数，那么 yz=xz+mz, mz 为正，因此 xz<yz

习题 4.2.6: 不等式两边乘以负数

如果 x、y、z 是有理数，并且满足 x < y 和 z 是负的，那么 xz > yz。

x<y 意味着 y=x+m, m 为正有理数，那么 yz=xz+mz, mz 是正有理数乘以负有理数，得到的也是负数（按形式商展开后可以得到），因此 xz>yz.

我们在这展现

4.3 绝对值和指数

命题 4.3.3: 绝对值和距离的基本性质

设 x、y、z 是有理数。 (a) （绝对值的非退化性）我们有 |x| >= 0。另外，|x| = 0 当且仅当 x 为零。 (b) （绝对值的三角不等式）我们有 |x + y| <= |x| + |y|。 (c) 不等式 -y<=x<=y 成立，当且仅当 y >= |x|。特别地，-|x|<= x <= |x|。 (d) （绝对值的可乘性）|xy| = |x||y|。特别地，|-x| = |x|。 (e) （距离的非退化性）d(x, y) > 0。另外，d(x, y) = 0 当且仅当 x = y。 (f) （距离的对称性）d(x, y) = d(y, x)。 (g) （距离的三角不等式）d(x, z) <= d(x, y) + d(y, z)。

距离的定义

def __abs__(self):
    return Rational(abs(self.a), abs(self.b))

Rational.__abs__=__abs__

def distance(x, y):
    return abs(x - y)

distance(Rational(10,100), Rational(11,101))

90 // 10100

习题 4.3.1: 绝对值和距离的基本性质证明

(a): 根据定义 x 是正，则 |x| = x 是正的，因此 x>0, 如果， x 为负，则 x=-m, m 为正，那么 |x|=-(-m)=m >0, 这同样说明，如果 x 不为 0, 那么 |x| 不为 0 （这等价于 |x|=0 -> x=0）, 接着说明如果 x 为 0, 那么根据定定义 |x| 为 0.

(b): 按 x 的三歧性分类：

如果 x 为 0, 那么问题就变成 |y|<=|y| 了，由于 |y| 是有理数，这是恒成立的。同样 y 等于 0 的时候，也成立，因此之后我们只讨论 x,y 分别为正和负的情况
x 为正，且 y 为正： x + y 为正，因此可以直接拿掉绝对值，|x+y|=x+y=|x|+|y|
x 为正，且 y 为负：假设 y=-m, |x|+|y|=x+m, 那么根据三歧性继续考虑三种情况：
- x-m>0: |x+y|=|x-m|=x-m <= x+m <= |x|+|y| ，因为 x<x+2m
- x-m<0: |x+y|=|x-m|=m-x <= x+m <= |x|+|y| ，因为 -x<=x
- x-m=0: |x+y|=|x-m|=0 <= x+m <= |x|+|y| ，因为 x+m 为正
x 为负，y 为正和以上是对称的
x 为负，y 为负，那么 |x+y|=-(x+y)=-x+-y=|x|+|y|

(c): 根据 x 的三歧性：

x>=0, 那么 x=|x| （0 也放在一起处理）
- 如果 -y<=x<=y 成立，那么 y>=x, 因此 y >= |x|
- 反过来，如果 y >= |x|, 那么 y>=x, 大于等于关系传递性可得 y>=0, 两边乘以 -1 由习题 4.2.6 可得 0>=-y, 因此 -y<=x<=y
x<0, 那么 x=-m, m 为正有理数， |x|=m
- 如果 -y<=x<=y 成立，那么 -m>=-y, 两边乘以 -1 可得 y>=m, 因此 y >= |x|
- 反过来，如果 y >= |x|=m, 那么 y>=m>=-m=x, 两边乘以 -1 可得 -m>=-y, 即 x>=-y, 因此 -y<=x<=y

特别地，|x|>=|x|, 因此 -|x|<= x <= |x|。

(d): 根据 x 的三歧性：

x=0, |xy| = 0 = |x||y|, 同时 y =0 时也是一样的，因此后文不考虑 y=0 情况。
x>0, 继续根据 y 的正负分类：
- y>0: |xy|>0, 因此 |xy| = xy = |x||y|
- y<0: y=-m, n 为正有理数，那么 |xy|=xm=|x||y|
x<0, y> 0 是情况类似。
- x<0,y<0, 时那么 x=-m, y=-n, m,n 都是正有理数 |xy|=mn=|x||y|

特别地，y=-1 时有 |-x| = |x|。

(e) 根据定义 d(x, y) = |x-y|, 而根据 (a)。 |x-y| >= 0 同样根据 (a) |x-y| = 0 时， (x-y)=0, 因此 x=y

(f) 根据定义 d(x, y) = |x-y|, 根据 (d) |x-y|=|-(x-y)|=|y-x| 因此 d(x, y) = d(y, x)。

(g) 根据 (b) |x -y + y - z| <= |x-y| + |y-z|。而 |x -y + y - z| = |x-z| 根据距离定义可知： d(x, z) <= d(x, y) + d(y, z)。

定义 4.3.4: ε-接近性

设 ε > 0 是一个有理数，并且设 x 、 y 是有理数。我们称 y 是 ε-接近于 x 的，当且仅当 d(y, x) <= ε。

以上定义的是一种等价关系。

命题 4.3.7;习题 4.3.2: ε-接近性的性质及其证明细节

(a) 如果 x = y，那么对任意的 ε > 0，x 都是 ε-接近于 y 的。反过来，如果对于任意的 ε > 0，x 都是 ε-接近于 y 的，那么 x = y。

(b) 设 ε > 0，如果 x 是 ε-接近于 y 的，那么 y 也是 ε-接近于 x 的。

(c ) 设 ε, δ > 0，如果 x 是 ε-接近于 y 的，并且 y 是 δ-接近于 z 的，那么 x 和 z 是 (ε + δ)-接近的。

(d) 设 ε, δ > 0，如果 x 和 y 是 ε-接近的，并且 z 和 w 是 δ-接近的，那么 x+z 和 y + w 是 (ε + δ)-接近的，并且 x − z 和 y − w 也是 (ε + δ)-接近的。

(e) 设 ε > 0，如果 x 和 y 是 ε-接近的，那么对任意的 ε‘ > ε，x 和 y 也是 ε’-接近的。

(f) 设 ε > 0，如果 y 和 z 都是 ε-接近于 x 的，并且 w 位于 y 和 z 之间（即 y <= w <= z 或 z<= w<= y），那么 w 也是 ε-接近于 x 的。

(g) 设 ε > 0，如果 x 和 y 是 ε-接近的，并且 z 不为零，那么 xz 和 yz 是 ε|z|-接近的。

(h) 设 ε, δ > 0，如果 x 和 y 是 ε-接近的，并且 z 和 w 是 δ-接近的，那么 xz 和 yw 是 (ε|z| + δ|x| + εδ)-接近的。

.

设 x、y、z、w 是有理数。证明中有时候用 e 来代替 ε

(a) x=y, 则 |x-y|=0, 而 e>0 ，因此对任意 e, x 都 e-接近于 y.

反过来，用反证法，如果 |x-y|>=0, 假设 |x-y| 是一个正有理数 z, 由于对于任何 e 都满足 x e-接近于 y, 那么取 e 可以是 z/2 ，这就要满足 z<=z/2, 得到 2<=1, 导致矛盾，|x-y| 只能取 0.

(b) 根据习题 4.3.3(f) 距离对称性 d(x,y)=d(y,x) 即可证。

(d) d(x+z,y+w)=|x+z-(y+w)|=|x-y+z-w|<=d(x,y)+d(z,w), 因此 x+z 和 y + w 是 (ε + δ)-接近的

d(x-z,y-w)=|x-z-(y-w)|=|x-y+w-z|<=d(x,y)+d(w,z), 根据 (b) 后者等于 d(x,y)+d(w,z)=ε + δ, 因此 x-z 和 y-w 是 (ε + δ)-接近的

(e) d(x,y)<=ε <ε’ , 因此 d(x,y)<= ε’。

(f) 以下证明 y <= w <= z 的情况，根据对称性 z<= w<= y 也可以被类似证明。

对 y <= w <= z 各个元素分别减去 x 得到 y-x <= w-x <= z-x

如果 x<=w, 那么 0<= w-x <= z-x, 因此 |w-x| <= |z-x|<=e, 有 d(w,x)<=e
如果 x>w, 那么 y-x <= w-x <0, 两边乘以 -1 有 x-y >= x-w >0, 因此 |x-y| >= |x-w|, 有 d(w,x)<=e

(g) d(x,y)=|x-y|<=e, 则 |z||x-y|<=e|z|, 根据习题 4.4.4(d) 以及 z 为正的性质， |z||x-y| = |zx-zy|<=e|z|, 因此 xz 和 yz 是 e|z| 接近的

(h) 书本上已证明

定义 4.3.9: 自然数次幂的指数运算

设 x 是一个有理数，为了把 x 升到 0 次幂，我们定义 x**0:= 1；特别地，我们定义 0**0:= 1。现在归纳性地假设对于某个自然数 n，x**n 已经被定义了，于是我们定义 x**(n+1) := x**n*x。

这里是一种递归的计算方式，并且其指数只约定为自然数。我们在之后定义了负数也可以作为指数的情况下一同实现。

命题 4.3.10: 自然数指数运算性质

(a) 我们有 x**nx**m = x**(n+m)，(x**n)**m = x**(nm)，(xy)**n = x**ny**n。

(b) 假设 n > 0，那么 x**n = 0 当且仅当 x = 0。

(c) 如果 x >= y >= 0，那么 x**n >= y**n >= 0。如果 x > y >= 0 并且 n > 0，那么 x**n > y**n >= 0。

(d) 我们有 |x**n| = |x|**n。

.

注意目前定义的是有理数的自然数幂，而不是自然数的有理数幂。因此关于指数性质的证明可以用归纳法

习题 4.3.3: 自然数指数运算性质证明

(a)

x**nx**m = x**(n+m), 对 n 进行归纳证明：
- n=0 时， x**0x**m=x**m=x**(0+m)
- 当归纳假设成立时，要证明 x**(n++)x**m= x**((n++)+m),
左边根据定义等于 x**nxx**m, 根据归纳假设它等于 x**(n+m)x

右边等于 x**((n+m)++)=x**(n+m)x, 因此与左边相等

(x**n)**m = x**(nm)，(xy)**n = x**ny**n。
(x**n)**m = x**(nm), 对 m 进行归纳证明：
- m=0 时，左右都是 x**0
- 当归纳假设成立时，要证明 (x**n)**(m++) = x**(n(m++))
左边等于 (x**nx**m)(x**n), 根据归纳假设它等于 x**(n+m)x**n

右边等于 x**(nm+n), 根据 1 中的证明等于 x**(nm)x**n, 因此两边相等
(xy)**n = x**ny**n, 对 n 进行归纳
- n=0 时，左右两边都是 1
- 当归纳假设成立时，要证明 (xy)**(n++)= x**(n++)y**(n++),
左边根据定义等于 (xy)**n xy, 根据归纳假设它等于 x**n y**n xy

右边等于 x**nxy**ny, 因此等于左边

(b) 假设 n > 0，那么 x**n = 0 当且仅当 x = 0。

根据定义： x**n=x**(n-1)x, x=0 时该式子为 0. 反过来，对 n 进行归纳：

n=1 时，如果 x**n=x**1=x*1=x, 如果它等于 0, x=0
如果 x**n=0 能推出 x=0, 那么 x**(n++)=x**(n)x=0 时，由整数 ab=0 那么 a=0,b=0 的性质可以扩招到自然数也是如此，因此要么 x**(n)=0, 要么 x=0, 这都导向了 x=0

(c)

如果 x >= y >= 0，那么 x**n >= y**n >= 0。

根据归纳法：

n=0 时， x**0=1,y**0=1, 因此命题成立
而 x**(n+1)=x(x**n), 在归纳假设成立情况下，并且结合正的乘法保序性（以及0 的性质）： x(x**n)>=x(y**n), 归纳假设里也蕴含了 y**n>= 0, 因此继续根据保序性， x(y**n)>=y(y**n), 因此 x**n >= y**n >= 0。
如果 x > y >= 0 并且 n > 0，那么 x**n > y**n >= 0。

仍然是归纳法，但从 1 开始：

n=1 时， x**1=x,y**=y, 因此命题成立
x**(n+1)=x(x**n), 在归纳假设成立情况下，并且结合正的乘法保序性（不考虑0）： x(x**n)>x(y**n), 归纳假设里也蕴含了 y**n>= 0, 因此继续根据保序性（以及0d 的性质）， x(y**n)>=y(y**n), 因此 x**n > y**n >= 0。

(d) 对 n 归纳：

n =0 时， |x**0|=1 =|x|**0。
归纳假设成立情况下， |x**(n++)|=|x**(n)x|, 根据命题 4.3.3(d) 后者等于 |x**(n)||x|=|x|**n|x|=|x|**(n++)

定义 4.3.11: 负整数次幂的指数运算

设 x 是一个不为零的有理数，那么对任意的负整数 -n，我们定义 x**(-n) := 1/(x**n).

为了提高效率，这里用分治来实现，并且指数直接用 python 的 int 类型：

def __pow__(self, n: int):
    if n < 0:
        return (self ** (-n)).__reverse__()

    if n == 0:
        return Rational(1)

    if n % 2 == 0:
        return (self * self) ** (n // 2)
    return self * (self ** (n - 1))

Rational.__pow__ = __pow__

print(Rational(2,3)**10)
print(Rational(2,3)**-10)

1024 // 59049
59049 // 1024

命题 4.3.12: 整数指数运算性质

设 x 和 y 是不为零的有理数，并且设 n 和 m 是整数。

(a) (x**n)x**m = x**(n+m)，(x**n)**m = x**(nm)，(xy)**n = x**ny**n。

(b) 如果 x >= y > 0，那么当 n 为正数时有 x**n >= y**n > 0。当 n 为负数时，有 0<x**n<=y**n

(c) 如果 x,y>0, n!=0, 并且 x**n = y**n, 那么 x=y.

(d) |x**n| = |x|**n。

.

这里幂部分是整数，因此无法用归纳法。

习题 4.3.4: 整数指数运算性质证明

整数本身由于负数和自然数构成，自然数部分已经在命题 4.3.10 证明，这里只讨论负数部分，将 n,m 记为 -a,-b, 其中 a 和 b 都是正自然数。

(a) (x**n)x**m = x**(n+m)，(x**n)**m = x**(nm)，(xy)**n = (x**n)y**n。

证明 (x**(-a))x**(-b) = x**(-a-b)
- 根据有理数乘法，左边 = 1/((x**a)(x**b)),
- 根据自然数幂性质，左边 = 1/(x**(a+b))
- 根据定义，右边 = 1/(x**(a+b))
- 因此等式左右对象相等
(x**(-a))**(-b) = x**(ab)，
- 根据负整数指数定义，左边 = 1/((1/x**a)**b)
- 根据商性质，左边 = (x**a)**b
- 根据自然数指数性质，左边 = x**(ab) = 右边
(xy)**(-a) = (x**(-a))(y**(-a))。
- 根据负整数指数定义，左边 = 1/((xy)**a)
- 根据自然数指数性质，左边 = 1/((x**a)(y**a))
- 根据有理数乘法，左边 = (1/(x**a))(1/(y**a))
- 根据负指数性质，左边 = (x**(-a))(y**(-a)) = 右边

(b) 如果 x >= y > 0，那么当 n 为正数时有 x**n >= y**n > 0。当 n 为负数时，有 0<x**n<=y**n

当 n 为正数时，已经在命题 4.3.10 中证明
当 n 为负数时，写成 -a, 要证明 0<x**(-a)<=y**(-a).

首先证明它们都大于 0, 因为 x>0, 因此 x**(-a)=1/(x**a), 根据命题 4.3.10(c), x**a>0, 根据有理数性质 1/(x**a)>0, 对于 y 是一样的。

接着证明 1/(x**a)<=1/(y**a), 同样根据根据命题 4.3.10(c), 分母部分满足 (x**a)>=(y**a), 根据有理数序的定义，如果 0<c<=d, 那么 1/c-1/d=(d-c)/cd, 分子是非负的，分母为正，因此 1/c>=1/d

于是有 1/(x**a)<=1/(y**a), 即 x**(-a)<=y**(-a).

n 为正时，如果 x**n=y**n, 用反证法，如果 x!=y, 那么三歧性，要么 x>y, 要么 x<y, 无论哪种情况，根据命题 4.3.10(c), 都无法得到 x**n=y**n, 与前提矛盾。
n 为负时，记为 n=-a，如果 x**(-a)=y**(-a), 那么 1/(x**a)=1/(y**a), 根据有理数相等性质，x**a=y**a, 根据 n 为正的时的结论， x=y.

(d) |x**n| = |x|**n。

n 非负时命题 4.3.10(d) 已证明
n 为负时 n=-a:
- 左边等于 |1/(x**a)|, 根据 (a) 中 (xy)**n=(x**n)(y**n), 把其中 y 替换为 1/x, n 替换为 a, 那么 (x*1/x)**n=(x**a)(1/x)**a=1, 也就是 1/(x**a)=(1/x)**a, 因此左边 = |(1/x)**a|=|1/x|**a
- 右边=1/|x|**a
- 为了证明左边等于右边，需要先证明 |1/x|=1/|x|, 情况讨论，x 无论正负，等式都成立。
- 因此左边 = |1/x|**a = (1/|x|)**a=1/|x|**a, 后一个等式成立还是因为 (a) 中的 (xy)**n=(x**n)(y**n)

习题 4.3.5: 2**N > N 对一切正整数 N 均成立。

N=1 时，能够推导出 2>1 成立
N>1 时：归纳假设成立情况下 2**(N++)=2**(N)>2N>N+1, 因为 N>1

实际对所有 N 都成立：

当 N < 0 时，N 可以写成 -m, m 是正自然数，而根据定义 2**(-m)=1/(2**m)>0, 因此 2**N > N
N=0, 则 1>0 成立

4.4 有理数之间的间隔

有理数和整数的非常大的区别在于，任意两个整数的距离有最小值，也就是 1, 这使得它们被称为是离散的。

但对于有理数，任意两个有理数之间找不到最小值，这种性质被称为稠密性。这看上去似乎像是在说：有理数能够表示一切精细的事物。直觉上确实如此，以至于毕达哥拉斯学派以宗教形式否认无理数的存在。从有理数中挑出毛病甚至引发了数学史上第一次危机。而本文最初也提到过，欧拉等人都没有严格地定义清楚极限从而说清楚实数，因此从这里开始到实数的完整构建，看似只有一章的距离，对于人类却走了 2500 多年。

命题 4.4.1: 有理数取整

设 x 是一个有理数，那么存在一个整数 n 使得 n<= x < n+1。事实上，这个整数是唯一的 (即对每一个 x，只有一个 n 使得 n<= x < n+1)。特别地，存在一个自然数 N 使得 N > x（也就是，不存在某个大于全体自然数的有理数）。

.

习题 4.4.1：有理数取整证明

如果 x 为 0, 那么 n =0
如果 x 为正, 那么它可以写成两个自然数的形式商，a//b, 命题 2.3.9 指出，任意自然数 a 可以写成 cb+r 形式，其中 0<=r<q, 因此这里选择 n = c, 因为 cb+r//b>=cb//b, 同时 cb_r//b<=(cb+b)//b 。
如果 x 为负, 可以先得到 n<=-x<=n+1, 然后根据序的性质，取反后 -n-1<=x<=-n 而 -n-1 和 n 满足命题里所描述的关系。

习题 4.4.2: 无穷递降原理

如果对任意自然数 n, a[n]>a[n+1], 那么称为 a[0],a[1],… 这个无限序列是无穷递降的

(a) 不存在无穷递降的自然数列

(b) 存在无穷递降整数和正有理数序列

.

(a): 如果存在某个无穷递降的自然数序列，那么 a[0] 是其中的最大值，假设这个值为 M.

那么可以用归纳法证明，对任意 k, 以及 n 都满足 a[n]>=k

k=0 时， a[n]>=0 恒成立，因为自然数都是大于等于 0
归纳假设成立情况下，要证明对任意 n 都满足 a[n]>=k++
由于任意 n 都满足 a[n]>=k, 因此对于任意 n, a[n++]>=k, 而由于 a[n]>a[n++], 因此 a[n]>=k++

因此对所有 n ，a[n]>=k++.

这意味着对任意 k 和 n, a[n]>=k, 因此 k 可以大于 M, 这说明 M 不是最大值，导致矛盾。

(b):

存在无穷递降整数序列，可以取 a[n+1]=a[n]-1
存在无穷递降有理数序列，可以取 a[n+1]=a[n]/2

命题 4.4.4: 根号 2 不是有理数

习题 4.4.3: 根号 2 不是有理数证明

这里只证明文中提到为什么的部分：

如果存在一个自然数 k 使得 p = 2k，那么我们定义自然数 p 是偶数；如果存在一个自然数 k 使得 p = 2k + 1，那么我们定义自然数 p 是奇数。

为什么自然数要么是偶数要么是奇数？
- 首先，1 无法写成 2k, 因为如果 1=2k, 即 1=k+k, k 是自然数，那么 1>=k, 而满足这个关系的只有 0 和 1, 将二者代入都无法成立。
- 如果某个数既是奇数又是偶数，那么它可以写成 2k, 也可以写成 2p+1, 那么 2k=2p+1 这时候 1=2k-2p=2(k-p), 这样 1 就是偶数，与上一条证明结论矛盾。
如果 p 是奇数，为什么 p**2 也是奇数
- 因为 p=2k+1, 按照习题 2.3.4 平方定义和展开公式，p**2=4k**k+4k+1, 而 4k**k+4k 是自然数，因此 p**2 是奇数
如果 $ p^{2}=2q^{2} $, 那么 q<p
- 如果 p=q, 那么会得到 p=0, 但与 p 为正的前提矛盾
- 如果 p<q, 那么存在正自然数 k 使得 q=p+k, 代入后展开会得到 p**2+4pk+2k**2=0 与 p,k 都为正矛盾。

对形式商的抛弃：有理数的稀疏表征到紧凑表征

正如整数减法定义之后可以抛弃形式差，商定义之后也可以抛弃形式商，这样做的好处有：

整数和有理数类型能够自然转换，也就是说有理数只是在整数上对 / 进行额外扩展所获得的对象，对于那些原本是整数的对象，直接就返回整数因此当初始化 Rational(2,1) 后，我希望直接返回 python 内部的 int(2).

这同时包括 Rational 对象和 int 对象可以自然地操作。
等价类的塌缩，在形式差表示中， 3/2 6/4, 12/8 是等价类，但既然相等，我们就选择一个作为代表即可，因此用 gcd 来化简这种表示

from math import gcd
print(12//gcd(12, 8), 8//gcd(12, 8))

3 2

以下是对有理数的重新定义，用 Rational2 完整实现：

class Rational2:
    def __new__(cls, a, b=1, *, force_int=False):
        assert b != 0, "Denominator cannot be zero"

        # 化简 a 和 b
        g = gcd(a, b)
        a //= g
        b //= g

        if b == 1 and force_int:
            return int(a)
        else:
            instance = super().__new__(cls)
            instance.a = a
            instance.b = b
            instance.force_int = force_int
            return instance

    def __init__(self, a, b=1, *, force_int=False):
        # 在 __new__ 方法中已经完成属性初始化，无需重复初始化
        pass

    def __repr__(self):
        if self.b == 1:
            return str(self.a)
        else:
            return f"{self.a}/{self.b}"

    def _check_int_and_convert(self, other):
        if isinstance(other, int):
            return Rational2(other, 1)
        return other

    def __eq__(self, other):
        # only consider int and Rational2 type
        other = self._check_int_and_convert(other)
        return self.a * other.b == self.b * other.a

    def __add__(self, other):
        other = self._check_int_and_convert(other)
        return Rational2(self.a * other.b + self.b * other.a, self.b * other.b)

    def __radd__(self, other):
        return self + other

    def __sub__(self, other):
        return self + (-other)

    def __rsub__(self, other):
        return -(self - other)

    def __mul__(self, other):
        other = self._check_int_and_convert(other)
        return Rational2(self.a * other.a, self.b * other.b)

    def __rmul__(self, other):
        return self * other

    def __reverse__(self):
        assert self.a != 0, "cannot reverse 0"
        return Rational2(self.b, self.a)

    def __truediv__(self, other):
        other = self._check_int_and_convert(other)
        return self * other.__reverse__()

    def __rtruediv__(self, other):
        other = self._check_int_and_convert(other)
        return other / self

    def __neg__(self):
        return Rational2(-self.a, self.b)

    def __abs__(self):
        return Rational2(abs(self.a), abs(self.b))

    def __le__(self, other):
        other = self._check_int_and_convert(other)
        return lesseq0(self + (-other))

    def __lt__(self, other):
        return self <= other and not self == other

    def __ge__(self, other):
        other = self._check_int_and_convert(other)
        return other <= self

    def __gt__(self, other):
        other = self._check_int_and_convert(other)
        return other < self

    def __pow__(self, n: int):
        if n < 0:
            return (self ** (-n)).__reverse__()

        if n == 0:
            return Rational2(1)

        if n % 2 == 0:
            return (self * self) ** (n // 2)
        return self * (self ** (n - 1))

说明：

首先用 __new__ 来精细控制类的创建过程，先对其化简，如果分母为 1 ，可以根据选项直接返回 int 类型，否则返回化简后的有理数类型，这种实现使得有理数的表示并不是统一的形式差，如果能化简到整数，它就是整数对象，而不是两个数的形式差。

(但为了保持计算中类型统一，计算中还是用 Rational2 统一 int 和无法化简的有理数)

之后的代数运算实现都考虑到与 python 原生 int 类型的交互，使得以下操作都是合理的

r1 = Rational2(1, force_int=True)  # 1
r2 = Rational2(3, 4)
r3 = 2

assert type(r1) == int
assert type(r2) == Rational2
assert type(r3) == int
assert r2 + r1 == Rational(7, 4) 
assert r1 + r2 == Rational(7, 4)

def epsilon_close(x, y, epsilon=Rational2(1, 1000)):
    return distance(x, y) <= epsilon

epsilon_close(Rational2(10,100), Rational2(11,101))

False

实数的形式极限定义

书本里将实数将作为有理数序列的极限

当谈到序列时，默认都是指无限序列，柯西序列是一个无限长的序列，对任意个足够小的正有理数 e, 都存在一个 N, 使得对任意 i,j>=N, d(a[i],a[j])<=e.

前文说过，从逻辑角度看（或者当前的实分析角度看），我们从小学习的整数四则元素里的规则，实际是数的十进制表征下发展出来的一种计算技巧。但对于计算来说，技巧本身就是该运算的本质。

计算机无法表示无限的实数，因此它只能通过近似的方式来处理。

柯西序列

符号约定，本文中，用 a[m:] 表示无穷序列 $ (a_{n})_{n=m}^{\infty} $

定义 5.1.1: 有理数序列

定义 a[m:]=[a[m],a[m+1],…] 表示一个无限长的序列，其中 m 是自然数，该序列中，从 n>=m 开始，每个自然数 n 都映射到了一个有理数 a[n].

注意这个定义并不要求每个自然数 n 能通过一个固定的函数映射到 a[n] ，这种简单映射的典型序列是 a[n]=1/n 。

但还可以通过更复杂的机制来定义 a[n]，比如牛顿法：

$ a_{n+1}=(a_{n}+\frac{x}{a_{n}}) /2 $

def sqrt_stream(x, precision=1e-10):
    guess = 1.0
    while True:
        next_guess = (guess + x / guess) / 2
        if abs(guess - next_guess) < precision:
            break
        guess = next_guess
        yield guess

# 使用生成器
sqrt_gen = sqrt_stream(2)
for approximation in sqrt_gen:
    print(approximation)

1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899

但我们要求这些都是用前文定义过的有理数来实现：

def sqrt_stream(x, precision=Rational2(1, 1000)):
    guess = Rational2(1)
    while True:
        next_guess = (guess + x / guess) / 2
        if abs(guess - next_guess) < precision:
            break
        guess = next_guess
        yield guess

# 使用生成器
sqrt_gen = sqrt_stream(2)
for approximation in sqrt_gen:
    print(approximation)

sqrt_gen = sqrt_stream(4)
for approximation in sqrt_gen:
    print(approximation)

定义 5.1.8: 有理数的柯西序列

定义 5.1.3: ε-稳定性。 ε-稳定的序列中，对于任意 i,j, a[i] 和 a[j] 的距离都小于 ε

定义 5.1.6: 最终 ε-稳定性。即存在一个 N, 使得 a[N:] 序列是 ε-稳定的

定义 5.1.8: 柯西序列 a[0:] 是这样一个序列，对于任意 ε，它都是最终 ε-稳定的

.

对于序列，我们用 python 的生成器来表示：

from itertools import count
def gen_1_n():
    for n in count(start=1):
        yield Rational2(1, n)


_1_n = gen_1_n()
for _ in range(5):
    print(next(_1_n))

1
1/2
1/3
1/4
1/5

我们直接定义最终 e 稳定，函数接受一个生成器函数，然后用一个阈值，用模拟的方式去检查：

import random
from itertools import islice
def final_e_stable(gen_func, n=20, e=Rational2(1, 200)):
    gen = gen_func()
    elements = list(islice(gen, n, n+5))
    for _ in range(5):
        ele1, ele2 = random.sample(elements, 2)
        if abs(ele1 - ele2) > e:
            return False
    return True

final_e_stable(gen_1_n)

True

注意传入 final_e_stable 的需要是一个生成器函数，而不是生成器，因为生成器执行 islice 或者 next 取值后会消耗掉，我们需要维持函数才能多次检查这个序列。

n=20 和 e=1/200 是以 1/n 的标准来选择的，我们就以这个标准近似判断柯西序列。

定义 5.1.12: 有界序列

M 是大于等于 0 的有理数，那么：

有限序列 a[1:n+1] 以 M 为界，等价于所有 1<=i<=n, |a[i]|<=M

无限序列 a[1:] 以 M 为界，等价于所有 i>=1, |a[i]|<=M

.

引理 5.1.15；习题 5.1.1: 柯西序列是有界的

柯西序列是有界的

思路书本已经给出，对于柯西序列 a[1:], 由于它对任意 e 都是 e-稳定的，因此它是 1-稳定的，即存在一个 N 使得所有 i,j>=N 都满足 d(a[i],a[j])<=1, 那么这意味着，所有 a[i] 都在 a[N]-1 和 a[N]+1 之间，因此所有 |a[i]|<=a[N]+1。而对于小于 N 的部分 a[1:N+1] 是有界的，因此存在一个 M 使得所有 |a[i]|<=M 其中 i<=N

取 M' 为 max(a[N]+1, M), 可以知道 a[1:] 是以 M' 为界的

习题 5.2.2: 最终 ε-接近与有界

a[1:] 和 b[1:] 是最终 e 接近的，那么 a[1:] 有界等价于 b[1:] 有界

本题中 a,b 可以不是柯西序列，比如 a,b 都是同一个 1 和 -1 交替的序列。

如果 a[1:] 有界，那么对任意 i>=1, |a[i]|<=M, 由于 a,b 是最终 e 接近，因此存在一个 N 使得 j>=N 时，d(a[j],b[j])<=e, 因此类似引理 5.1.15 的证明，对 b[N:] 部分，任意 |b[j]|<=M+e, 而对于 b[1:N+1] 它是有限、有界的，因此 b[1:] 是有界的。

定义 5.2.6: 等价序列

按照前文中形成的惯例，我们定义完一个新的数学对象之后，一般马上定义对象之间的等价关系，以上定义完序列之后我们也马上定义序列等价关系：

定义 5.2.1: ε-接近的序列。序列 a[0:] 和 b[0:] 是 ε-接近的，那么对于任意 i, a[i] 和 a[j] 之间的距离小于 ε

定义 5.2.3: 最终 ε-接近的序列。序列 a[0:] 和 b[0:] 是最终 ε-接近的，那么存在一个 N ，使得 a[N:] 和 b[N:] 是 ε-接近的

定义 5.2.6: 等价序列。如果两个序列对于任意正有理数 ε 都是最终 ε-接近的序列，那么二者是等价的

.

同样，逻辑上，我们要照例去证明这种等价关系是符合等于公理的，但由于它是直接基于每个 a[i],b[i] 数值之间的近似性，因此只要近似关系符合等于公理，那么该定义也符合等于公理。

和 final_e_stable 很类似，这里我们

def seq_equal(gen_func1, gen_func2, n=20, e=Rational2(1, 20)):
    gen1 = gen_func1()
    gen2 = gen_func2()
    elements1 = list(islice(gen1, n, n+5))
    elements2 = list(islice(gen2, n, n+5))
    for ele1, ele2 in zip(elements1, elements2):
        if abs(ele1 - ele2) > e:
            return False
    return True

def gen_2_n():
    for n in count(start=1):
        yield Rational2(2, n)

seq_equal(gen_1_n, gen_2_n)

True

命题 5.2.8: 1.00.. = 0.999.. 是相等的

通过证明序列 $ 1+\frac{1}{10^{n}} $ 和 $ 1-\frac{1}{10^{n}} $ 是等价的，我们第一次严格地说清楚了以上两个数字是相等的。

但要理解的是，此处的"相等"来自于序列的等价，它显然与自然数的相等是不一样，但这些相等都满足等于公理，在数学使用，它们就是"相同"的"相等" 。

习题 5.2.1: 等价的柯西序列

如果 a[1:] 和 b[1:] 等价，那么 a[1:] 是柯西序列等价于 b[1:] 是柯西序列

这里是一个距离传递的问题，如果 a b 两个序列很接近， a 又是最终平稳，那么 b 也会最终平稳。

逻辑上，我们已经开始频繁使用经典的 ε-N 模式，也就是用全称连词修饰（一个非常小）有理数 ε，用存在量词修饰（一个大的）整数 N, a[1:] 是柯西序列可以写成：

A(e)E(N)[A(i,j)[(i>=N&j>=N)->d(a[i],a[j])<e]]

我们最终想把以上的 a 替换成 b:

A(e)E(N)[A(i,j)[(i>=N&j>=N)->d(b[i],b[j])<e]]

即我们要证明，给定任何 e, 存在一个 N>=1, 使得 d(b[i],b[j])<e 对所有 i,j>=N 成立。这里的证明方式不是直接用逻辑演绎规则去替换第一个命题然后一步一步得到第二个命题，我们更多的是用类似自然推理的方式。所谓自然推理是说，先假定某些你所需要的结论里的部分前提命题，比如，"给定任何 e" ，然后在这个前提下，去找一些子规则，比如根据 a 是柯西序列假设，可以得到，

存在一个 N'>=1, d(a[i],a[j])<e/3 对所有 i,j>=N' 均成立。
同时根据 a[1:] 和 b[1:] 等价，存在 M'>=1, d(a[i],b[i])<e/3 对多有 i,j>=M' 均成立。
注意以上两句话里的 i,j 都是不同的，它们分别是在 N', M' 的语境下的任意 i,j, 我们需要去统一这两组不同的 i,j
那么取 M=max(M',N'), 也就对任意 i,j>=M, 满足 d(a[i],b[i])+d(a[i],a[j])<2e/3
根据三角不等式，我们能证明 d(a[j],b[i])<=2e/3
但我们要证明的是 d(b[i], b[j])<e
根据三角不等式，又有 d(b[i],b[j])<=d(b[i],a[i])+d(a[i],b[j])<=e/3+2e/3=e
于是得到了希望的结果， d(b[i],b[j])<=e

首先我们都是在"给定任意 e" 这个要证明的结论里的前提假设下，e 只是一个占位符，可以被任何值替换，至于为什么要选择 e/3, 完全是先逆向凑出来的。

在证明多个序列之间关系上

def gen_1_0000():
    for n in count(start=1):
        yield 1 + 1 / Rational2(10)**n


def gen_0_9999():
    for n in count(start=1):
        yield 1 - 1 / Rational2(10)**n

seq_equal(gen_1_0000, gen_0_9999)

True

实数的构造

正如我们只能传入最多 a,b 两个数到 Rational2 中来构建有理数，假设我们已经构造了一个叫作 Real 的类，那么我们能传入的就是一个前文提到过的以下类型的生成器函数：

def gen_0_9999():
    for n in count(start=1):
        yield 1 - 1 / Rational2(10)**n

而本章中对于实数的运算，都是按位运算，比如乘法是如下形式：

for n in count(start=1):
     yield next(gen1)*next(gen2)

因此在实现上，它比有理数还要直观，毕竟有理数的加法还是需要对分母通分的。

实数的关键操作是形式极限，但实现上只能计算近似极限。由于我们只能给出具体的生成器函数，因此对该函数对应的序列求近似极限，实际就是把生成器计算到某个精度，比如：

list(islice(gen_0_9999(), 20))[-1]

99999999999999999999/100000000000000000000

因此这部分的核心是逻辑上的，如何逻辑上严谨地把实数"逼"出来。除此之外，从计算角度看都是工程问题，比如抽象层上 IEEE 754 对浮点数是如何表征的，实现层上则是具体浮点运算硬件的设计了，这些本文都不做讨论。

在后文中上确界运算被逻辑刻画后，以及"极限" 操作被定义出来（正如除法被定义出）后，我们才会实现完整的 Real 类来近似地表达逻辑上的严格实数。

定义 5.3.1: 实数

实数被定义为形如 LIM_a[1:] 的对象，它可以看作是柯西序列 a[1:] 一个形式极限，两个实数相等，则它们对应的柯西序列等价。

这种形式极限和定义自然数，唯一区别是这个序列是无限的，我们从逻辑上可以很容易描述出它是无限（因为有自然数这种无限集），但在实现上，只能通过近似的方式来展示极限序列的前缀部分的性质。

但在另一个维度上，这种形式极限和自然数、有理数的形式又是类似的，即一个数都有无穷种形式。比如 1–3 和 2–4 等价 2//4 和 1//2 等价，而序列 1/n 和 $ 1/n^2 $ 的形式极限也是等价。

命题 5.3.3: 形式极限是定义明确的；习题 5.3.1: 实数等价符合公理

自反性： LIM_a[1:]=LIM_a[1:] 根据定义等价于柯西序列 a[1:] 和 a[1:] 等价，这是合理的，因为序列与自身的都是稳定 0-接近的。
对称性： x=y 等价于 y=x, 这可以规约到命题 4.3.7(b) 中 e-接近性的对称性。
传递性： x 和 y 等价，那么对于任意 e, 它们是最终 e/2 接近，同理 y 和 z 也是最终 e/2 接近，根据命题 4.3.7(c), x 和 z 是最终 e-接近

定义 5.3.4: 实数的加法

两个实数加法定义为，两个柯西序列对应元素的和构成的新的序列的形式极限

定义 5.3.9: 实数的乘法

两个实数乘法定义为，两个柯西序列对应元素的乘积构成的新的序列的形式极限

命题 5.3.10;习题 5.3.2: 乘法是定义明确的

如果 x = x'，那么 xy = x'y。

首先，x,y 可能对应无穷条相互等价的柯西序列，比如 1/n 1/n^2, 2/n 都可以是实数 0 的柯西序列。

但根据引理 5.1.15, 所有柯西序列都是有界的，假设其中某一条序列对应的界分别是有理数 Mx 和 My, 那么根据习题 5.2.2, 其他所有等价的的序列的界也多是 Mx 和 My, 因此我们不讨论这些序列具体是什么，而只讨论它们的界。

x,y 对应的界是 Mx 和 My, 那么 M=Mx+My 就是它们共同的界。

x=x' 意味着 x 和 x' 是最终 e/M 接近的，y 和 y 是最终 0 接近，，命题 4.3.7(h) 说的是 ε, δ > 0, x 和 y 是 ε-接近，并且 z 和 w 是 δ-接近的，那么 xz 和 yw 是 (ε|z| + δ|x| + εδ)-接近的。

替换到本题场景，那么存在一个足够的的 N, 使得 (xy)[i] 和 (x'y)[i] 是 M(e/M)=e 接近的，因此 xy 和 x'y 等价。

这说明实数乘法是符合等于关系的替换公理的，因此它是一个定义良好的运算（或函数）

习题 5.3.3: 有理数可以被实数覆盖

设 a、b 是有理数，证明：a = b，当且仅当 LIM_a[1:] = LIM_b[1:], 其中对于所有 i>=1, a[i]=a,b[i]=b

a=b, 那么序列 a,a,… 和 b,b,b… 是 0-接近的，根据实数定义，两个序列的形式极限是等价的，即 LIM_a[1:] = LIM_b[1:]
如果序列 LIM_a[1:] 和 LIM_b[1:] 等价，那么对于任何有理数 e>0, 存在一个足够大的 i, 使得 d(a[i],b[i])<=e, 也就是 d(a,b)<=e, 根据命题 4.3.7(a) 得到 a=b.

习题 5.3.3 里没有有讨论一般的有理数对应的其他序列？比如题中 a,b 是有理数，但如果把它类型改为实数，也就是 a 是实数，那么全 a 组成的柯西序列 a[1:] 只是 a 对应的柯西序列等价类之一，但至少我们可以用 0,1,2 来表示某个具体的实数了，也就是本题之后 0,1,2 又获得了实数的类型。

习题 5.3.4: 等价有理数序列

如果有理数序列 a[0:] 是有界的，且 a[0:] 等价于 b[0:], 证明 b[0:] 有界。

注意这个题目和习题 5.2.2 的差别，后者基于更底层 e-接近概念，因此将等价翻译到 e-接近即可。 a[0:] 和 b[0:] 等价，意味着任意有理数 e>0 下两者都是最终 e 接近，因此取 e=1, 那么 a[0:] 和 b[0:] 是最终 1 接近的，根据 5.2.2, a[0:] 有界意味着 b[0:] 有界。

习题 5.3.5: LIM_1/n = 0

再次强调：因为习题 5.3.3 我们才能写出这种式子，否则 LIM_1/n 与 0 会类型不匹配，无法比较。

取 N=1/e, 即可以得到，当 n>=N 时， |1/n-0|=e<=e, 因此 1/n 序列和 0 序列是等价的。

命题 5.3.11: 实数域

x + y = y + x

(x + y) + z = x + (y + z)

x + 0 = 0 + x = x

x - (−x) = (−x) + x =0

xy = yx

(xy)z = x(yz)

x1 = 1x = x

x(y + z)= xy + xz

(y + z)x = yx + zx

$ xx^{-1} = x^{-1}x =1 $

实数域性质

定义 5.3.12: 远离 0 的序列

a[1:] 是远离 0 的，等价于存在一个有理数 c 使得 |a[n]|>=c 对于一切 n>=1 均成立。

引理 5.3.14: 不为 0 的实数是某个远离 0 的柯西序列的形式极限

设 x 是一个不为零的实数，那么存在某个远离 0 的柯西序列 a[1:] 使得 x=LIM_a[1:]

实数的排序

命题 5.4.4: 正实数的基本性质

对于任意的实数 x，下述三个命题中恰好有一个为真：(a) x 是 0；(b) x 是正的；(c) x 是负的。

实数 x 是负的，当且仅当 −x 是正的。

如果 x 和 y 都是正的，那么 x + y 和 xy 都是正的。

.

习题 5.4.1: 正实数基本性质证明

我们回顾之前证明各种数的三歧性的方法，首先都要证明三个命题两两之间不能同时成立，这部分按照小于的定义更容易说明，然后证明三个命题至少一个成立，对于后者：

自然数上，通过归纳法证明，因为我们没有说明某个关系一定存在的公理，只能回到 basecase 状态
整数和有理数都是构建在自然数之上，因此可以基于自然数的三歧性来证明
目前来到了实数，一个实数可以对应无数条等价的柯西序列，但目前我们划分出来了正远离 0,负远离 0 和 0 三类。如果它是正的，显然它也存在一些在 0 上下穿梭的等价序列，但我们不关心这类序列。如果它是 0, 那么一切穿梭于 0 上下的等价于 0 的序列都被看作是 0 （当然也包括元素都是大于 0 的序列，比如 1/n）
三歧性证明：先证明三者不能共存：
- 如果 x 是 0, 根据习题 5.3.3, x 等价于一个全是有理数 0 的柯西序列那么说明对任意正有理数 e, 都能找到足够大的 i, 使得 |x[i]|<e, 如果它是远离 0 的，那么存在一个正有理数 c, 满足 |x[i]|>c, 但 e=c/2 就会导致矛盾。
  
  因此 x 是 0 的时候，正远离 0 或负远离 0 都不成立。
- 如果 x 是正远离 0 ，根据定义，存在一个柯西序列，每个 i 都满足 x[i]>c, c 是正有理数，现在假设同时存在一个与之等价的柯西序列 y，对每个 i 都满足 y[i]<-d, 其中 d 是正有理数，那么这两个序列的每个 i 都满足 d(x[i],y[i])>d+c, 因此 x 和 y 就不是 (d+c)/2 稳定的，这与它们等价是矛盾的。所以 x 不会是负远离 0 的。
- 同理，x 是负远离 0 时 x 不可能是正远离 0
以上证明了三者最多有一个命题成立。接着证明至少有一个命题成立：
- 如果存在一个实数 x，它不等于 0, 那么根据引理 5.3.14, 它一定是某个远离 0 的柯西序列的形式极限。
- 接着证明，远离 0 的柯西序列要么是正远离 0 要么是负远离 0.
  
  这个证明基本是对引理 5.3.14 证明的延续，该引理的证明中，已经得到结论，x 所对应的柯西序列 b[1:] 满足 |b[n]| > e/2 对所有的 n >= N 均成立，这里 e 是任意取的。因此只需要继续证明，对于所有 n>=N, b[n]>e/2 恒成立或者 b[n]<-e/2 恒成立，而不能有些大于 e/2, 有些则小于 -e/2, 因为这样的话，那么对于任意 e, 就存在 i,j>N, 满足 |a[i]-a[j]|>e 这与柯西序列性质矛盾。
- 所以不等于 0 的实数 x 对应的序列要么是正远离 0 要么是负远离 0.
如果实数 x 是负的，那么 a[i]<=-c 对所有 i>=1 都成立，c 是大于 0 有理数，根据有理数乘法性质，两边乘以 -1, -a[i]>=c, 因此得到的序列是正远离 0 的，因此 -x 为正。反过来同理。
如果实数 x,y 都是正，那么 x+y 就是 x[i]+y[i] 构成的序列，它们都大于等于 c1+c2, c1,c2 分别是 x,y 远离 0 的阈值。因此 x+y 也是正。 xy 是 x[i]y[i] 构成的序列，根据有理数乘法性质，它们都大于等于 c1y>=c1c2, 因此 xy 为正。

命题 5.4.7: 实数上序的基本性质

(a) （序的三歧性）命题 x = y、x < y 和 x > y 中恰有一个为真。 (b) （序是反对称的）我们有 x < y 当且仅当 y > x。 (c) （序是可传递的）如果 x < y 且 y < z，那么 x < z。 (d) （加法保持序不变）如果 x < y，那么 x + z < y + z。 (e) （正的乘法保持序不变）如果 x < y 且 z 是正的，那么 xz < yz。

习题 5.4.2: 实数上序的基本性质证明

基本依赖命题 5.4.4

(a) （序的三歧性）x-y 根据定义是柯西序列，根据上一节实数三歧性，它有 =0,>0,<0 三种状态，根据序的定义，就说明了以上三个命题恰有一个为真。 (b) （序是反对称的） x<y 意味着 x-y 是负的，根据习题 5.4.3 那么 -(x-y) 就是正的，而负实数的定义，它等于 y-x, 因此 y>x (c) （序是可传递的）x<y, y<z 意味着 y=x+m , z-y=n, 其中 m,n 都是正实数那么 z-(x+m)=n, z=x+m+n, m+n 为正实数，因此 z>x, 根据 (b) x<z (d) （加法保持序不变） x<y 意味着 y-x 是正的，那么 y+z-x-z 是正的, 因此 x+z<y+z (e) （正的乘法保持序不变）书本证明

对比习题 4.2.5 中证明，除了把有理数改成实数，其他基本都没有变化，因此目前为止，还没有体现出实数相比有理数的优越性，假设这个有理数序列是有限的，那么它们之间确实不会有什么差别，更像是把一个标量变成了向量，而且向量只满足按位运算，它和有理数没有"维度" 上差别。

命题 5.4.9: 非负实数集是闭的

设 a[1],a[2],a[3], ··· 是非负有理数的一个柯西序列，那么 LIM_a[1:] 是非负实数。

如果是正有理数柯西序列，无法推出 LIM_a[1:] 是正实数。

推论 5.4.10: 从全体序关系到极限序关系

如果 a[1:], b[1:] 是有理数柯西序列，满足 a[i]>=b[i] 对所有 i 都成立，那么 LIM_a[1:]>=LIM_b[1:]

习题 5.4.3: 实数取整

对于每一个实数 x，恰好存在一个整数 N 使得 N <= x < N + 1（这个整数 N 被称为 x 的整数部分，并记作 N = [x]）。

这是一个存在性证明，我们要找出与 x 等价的柯西序列形式极限，序列中每个有理数都大于等于 N 但小于 N+1.

存在性证明需要能构造出一个符合性质的柯西序列，因此用 "足够大截断再重构法":

实数 x 是某个有理数的柯西序列 x[1:] 的形式极限，对于任意 e>0, 存在一个 n, 满足对于所有 i,j>=n 满足 d(x[i],x[j])<e，根据命题 4.4.1, 每个有理数 x[i] 都存在一个唯一整数 n<= x[i] < n+1:

如果 x 等于某个有理数 q，那么根据习题 5.3.3 可以知道，x 等价于全 q 序列的形式极限，由于存在整数 N 满足 N<=q<N+1, 那么 q-N 对应了一个元素都是非负有理数的柯西序列，根据命题 5.4.9, q-N 是非负实数，即 q-N>=0, q>=N; 而 N+1-q 对应了一个每个元素都是大于 0 且恒大于 (N+1-q)/2 的正远离 0 的柯西序列，因此 N+1-q>0. 最终有 N<=x<N+1
如果 x 不等于某个有理数 q, 那么可以找到一个 e 以及对应的 i, 满足 N<x[i]<N+1, 并且 x[i]-N>e 且 N+1-x[i]>e, 这意味着 j>=i 的所有 x[j] 都在 N 和 N+1 之间。

为什么可以找到？模仿引理 5.3.14 的证明：
- 因为该序列的形式极限不等于任何有理数，也就不等于任何整数，给定任何整数 M, 我们都可以找到一个 e>0 使得序列 x[1:] 不是最终 e-接近 LIM_n 的。
- 把 e 设为定值，因为 x[1:] 是柯西序列，所以它是最终 e-稳定的，由于 e/2>0, 因此它还是最终 e/2 稳定的。于是存在一个 M>=1 使得 |x[i]-x[j]|<=e/2 对所有 i,j>=M 均成立。
- 另外我们得不到 |x[i]-n| 对所有 i>=M 均成立，这样就蕴含了 x[1:] 最终 e-接近全 n 的整数序列了。因此必定存在一个 k>=M, 使得 |x[k]-n|>e, 又因为 |x[k]-x[i]|<=e/2 对所有 i>=M 均成立，于是根据三角不等式， |n-x[i]|+|x[k]-n|>=|x[k]-x[i]| 得到 |n-x[i]|>=e/2 对所有 i>=M 均成立。
- 因此如果 M 是 x[i] 的整数下限，那么存在 e1 满足 x[i]-e1/2>=N, 如果 N+1 是 x[i] 的整数上限，那么存在 e2 满足 N+1-x[i]>=e2/2.
- 选择 e=min(e1/+e2/2) 即可找到一个 M, 使得当 i>M 时， x[i] 与 N 和 N+1 的距离都小于 e。
这并没有结束，还要把序列 x[:i+1] 中每个值都重新设成 x[i], 这样新的序列和原序列是等价的。
于是给定任何实数 x 对应的柯西序列, 都可以构造出一个与之等价的柯西序列，其中每个有理数都在 N 和 N+1 之间，因此 N-x 是负的，N+1-x 是正的

这里的核心在于，只有 >= 才满足，如果每个元素都满足 a[i]>b[i], 并不能保证极限是大于的，很可能会是等于，这是无限导致的问题，并开始显示出实数和有理数的差别。

命题 5.4.12: 有理数对实数的界定

设 x 是一个正实数，那么存在一个正有理数 q 使得 q <= x，并且还存在一个正整数 N 使得 x <= N。

推论 5.4.13: 阿基米德性质

设 x 和 ε 是任意的正实数，那么无论 x 多大，ε 多小，只要后者不断重复，一定存在一个正整数倍数 M 使得 Mε > x。

有理数也有这个性质，但实数本身是更难描述的，而本推论实际建立了一般实数和整数之间的关系

习题 5.4.4: 正实数的有理数下界

对任意的正实数 x > 0，存在一个正整数 N 使得 x > 1/N > 0。

根据阿基米德性质，1 和 x 都是正实数，那么存在 N 使得 Nx>1, 两边乘以正数 1/N 即得证。

命题 5.4.14: 实数之间存在有理数

给定任意两个实数 x < y，我们能够找到一个有理数 q 使得 x < q < y。

习题 5.4.5: 实数之间存在有理数证明

用阿基米德性质证明两个实数 x < y，能够找到一个有理数 q 使得 x < q < y。

这里的思路是，我们不知道 x 和 y 之间"间隔" 是多大，但根据阿基米德性质，可以用整数去放大它们之间的间隔，即 y-x 是正数，那么根据习题 5.4.4, 存在 N 使得 y-x>1/N>0, 也就是 Ny-Nx>1,

这时候间隔足够大，大到比整数间隔还大，因此想说明 Nx 和 Ny 之间容得下一个整数，然后把整数除以 N ，回到原始的尺度，得到的有理数就是满足 x<q<y 的 q 。

因此这里要构造 Nq, 而习题 5.4.3 证明任何实数 x 都可以找到整数 a 使得 a<=x<a+1，因此 Nx 也必然在两个整数 a 和 a+1 之间，满足 a<=Nx<a+1，根据 Ny-Nx>1 又得到 Ny>Nx+1, 继而有 Ny>a+1, 因此 Nx<a+1<Ny a+1 就是要找的 Nq, 最终的有理数为 q=a+1/N

习题 5.4.6: 实数作为 ε 的性质1

设 x、y 是实数，并且 ε > 0 是一个正实数，证明：|x−y| < ε 当且仅当 y−ε < x < y+ε，以及 |x − y|<=ε 当且仅当 y − ε <= x <= y + ε。

之前我们都是将 e 看作足够小的正有理数，这里证明的是实数。

x-y 如果大于或等于 0, 那么 |x-y|=x-y<e 等价于 x<y+e

x-y 如果小于 0, 那么 |x-y|=-(x-y)=(y-x)<e 等价于 x>y-e
反过来， y−e < x < y+e , 根据命题 5.4.7, 两边加上实数 -y 得到： e>x-y>-e:
- 当 x-y>0, |x-y|=x-y<e,
- 当 x-y<0, 因为 x-y>-e 所以 x-y+e>0, 两边乘以 -1, 根据命题 5.4.4, -(x-y+e)<0 ，根据命题 5.3.11, y-x-e<0, 继而得到 0<y-x<e. 因此 |y-x|=y-x<e.

<= 的证明方法类似。

习题 5.4.7: 实数作为 ε 的性质2

设 x 和 y 是实数：

x <= y + ε 对所有的实数 ε > 0 均成立，当且仅当 x <= y。
- 从右到左：如果 x<=y, 那么 x-y<=0<=e, 因此 x<=y+e 多所有实数 e>0 都成立
- 从左到右：x<=y+e 对所有实数 e>0 都成立，假设 x>y, 那么 x-y=a 是一个正实数，这时候可以选择 e=a/2, 由于 x-y 可以小于等于任意正实数，因此 x-y=a<=a/2, 导致了矛盾。
|x − y| <= ε 对所有的实数 ε > 0 均成立，当且仅当 x = y。
- 从右到左：如果 x=y, 那么 x-y =0, 对任意实数 e>0, 都满足 0<=e.
- 从左到右： |x − y| <= e, 如果 x!=y, 那么：
  - x-y>0 时，x-y<=e, 可以用与上一个证明相同的方式假设 x-y 是一个固定值，结果导出矛盾
  - x-y<0 时，x-y>=-e, 两边乘以 -1, y-x<=e, 同样假设 y-x=a, a 为正实数，导出矛盾。

习题 5.4.8: 序列上界到极限上界

设 a[1:] 是有理数的一个柯西序列，并且设 x 是实数。

证明：如果 a[n] <= x 对所有的 n >= 1 均成立，那么 LIM_a[1:] <= x。

类似地，证明：如果 a[n] > x 对所有的 n > 1 均成立，那么 LIM_a[1:] > x。

.

证明：如果 a[n] <= x 对所有的 n >= 1 均成立，那么 LIM_a[1:] <= x。

假设 x 对应了某个柯西序列 x[1:], a[n] <= x 对所有的 n >= 1 均成立意味着对于每个 a[n], 存在一个与 x[1:] 等价的柯西序列，它的每一项都大于等于 a[n], 这里要证明的是，把 a[n] 组成一个序列后，仍然能找到一个与 x[1:] 等价的柯西序列满足形式极限之间的不等式关系（有点对角线法的感觉）

用反证法：如果 LIM_a[1:]>x, 那么根据命题 5.4.14, 存在一个有理数 q, 满足 x<LIM_q<LIM_a[1:]
q 组成的柯西序列形式极限是一个实数 LIM_q，由于 x>=a[n] 对每个 n>=1 都成立，因此对任意 i, 有 LIM_q>x>=LIM_a[i], 根据传递性有： LIM_q>=LIM_a[i], 这意味着对任意 i, q>=a[i]
根据推论 5.4.10, LIM_q>=LIM_a[1:], 这与 x<LIM_q<LIM_a[1:] 矛盾

类似地，证明：如果 a[n] > x 对所有的 n > 1 均成立，那么 LIM_a[1:] > x。

反证法：假设 LIM_a[1:] <= x, 这时要考虑两种情况

LIM_a[1:] < x 时, 用类似上一小题的方式可以证明。
LIM_a[1:] = x ，那么 x 对应一个柯西序列 x[1:], 对任何有理数 e>0, 存在 N>=1, 使得 |x[i]-a[i]|<e 对所有 i>=N 均成立。

而 a[n]>x 对任意 n 都成立，那么选择 n=i, 那么 x 对应着另外一个柯西序列 b[1:], 其中存在 N 使得 a[i]-b[j]>=c 对所有 j>=N 均成立，c 是某个固定正有理数。|a[i]-b[j]|>=c 自然也成立。

根据三角不等式， |x+y|-|x|<=|y| 有 c-e <=|x[i]-a[i]|-|b[j]-a[i]|<=|x[i]-b[j]|, 这表明 x[1:] 和 b[1:] 不等价，因此矛盾。

最小上界性质

该性质是实数真正的核心特点

定义 5.5.1: 上界

设 E 是 R 的一个子集，并且设 M 是一个实数。称 M 是 E 的一个上界，当且仅当对于 E 中任意一个元素 x 都有 x<=M。

定义 5.5.5: 最小上界

设 E 是 R 的一个子集，且 M 是一个实数。称 M 是 E 的一个最小上界，当且仅当(a) M 是 E 的一个上界，同时(b) E 的任意其他上界 M' 一定大于或等于 M。

空集没有最小上界，因为如果存在最小上届 M, 那么由于任意数都是空集的上界，那么小于 M 的数也是上界，导致矛盾。

命题 5.5.8: 最小上界的唯一性

设 E 是 R 的一个子集，那么 E 最多有一个最小上界。

通过反证法，根据定义可以直接得到唯一性。但存在性更难证明（自然数三歧性存在性可以用归纳法）

命题 5.5.9: 最小上界的存在性

设 E 是 R 的一个非空子集，如果 E 有一个上界（即 E 有一个上界 M），那么它必定恰好有一个最小上界。

首先这里证明的是，如果存在上界，那么存在唯一的最小上界。核心在于最小上界是通过有理数序列构造出来的，这是实数的形式，因此有理数集合是无能为力的。

习题： 5.5.2: 逼近上界的有理数整数

设 E 是 R 的一个非空子集，n > 1 是一个整数，并且设 L < K 是两个整数。假设 K/n 是 E 的一个上界，但是 L/n 不是 E 的上界。证明：存在一个整数 L < m <= K 使得 m/n 是 E 的一个上界，但 (m − 1)/n 不是 E 的上界。

先从最基础的 n=2 开始：

n=2 时， K/2 是 E 的上界，但 L/2 不是 E 的上界，要证明存在 m/2 是 E 的上界，但 (m-1)/2 不是。这里证明的是什么？它想说的是上界和非上界之间间隔大小的问题，并且我们不能假设有一个上确界存在，因为本证明是上确界存在证明的一个环节，需要避免循环证明。因此我们没有一个具体的锚点，来谈论 L/2 与锚点的距离，但对于上界，可以谈论它与集合 E 中所有元素的序关系。

整数之间最小间隔是 1, 因此除以 2 之后， K/2 和 L/2 之间最小间隔是 1/2. 这里要证明的就是，上界和非上界之间的最小距离至少是 1/2 （显然上界和非上界距离可以无穷远）

由于 L/n 和 K/n 如此宽泛，没有什么构建的着手点，因此用反证法，如果对于所有满足 L<m<=K 的 m, 出现两种反例：
- m/2 和 (m-1)/2 都是 E 的上界：
  
  对于 E 中所有元素 x, x<=(m-1)/2 ，如果取 m=L+1/2, 由于 L 和 K 都是整数，满足 L+1/2 在 L 和 K 之间，这意味着 E 中所有元素 x 都满足 x<=L/2-1/4 。
  
  由于 L/2 不是上界，那么存在一些 E 中元素 x 满足 x>L/2,, 但这与所有 x 满足 x<=L/2-1/4 是矛盾的。
- m/2 和 (m-1)/2 都不是 E 的上界：
  
  说明 E 中存元素 x 满足 x>m/2.
  
  这时候取 m=K, 它满足 L<m<=K, 因此 E 中存在元素 x 满足 x>K/2, 这与 K/2 是上界矛盾。
不需要用归纳法，直接考虑 n 的情况，证明存在整数 L < m <= K 使得 m/n 是 E 的一个上界，但 (m − 1)/n 不是 E 的上界。

和以上的证明类似，用反证法考虑两种情况
- m/n 和 (m-1)/n 都是 E 的上界：
  
  那么对于 E 中所有元素 x, x<=(m-1)/n ，如果取 m=L+1/n, 由于 L 和 K 都是整数，满足 L+1/n 在 L 和 K 之间，这意味着 E 中所有元素 x 都满足 x<=L/n-1/n^2 。
  
  由于 L/n 不是上界，那么存在一些 E 中元素 x 满足 x>L/n, 但这与所有 x 满足 x<=L/n-1/n^2 是矛盾的。
- m/n 和 (m-1)/n 都不是 E 的上界：
  
  说明对任意 m, E 中存元素 x 满足 x>m/n.
  
  这时候取 m=K, 它满足 L<m<=K, 因此 E 中存在元素 x 满足 x>K/n, 这与 K/n 是上界矛盾。
这意味着，我们可以用任意小的区间来"逼近" 区间的上边界

习题 5.5.3: 逼近上界的有理数的唯一性

设 E 是 R 的一个非空子集，n > 1 是一个整数，并且设 m、m' 是具有下述性质的整数：m/n 和 m'/n 都是 E 的上界，但 (m − 1)/n 和 (m' − 1)/n 都不是 E 的上界。证明：m = m'。这说明在习题 5.5.2 中构造的整数 m 是唯一的。

假设 m!=m', 考虑两种情况：

m'<m, 那么 m'<=m-1, 由于 (m-1)/n 不是 E 的上界，那么 E 中存在元素 x 满足， x>(m-1)/n>m'/n, 这与 m'/n 是上界矛盾。
m'>m, 由于 m 和 m' 对称，方法证明和以上一样。

习题 5.5.4: 逼近上界的有理数的唯一性

设 q[1], q[2], q[3],… 是一个有理数序列，并且该序列满足：只要 M >= 1 是一个整数且 n, n' >= M，就有 |q[n] − q[n']|<=1/M。

证明： q[1], q[2], q[3],… 是一个柯西序列。

另外，若 S :=LIM_q[n]，证明：|qM −S|<=1/M 对每一个 M >1 均成立。

.

q[1:] 是一个柯西序列，因为对于任何自然数 e, 能找到一个 N 使得 Ne>1 ,i,j>=N 时， |q[i]-q[j]|<=1/N<e
|q[M] - S|<=1/M 对每一个 M >1 均成立。

这里又在证明什么？前提给出一个序列，当 n 足够大的时候，其中每个元素之间的距离小于 1/M. 现在要证明的是，每个 q[i] 组成的有理数序列与 S 的距离都小于 1/M 组成的有理数的序列。

TODO

练习 5.5.5: 实数之间存在实数

将命题 5.4.14 中有理数替换为无理数：

给定任意两个实数 x < y，我们能够找到一个无理数 q 使得 x < q < y。

.

同样我们不知道 x,y 之间的间隔多大，可以通过阿基米德性质去放大这个间隔，这不过这个时候间隔取为一个无理数，比如 $ \sqrt{2} $

y-x 是正数根据阿基米德性质，存在 N 使得 y-x>sqrt(2)/N>0, 即 Ny-Nx>sqrt(2)

构造 Nq: 实数和整数性质在习题 5.4.3 证明过，这表明 Nx 夹在两个整数 a 和 a+1 之间，那它也在 a+sqrt(2) 之间，满足 a<=Nx<a+sqrt(2)，Ny-Nx>sqrt(2) 能够引出 Ny>Nx+sqrt(2), 继而 Ny>a+sqrt(2), 因此 Nx<a+sqrt(2)<Ny a+sqrt(2) 就是要找的 Nq, q=(a+sqrt(2))/N

最大下界

习题 5.5.1: 最大下界

设 E 是实数集 R 的一个子集，并且假设 E 的最小上界是实数 M，即 M = sup(E)。设 -E 表示集合 -E := {-x : x ∈ E} 证明：-M 是 -E 的最大下界，即 -M = inf(-E)。

证明 -M 是 -E 的下界，由于 M 是 E 的上界，因此任何 E 中元素 x 满足 M>=x, 那么 -M<=-x, 因此 -M 是下界
证明 -M 是最小的下界：对于任何小于 -M 的实数 y, y<-M, 那么 -y>M, 由于 M 是 E 的上确界，因此 -y 大于任何 E 中的元素 x，这意味着 y<-x, 因此 y 是 -E 的下界。

实数的有理数指数运算

定义 5.6.1: 实数的自然数次幂

设 x 是一个实数，为了把 x 升到 0 次幂，我们定义 x**0:= 1。现在递归地假设对于某个自然数 n 已经定义了 x**n，那么我们定义 x**(n+1) := x n × x。

定义 5.6.2: 实数的整数次幂

设 x 是一个非零实数，那么对任意的负整数 −n，我们定义 x**(−n) := 1/(x**n)。

以上两个定义和有理数的是一样的。

命题 5.6.3: 实数整数次幂的性质

设 x 和 y 是不为零的实数，并且设 n 和 m 是整数。

(a) (x**n)(x**m) = x**(n+m)，(x**n)**m = x**(nm)，(xy)**n = x**ny**n。

(b) 假设 n > 0，那么 x**n = 0 当且仅当 x = 0。

(c) 如果 x >= y > 0，那么当 n 为正数时有 x**n >= y**n > 0。当 n 为负数时，有 0<x**n<=y**n

(d) |x**n| = |x|**n。

(f) 如果 x,y>0, n!=0, 并且 x**n = y**n, 那么 x=y.

.

定义 5.6.4: n 次根的定义

设 x >= 0 是一个非负实数，且 n >= 1 是一个正整数，我们定义 x**(1/n)（也称作 x 的n 次根）为 x**(1/n) := sup{In(y, R) : y > 0 且 y**n <= x} 我们一般把 x**(1/2) 写作 $ \sqrt{x} $ 或 sqrt(x)。

.

这是实数里新出现的运算，n 次根的定义是集合的上确界，这是一种纯粹逻辑描述，而不提供算法。

引理 5.6.5: n 次根的存在性

设 x >= 0 是一个非负实数，且 n >= 1 是一个正整数，那么集合 E:={In(y, R) : y >= 0 且 y**n <= x} 是非空的并且是有上界的。特别地，x**(1/n) 是一个实数。

注意这里要证明什么？

非空： 0 在该集合中，因为 0 符合 0>=0 且 0**n =0 <=x
有上界

有了这两个条件，根据定理 5.5.9, 那么它就有上确界，因为我们定义的是一个实数集合

引理 5.6.6: n 次根性质

设 x,y > 0 是非负实数，且 n,m > 1 是正整数。

(a) 如果 y = x**(1/n) ，那么 y**n = x。

(b) 反过来，如果 y**n = x，那么 y = x**(1/n) 。

(c) x**(1/n) 是一个非负实数。

(d) x>y ，当且仅当 x**(1/n) >y**(1/n)。

(e) 如果 x> 1，那么 x**(1/k) 是关于 k 的一个减函数。如果 x< 1，那么 x **(1/k) 是关于k 的一个增函数。如果 x =1 ，那么对所有的 k 均有 x**(1/k) =1。

(f) (xy)**(1/n) = x**(1/n)y**(1/n)。

(g) (x**(1/n))**(1/m) = x**(1/nm)。

.

根据以上性质 y=x**(1/1) 从定义上是集合 {z>=0,z**1=x} 的上确界，但由于 (a), 可以得到 y**1=x, 根据指数定义 y**1=y, 因此 y=x.

所以 x**(1/1)=x**1=x.

习题 5.6.1: n 次根性质证明

(a) 如果 y = x**(1/n) ，那么 y**n = x。

模仿书本里对命题 5.5.12 的证明，如果 y = x**(1/n), 根据定义 y 是实数集合 S={z >= 0 且 z**n<=x} 的上确界。

用反证法，根据三歧性： y**n<x, y**n=x, y**n>x 只有一个命题成立，分别检查三种情况下 y 是否有可能是以上集合的上确界。

如果 y**n<x, 那么存在一个 e, 使得 (y+e)**n =y**n+eO, 这里 O 是关于 e 和 y 的多项式，只要 e 选择足够小，就可以使得 (y+e)**n<x. 那么集合中存在 y+e>y, 因此 y 不是上界，也就不是上确界。
如果 y**n>x, 那么同样可以找到足够小的 e, 使得 (y-e)**n=y-eO, 满足 (y-e)**x>x, 因此 y**n 不是最小上界。
于是只有 y**n=x 时，y 才是该集合的上确界，也就是 y=x**(1/n)

因此只有 y**n=x 不会导出矛盾。

(b) 反过来，如果 y**n = x，那么 y = x**(1/n) 。

如果 y**n=x, 证明 y 是 S={z >= 0 且 z**n<=x} 集合的上确界。 (a) 中最后一个情况已经证明了 y**n=x 是 S 的上确界，但这里还是列出标准的证明某个元素是上确界的思路：

先证明 y 是上界，再证明所有 S 的上界都大于或等于 y.

要证明 y 是 S 的上界，由于 S 中的元素 z 都满足 z**n<=x, 因此转而证明 z<=y:
- 反证法，如果存在 S 中元素 z>y, 那么根据命题 5.6.3(c), 会得到 z**n>y**n, z 无法满足属于 S 集合的条件，导致了矛盾。
- 因此 y 是上界。
要证明 y 是最小上界，就要证明，所有 S 的上界 u 都大于等于 y:
- 在 (a) 的证明中已经知道，只有 u 满足 u**n>=x 才是 S 的上界。
- 那么要证明 u>=y, 同样反证法，如果 u<y, 那么根据根据命题 5.6.3(c), u**n<y**n<x, 和 u 是 S 上界矛盾。
因此 y 是最小上界

根据定义 y=x**(1/n) 是 S={z >= 0 且 z**n<=x} 集合的上确界：

首先证明 0 是其中的元素：
- 它满足集合的第一个命题： 0>=0
- 并且 0**n=0 在 n>=1 时成立, 可以通过归纳法证明，n=1 是 0**1=(0**0)*0=0, 而之后归纳假设成立情况下，任何更大的 n 都满足 0**n=0. 由于 x 是非负的，因此 0<=x 为真。
接着用反证法，如果 y<0, 那么由于 0 是 S 中元素，那么 y 不可能是上界，也就不可能是上确界，因此 x**(1/n) 是非负的。

(d) x>y ，当且仅当 x**(1/n) >y**(1/n)。

先证明从右到左边：

如果 x**(1/n) > y**(1/n), 根据命题 5.6.3(c), 那么 (x**(1/n))**n> (y**(1/n))**n
根据 (a), (x**(1/n))**n=x, (y**(1/n))**n=y, 于是 x>y

再证明从左到右边：

如果 x>y, 根据 (a), 这可以写成 (x**(1/n))**n > (y**(1/n))**n
反证法，如果 x**(1/n)<=y**(1/n), 那么根据命题 5.6.3(c), x<=y, 导致矛盾。

(e)

如果 x> 1，那么 x**(1/k) 是关于 k 的一个减函数。

减函数定义为，当对任何 a>b, x**(1/a)<x**(1/b)

由于 (d) 中的等价性，相当于要证明 (x**(1/a))**(ab)<(x**(1/b))**ab

根据命题 5.6.3(a) 中的性质，等价于证明：

((x**(1/a))**a)**b)<((x**(1/b))**b)**a

根据 (a) 和 (b) 中证明的等价性，这相当于要证明：

x**b<x**a

a>b 等价于存在正自然数 c 满足 a=b+c, 因此这等价于证明：

x**b<x**(b+c)=(x**b)(x**c); 这是根据命题 5.6.3(a)

两边乘以 1/(x**b), 由于这是大于 0 的因此不改变不等式方向，于是等价于证明

1<x**c

因为 x>1, 根据命题 5.6.3(c), x**c>1**c=1 成立。
如果 x < 1，那么 x**(1/k) 是关于k 的一个增函数。

增函数定义为，当对任何 a>b, x**(1/a)>x**(1/b) 展开方式和第一小题一样，只不过最后要证明 x**c< 1.

因为 x<1, 根据命题 5.6.3(c), x**c<1**c=1 成立。
如果 x=1 ，那么对所有的 k 均有 x**(1/k)=1。

根据 (a) 和 (b)， x**(1/k) = 1 等价于 x=1**k

因为 x=1, 用归纳法可知 1**k=1

(f) (xy)**(1/n) = x**(1/n)y**(1/n)。

根据 (a) 和 (b)， (xy)**(1/n) = x**(1/n)y**(1/n) 等价于：

xy = (x**(1/n)y**(1/n))**n

根据命题 5.6.3(a), (x**(1/n)y**(1/n))**n = (x**(1/n))**n(y**(1/n))**n

再根据 (a)(b), 上式继续等于 xy.

因此等式左边等于右边

(g) (x**(1/n))**(1/m) = x**(1/nm)。

同样根据 (a),(b), 上式等价于 x**(1/n) = (x**(1/nm))**m。

再应用一次，等价于 x= (x**(1/nm))**(mn)=x

定义 5.6.7: 实数的有理数次幂

设 x> 0 是一个正实数， q 是一个有理数。为了定义 x**q，我们记 q = a/b ，其中 a 是整数且 b 是正整数，并定义： x**q:=(x**(1/b))**a

引理 5.6.9: 实数的有理数次幂性质

设 x, y > 0 是正实数，且 q 和 r 是有理数。 (a) x**q 是一个正实数。

(b) x**(q+r) = (x**q)(x**r) 且 (x**q)**r = x**(qr)。

(c) x**(-q) = 1/(x**q)。

(d) 如果 q > 0，那么 x > y 当且仅当 x**q > y**q。

(e) 如果 x > 1，那么 x**q > x**r 当且仅当 q > r。如果 x < 1，那么 x**q > x**r 当且仅当 q < r。

.

习题 5.6.2: 实数的有理数次幂性质证明

记 q = a/b, r=c/d, a,c 都是整数， b,d 是正整数 (a) x**q 是一个正实数。

x**q=(x**(1/b))**a, 根据引理 5.6.6(c), 如果 x 是非负实数，那么 x**(1/b) 是非负的，我们只需要进一步证明，x!=0 时，x**(1/b)!=0 。

反证法，如果x**(1/b)=0, 那么根据引理 5.6.6(c), 0**b=x=0, 与 x!=0 矛盾。因此 x**q 不能是 0, 只能是一个正实数。

(b)

证明： x**(q+r) = (x**q)(x**r)

左边 = x**(a/b+c/d)=(x**(1/(bd)))**(ad+bc), 根据命题 5.6.3(a):

左边 = (x**(1/(bd)))**(ad) (x**(1/(bd)))**(bc), 根据定义：

左边 = (x**(a/b)) (x**(c/d)) = (x**q)(x**r)

证明： (x**q)**r = x**(qr)。

根据定义 x**(a/b)=(x**(1/b))**a, 我们先证明，如果 x>0, 那么 (x**(1/b))**a=(x**a)**(1/b), 也就是说，b 次根和 a 次方可以交换。

根据引理 5.6.6(a)(b), y=(x**a)**(1/b) 等价于 y**b=x**a

再根据命题 5.6.3(a) 和实数有理数幂定义： ((x**(1/b))**a)**b=x**(ab/b)=x**a

因此我们证明了正实数先求 b 次根再求 a 次方等价于先求 a 次方再求 b 次根。

回到原命题左边 = (x**q)**r = (((x**(1/b))**a)**(1/d))**c, 我们可以知道，以上每个步骤的结果都是正的，因此可以把 a 交换到最外层，然后与 c 合并成 ac 得到： ((x**(1/b))**(1/d))**(ac),

而根据引理 5.6.6(g), 1/b 和 1/d 可以合并，得到：

((x**(1/bd))**(ac) = x**(ac/bd)=x**qr

根据 (b), x**(-q)=(x**q)**(-1)=1/(x**q)

(d) 如果 q > 0，那么 x > y 当且仅当 x**q > y**q。

根据引理 5.6.6(c)(d), x>y 等价于 x**(1/b) >y**(1/b)>0, 根据命题 5.6.3(c), 这又能推出 (x**(1/b))**a > (y**(1/b))**a >0,

如果 x**a > y**a >0, 用反证法可得 x>y, 所以逆向过程也成立。

(e) 如果 x > 1，那么 x**q > x**r 当且仅当 q > r。如果 x < 1，那么 x **q > x**r 当且仅当 q < r。

先把 q 和 r 的分母统一：

x**q=x**(ad/bd), x**r=x**(bc/bd)

设 y=x**(1/bd), 当 x>1 时，根据引理 5.6.6(d) y>1**(1/bd)=1.

同理如果 x<1 ，y<1. 因此本题转换为： y>1 时 y**a>y**b 当且仅当 a>b, 如果 x<1, 那么 y**a<y**b 当且仅当 a>b. 这里 a,b 都是整数。问题变成了实数的整数次幂的单调性。

证明 y>1 情况：
- 如果 y**a>y**b, 用反证法：
  - 如果 a=b 那么 y**a=y**b, 与前提矛盾。
  - 如果 a<b, 那么 b=a+z, z 是正整数
    - y**b=(y**a)(y**z), 由于 y>1, 因此 y**z>1
    - 因此 y**b>y**a, 与前提矛盾
- 如果 a>b, 同样写成 a=b+z, 可以证明 y**a>y**b
证明 y<1 情况：
- 如果 y**a<y**b, 用反证法：
  - 如果 a=b 那么 y**a=y**b, 与前提矛盾。
  - 如果 a<b, 那么 b=a+z, z 是正整数
    - y**b=(y**a)(y**z), 由于 y<1, 因此 y**z<1
    - 因此 y**b<y**a, 与前提矛盾
- 如果 a>b, 同样写成 a=b+z, 可以证明 y**a<y**b

习题 5.6.3: 绝对值与指数

如果 x 是一个实数，证明 |x| = (x**2)**(1/2)。

x>0, 那么 |x|=x>0, 根据引理 5.6.9(b) (x**2)**(1/2)=x**1=x=|x|
x=0, 那么根据定义可以得到 |x|=0=(x**2)**(1/2)。
x<0, |x|=-x, 根据命题 5.6.3(d) |x**2|=|x|**2, 而根据实数定义，如果 x<0, 它有对应的负远离 0 的柯西序列，那么它可以写成 -z, z 对应了正远离 0 的柯西序列，因此 x**2=(-z)**2>0, 因此 |x**2|=x**2

因此 x**2 可以写成 |x|**2, 记 y=(x**2)**(1/2), 根据引理 5.6.6(a), y**2=|x|**2, 根据命题 5.6.3(f), y=|x|

计算 vs 逻辑

柯西序列 vs 戴德金分割

书本中用柯西序列来表示实数，这使得我们至少更能够用一种近似的方式来表示实数，而还有一种比较经典的定义实数的方式，称为戴德金划分，它描述了实数的性质，可以把实数全体集合分割成两个集合，L 和 R, 满足

每个实数要么属于 L 要么属于 R
每个类至少包含一个数
L 中的任意一个数都小于 R 中的任意一个数。

那么存在一个实数 a, 小于 a 的所有数都在 L 中，大于 a 的所有数都在 R 中。数 a 本身可能属于 L 或 R 中的任意一类。

注意如果替换成自然数、整数或者有理数，那么不一定能找到符合要求的数 a. 比如对于有理数，如果按照小于 e 的有理数集 L 和大于 e 的有理数集 R 进行划分的话，就不存在一个有理数 a 满足以上命题，因为 L 中没有最大有理数，R 中也没有最小值有理数。

戴德金划分完全是一种逻辑描述形式，它不是构造性的，几乎无法用 python 来表达这种划分的逻辑概念，即便近似也很难。

此外，命题 5.5.9 对上确界的存在性证明是构造性的，因此我们可以近似实现这个算法：

集合最小上界算法

对于上确界操作 sup, 它作用的对象是某个实数集合，但我们无法在 python 去具体构造这种无限的稠密集合，因此只能用逻辑判断的形式。

比如 $ \sqrt{x} $ 被定义为 E={y>=0, y**2<=x} 集合的上确界，由于这是用有理数的序来做为谓词描述的，因此我们可以直接检查某个数是否是这个集合的上界。

该算法描述为：

从 n=2 开始，找到一个对整数 L 和 K, 使得 L/2 不是 E 上界，K/2 是 E 上届。对于以上形式的定义，我们可以
找到 L 和 K 后我们用二分查找的方式去找到 M, 使得 M/2 是 E 上界，但 (M-1)/2 并不是。
不断增加 n, 以此构造出一个生成器函数不断逼近特定实数

这里我们假设我们大致知道这个数是在 low 和 high 之间：

def sup(is_upper_bound, low=0, high=100):
    for n in count(start=2):
        m_n = find_M(is_upper_bound, low, high, n)
        yield m_n


def find_M(is_upper_bound, low, high, n):
    assert not is_upper_bound(low)
    assert is_upper_bound(high)
    low, high = low * n, high * n
    while 1:
        mid = (low + high) // 2
        left = not is_upper_bound(Rational2(mid - 1, n))
        right = is_upper_bound(Rational2(mid, n))
        if not left:
            high = mid
        elif not right:
            low = mid
        else:
            return Rational2(mid, n)

from functools import partial
def n_sqrt_root(x, n, y):
    return y**n > x
sqrt_root_2 = sup(partial(n_sqrt_root, 2, 2))

print(final_e_stable(lambda: sqrt_root_2, n=100))
print(final_e_stable(lambda: sqrt_root_2, n=200))

False
True

注意这个算法收敛很慢，在 n=200 的时候才达到 1/200-稳定，而前文给出过牛顿法 sqrt_stream 迭代 4 、5 次就几乎稳定了，这体现了通用算法和特别为某个场景设计的算法的效率差别，牛顿法是在极限基础上建立函数的微分才能更好描述的方法。

此外，只有集合 E 的定义是通过构造性或计算性的方式来描述的，我们才能用这种最小上界算法来近似逼近实数，然而有很多实数是不可计算的，即它的定义没法拆解成每一步都是可以同构构造方式来获得，这会引入到计算机的可计算性领域，不在此讨论。

代数数、超越数和复数的说明

从自然数扩展到整数是加法的逆 – "减法" 操作导致的扩展
从整数到有理数是乘法的逆 – "除法" 操作导致的扩展

但这个规律没有延续：

从有理数到无理数是 n 次方的逆 – "n 次根" 操作所"开启"的，但如果只是用 n 次根操作来扩展的话，得到的只是有理数+代数数+部分复数。
除去代数数之外的无理数被称为超越数，例如 e 和 $ \pi $
因此本章用有理数柯西序列方式定义出的"完备"的实数集合，实际是经过了非常长时间的打磨才得到的凝练结晶，它避开了非常多诱人却充满陷阱的直觉归纳。

体现在 sup 算法实现上，对于简单的代数数，如果能估计数的范围，是可以用 sup 算法以比较低效的方式去计算的。但对于超越数，比如 pi, 如何写它对应的 is_upper_bound 呢？

由于我们目前定义的最复杂操作就是指数运算，能写出来的 is_upper_bound 都是多项式表达出的关系。因此目前还无法用 sup 计算出超越数，它只有在定义了级数和其他更多辅助函数之后才能描述出来，但这些基本都是逻辑上的说明。从构建角度来看，级数就是对生成器函数产生的前 n 项元素进行 reduce 求和。

扬弃：从形式极限到序列极限

形式差和形式商可以看作是二元数据，它们连接了两个具体的对象，组成新的对象（数据结构），在该数据结构上继续定义一套交互规则（加减乘除算法）。

当定义完减法 "-" 和除法 "/" 之后，我们实际上是用二元函数取代了统一的二元数据结构，在计算机科学里，数据和函数（过程）实际都是代码，正如底层的数据和指令都是二进制串。

那么同样的，我们希望用动态的函数"极限" 去取代静态的数据 "极限"，后者是一个（潜在的）无限长序列。

前文已经提到，数学并不在乎其研究的对象具体是什么组成的，用形式差来表示整数，只是说明我们可以用已经定义的自然数来表示一种新的数学对象。实际上我们也不知道自然数具体是什么，比如本文中自然数竟然是一个 python 类，而对于刚学习数数的小朋友来说，自然数可能只是手指头或者其他某种可以累加的意象。

当我们借助形式差这种数据结构说明了某种新的数学对象（取名为整数）是可以被无矛盾地被论述时，就可以不拘泥于这种形式了，就像到了小学就不会把手指当成计数工具一样，我们留下的只有命题 4.1.6 中整数交换环所描述的性质，而这些性质似乎变成了整数的“本质”，于是学习数学的时候似乎只要去记住这些公式定理即可，然而数学的本质似乎更应该是从数据形式的构建到数学形式的抛弃，最终留下一种相对稳固且自洽的描述逻辑性质抽象层的思维方式（当然这可能只是数学研究者中数学的本质，而非数学应用者的本质）。

当抛弃了形式差之后，实际我们获得了更加灵活的表示整数的方式，比如 python 里内置的整数实际分了很多层，对于最底层，python 内部并不是把两个自然数作为数对放在相邻的内存里来表示整数的，而是用特殊的编码方式。它把二进制编码作为数的本质，底层的运算实际是一种在编码上直接变换的捷径（shortcut），比如加法用的是与、异或等逻辑计算方式，但在高层，它却假装回到了人所熟悉的符号：

20 + -1

正是因为抛弃了“死板”的形式差表示，python 对数的实现才能既满足机器的口味，又满足人的偏好。

同样，有理数的表示是如此，形式商的形式只是说明，我们可以通过已经描述过的整数，通过固定方式的排列来定义一个新数学对象，以此获得了命题 4.2.4 里有理数域的性质，至少我们证明了确实存在一种对象是可以满足这些性质的，但不需要执着于这种具体的对象上。

通过有理数的形式极限，说明了确实存在一种更丰富的数学对象，称为实数。现在我们也不需要执着于这种形式，既然实数确实存在，并且整数，有理数都可以看作是实数，那么可以直接去谈论它，而不用非得写成形式极限这种结构。

收敛和极限定律

定义 6.1.3: 实数的柯西序列

和有理数柯西序列类似，但把 e 和其中元素都替换为实数

习题 6.1.1: 增序列

设 a[0:] 是一个实数序列，并且满足 a[n+1] > a[n] 对任意的自然数 n 均成立。

证明：只要 n 和 m 都是自然数且满足 m > n，那么 a[m] > a[n]。(我们把这种序列记作增序列)。

对 m 进行归纳：

m = 0 时，前提 0>n 为假，空推断成立
假设 m>n 时，a[m]>a[n], 那么证明 m++>n 时， a[m++]>a[n] 因为前提中 a[m+1]>a[m], 因此 a[m++]>a[m]>a[n]

定义 6.1.5: 序列的收敛

实数序列 a[m:] 收敛于 L，当且仅当对于任意实数 ε > 0，该序列都是最终 ε-接近于 L。

收敛是一个序列相对一个数对象的关系，由于之前我们没有定义出实数，如果谈论收敛，就只能说某个有理数序列收敛于某个有理数，但这就好比没有定义整数的时候我们谈论 3 减 1 等于 2, 这当然是有效的，但一旦谈论 1 减 3 的时候，就会得到未定义的对象。同样的，在谈论有理数序列收敛于某个有理数时，也会遇到大量未定义的问题。因此前一章我们只谈论有理数柯西序列中各个有理数之间的接近关系，而，只有在实数对象被证明是可以定义的情况下，谈论收敛才更合适。

习题 6.1.2: 收敛概念的展开证明

设 a[m:] 是一个实数序列，且 L 是一个实数。

证明：a[m:] 收敛于 L，当且仅当对于任意给定的实数 ε > 0，存在一个 N > m 使得 |a[n] − L| < ε 对所有的 n > N 均成立。

.

这是实际就是把收敛定义展开到最底层，根据定义 a[m:] 收敛于 L, 那么该序列与 L 最终 e-接近，意味着存在一个 N>m 使得所有 i>=N 的元素 a[i] 满足 |a[i]-L|<e, 这正是所要证明的。

定义 6.1.8: 序列的极限

如果序列 a[m:] 收敛于实数 L，那么 a[m:] 是收敛的并且它的极限是 L。我们用下式来表述它：L = lim(a[m:])

如果序列 a[m:] 不收敛于任何实数 L，那么序列 a[m:] 是发散的，并且 lim(a[m:]) 是无定义的。

习题 6.1.3: 初始指标和极限无关

设 a[m:] 是一个实数序列，c 是一个实数，且 m' > m 是一个整数。证明 a[m:] 收敛于 c 当且仅当 a[m':] 收敛于 c ，即 lim(a[m:])=lim(a[m':])

从右到左： a[m':] 收敛由于 c, 根据定义 a[m':] 是最终 e-接近于 c 的，于是存在一个 N>=m' 使得 d(a[i],c)<=e 对所有 i>=N 均成立。由于 m'>m, 因此所有 i>=N>=m'>m, 这意味着存在一个 N>=m 使得 d(a[i],c)<=e 对所有 i>=N 均成立，也就是 a[m:] 收敛于 c.
从左到右边： a[m:] 收敛由于 c, 根据定义 a[m:] 是最终 e-接近于 c 的，于是存在一个 N>=m 使得 d(a[i],c)<=e 对所有 i>=N 均成立。由于 m'>m,
- N>=m': 这直接可以导出 a[m':] 收敛于 c 的描述。
- N<m' : 由于所有 i>=N 的场景，d(a[i],c)<=e 都满足，那么我们可以选择到一个 N'>=m', 使得所有 i>=N' 的情况 d(a[i],c)<=e 仍然满足。这正式 a[m':] 收敛于 c 的定义。

习题 6.1.4: 初始指标和极限无关 2

设 a[m:] 是一个实数序列，c 是一个实数，且 k >= 0 是一个非负整数。

证明：a[m:] 收敛于 c，当且仅当 a[m+k:] 收敛于 c。

本题和书本用的记号不同，但本质上还是在做初始下标的偏移。

由于 m+k>m, 因此根据系统 6.1.3 直接可以证明。

命题 6.1.12: 收敛序列是柯西序列

假设 a[m:] 是一个收敛的实数序列，那么 a[m:] 也是一个柯西序列。

收敛定义是序列最终每个值都非常接近某个数（外部距离），而柯西序列是序列最终每个值之间距离很小（内部距离），用三角不等式作为这两种距离关系的桥梁。

习题 6.1.5: 收敛序列是柯西序列的证明

假设 a[m:] 收敛由于 c, 根据定义 a[m:] 是最终 e-接近于 c 的，也是最终 e/2 接近于 c 的，于是存在一个 N>=m 使得 d(a[i],c)<=e/2, d(a[j],c)<=e/2 对所有 i,j>=N 均成立。

那么根据三角不等式，d(a[i],d[j])<=d(a[i],c)+d(a[j],c)=e, 而这是柯西序列的定义。

命题 6.1.15: 形式极限是真正的极限

假设 a[1:] 是有理数的一个柯西序列，那么 a[1:] 收敛于 LIM_a[n:]，即 LIM_a[n:] = lim(a[n:])

LIM_a[n:] 是一种特殊的实数的定义，并且是构造性的，它是定义在有理数序列上的，我们要证明更一般的极限概念可以覆盖这种特殊形式的极限的定义。

习题 6.1.6: 极限可以替代形式极限

设 a[m:] 是一个有理数的柯西序列，并且记 L := LIM_a[m:]，证明 a[m:] 收敛于 L。

由于我们对极限的定义完全建立在实数之间比较之上的，当谈论 a[m:] 收敛与 LIM_a[m:] 时，我们不需要拆开形式极限对应的序列里的每一项，而只要谈论 a[m:] 中每一项与 L 的序关系。

设 e > 0，利用反证法，假设序列 a[m:] 不是最终 e-接近于 L 的。由于 a[m:] 是柯西序列，那么存在一个 N>=m, 使得 d(a[i],a[j])<=e/2 对所有 i,j>=N 均成立，我们取。但根据假设，不可能所有 n>=N 都满足 d(a[n],L)<=e, 因此存在一个 i>=m d(a[i],L)>e, 这有两种情况：

a[i]>L+e, 根据柯西序列性质， a[j]>L+e/2 对所有 j>=k 均成立，根据习题 5.4.8, LIM_a[k:] > L+e/2, 与 L 定义不符合。
a[i]<L-e, 根据柯西序列性质， a[j]<L-e/2 对所有 j>=k 均成立，，根据习题 5.4.8, LIM_a[k:] < L-e/2, 于 L 定义不符合。

极限和形式极限有什么区别？

用形式商定义有理数时，形式上是统一的，一定是两个分量 a,b 来表示，但定义除法后， a/1=a, 于是我们可以把 a 作为有理数，它只是"一个对象", 也就是我们不在乎它是否真的是一个整数对
用形式极限定义实数时，实数是一个无穷多个有序的有理数，但定义极限后， 1 也是实数，我们不需要将其写成 1,1,1,1… 的形式极限，比如 LIM_1, 只谈论它的性质，它可以以任意灵活地（比如存储高效，计算高效）的方式去表达，甚至可以是用符号替代而根本不用求值，比如 pi 。

定义 6.1.16: 有界序列

实数序列 a[m:] 以实数 M 为界，当且仅当 |a[n]|<=M 对所有的 n >= m 均成立。我们称 a[m:] 是有界的，当且仅当存在某个实数 M > 0 使得该序列以 M 为界。

习题 6.1.7: 实数序列和有理数序列有界定义一致

模仿书本中对命题 6.1.4 的证明：

首先证明有理数有界的定义可以改写成实数有界的定义：如果 a[m:] 是有理数序列且以有理数 M 为界，那么由于有理数 q 和实数 LIM_q 是相等的，因此可以把 a[m:] 和 M 都认为是实数。
再证明实数序列有界的定义，这时候由于不是所有实数都可以映射到有理数，我们就不能精确地把序列里的对象转成有理数了，而需要考虑更宽泛的缩放，假设实数序列 a[m:] 以实数 M 为界，根据命题 5.4.14, 存在一个有理数 q 使得 M<q, 因此这和定义 5.1.12 有理数做为界定义是一致的。

也就是说如果序列有实数界，那么就有有理数界，反之亦然。

定理 6.1.19: 极限定理

设 a[m:], b[m:] 都是收敛的实数序列，并且实数 x,y 分别是序列极限 lim(a[n:]), lim(b[n:])。

(a) 序列 (a+b)[m:] 收敛于 x+y

(b) 序列 (ab)[m:] 收敛于 xy

(c) 对于任意的实数 c，序列 ca[m:] 收敛于 cx。

(d) 序列 (a-b)[m:] 收敛于 x-y 。

(e) 假设 y != 0，且对于所有的 n >= m 都有 b[n] != 0，那么序列 (1/b)[n:] 收敛于 1/y.

(f) 假设 y != 0，且对于所有的 n >= m 都有 b[n] != 0，那么序列 (a/b)[n:] 收敛于 x/y.

(g) 序列 max(a,b)[n:] 收敛于 max(x,y)

(h) 序列 min(a,b)[n:] 收敛于 min(x,y)

.

习题 6.1.8: 极限定理的证明

(a) 序列 (a+b)[m:] 收敛于 x+y

给定任意固定值 e 的情况下，根据收敛定义：

存在一个 N>=m 使得 d(a[i],x)<=e/2 对任意 i>=N 均成立。
存在一个 M>=m 使得 d(b[i],x)<=e/2 对任意 i>=M 均成立。
假设 N'=max(M,N), 那么 i>=N' 时，d(a[i],x)<=e/2 和 d(b[i],x)<=e/2 均成立
根据命题 4.3.7(d) 在实数上的扩展性质，可以知道 d(a[i]+b[j], x+y)<=e 成立

因此 (a+b)[m:] 收敛于 x+y

(b) 序列 (ab)[m:] 收敛于 xy

给定任意固定值 e 的情况下：

如果 0<e<=2|x||y| 根据收敛定义：

存在一个 N>=m 使得 d(a[i],x)<=e/(4|y|) 对任意 i>=N 均成立。
存在一个 M>=m 使得 d(b[i],x)<= d(b[i],y)<=e/(4|x|) 对任意 i>=M 均成立。
假设 N'=max(M,N), 那么 i>=N' 时，d(a[i],x)<=e/(4|y|) 和 d(b[i],x)<=e/(4|x|) 均成立
根据命题 4.3.7(h) 在实数上的扩展性质，可以知道 d(a[i]d[j], xy)<=((e/4|y|)|y| + (e/4|x|)|x| + e**2/(16|x||y|))<=(e/2+e/4)<=3e/4<=e, 因此 (ab)[m:] 收敛于 xy

如果 e>2|x||y| 根据收敛定义：

存在一个 N>=m 使得 d(a[i],x)<=|x|/2 对任意 i>=N 均成立。
存在一个 M>=m 使得 d(b[i],x)<= d(b[i],y)<=|y|/2 对任意 i>=M 均成立。
假设 N'=max(M,N), 那么 i>=N' 时，d(a[i],x)<=|x|/2 和 d(b[i],x)<=|y|/2 均成立
根据命题 4.3.7(h) 在实数上的扩展性质，可以知道 d(a[i]d[j], xy)<=(|x||y|/2+|y||x|/2 + |x||y|/4)<=5|x||y|/4<=e, 因此 (ab)[m:] 收敛于 xy
因此给定任意 e, (ab)[m:] 与 xy 都是最终 e-接近，因此 (ab)[m:] 收敛于 xy

假设实数序列 c[m:] 中每个元素 c[i]=c, 那么 c[m:]a[m:] 和 ca[m:] 是相同的
根据 (b) 由于序列 c[m:]a[m:] 收敛于 (lim(c))x ，而 lim(c) 和 c 是 0-接近的，因此 lim(c)=c, 于是序列 c[m:]a[m:] 收敛于 cx, 也就是 ca[m:] 收敛于 c

(d) 序列 (a-b)[m:] 收敛于 x-y 。

将 c 取为 -1, 根据 (c) 可知 -b[m:] 收敛于 -y
根据 (a) 可知 (a-b)[m:] 收敛于 x-y 。

(e) 假设 y != 0，且对于所有的 n >= m 都有 b[n] != 0，那么序列 (1/b)[n:] 收敛于 1/y.

先需要证明一个辅助的结果：如果一个序列的所有元素都不为零，并且该序列收敛于一个非零极限，那么这个序列是远离 0 的。

我们要证明，存在一个正实数 c, 使得序列 |a[i]|>c 对任何 i>m 都成立
反证法，如果不存在一个 c, 满足 |a[i]|>c 对任何 i>m 都成立。
由于 a[m:] 收敛于非 0 实数 L, 那么这意味着，对于任意给定的 e:
- 收敛序列都是柯西序列，于是存在 M>=m, 使得 d(a[i],a[j])<e/2 对所有 i>=M 均成立。
- 由于反证的假设，存在一个 n0>=M, 满足 d(a[n0],0)<=e/2
- 但 d(a[n0],a[j])<e/2 对所有 i>=n0 仍然成立
- 根据三角不等式， d(a[j],0)<e 对所有 j>=n0 恒成立，这与 a[m:] 收敛于非 0 实数矛盾
到目前说明的是，对于 j>=n0 部分，一定存在某个正数 d 满足 |a[i]|>d 对任何 i>=n0 都成立。
而对于 i<n0 的部分，它是有限的，由于序列所有元素不为 0, 因此这些元素的绝对值存在一个非 0 的最小值 z
取 c=min(d,z), 存在一个正实数 c, 使得序列 |a[i]|>c 对任何 i>m 都成立，因此整个序列都是远离 0 的。

接着给定任意固定值 e 的情况下，根据收敛定义：

存在一个 N>=m 使得 d(b[i],y)<=c|y|e 对任意 i>=N 均成立。这里 c 是序列 b[i] 中远离 0 描述里的那个正实数。
那么 d(1/b[i], 1/y)=|1/b[i]-1/y|=d(b[i],y)/(|b[i]||y|)<=e

因此 (1/b)[m:] 收敛于 1/y.

(f) 序列 (a/b)[m:] 收敛于 x/y 。

根据 (e) 可知 (1/b)[m:] 收敛于 1/y
根据 (b) 可知 (a/b)[m:] 收敛于 x/y 。

(g) 序列 max(a,b)[n:] 收敛于 max(x,y) 给定任意固定值 e 的情况下，根据收敛定义：

存在一个 N>=m 使得 d(a[i],x)<=e 对任意 i>=N 均成立。
存在一个 M>=m 使得 d(b[i],x)<=e 对任意 i>=M 均成立。
假设 N'=max(M,N), 那么 i>=N' 时，d(a[i],x)<=e 和 d(b[i],x)<=e 均成立
由于 z=max(a[i],b[i]) 一定是在 a[i] 和 b[i] 中选择, 这意味着 d(z,x)<=e 也成立

(h) 序列 min(a,b)[n:] 收敛于 min(x,y)

和 (g) 的证明结构一样，只是把 max 改成 min

习题 6.1.9: 分母极限为 0 情况下的比值

为什么当 b[m:] 极限为 0 时，序列 (a/b)[m:] 收敛于 x/y 不成立。

如果 b[m:] 极限为 0, 序列 (a/b)[m:] 收敛于 x/y, 那么可以理解为序列 (a/b)[m:] 不收敛。

但我们可以给出反例，比如 a[n]=1/n, b[n]=1/n, 极限都是 0, 那么它们的比值极限是 1, 并非不收敛，或者 1!=0/0。

原因在于即便分母极限是 0, 但实际 (a/b)[m:] 都是非 0 的值的比值，它们是有意义的。即在无限远处可能没有定义，但具体的计算是每一步有意义的比值，这是实数相比有理数的一大特点：比值的极限不等于极限的比值。

一些不恰当的形而上类比：

每一步都有每一步的意义，尽管想象中的无限未来是没有意义的。
长远来看是悲观的，但短期都应该是乐观的
世上只有一种英雄主义，就是在认清(长远的)生活真相之后依然热爱（当下的）生活。

习题 6.1.10: 实数序列等价

如果 a[0:] 和 b[0:] 都是实数序列，证明：对于任意的有理数 e > 0，a[0:] 和 b[0:] 都是最终 e-接近的，当且仅当对于任意的实数 e > 0 它们都是最终 e-接近的。

模仿书本中对命题 6.1.4 里的证明：

从右到左：假设 a[0:] 和 b[0:] 对于任意的实数 e > 0 都是最终 e-接近的，那么特别的，当 e 是有理数的时候，它们也是 e-接近的。
从左到右：对于给定的任意实数 e>0, 根据命题 5.4.12, 存在小于 e 的有理数 q, 由于 a[0:] 和 b[0:] 等价是在定义 5.2.6 下以有理数 e-接近的，因此两个序列是最终 q 接近的。

广义实数系

定义 6.2.1: 广义实数系

在一般实数系上加入 inf 和 -inf 两个符号，它们与每一个实数都不同。并且定义实数有限的概念，如果实数是 inf 或 -inf, 那么它是无限的，否则是有限的。

定义 -(-inf)=inf, -(inf)=-inf, 且 -inf<=x<=inf, 对任何实数 x 都成立

命题 6.2.3: 广义实数排序的定义

设 x 和 y 是广义实数，我们称 x<= y，即 x 小于或等于 y，当且仅当下述三个命题之一为真。

(a) x 和 y 都是实数，并且满足 x<= y。 (b) y = inf (c) x = -inf 。

如果 x<= y 且 x != y，那么我们称 x<y 。有时我们把 x<y 写成 y>x ，并把 x<= y 写成 y >= x。

广义实数的排序

命题 6.2.5: 广义实数的序

设 x、y、z 是广义实数，那么下列命题为真。

(a) （自反性） x <= x。

(b) （三歧性）命题 x<y 、x = y 和 x>y 中恰好有一个为真。

(c) （传递性）如果 x <= y 且 y <= z，那么 x = z。

(d) （负运算使序改变）如果 x <= y，那么 -y >= -x。

.

习题 6.2.1 广义实数序的性质证明

首先，如果 x,y,z 都是一般实数，那么这些命题已经在前文（尤其是命题 5.4.7）证明过，以下只考虑出现 inf 和 -inf 场景

(a) （自反性） x <= x。

x=inf, 根据定义 6.2.3, inf<=inf
x=-inf, 根据定义 6.2.3, -inf<=-inf

(b) （三歧性）命题 x<y 、x = y 和 x>y 中恰好有一个为真。根据定义， x 要么是实数，要么是 inf 或 -inf, 分以下情况：

x=-inf: 根据命题 6.2.3, x<=y, 当 y=-inf 是 x=y, 否则根据 -inf 定义，x!=y, 因此 x<y.
x 是普通实数: 那么如果 y 是普通实数，那么满足实数的三歧性。如果 y 是 -inf, 那么可以知道 y<x. 如果 y 是 inf, 则 x<y
y 是 inf, 根据命题 6.2.3 可知 x<=y, 如果 x 也是 inf 则 x=y, 否则根据 inf 定义， x ！=y, 因此 x<y.

x=-inf, 则 x<=z 对任何广义实数 z 成立
x 为实数，y 为 inf, 则 z 只可能是 inf, 因此 x<=z
x 为实数，z 不是 inf, 那么 x,y,z 都是实数，那么它们满足实数的传递性
x 为 inf, 那么 x,y,z 都是 inf, 所有 x<=z

(d) （负运算使序改变）如果 x <= y，那么 -y<=-x。

如果 x 是 -inf, 则根据定义 -(-inf)=inf, 它大于等于任何广义实数，因此 -y<=-x
如果 x 是 inf, 则 y 必须是 inf, -inf<=-inf 也成立。
如果 x 是实数, y 是实数那么根据实数序性质可证。如果 y 是 inf, 则 -inf<=-x 对任何 x 都成立。

定义 6.2.6 广义实数集的上确界

如果集合 E 中不包括 inf ，则 sup(E) 为集合 E-{-inf} 的上确界

如果集合 E 中包括 inf ，则 sup(E)=inf

下确界定义为 inf(E)=-sup(-E)

.

注意这里 inf 为函数的时候表示确界，否则就是表示正无穷。

定理 6.2.11: 广义实数上下确界性质

设 E 是 R* 的一个子集，那么下列命题均为真。

(a) 对于每一个 x ∈ E 都有 x<= sup(E) 和 x >= inf(E)。 (b) 假设 M ∈ R* 是 E 的一个上界，即 x <= M 对所有的 x ∈ E 均成立，那么我们有 sup(E)<= M。 (c) 假设 M ∈ R* 是 E 的一个下界，即 x > M 对所有的 x ∈ E 均成立，那么我们有 inf(E) > M。

.

习题 6.2.2: 广义实数上下确界性质证明

(a) 对于每一个 x ∈ E 都有 x<= sup(E) 和 x >= inf(E)。

如果 E 中包括 inf, 则 sup(E)=inf, 因此 x<=sup(E) 恒成立。

如果不包括 inf 则如果 x!=-inf, 则根据实数集合上确界性质可知 x<=sup(E), 如果 x=-inf, 则 x<=sup(E) 对任何 sup(E) 都成立。

如果 E 中包括 -inf, 则 inf(E)=-inf, 那么 inf(E)<=x 对任何 x 都成立。如果 E 中不包括 -inf, 如果 x=inf, 则 x>=inf(E) 恒成立，如果 x 是一般实数，那么根据一般实数集下确界性质，x>=inf(E)

(b) 假设 M ∈ R* 是 E 的一个上界，即 x <= M 对所有的 x ∈ E 均成立，那么我们有 sup(E)<= M。

如果 M 是 inf, 则 sup(E)<=M 恒成立
如果 M 是 -inf, 意味着 R* 是空集，根据定义 sup(E)=-inf<=M 成立
如果 M 是实数, 那么根据上确界，根据定义实数上确界定义 sup(E)=<=M 成立

由于 inf(E)=-sup(-E), 这里要证明的是 sup(-E)<=-M ，如果 x >= M 对所有的 x ∈ E 均成立，那么 x<=-M 对于所有 $ x\in -E $ 也是成立的，因此根据 (b), 我们有 sup(-E)<=-M 即 inf(E) >= M。

序列的上确界和下确界

前一章介绍过实数的最小上界性质，即任何实数集 E 都会有一个最小上界，称为上确界。这是实数集合的关键性质，因为在整数或有理数的论域下，有些集合不存在最小上界，为什么？

这是因为在已定义的关系之下，逻辑的描述能力“突破”了数的类型，比如集合 X= $ \{y : y > 0; y^2 < 2\}$, 即便放在自然数一节，该集合的逻辑描述中所涉及的序、平方关系都已经被定义了，但 y 不会是自然数，也不会是有理数。

只有把 y 放在实数集合， X= $ \{y \in \mathbb{R} : y > 0; y^2 < 2\}$ 才不会是空集。

本节关注由序列所定义的集合的上确界和下确界，称为序列的上确界和下确界。注意，序列往往展示了某个数的计算历史过程，它展示了具体“算法”，而一般的集合可能是描述性质的，比如 X 集合的上确界是 $ \sqrt{2} $ ，但这个集合没有描述如何计算出 $ \sqrt{2} $ ，证明它是上确界用的是序和多项式的性质。

而证明（无限）序列的上下确界性质则一般用到的是 e-接近语言。

习题 6.3.1: a[n]=1/n 序列的上下确界

由于 1/n>1/(n+1), 对于所有 i, 都有 1>=a[1]>=a[i], 因此 1 是上界。接着证明 1 是最小上界，根据定义 5.5.5, 要证明其他上界 M 都满足 M>=1, 对任何小于 1 的元素，都不是 a[0:] 的上界，因为 a[1]=1, 而对于所有 x>=1 都满足 x>=1>=a[i], 因此所有 x>=1 的值都是 a[0:] 上界，因此 1 是最小上界。
接着证明 0 是最大下界。首先序列 1/n 对任何 n 都是大于 0 的，因此 0 是下界，同时说明任何小于 0 的数也是下界。接着证明 0 是最大下界。只要证明大于 0 的实数不可能是下界，那么 0 自然就是最大下界。给定任意实数 x>0 根据推论 5.4.13 阿基米德性质，存在整数 M 使得 Mx>1, 也就是 x>1/M = a[M], 所以任意 x>0 的数都不会是 a[0:] 的下界，因此 0 是最大下界。

命题 6.3.6: 序列最小上界性质

任何实数序列的 sup() 和 inf() 满足一般实数集情况下的上确界和下确界性质，例如所有 E 中的元素都小于等于上确界 sup(E), 所有上界都大于等于 sup(E).

额外的对于任何 y<sup(E), 在序列中都能找到一个元素 a[i], 满足 y<a[i]<=sup(E)

习题 6.3.2: 实数序列的小上界性质证明

由于序列中的元素构成了一个集合，而其 sup() 和 inf() 的定义于集合的一致，因此根据定理 6.2.11 自然就证明了其性质。

但额外的，我们要说明对于任何小于上确界 x 的实数 y, 能找到一个介于 y 和 x 之间的序列元素。

用反证法，假设序列中任意元素 a[i]<=y, 那么 y 就是序列的上界，且满足 y<x, 那么 y 就是上确界 sup(E), 这与 x 是上确界矛盾。

命题 6.3.8: 单调有界序列收敛

a[m:] 是一个以 M 为上界的单调递增（对所有 n>=m, 都有 a[n+1]>=a[n]）的实数序列，那么 a[m:] 是收敛的，并且其极限为 sup(a[m:])<=M 。

习题 6.3.3: 单调有界序列收敛的证明

一种“分解”的证明思路是，首先证明 a[m:] 的收敛性质，再证明其收敛于 sup(a[m:]) 。但实际第一部分证明会很困难，因为没有一个具体的收敛值作为抓手。反而直接证明 a[m:] 收敛于上确界是更方便的。

定义 x 为 sup(a[m:])，x<=M, 因为如果 x>M, 那么由于 M 是上界，因此 M=sup(a[m:]) ，这与 x>M 矛盾。

接着要证明对于任意实数 e>0, 都存在一个 n 使得 d(a[i], x)<e 对任何 i>=n 都成立。根据上一届序列上确界的性质 a[i]<=x 对所有 i>=m 都成立，因此实际要证明 x-a[i]<e 对任何 i>=n 都成立。

现在给定一个 e>0, 那么有 x-e<x, 根据命题 6.3.6, 存在一个元素 a[i], 满足 x-e<a[i]<=x 也就是 x-a[i]<e, 而由于 a[m:] 的单增性质，对任何 j>i, 都满足 a[j+1]>a[j]>..>a[i], 因此对任何 j>i 都有 x-a[j]<e, 因此 x 是 a[m:] 的极限。

习题 6.3.4: x>1 时 lim(x^n) = 0 不成立。

实际要证明序列 a[1:], 其中个元素 a[n]=x^n 是发散的。

用反证法，假设 $ (x^{n})_{n=1}^{\infty} $ 存在极限 L, 由于 $ (x^{n+1})_{n=1}^{\infty} $ 和 $ (x^{n})_{n=2}^{\infty} $ 是一样的，因为都是 $ x^{2},x^{3}\dots $, 而 $(x^{n+1})_{n=1}^{\infty} $ 等于 $ x(x^{n})_{n=1}^{\infty} $, 因此它的极限是 xL, 而根据习题 6.1.3, 极限和初始下标无关，因此 L=xL, 这包括两种情况：

L!=0, 那么 x=1, 这于前提 x>1 矛盾
L=0, 但由于 x>1 时，用归纳法可以知道序列每个元素都大于 1, 根据习题 5.4.8 迁移在实数序列上的性质，该序列极限 L>=1, 与 L=0 矛盾。

因此该序列发散。发散序列的极限不能参与一般计算，就像 0 不能作为分母一样。

上极限、下极限和极限点

radioLinkPopups

#rethink

如对本文有任何疑问，欢迎通过 github issue 或进行反馈