陶哲轩的前几章不算很难, 所以就只列出定理, 推导过程自己看着办吧.
Natural Number
要构建自然数, 先从皮亚诺公理开始. 要说明皮亚诺公理, 先定义运算符号++来代表增量.
Peano axioms
定义自然数集为N, N满足5个条件:
- $0\in N$.
- $\forall n\in N(n++\in N)$.
- $\forall n\in N(n++\not= 0)$ (防止循环)
- $\forall n,m\in N(n\not=m\to n++\not= m++)$ (一一对应)
- $\forall n\in N(P(0)\wedge P(n)\to P(n++))$ (归纳法原理)
则称$\forall n\in N$, n为自然数.
还可以通过集合论来构造自然数. 详见E.Ok: Natural Numbers
Recursion Definition
$\forall n\in N$, 存在一函数$f_{n}:N\to N$ 满足: 存在$c\in N$, 有$a_{0}=c \wedge a_{n++}=f(a_{n}),\ for\ a_{n}\ unique$.
这就是数学归纳法的用法.
Addition
Main Def: 先定义$0+m := m\ for\ m \in N$ , 那么假设定义了$n+m\ for\ n\in N$, 则有$(n++)+m := (n+m)++$. 这种方法实际上是把加号左边的数字作为右边数字做增量运算的次数了.
lemma 1: $\forall n\in N(n+0=n)$. 证明用归纳法fix 0.
lemma 2: $\forall n,m\in N(n+m(++)=(n+m)++)$. 证明用def, lemma 1进行归纳, fix m.
proposition 1(Commutative): $n+m=m+n$.
proposition 2(Associative): $(a+b)+c=a+(b+c)$.
proposition 3(Cancellation): $a+b=a+c\to b=c$.
Def 2: 自然数n是正的, 当且仅当$n\not = 0$.
proposition 4: 正自然数n加上任意自然数,结果为正.
lemma 3: $\forall n\exists b_{1}\exists b_{2}(n\in N^{+}\wedge b_{1},b_{2}\in N\to(n=b_{1}\wedge n=b_{2}\to b_{1}=b_{2}))$. 反证法
def 3: 二元关系$\ge:=\{(a,b)\in N^{2}:\exists p\in N(b+p=a)\}$. 则$\ge$满足reflexive, transitive, symmetric; 同时定义二元关系$<:=N^{\infty}\setminus\ge$ (二元关系的定义和关系见此:E.Ok: Binary Relation).
proposition 5: $\ge\cup<$ is complete. (序的三歧性)
proposition 6 (强归纳法): suppose $m_{0}\in N$, for $\forall m >m_{0}[(\forall m'\in[m_{0},m)P(m')\to P(m))\ \to\ P(m)]$.
Multiple
def 4: 任意自然数m, 定义$0\cdot m=0$. 假设已经定义了$n\cdot m$, 则定义: $(n++)\cdot m:=(n\cdot m)+m$.
lemma 4: 乘法满足交换律$\to$分配律$\to$结合律; 满足消去律(用三歧性证).
lemma 5: 乘法保持序不变.
proposition 7 (Euclidean algorithm): suppose $n\in N \wedge q\in N^{+}$, 则$\exists m,r\in N(0\le r <q\wedge n=mq+r)$.
-
此命题十分重要. 在此给出证明: from givens, suppose n = 0: m = 0 and r = 0 satisfies the condition. Suppose for some values n, the condition satisfies, then we have: for n++: $n++=n+1=mq+r+1$. If $r+1<q\to n++=mq+r',\ for\ r'=r+1$.
And if $r+1=q$: $n++=(m++)q+0|_={r'}$.
There is no possibility that $r+1>q$.
Q.E.D
-
有点像余数
Integer
def 5: 利用自然数定义整数集: 令整数集为$Z$, 则定义函数$M:=\{((a.b),z)\in N^{2}\times Z :(a,b)Mz\}$ 满足$\forall a,b,c,d\in N[M(a,b)=M(c,d)\leftrightarrow a+d=b+c]$.
def 6:继续定义整数的和与积:
-
$M(a,b)+M(c,d):=M(a+c,b+d)$. very classical !
-
$M(a,b)\times M(c,d):=M(ac+bd,ad+bc)$.
def 6$\to$proposition 8: 整数集上的加和乘是定义明确的: $\forall M_{1}, M_{2},M_{3}\in Z(M_{1}=M_{2}\to (M_{1}+M_{3}=M_{2}+M_{3}))$. 2024.4.4:突然有点说不明白如果不是定义明确的该怎么称呼? 泛函空间定义错误?
proposition 9: 自然数n和整数$M(n,0)$有相同的性质. 这是因为自然数部分的所有定理和证明中的所有自然数n都可以用$M(n,0)$来代替, 利用整数的定义得证. 所以我们在此将n和$M(n,0)$画等号. (多么伟大的一步). 结果就是自然数上的增量运算在整数的非负部分成立, 因此自然数上的加法在整数部分也成立, 由整数和的定义可将该加法扩展到负数部分. (可能有更块的路径)
def 7 (整数的负运算): $\forall M(a,b)\in Z(-M(a,b)=M(b,a))$. 负整数的定义扩展了自然数集: $\forall n\in N(-n)$. 同理, 负整数的定义是明确的.
def 7$\to$proposition 10: 整数的三歧性: $\forall z\in Z(z>0\vee z=0\vee z<0)$. z小于0即z是某正自然数的负运算的结果. 注意: 不建议三歧性来定义整数. 即虽然整数在非负区间上和自然数性质一样, 同时负数区间就是对自然数进行负运算. 按道理说用三歧性来定义非常简洁, 但实际上接着定义整数的运算需要进行非常多的case by case, 非常混乱.
proposition 11: 整数的代数定律: $\forall x,y,z\in Z$:
- $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$
由上面的定理得出结论: 全体整数构成一个交换环(见E.Ok: Ring). 易证每一个等式.
Minus
定义了整数之后，就可以定义减法 (-): $\forall x,y\in Z(x-y:=x+(-y))$.
同时因为$\forall a,b\in N(M(a,b)=a+(-b)=M(a,0)+M(0,b)=M(a,b))$, 得到结论:$-=M$. (函数相等定义见E.Ok: Function).
proposition 12: $\forall a,b\in Z(ab=0\to a=0\vee b=0)$.
proposition 13:整数满足消去律.
def 8: Order on Integer: $\forall n,m\in Z(n\ge m \leftrightarrow \exists a\in N(n=m+a))$, 且$>$就是$\ge$的non symmetric部分.
def 8$\to$ lemma 6: 懒得写了.
- 加法序保持不变
- 正乘法序保持不变
- 负运算反序
- 序是transitive的
- 序有三歧性
易证
Rational Number
利用类似除法的方法定义有理数集Q. 在这之前先定义除运算: $D=\{(x,y,z)\in Z^{2}\times Q:y\not =0\wedge \ xDy=z \}$
def 9: 有理数的加法和乘法和负运算
- $D(a,b)+D(c,d):=D(ad+bc,bd)$.
- $D(a,b)\cdot D(c,d):=D(ac,bd)$.
- $-D(a,b)=D(-a,b)$.
这些定义都是明确的, 易证.
def 10: 有理数的倒数运算: $x=D(a,b)\not=0\to x^{-1}=D(b,a)$.
proposition 14: 有理数是一个field.
- $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$.
域的定义及性质见E.Ok: Field.
Division
定义了除运算之后，可以定义除法(/): $a/b=a\cdot b^{-1}$.
def 11: 定义正有理数x, iff $\exists a,b\in Z^{+}(x=D(a,b))$.
proposition 15: 有理数有三歧性
def 12: 有理数的序:
- $x>y\ iff \ \exists p\in Q^{+}(x-y=p)$.
- $>$为$\ge$的asymmetric部分.
有理数的序满足性质:
- 序有三歧性
- 序是anti symmetric的
- transitive
- 加法保持序不变
- 正的乘法保持序不变
我们可以定义$(Q,+,\cdot,>)$为一个有序域(详见E.Ok: field).
Absolute Value
def 13 absolute value: 定义绝对值运算为
$$|x|=x\ \ for\ \ x>0,\ =-x\ \ for\ \ x<0.\ =0\ \ for\ \ x=0$$
并定义$|x-y|=d(x,y)$.
proposition 16: 绝对值有一些性质:
- $|x|=0\leftrightarrow x=0$
- $|x+y|<|x|+|y|$ (绝对值的三角不等式).
- $|xy|=|x||y|$
- $|x-y|\ge0\wedge\ |x-y|=0\leftrightarrow x=y$.
- $|x-y|=|y-x|$
- $|x-y|\le |x-z|+|z-y|$. (距离的三角不等式)
两个三角不等式值得证明一下.
def 14: ($\epsilon$接近性)当x和y的距离小于一个任意小正数$\epsilon$, 称x和y是$\epsilon$接近的. $\epsilon$接近性有一些性质:
...
Exponential
def 14 exponential: 定义$\forall x\in Q(x^{0}:=1)$. 假设$x^{n}$已经定义了, 那么定义: $x^{n+1}:=x^{n}\cdot x$.
proposition 17: 指数满足:
- $x^{n}x^{m}=x^{n+m}$, $(x^{n})^{m}=x^{nm}$, $(xy)^{n}=x^{n}y^{n}$.
- $\forall n\in Q^{+}(\forall x,y\in Q(x\ge y>0\to x^{n}\ge y^{x}>0)$. n为负数则序的方向改变
- $x,y>0\wedge n\not= 0\wedge x^{n}=y^{n}\to x=y$.
- $|x^{n}|=|x|^{n}$.
def 15: $\forall x\in Q\setminus \{0\} (\forall n\in Z^{-}(x^{-n}:=\frac{1}{x^{n}}))$.
Gaps between Rational Number
proposition 18 (有理数的整数散布): $\forall x\in Q(\exists n\in Z(n\le x<n+1)\wedge \forall n_{1},n_{2}(P(n)\to n_{1}=n_{2}))$. (unique)
证: This is a unique exists question, thus we divide in two steps:
- For the exist part: suppose arbitrary $x\in Q$ we have: $\exists a,b\in Z(x=\frac{a}{b})$.
- suppose $x=0$: for $n=0$ satisfies.
- suppose $x>0$: for $x=\frac{a}{b}\to \frac{a}{b}>0$. By proposition 9 andEuclidean algorithm, we have: $\forall a\in Z,b\in Z^{+}$, we have: $\exists m\in Z,n\in Z\wedge n\in [0,b)$ that $a=mb+n$. This implies $\frac{a}{b}=m+\frac{n}{b}\to m=\frac{a}{b}-\frac{n}{b}\le x$. And we have: $m+1=\frac{a}{b}=\frac{b-n}{b}>x$.
- suppose $x<0$: for $x=\frac{a}{b}\to \frac{a}{b}<0$. Because by the definition of rational numbers, the negative signs are homogeneous cases of negative denominator and negative nominator, so we suppose b<0. We have: $\exists (m,n)\in N\times [0,-b)(a=m(-b)+n)\to \frac{a}{-b}=m+\frac{n}{-b}$. We have: $x=-m+\frac{n}{b}<-m$ and $-m-1=-m+\frac{-b}{b}\le x$.
- For unique part: suppose $\exists n_{1},n_{2}\in Z(n_{1,2}\le x<n_{1,2}+1\wedge n_{1}\not=n_{2})$. Then: we have: $[n_{1}b,(n_{1}+1)b)\cap[n_{2}b,(n_{2}+1)b)\not= \phi\to n_{1}+1>n_{2}\wedge n_{2}+1>n_{1}$. Because all of them are integer. we have: $n_{1}\ge n_{2}\wedge n_{2}\ge n_{1}\to n_{1}=n_{2}$. Contradict. Thus the result holds.
Q.E.D
proposition 19 (有理数的有理数散布): $\forall x,y\in Q(x<y\to\exists z\in Q( x<z<y))$.
证: 取对半.
proposition 20: 给定不存在有理数的平方是2, 且对任意正有理数$\epsilon$, 有:$\exists x\in Q(x^{2}<2<(x+\epsilon)^{2})$.
证: suppose there is no such non-negative rational number x satisfying the condition, then: $\forall x\in Q(x^{2}\ge 2\vee (x+\epsilon)^{2}\le 2)$. Thus, once any rational number has $x^{2}<2\to(x+\epsilon)^{2}\le 2$. We have:
- $0^{2}<2\to (0\epsilon)^{2}<2$.
- suppose for some $x=n\epsilon(x^{2}<2)$,
- for $((n+1)\epsilon)^{2}<2$ is derived from the result.
This implies all natural numbers have $(n\epsilon)^{2}<2$. However, using proposition 17, there is a unique integer that $n>\frac{2}{\epsilon}\to n\epsilon >2\to (n\epsilon)^{2}>4>2$, contradict.
Q.E.D
Problem set:
4.4.2: $\{a_{i}\}$被称为是无穷递降的, if $\forall n\in N(a_{n}>a_{n+1})$.
-
求证: (无穷递降原理): 不存在无穷递降的自然数列.
-
证: suppose the series {$n_{i}$} is such series. Then: for each item in the series, they are all natural numbers. Thus: for $\forall k\in N$, suppose n = 0, and we have $a_{0}\ge k$. suppose $a_{n}\ge k$, then$if\ \ a_{n+1}< k\to \forall i\in[a_{i+2,\infty})(a_{i}\not\in \{a_{i}\})$, contradict with the assumption. Thus $\forall i\in N(\forall k\in N(a_{i}>k))$. According to the proposition 17, $\exists o\in N(o\le k)$, contradict!
Q.E.D
-
-
求证: 是否存在无穷递降的整数数列?
- 证: 存在. 用无穷递增的自然数序列取负数就是整数集上的无穷递减数列.
-
求证: 是否存在无穷递减的有理数数列?
- 证: 存在. 取任意$d(x,y)>0$的两有理数, 利用proposition 18, x和y之间永远有中间数, 所以存在无穷递降数列.