归纳定义导论

引论

对于集合的归纳定义经常被非形式化地呈现为给出生成这个集合的元素的规则, 然后添加一个对象在这个集合之中仅当其由规则生成的陈述. 等价的描述是刻画这个集合为在规则之下封闭的最小集合.

当然了, 归纳定义的基本例子是生成自然数的例子. 但是, 长久以来其被证明是呈现形式语言的句法的有用设备.

第1章什么是归纳定义?

第1.1节作为广义形式系统的归纳定义

当逻辑学家描述语言的句法时, 归纳定义总是被不断地使用. 例如, 一阶语言的项被定义为包含变量和常量, 并且在项的构造规则:

如果 $t_{1}, \dots, t_{n}$ 是项而 $f$ 是语言的 $n$ 元函数符号, 那么表达式 $f (t_{1}, \dots, t_{n})$ 也是一个项.

之下封闭的最小的表达式的集合.

类似地, 一阶语言的公式被定义为包含原子公式的在逻辑符号 $\neg, \lor, \land, \to, \exists x, \forall x$ 的诸构成规则下封闭的最小表达式集合.

对于我们的目的而言, 要考虑的最有用的例子是对于形式系统的定理的类的定义. 考虑一阶逻辑的Hilbert风格系统 $H$ , $H$ 的定理集 $Th (H)$ 因而是基于 $H$ 的证明概念定义的. 但是, $Th (H)$ 也可以被刻画为包含公理且在推理规则之下封闭的最小公式集合. 每个推理规则的实例都具有以下形式:

根据 $X$ 中的前提 $θ$ , 推出结论 $ψ$ . {译注: 这种说法可能引起误解, 它实际上指的是根据 $X$ 中所有的元素.}

在modus ponens的情况下,

X

由两个前提构成, 即

φ

和

(φ \to ψ)

. 泛化规则的实例只有一个前提. 将公理模式 (axiom scheme) 当作推理规则的特殊形式是方便的, 其中每个实例的前提集都是空集. 使用这个约定, 形式系统

H

确定了一个序对

(X, ψ)

的集合

Φ_{H}

, 其中每个元素都是

H

的推理规则的实例. {译注: 也就是说,

X

是前提集,

ψ

是结论.} 然后,

Th (H)

不过就是在

(X, ψ) \in Φ_{H}

下封闭的最小集合.

推广之后我们得到了以下定义.

定义1.1.1.

一个规则(rule)是一个序对 $(X, x)$ , 其中 $X$ 是一个集合, 其被称为前提集, 而 $x$ 是结论. 通常我们将规则记为 $X \to x$ .
如果 $Φ$ 是一个规则的集合 (以下也称为规则集(rule set)), 那么一个集合是 $Φ$ 封闭的, 如果对于每个 $Φ$ 中的规则, 若其前提在 $A$ 之中, 那么结论也在 $A$ 之中. 我们记 $Φ : X \to x$ 来表示规则 $X \to x$ 在 $Φ$ 之中. 于是, $A$ 是 $Φ$ 封闭的, 如果 $Φ : X \to x & X \subseteq A$ 可以推出 $x \in A$ .
如果 $Φ$ 是一个规则集, 那么 $I (Φ)$ , 即由 $Φ$ 归纳定义的集合, 其定义为 $I (Φ) = ⋂ {A | A 是 Φ 封闭的}$ .

注意.

Φ

封闭集合的确存在, 只需要取

Φ

中的每个规则的结论构成的集合即可. 另外, 由

Φ

封闭集合构成的任意族的交也是

Φ

封闭的. 特别地,

I (Φ)

是

Φ

封闭的, 因而

I (Φ)

是最小的

Φ

封闭集合. {译注: 这里存在一点基础问题, 但是或许很容易解决, 因为我们总是会假设存在一个全集 (universe), 它囊括了所有

A

可能拥有的元素.}

回到我们之前的例子上来, 我们看到 $Th (H) = I (Φ_{H})$ . 类似地, 用于归纳定义某个一阶语言的项和公式的集合的规则集也是很容易找到的.

注意. 通常被称为一个推理规则或者形成规则的东西对应于我们所说的一个规则集. 而推理规则或形成规则的实例对应于我们所说的规则. {译注: 实际上是这样的, 推理规则是一个模式, 里面可以有元变量, 具体化之后就得到了这里文章所说的规则, 而推理规则本身应该视为其所有可能的实例化/具体化的结果所构成的集合.}

