完全性

出典: 謎の百科事典もどき『エンペディア(Enpedia)』
ナビゲーションに移動 検索に移動

数理論理学における完全性 (: completeness) とは、理論が持つ性質を表す用語。数理論理学に限っても同じ単語が複数の意味で使われており、紛らわしい。

定義[編集]

意味論的完全性
文φが理論Tの論理的帰結であるならば、φはTから証明可能であるとき、Tは(意味論的に)完全 (: complete) であるという。完全でないことを不完全 (: incomplete) であるという。ゲーデルの完全性定理における「完全」はこの意味である。この逆(Tから証明可能ならばTの論理的帰結である)を健全性という。
構文論的完全性
いかなる文φに対しても、理論Tがφと¬φの少なくとも片方を証明可能であるとき、Tは(構文論的に)完全 (: complete) であるという。完全でないことを不完全 (: incomplete) であるという。ゲーデルの不完全性定理における「完全」はこの意味である。

関連項目[編集]