感觉自己的Ubuntu桌面不够妙,从网上搜索了一波美化教程,然后就这样了,超开心! 然后呢,这个博客主要是为集合论图论做的笔记,下周就要考了,涨涨RP吧。
皮亚诺系统
皮亚诺系统描述了一个“类似于自然数的系统”,怎么个类似法?它给出了五条公理:
- 0是自然数。
- 任何一个自然数的后继是自然数。
- 0不存在后继。
- 如果两个自然数的后继相同,则它们相同。
- 如果有一个包含0的自然数集的子集,这个集合同时也包含在该集合内任意一个自然数的后继,那么这个集合就是自然数集合本身。
理解并不太难,形式化地,对于一个皮亚诺系统(N, e_0, f)
,给出数学描述:
e_0 \in N
x \in N \Rightarrow f(x) \in N
\forall a, b \in N, a^+ = b^+ \Rightarrow a=b
f是单射
e_0 \in E \land E相对F封闭 \Leftrightarrow E = N
其中,N
是一个“类似自然数集”的集合,e_0
是0元,f
是“后继”关系函数,上面的五条文字描述可以一一对应到下面的数学表述内,每一条都不可或缺。 很方便的,我们可以验证我们熟知的自然数集是满足皮亚诺系统五条公理的。同时,一个皮亚诺系统也会具有类似于自然数的一些方便性质,有利于研究。 现在考虑如何使用集合——非常基础的数学元素——来构造一个皮亚诺系统,这让我们得以更好地观察自然数集1。
先给出两个定义:
后继
令A
是一个集合,定义A
的后继A^+=f(A)=A\cup\{A\}
不同于策梅罗定义的自然数2,我们发现这个后继的定义有一些好的性质,比如集合的包含和属于运算在这个后继的定义下,具有传递性。
归纳集
定义0=\emptyset
定义集合A
是归纳集当且仅当0\in A ~ \land ~ \forall x \in A, x^+\in A
。
换个说法,零元属于归纳集,且归纳集对$f$封闭。需要注意的是,按照后文对自然数的定义,自然数集并不包含所有归纳集。
自然数
用自然数的记号表示一些集合,令0=\emptyset, 1=0^+, 2=0^{++}=1+
,以此类推。 将自然数之间进行集合运算可以得到一些有趣的结果,比如min\{a, b\}=a \cup b
。
自然数集
终于可以定义自然数集啦! 那么先直接给出定义:
D=\{v|v是归纳集\} \\
N=\bigcap D
由于任意两个归纳集的交也是归纳集(不证了),所以N
是归纳集,同时易证它是最小的归纳集。 那么问题来了,这样定义的自然数系统
是一个皮亚诺系统吗? 验证公理,第一、二、三条显然满足。对于第五条,易验证一个满足性质的集合是一个归纳集,那么显然有N
包含于任意一个归纳集,同时根据公理,这个归纳集又是$N$的子集,那么必然和N
相等。 接下来验证第四条: n^+ = m^+
\Rightarrow n \in n^+ = m^+ = m\cup \{m\}
\Rightarrow n \in m \lor n=m\Rightarrow n\subseteq m \lor n = m
假设n\ne m
,则同理可以得到m\subseteq n
,则n=m
那么我们就使用集合找到了一个满足皮亚诺公理的自然数集。
其它
上面的集合定义自然数和介绍的一些概念可以得到一些有趣的性质,比如\forall n, m \in N, n^+=m^+ \Leftrightarrow n=m
,数学归纳法也可以使用归纳集的方法进行思考:证明一个命题P
时,证明集合\{n|n\in N \land P(n)\}
是归纳集就可以了。 我们还可以定义皮亚诺体系P_1, P_2
的相似,是存在一个属于集合M_1, M_2
元素间的双射函数,并且这个函数与后继函数f_1, f_2
交换。显然有(不证了)任意皮亚诺体系之间都是相似的。
传递集
传递集是“集合内的元素内的元素是集合内的元素”的集合,给出传递集的定义:A
是传递集当且仅当\forall x \in A, \forall y \in x, y \in A
。
关于传递集有一些简单可证明的等价描述:A是传递集\Leftrightarrow \bigcap A \subseteq A \Leftrightarrow x \in A \rightarrow x \subseteq A \Leftrightarrow A \subseteq P(A)
,这些等价描述是可以循环互证的。 有了这些基础结论,可以快速优雅地推导一些进阶结论,比如A为传递集\Leftrightarrow P(A)为传递集
,证明只有两行不放了。 还有一些简单的结论比若\bigcup A^+ = A
,也是可以用定义等价快速证明的。