エルブランの定理
{\displaystyle a_{1},a_{2},...,a_{n},...} は変数の集まりを表す。以下の3つの特性について考える。
F {\displaystyle F} は無矛盾(consistent)、つまり F {\displaystyle F} を仮定した場合に矛盾( F ∧ ¬ F {\displaystyle F\land \lnot F} )を導きだせないこと。これは ¬ F {\displaystyle \lnot F} が自然演繹のような述語論理の演繹システムで導きだせないことで、次のように表記する: ⊬ ¬ F {\displaystyle \not \vdash \lnot F} .
F {\displaystyle F} は充足可能(satisfiable)、つまり F {\displaystyle F} が真となるようなモデルが存在すること。これは次のように表記できる: ⊭ ¬ F {\displaystyle \not \vDash \lnot F} .
全ての n {\displaystyle n} に対し、以下 Q ( a 1 , . . . , a n ) {\displaystyle Q(a_{1},...,a_{n})} と表現する以下の論理式を真にするようなモデルが存在すること。これは次のように表記できる:全ての n {\displaystyle n} に対して ⊭ ¬ Q ( a 1 , . . . , a n ) {\displaystyle \not \vDash \lnot Q(a_{1},...,a_{n})}
P ( a 1 , a 1 ) ∧ P ( a 1 , a 2 ) ∧ P ( a 2 , a 1 ) ∧ P ( a 2 , a 2 ) ∧ ⋯ ∧ P ( a 1 , a n ) ∧ ⋯ ∧ P ( a n − 1 , a n ) ∧ P ( a n , a 1 ) ∧ ⋯ ∧ P ( a n , a n ) {\displaystyle P(a_{1},a_{1})\land P(a_{1},a_{2})\land P(a_{2},a_{1})\land P(a_{2},a_{2})\land \cdots \land P(a_{1},a_{n})\land \cdots \land P(a_{n-1},a_{n})\land P(a_{n},a_{1})\land \cdots \land P(a_{n},a_{n})}
ゲーデルの完全性定理は上の(1)と(2)が同値であると主張している。さらに(2)は(3)を含み、(3)で真となるモデルは(2)のモデルとなる。エルブランの定理は逆に、エルブラン領域という特定の領域で(3)が(2)を含んでいるということを主張する。つまり、エルブラン領域という特定の領域で考えると、上の(2)と(3)はエルブランの定理の別の表現であり、(1)、(2)、(3)は同値である。なお、エルブラン領域では変数が無くなるため(3)での全称記号が消え、解くべき論理式は命題論理の命題として扱うことができる。