为什么在自然数的递归定义中需要一个最小的集合



来自维基百科关于递归定义的条目:

集合的归纳定义用集合中的其他元素来描述集合中的元素。例如,自然数集合N的一个定义是:

  1. 1在N中
  2. 如果元素n在n中,则n+1在n中
  3. N是满足(1)和(2)的最小集合

有许多集合满足(1)和(2)-例如,集合{1,1.649,2,2.649,3,3.649,…}满足定义。

我不明白为什么需要(3)。在给出的例子中,它指出1.649是这个集合的一个成员,但1.649不满足(1)或(2)。

为什么需要(3),1.649是如何在集合中的?

列表中的规则2是"if",而不是"if and only if"。它们不是生成集合的规则,而是决定是否允许集合的规则。集合{1,1.649,2,2.649,3,3.649,…}满足规则1,因为1在集合中。它满足规则2,因为对于集合中的每个元素,该元素加1也在集合中。事实上,即使是实数集也满足前两条规则,并且它有无数个你不需要的"额外"元素。

只有第3条规则可以阻止您向集合中添加任意的额外元素,即集合必须是尽可能小的一个。

前两个需求并不能确定某些元素不在集合中。虽然我们保证有1,但没有理由不包含1.649。

很明显,我们希望自然数集是唯一的,并且只有{0,1,…},因为我们需要能够对所有自然数做出断言。

举个例子,我们希望能够做出的一个基本陈述是,任何自然数要么是自然数的后继,要么是1。从集合中的另一个数字开始有一个等价的链是没有帮助的。

(1) 1 is a natural number`
(2) If N is a natural number, than N+1 is a natural number as well

这是含义,而不是等价。这说明,如果对于任何一个数,这些条件成立,它就是一个自然数。它没有说明是否存在其他自然数。

(3) N is the smallest set satisfying (1) and (2)

这恰恰说明前两种情况令人精疲力竭。不仅每个满足它们的数都是自然的,而且——任何不满足的数都不是自然的。

条件(3)也可以重新表述为

Every natural number can be obtained by a finite number of applications of (2) on (1)

或简称

Nothing else is a natural number

最新更新