或许数学中最为人熟知的归纳定义的例子是我们将自然数的集合 $ω = {0, 1, 2, \dots}$ 刻画为包含 $0$ 且在后继函数下封闭的最小集合, 即 $ω = I (Φ_{ω})$ , 其中 $Φ_{ω}$ 由规则 $\emptyset \to 0$ 和规则 ${n} \to n + 1$ 构成. 这种刻画澄清了数学归纳法: 如果 $P$ 是一个性质, 对于 $0$ 成立且每当对于 $n$ 成立则对于 $n + 1$ 成立, 那么 $P$ 对于所有的自然数成立, 即 ${n \in ω | P (n)}$ 是 $Φ_{ω}$ 封闭的可以推出 $ω \subseteq {n \in ω | P (n)}$ .

对于数学归纳法进行推广, 我们发现对于每个规则集 $Φ$ 而言存在所谓的 $Φ$ 归纳法: 如果 $P$ 是一个性质, 满足每当 $Φ : X \to x$ 和 $\forall y \in X P (y)$ 就有 $P (x)$ , 那么 $P (a)$ 对于每个 $a \in I (Φ)$ 成立.

上述原理是证明 $I (Φ)$ 的性质的自然工具.

译者注记. 考虑

I (Φ)

的一个子集

B = {b \in I (Φ) | P (b)} .

对于(任意的)一条规则

Φ : X \to x

, 如果

X \subseteq B

, 那么

X \subseteq I (Φ)

而

x \in I (Φ)

. 鉴于对于每个

b \in B

都有

P (b)

成立, 那么对于每个

b \in X

也有

P (b)

成立. 因此根据性质

P

的条件,

P (x)

成立. 换言之, 即

x \in B

. 也就是说, 鉴于

Φ : X \to x

是任意的,

B

是一个

Φ

封闭集合. 然而,

I (Φ)

是最小的

Φ

封闭集合, 所以有

B = I (Φ)

. 这就澄清了

Φ

归纳法.

例子1.1.2. 为了表明

H

的每个定理在每个结构中都是

定义1.1.3.

命题1.1.4.

第1.2节一个关系的良基部分

令 $≺$ 是一个集合 $A$ 上的一个二元关系. $≺$ 的良基部分是 $A$ 的一个子集 $W (≺)$ , 其满足不存在无穷递降序列 $a ≻ a_{0} ≻ a_{1} ≻ \dots$ . 关系 $≺$ 是一个良基关系, 如果 $A = W (≺)$ . $W (≺)$ 可以按照如下方式归纳定义.

命题1.2.1.

归纳定义导论

引论

第1章什么是归纳定义?

第1.1节作为广义形式系统的归纳定义

第1.2节一个关系的良基部分

第1.3节作为算子的归纳定义

第1.4节单调归纳的证明的概念

第1.5节内核——归纳定义的对偶

第1.6节经典数学中的一些归纳的例子

第2章递归论中的归纳

第2.1节递归可枚举关系

第2.2节 $Π_{1}^{1}$ 关系

第2.3节可表示性

第3章归纳定义的类

第3.1节一般框架

归纳定义导论

引论

第1章 什么是归纳定义?

第1.1节 作为广义形式系统的归纳定义

第1.2节 一个关系的良基部分

第1.3节 作为算子的归纳定义

第1.4节 单调归纳的证明的概念

第1.5节 内核——归纳定义的对偶

第1.6节 经典数学中的一些归纳的例子

第2章 递归论中的归纳

第2.1节 递归可枚举关系

第2.2节 Π11关系

第2.3节 可表示性

第3章 归纳定义的类

第3.1节 一般框架

第1章什么是归纳定义?

第1.1节作为广义形式系统的归纳定义

第1.2节一个关系的良基部分

第1.3节作为算子的归纳定义

第1.4节单调归纳的证明的概念

第1.5节内核——归纳定义的对偶

第1.6节经典数学中的一些归纳的例子

第2章递归论中的归纳

第2.1节递归可枚举关系

第2.2节 $Π_{1}^{1}$ 关系

第2.3节可表示性

第3章归纳定义的类

第3.1节一般框架