归纳定义导论

引论

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

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

第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$ 中的前提 $θ$ , 推出结论 $ψ$ .

在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 (Φ)

是最小的

Φ

封闭集合.

回到我们之前的例子上来, 我们看到 $Th (H) = I (Φ_{H})$ . 类似地,

例子1.1.2.

定义1.1.3.

命题1.1.4.

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

命题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节一般框架