(底层)前置知识:(高中程度的基本逻辑符号/充分必要条件/高中程度的集合基础/”$\To$\mid”蕴含关系/最大公因|约数(gcd)的定义)
额外简化符号. $\exists!$表存在唯一, $X\dot\subset Y$表$X\ne\emptyset\wedge X\subset Y$, $:=$表右侧式定义左侧式,$=:$同理;
考虑一下集合的概念. 一个很自然的想法是”具有一定相同性质的对象的总称”, 也是朴素集合论的观点. 然而考虑集合$M=\{x\mid x\not\in x\}$, 其存在性直接造成了集合概念本身的矛盾. 因此, 我们不得不寻求一个比集合更广泛的存在. 此外, 我们可以定义集合之间的关系, 注意这里的关系不仅仅局限在包含等基础的集合关系.
1. $\varphi(x,p)$为命题, $p$为参数, 称${ x \mid \varphi(x,p)}$为一个类, 不是集合的类称为真类(如上面的$M=\{x\mid x\not\in x\}$), 并且与集合上类似地定义类的包含和交并差.
2. 若$R={(x,y)\mid \varphi(x,y)}$, 则称$R$为一个二元关系, 且其定义域为$\dom R:={x\mid\exists y:(x,y)\in R}$, 值域$\ran R:={\exists x:(x,y)\in R}$.
3. 若二元关系$f$满足$(x,y),(x,z)\in F\Rightarrow y=z$, 则称$f$为一个映射；且若$(x,y)\in f$, 则记$y=f(x)$.
4. 若映射$f$满足$f(x)=f(y)\Rightarrow x=y$, 则称f为单射；若$f$满足$\ran f=Y$, 则称$f$为满射. 若$f$为单射和满射, 则称$f$为双射或一一映射. 如果$X,Y$都是数集, 那我们称映射$f$为一个函数.
5. 若$\exists f:X\to Y, g: Y\to Z, \dom g\subset\ran f$, 则定义$f$与$g$的复合$(g\circ f )(x):= g(f(x))$; 定义$f^{-1}: \dom X\to X$, 称为$f$的逆映射.
6. 若$\forall x,y,z\in X$, $\sim$为$X$上一个二元关系, 则若$x\sim x$, $x\sim y\Rightarrow y\sim x$, $x\sim y\wedge y\sim z\Rightarrow x\sim z$, 则称$\sim$为$X$上一个等价关系.
Ex. 有一个映射的等价定义：若$\forall x\in X,\exists ! y\in Y$按对应规则$f$与之对应, 则称定义了映射$f: X\to Y, x\mapsto y$.
注. 很明显的一个事实是对于$f: X\to Y, \ran X\subset Y$; 另外映射的复合满足结合律. 另外, 我们有一个引理:
1. $gf=e\To g$满$\wedge f$单;
2. $f:X\to Y, g:Y\to X$为互逆双射$\iff gf=e_X\wedge fg=e_Y.$ 这里$e_X$表示$X$中的单位元.
现在我们给出ZFC公理体系:
这里的八条都是公理, 用定理模板是因为懒.
1. (外延)$\forall x(x\in X\iff \in Y)\iff X=Y$.
2. (配对)$\forall a,b,\exists X\forall x(x\in X\iff x=a\vee x=b)$.
3. (分离)$\forall X\forall p\exists Y\forall x(x\in Y\iff x\in X\wedge \varphi(x,p))$.
4. (并集)$\forall X\exists Y\forall x(x\in Y\iff \exists u(u\in X\wedge x\in u))$.
5. (幂集)$\forall X\exists Y\forall x(x\in Y\iff x\subset X)$.
6. (无穷)$\exists S$为归纳集, i.e. $\emptyset\in S\wedge(\forall x\in S)x\cup{x}\in S$
7. (替换)$\forall X\forall f:f(X)$为集合.
8. (正则)$\forall X(X\ne\emptyset\Rightarrow\exists x(x\in X\wedge X\cap x\emptyset))$
9. (选择)$\forall S\supset\emptyset, \exists f:f(X)\in X,\forall X\in S$.
配对公理和并集公理共用可构造$n$元集：$(a,b):=\{\{a\},\{a,b\}\}$, 归纳地(利用ZF公理已经可以构造自然数, 进而我们有有限数学归纳法)可定义有序$n$元组$((a_1,\cdots a_{n-1},a_n)$.
分离公理提供了从原集合分离出新集合的方式, 正则公理的引入目的为避免罗素悖论的发生. 如果至少存在一个集合, 则$\emptyset$为集合, 无需正则公理和选择公理的条件；而无穷公理也保证了至少存在一个集合.
选择公理中的$f$为一个集合, 其没有具体构造$f$, 而是直接声明其存在, 这时其与其余ZF公理的不同.
集合的直积$X\times Y:=\{(x,y):x\in X\wedge y\in Y$为集合($X\times Y\subset P(P(X\cup Y))$.
若替换公理成立且空类为集合, 则分离公理成立. (空集公理可以代替分离公理)
自然数上成立序关系, 所以为了构造自然数集, 我们需要先引入序关系.
1. 若集合$P$上一个二元关系$<$满足$x\not<x$, $x<y\wedge y<z\Rightarrow x<z$, 则称$<$为$P$上一个偏序关系. 若还有$\forall x,y(x<y\vee x=y\vee x>y)$, 则称$<$为$P$上一个全序关系. 该定义可直接推广到类上.
2. 设偏序集$(P,<)$, $X\dot\subset P$. 若$x\in X$, 且$\forall y\in X: y\not< x$, 则称$x$为$X$的极小元；若$x\in X$, 且$\forall y\in X: y\geq x$, 则称$x$为$X$的最小元. 类似有极大元和最大元的定义.
3. 设偏序集$(P,<)$, $X\dot\subset P$. 若$\forall x \in P,\forall y\in X, y<x$, 则称$x$为$X$一个上界；若$x$为最小上界, 则称$x$为$X$的上确界. 类似有下界和下确界的定义.
4. 若全序集$P$的每个子集有最小元, 则称$P$为良序集.
5. 设$P,Q$为偏序集, 若$f:P\to Q$满足$x<y\Rightarrow f(x)<f(y)$, 则称$f$为保序的.
6. 若$f,f^{-1}$为保序双射, 则称$f:P\to Q$为同构. 称$f:P\to P$为$P$上的自同构.
7. 设$W$为良序集, 称$W(u):=\{x\in W\mid x<u\}$为$W$由$u$给出的前段.
8. 集合$T$称为传递集 if $x\in T\Rightarrow x\subset T$.
全序集的极小元和最小元没有区别(根据定义), 但在偏序集里, $y\not<x\not\Rightarrow y\geq x$.
上下界不一定是唯一的, 但确界是唯一的.
设$W$为良序集, 若$f:W\to W$保序, 则$\forall x\in W:f(x)\geq x.$
反设$X:=\{x\in W\mid f(x)<x\}\ne\emptyset$, 取$z=\min X,w=f(z)$. 则$w=f(z)<z\wedge z=\min X\Rightarrow w\not\in X$；而$f$保序$\wedge w<z\Rightarrow f(w)<f(z)=w\Rightarrow w\in X$. 矛盾.
1. 良序集的自同构只有恒等映射.(i.e. $f(x)=x$)
2. 两个良序集间的同构唯一.
3. 良序集不能同构于自身前段.
(1) 对自同构$f$, $f(x)\geq x$；$f^{-1}$也为自同构, 则$f^{-1}(x)\geq x\Rightarrow x\geq f(x)$. 综上有f(x)=x.
(2)考虑P的最小元, 其只能映射到Q的最小元. 同理第二小的元素也映射到第二小的元素, 依此类推.
(3)反设$\exists f:W\to W(u)$为同构, 则$f(u)\in W(u)\Rightarrow f(u)<u$, 矛盾.
设$V, W$为良序集, 则如下情况有且仅有一种成立:$V$与$W$同构;$V$与$W$一个前段同构;$W$与$V$一个前段同构.
设二元关系$f=\{(x,y)\in V\times W\mid V(x)$与$W(y)$同构$\}$.
则$f$为单射. 若$g$为$V(x)$和$W(y)$一个同构, $x'<x$, 则$V(x’)$同构于$W(g(x’))$, 故$f$保序.
且$y_1<y_2\wedge y_2\in\ran f\Rightarrow y_1\in \ran f.$
若$\dom f=V\wedge\ran f=W$, 则情形一成立；
若$\ran f\ne W$, 设$y_0:=\min{W-\ran f}\Rightarrow\ran f=W(y_0)$, 则$\dom f=V$.(否则$\exists x_0=\min{V-\dom f}\Rightarrow f:V(x_0)\to W(y_0)$为同构$\Rightarrow (x_0,y_0)\in f$, 即情形二成立；
情形三同理, 且三种情况只能成立其一.
注：类似这样的命题陈述被称为三分律/三歧性.
我们现在给出Peano公理体系, 用以对照自然数的构造过程.
- $0\in\N$.
- $”=”$为一个等价关系.
- $\N$封闭, i.e. $\forall a,b\wedge b\in\N \wedge a=b\Rightarrow a\in N$.
- $\forall n\in N,S(n)\in N$, 且$S$为单射, 且$S(n)\ne 0,\forall n\in \N$.
- $(0\in S\wedge(n\in \N\cap K \Rightarrow S(n)\in K))\Rightarrow K=\N$.
这里$S(n)$称为$n$的后继数；第五条也被称为归纳原理(因为保证了数学归纳法的正确性)
- $a+0=a$；$a+S(b)=S(a+b)$.
- $a0=0$；$aS(b)=a+(ab)$.
- $\forall a,b\in N, a\leq b\iff \exists c\in N:a+c=b$.
- $\forall a,b,c\in N\wedge a\leq b, a+c\leq b+c\wedge ac\leq bc$.
1. $\N=\bigcap_{X归纳}X$是最小的归纳集，称为自然数集.
2. $0:=\emptyset. $若$n\in N, n^* := n\cup\{n\}.$若$m,n\in N, (m<n):=(m\in n)$.
我们归纳地定义了自然数和其上的序关系.
1. $T:=\{x\in X\mid x\subset X\}$为归纳集.
2. $T:=\{x\in X\mid x$为传递集$\}$为归纳集.
3. $T:=\{x\in X\mid x$为传递集$\wedge x\not\in X\}$为归纳集.
4. $T:=\{x\in X\mid x$为传递集$\wedge \forall y\dot\subset x:y$有$\in$-极小元$\}$为归纳集.
5. $T:=\{x\in X\mid x=\emptyset\vee \exists y(x=y\cup\{y\})\}$为归纳集.
6. $\forall X\dot\subset\N, X$有$\in$-极小元.
7. (归纳)$0\in X\subset N\wedge (n\in X\To S(n)\in X)\To X=\N$.
(1) Trivially $\emptyset\in X\wedge\emptyset\subset X\Rightarrow \emptyset\in T; x\in X\wedge x\subset X \Rightarrow x\cup\{x\}\in X,\forall x\in X.$ 则$T$为归纳集.
(2) 根据(1), $\emptyset\in T$.
$\forall x\in T, x$为传递集. 现在要证$x\cup\{x\}$为传递集. 设 $y\in x\cup\{x\}$, 则 $y=x\vee y\in x$. 无论哪种情况都有$y\subset x\cup\{x\}$,
故$ x\cup\{x\} $为传递集，从而 $T$为归纳集.
(3) Trivially $\emptyset\in T$; 反设$x\cup{x} \space \in \space x\cup{x}$, 则有$\Rightarrow x\cup{x}=x\vee x\cup{x}\in x$, 这说明$x\in x$,与构造矛盾. 故$x\cup\{x\}\in T$, 命题成立.
(4) Trivially $\emptyset\in T$; $\forall y\in x, y\subset x\wedge y$有$\in$-极小元. 只要证$\forall y\in x\cup\{x\}: y\subset x\cup\{x\}\wedge y$在$x\cup\{x\}$中有$\in$-极小元. 只要分$y=x\vee y\in x$即可.
(5) Trivially $\emptyset\in T$;
(6) 取$n\in X$, $X\cap n=n$为有限集. 故再取$n_1\in n,\cdots$进行下去有限步内总会结束.
(7) 考虑到$X$为归纳集,且$\N=\bigcap_{N为归纳集}N$, 则$\N\subset X$;又由$X\subset \N$有$X=\N$.
根据我们的构造, $\forall n=\{m\in N\mid m<n\}\in N$和$\N$本身为传递集,且$n\not\in n\wedge n\ne S(n)$. 并且一个自然数要么是 0, 要么是某个自然数的后继.
于是$N$满足Peano公理的集合定义.
我们的(当前)最终目的是实数, 先要解决有理数的问题. 从这里开始, 自然数将不会再被作为集合这一概念来看待. 我们这里直接引入代数结构的观点, 这样一些描述将会变得很容易. 注意这里的叙述可能会更贴近英文的风格, 可它实在是太好用了(x):
1. 非空集合$G$上一个二元运算是一个映射$\cdot: G\times G\to G: (x,y)\mapsto x\cdot y, 且$\cdot$封闭(即进行多少次映射, 结果都仍会落在集合内)
2. 非空集合$G$被称为一个半群, 若$G$上有一个二元运算 $\cdot$ 满足结合律$a(bc)=(ab)c,\forall a,b,c\in G$.
3. 若还$\exists e\in G:ae=ea=a,\forall a\in G$则称半群$G$为一个幺半群,$e$ 称为其中的单位元.
4. 若再 $\forall a\in G,\exists a^{-1}\in G:a^{-1}a=aa^{-1}=e, $则称幺半群 $G$ 为一个群(group), $a^{-1}$ 称为 $a$ 的逆元.
5. 若半群$G$上的二元运算$\cdot$满足交换律 $ab=ba,\forall a,b\in G $，则称$G$ 是交换半群.
逆元存在则唯一. 这个证明很简单, 会在下一节开头给出.
我们也可以按照加法的风格来写定义. 考虑$\N$, 其中的加法满足结合律(由Peano公理保证),且有单位元$0$, 使得$(\N,+)$成为一个幺半群. 我们只需要再构造逆元: $\forall n\in\N,$我们定义$-n$ s.t. $n+(-n)=0$, 实际上这就是负整数的定义. 此时我们得到了整数集$\Z$(实际上,$(\Z,+)$为一个群, 从定义立即得出).
考虑我们有理数的定义$\Q:=\{ p\cdot q^{-1}\mid p,q\in\Z\wedge q>0 \wedge \gcd(p,q)=1 \}$, 这里面出现了乘法. 我们发现$\Z$对乘法满足结合律,也有单位元$1$, 故$(\Z,\cdot)$为一个幺半群. 同样地, 接下来构造逆元: $\forall n\in \Z,\exists n^{-1}\in \Z:nn^{-1}=1$, 我们立刻发现$0\in\Z$不可逆. 于是我们直接扔掉$0$, 剩下的$\Z^*:=\Z-\{0\}$对乘法就是一个群.
显然对于有理数, 交换性/结合性和分配律仍然成立. 我们对有理数要加上$q>0,\gcd(p,q)=1$的原因是一次性保证每个有理数直接有唯一的表达方式. 显然我们并不需要这两条, 只要证明对同一有理数的不同表达相等即可, 这一点是并不困难的. 于是, 我们构造出了有理数集. 显然$(\Q^*,\cdot)$为群.
1. 有$+,\cdot$两种运算的集合$R$称为一个环, 若$(R,+)$为交换群, $(R,\cdot)$为半群, 且$\cdot$对$+$左右都有分配律, i.e. $x(y+z)=xy+xz,(x+y)z=xz+yz$, 注意这里简记$x\cdot y$为$xy$.
2. 环$R$称为幺环, 若$(R,\cdot)$构成幺半群.
3. 环$R$称为交换环,若$(R,\cdot)$构成交换半群.
4. 幺环$R$称为除环, 若$(R^*,\cdot)$为群.
5. 除环$R$称为域, 若$R$可交换.
Ex. 定义了$+,\cdot$两种二元运算的集合$R$称为一个域, 若加法和乘法有交换律, 且任何元素存在加法逆元, 任何非零元素存在乘法逆元, 并且乘法对加法有分配律. 这是域的另一个定义,显然两个定义等价.
所以, $(\Q,+,\cdot)$为一个(数)域.
在$\Q$内, 成立Archimedes原理:$\forall x\in\Q_{>0},\forall y\in Q,\exists n\in\N:nx\geq y$. 这是从正整数集上的Archimedes原理推来的.
此外, 现在我们可以定义有理数域上的$nx$,$x^n$, 也是从正整数集上推广而来.
有一个关于绝对值的很重要的不等式:$|\sum x_i|\leq \sum |x_i|$, 证明考虑绝对值的定义和归纳法即可.
总结一下, 我们可以得到$\Q$内的三大公理体系(从正整数推广而来):
1. 域公理
$x + (y + z) = (x + y) + z, x + y = y + x$.
$\exists0\in\Q,\forall x\in\Q,0 + x = x$.
$\forall x\in\Q,\exists -x \in \Q:x + (-x) = 0$。
$x \cdot (y \cdot z) = (x \cdot y) \cdot z,x \cdot y = y \cdot x$.
$\exists 1\in \R:1 \neq 0\wedge\forall x \in \R:1 \cdot x = x$.
$\forall x\in \R^*,\exists x^{-1} \in \R:x \cdot x^{-1} = 1$.
$x \cdot (y + z) = x \cdot y + x\cdot z$.
2. 序公理
$x\leq y\wedge y\leq z\To x\leq z$.
$x\leq y\wedge y\leq x\To x=y$.
$\forall x,y\in \Q: x\leq y\vee y\leq x$.
3. Archimedes公理
$\forall x\in\Q_{>0},\forall y\in Q,\exists n\in\N:nx\geq y$.
我们下一节的目标是构造实数和描述实数的连续性, 以及数列极限.