作者cmlrdg (心之语)
看板logic
标题Re: [请益] 一阶逻辑的不可判定
时间Mon Dec 8 15:33:07 2008
※ 引述《MathTurtle (恩典)》之铭言：
: ※ 引述《cmlrdg (心之语)》之铭言：
: : ( 其中N为自然数系的model;
: : NT为自然数系的公理集合;
: : 1. "UNSATISFIABLE SENTENCES" 和 "NT |﹣φ"
: : 这两个languages是recursively inseparable.
: : (意思就是不存在一个recursive language可将两者分开;
: : 如果存在如此language, 则halting problem将为decidable) ▓
: : 2. 由1.我们也因此而得知下述结果:
: : 给定一个first order的sentence, φ
: : 以下三个problems皆为undecidable:
: : a) "VALIDITY," 也就是, "φ是否为valid?";
: : b) "N |﹦φ?";
: : c) "{NT} |﹣φ?".▓
: 这里我不是很懂, 原po问的应该是first order logic的undecidability,
: 这里给的似乎是要比自然数系(Peano Arithmetics)强的系统,
: 所以应该是无法用来证明一阶逻辑的不可判定性。
给定一个(consistent)公理集合Δ,
所有可从Δ导出的定理(Δ first-order theorem)φ所形成的language
称为 THEOREMHOOD
由 Godel's Completeness Theorem 知
THEOREMHOOD = VALIDITY
因此可得知 THEOREMHOOD 也是 undecidable
(既然由2.a)知道 VALIDITY 是 undecidable)
也就是 first order logic 的 undecidability
简单来说
"不存在一个程式可判定φ是否为Δ的定理"
有错请指正^^"
: : 原po所问的, 应该就是上面的a)这个问题了.
: : 详情可参阅
: : Computational Complexity, by Christos H. Papadimitriou
: : 的6.3节, 上述之定理取自其 Theorem 6.3 和 Corollary 1,
: : 这本书里皆有详细的说明和证明!
: : P.S. 他下一页的 Corollary 2
: : 即为赫赫有名的Godel's Incompleteness Theorem... XD
--
我是新手@@, 感谢各位的指教 <(_ _)>
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.5.39