自然数

内容纲要


感觉自己的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,也是可以用定义等价快速证明的。


  1. 有趣的是,冯诺依曼在这个研究领域做出了相当大的贡献,而它同时是计算机冯诺依曼结构的发明人(虽然对不住图灵但某种意义上也算是吧),同时是量子物理奠基人之一,博弈论奠基人之一。这,或许就是大佬吧。 

  2. 0=\emptyset, 1=\{0\}, n=\{n-1\},1908年Zermelo 

此条目发表在学习分类目录,贴了标签。将固定链接加入收藏夹。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注