作者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