実現可能性 (論理学)
クリーネによるオリジナル版の実現可能性の定義は、ハイティング算術(英語版)の論理式の実現子として自然数を用いる。自然数 n と式 A の間の関係「n が A を実現する」を、ハイティング算術の言語で定義する。 ただし以下において、順序対 (n, m) はある固定された有効な対関数を使うことで単一の数値として扱う。また、各自然数 n に対して φn はインデックス n の計算可能関数(すなわち、何らかの方法で列挙された計算可能関数の列 { φ n } n ∈ N {\displaystyle \{\varphi _{n}\}_{n\in \mathbb {N} }} における n 番目の関数)である。
自然数 n が原子論理式 s = t を実現するとは、 s = t が真であることと同値。 従って、任意の自然数は恒真な等式を実現し、また矛盾した等式を実現する自然数はない。
順序対 (n, m) が論理式 A ∧ B {\displaystyle A\land B} を実現するとは、n が A を実現して、かつ m が B を実現することと同値。つまり、連言の実現子とはそれを構成する各式の実現子の対である。