|
完全性定理
关于形式推理的定义,请参见本书前面的部分。一个语句A是理论T的逻辑推理的结果,即A是T的一个定理,记为
T│- A 。
定义7.3.1
(语法定义)一个理论T是协调的,如果对任一语句A
,T│-A及T│- A不可能同时成立。
定理7.3.1
(紧致性定理)T是协调的,当且仅当T的任一有穷子集合是协调的。
证明 如果T'
的某一有穷子集合T是不协调的,将有T'│-
A
及T'│- A,A是某一语句。根据形式推理的定义,当然有T
│-A∧T│- A,则T是不协调的。
如果T本身是不协调的,T│-
A∧T│- A
。又根据形式推理的定义,在两个推理中,只用了有穷个T中的语句作为推理前提,记为T'。显然
有T'│-A及T'│- A,因而T'是不协调的。T'是T的一个有穷子集合。
定义7.3.2
(语义定义) 一个理论T是协调的,如果它有一个模型M,M│=T
。
这两个定义是等价的。
定理7.3.2
一阶理论T在语法上是协调的,当且仅当T有一个模型。
引理7.3.1
如果T是协调的,A是任一语句,T∪{A}
或者T∪{ A}
其中至少有一个是协调的。
引理7.3.2
如果T是协调的,T中的任一语句都不含量词符号,则T有一个模型。
引理7.3.3
若T是协调的,则T*也是协调的。
定理7.3.3 Godel 完全性定理
|
|