完全性

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

定義[編集]

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