Heyting算術(Heyting arithmetic)とは、Peano算術と同じ公理を直観主義論理の上に置いた算術の理論である。Gödel–Gentzen の二重否定翻訳により Peano算術の定理は Heyting算術の定理に翻訳され、両者の無矛盾性は同値である。Friedman の翻訳により $\forall x\exists y$ の形で本体に量化記号を含まない文の証明可能性は両者で一致する。一方 Heyting算術は、閉じた選言の一方と閉じた存在文の証拠の数項を証明できるという、Peano算術にはない性質をもつ。
Heyting 算術(Heyting arithmetic)$\mathsf{HA}$ は、Peano算術 $\mathsf{PA}$ と同じ公理を 直観主義論理 の上に置いた理論である。排中律を使わないので、$\mathsf{HA}$ で閉じた文 $B\lor C$ が証明できるときは $B$ か $C$ のどちらかが実際に証明でき、閉じた文 $\exists xB(x)$ が証明できるときは証拠の数項が取り出せる。
それでも $\mathsf{HA}$ は $\mathsf{PA}$ に比べて極端に弱いわけではない。Gödel–Gentzen の二重否定翻訳により、$\mathsf{PA}$ の文は $\mathsf{HA}$ の文に翻訳され、両者の無矛盾性は同値である。さらに Friedman の翻訳により、計算の停止を述べる $\forall x\exists y$ の形の文については、$\mathsf{PA}$ で証明できることと $\mathsf{HA}$ で証明できることは同じになる。この記事では、この $2$ つの結果と、選言性・存在性を証明する。
公理を書き下した形は Peano算術 と同じである。加法と乗法の結合則・交換則・分配則の証明は等式の帰納法だけで書けるので、$\mathsf{HA}$ の中でも成り立つ。$\underline n$ は数 $n$ の数項($0$ に $S$ を $n$ 回施した項)を表す。
$\mathsf{HA}$ は次を証明する。
1 は $y$ の帰納法である。$y=0$ なら左の選言肢、$y=Sw$ の形の段階では $z:=w$ である。
2 は $\forall y$ をつけた形を $x$ の帰納法で示す。$x=0$ のとき、1 により $y=0$ か $y=Sz$ である。後者なら公理 $2$($\lnot0=Sz$)により $\lnot0=y$ である。$Sx$ の段階では、$y=0$ なら公理 $2$ で $\lnot Sx=y$ である。$y=Sz$ なら帰納法の仮定により $x=z$ か $\lnot x=z$ であり、前者なら $Sx=y$、後者なら公理 $1$ により $\lnot Sx=y$ である。
3 の準備をする。$Sz+x=0$ は不可能である。実際 1 により $x=0$ か $x=Sw$ で、$Sz+0=Sz$、$Sz+Sw=S(Sz+w)$ はどちらも $0$ でない。よって公理 $8$ から $\lnot x<0$ である。次に
$$
x< Sy\leftrightarrow(x< y\lor x=y)
$$
を示す。$Sz+x=Sy$ とする。$z=0$ なら $S0+x=Sx$ より $x=y$ である。$z=Sw$ なら $SSw+x=S(Sw+x)$ より $Sw+x=y$、すなわち $x< y$ である。逆は同じ等式を逆にたどればよい。この $2$ つから、3 は $y$ の帰納法と 2 で得られる。
4 は $P$ の構成の帰納法で示す。原子論理式は 2、3 に項を代入したものである。$\bot$ と $\land,\lor,\to,\lnot$ は決定可能性を保つ。$P\lor\lnot P$ から $\lnot\lnot P\to P$ が出る。$\square$
$L_A$ の論理式 $A$ に論理式 $A^g$ を次で対応させる。原子論理式と $\bot$ はそのままとし、$\lnot,\land,\to,\forall$ とは交換し、
$$
(B\lor C)^g:=\lnot(\lnot B^g\land\lnot C^g),\qquad(\exists xB)^g:=\lnot\forall x\lnot B^g
$$
と定める。
$A^g$ は $\lor,\exists$ を含まない。証明論 の否定翻訳 $A^N$ は原子論理式にも $\lnot\lnot$ を付けるが、算術では prop-ha-dec により $\mathsf{HA}$ で $A^g$ と同値である。この形が使えるのは、算術の原子論理式が安定だからである(Mos22 §4.1)。
すべての $A$ について $\mathsf{HA}\vdash\lnot\lnot A^g\to A^g$ である。
$A$ の構成の帰納法で示す。原子論理式は prop-ha-dec による。$\bot$ は明らかである。$A^g$ が $\lnot D$ の形のとき($\lnot,\lor,\exists$ の場合)は、直観主義で $\lnot\lnot\lnot D\to\lnot D$ である。残りは次の直観主義の定理と帰納法の仮定による。
$$
\lnot\lnot(B\land C)\to\lnot\lnot B\land\lnot\lnot C,\quad\lnot\lnot(B\to C)\to(B\to\lnot\lnot C),\quad\lnot\lnot\forall xB\to\forall x\lnot\lnot B.\ \square
$$
$\mathsf{PA}\vdash A$ なら $\mathsf{HA}\vdash A^g$ である。より詳しく、$\mathrm{NK}$ と $\mathsf{PA}$ の公理による $\Gamma\vdash A$ の導出があれば、$\mathrm{NJ}$ と $\mathsf{HA}$ の公理による $\Gamma^g\vdash A^g$ の導出がある。
導出の高さの帰納法で示す。翻訳と交換する結合子の規則は同じ規則に移る。残りの規則を確かめる。
1 は $\bot^g=\bot$ と thm-ha-g による。逆は $\mathsf{HA}$ の定理が $\mathsf{PA}$ の定理であることによる。2 は $\sigma^g=\sigma$ による。3 は、prop-ha-dec により $\mathsf{HA}\vdash P\leftrightarrow P^g$ となることによる(構成の帰納法で、$\lor$ の場合に決定可能性を使う)。$\square$
Gödel の第 $2$ 不完全性定理により $\mathsf{PA}$ の無矛盾性は $\mathsf{PA}$ で証明できないが、1 の翻訳そのものは有限的な手続きである。したがって排中律を禁じても、矛盾の危険が減るわけではない。二重否定翻訳が古典算術を直観主義算術に還元することは Avi00 p. 1 にも述べられている。
二重否定翻訳では $\exists yP$ は $\lnot\forall y\lnot P$ に移り、証拠が取り出せない。$\bot$ を別の論理式に置き換えると、これを克服できる。
論理式 $R$ を固定する。$A$ の束縛変数と導出の固有変数は、$R$ の自由変数と異なるように選ぶ。$A^R$ を次で定める。原子論理式 $P$ は $P^R:=P\lor R$ とし、$\bot^R:=R$、$(\lnot B)^R:=B^R\to R$ とし、$\land,\lor,\to,\forall,\exists$ とは交換する。
1 は $A$ の構成の帰納法である。$\exists$ では証拠を $0$ とすればよい。
2 も $P$ の帰納法である。$\land,\lor$ は分配則である。$B\to C$ の場合、$\to$ を示す。prop-ha-dec により $B$ か $\lnot B$ である。$B$ なら $B^R$ から $C\lor R$ を得る。$C$ の場合は $B\to C$ が出て、$R$ の場合は右の選言肢である。$\lnot B$ なら $B\to C$ である。$\leftarrow$ は 1 を使う。$\lnot B$ も同様である。
3 は、$\Gamma\vdash A$ の $\mathrm{NJ}$ の導出から $\Gamma^R\vdash A^R$ の導出を作る。$\lnot$ の規則は $\to$ の規則に移り、$\bot$ からの導出は 1 に移り、他の規則はそのまま移る。公理を確かめる。
$P(x,y)$ が量化記号を含まない論理式で $\mathsf{PA}\vdash\forall x\exists yP(x,y)$ なら、$\mathsf{HA}\vdash\forall x\exists yP(x,y)$ である。
$a$ を新しい自由変数とする。$\mathsf{PA}\vdash\exists yP(a,y)$ なので、thm-ha-g により $\mathsf{HA}\vdash\lnot\forall y\lnot P^g(a,y)$ である。$R:=\exists yP(a,y)$ とおき、lem-ha-r の 3 を適用すると
$$
\mathsf{HA}\vdash\forall y\bigl((P^g(a,y))^R\to R\bigr)\to R
$$
である。lem-ha-r の 2 と $\mathsf{HA}\vdash P^g\leftrightarrow P$ により、$(P^g(a,y))^R$ は $P(a,y)\lor R$ と同値である。$P(a,y)$ からは $\exists$ の導入で $R$ が出るので、括弧の中は証明できる。よって $\mathsf{HA}\vdash R$ であり、$a$ について全称化すればよい。$\square$
計算の停止を $L_A$ で書くと、$P$ に有界量化が入る。有界量化を含む $P$ でも prop-ha-dec の決定可能性と lem-ha-r の 2 は同じ形の有界な範囲の帰納法で成り立ち、thm-ha-pi2 の証明がそのまま通る。この拡張の細部はこの記事では書かない。したがって、$\mathsf{PA}$ が全域性を証明する計算可能関数は $\mathsf{HA}$ でも全域性が証明できる(計算可能性理論)。Avi00 p. 1 が述べる Friedman と Dragalin の結果である。次の形は Markov の規則 と呼ばれる。
$P$ が量化記号を含まないとき、$\mathsf{HA}\vdash\forall x\lnot\lnot\exists yP(x,y)$ なら $\mathsf{HA}\vdash\forall x\exists yP(x,y)$ である。
仮定から $\mathsf{PA}\vdash\forall x\exists yP$ である。thm-ha-pi2 を使う。$\square$
規則ではなく論理式としての Markov の原理 $\forall x(A(x)\lor\lnot A(x))\land\lnot\forall x\lnot A(x)\to\exists xA(x)$ は、$\mathsf{HA}$ で証明できない(Mos22 §5.2。この記事では証明しない。修正実現可能性による証明は Markovの原理 の定理「Markov の原理の独立性」にある)。
次の定義は、Kleene と Aczel の slash(Mos22 §6.3)を算術に合わせた形である。真理と証明可能性を同時に要求する点が要点である。
閉じた文 $A$ について、関係 $|\,A$ を $A$ の構成の帰納法で定める。
1 は $A$ の帰納法である。真な閉じた原子論理式の証明は Peano算術 の数項の計算による。$\land,\lor,\exists$ は帰納法の仮定から出て、残りは定義に含まれる。2 も $A$ の帰納法で、$\mathsf{HA}\vdash t=\underline n$ と等号の公理による。$\square$
$\mathsf{HA}\vdash A$ で $A$ が閉じた文なら $|\,A$ である。
$\Gamma\vdash A$ の $\mathrm{NJ}$ の導出の高さの帰納法で、次を示す:$\sigma$ を導出に現れる自由変数への数項の代入とすると、$\Gamma\sigma$ のすべての文に $|$ が成り立つなら $|\,A\sigma$ である。lem-ha-slash の 1 から、このとき $\Gamma\sigma$ は $\mathsf{HA}$ で証明できる。導出に $\sigma$ を施せば、$\mathsf{HA}\vdash A\sigma$ である。
規則の場合を見る。
$B\lor C$、$\exists xB(x)$ を閉じた文とする。
thm-ha-slash で $|$ を得て、定義と lem-ha-slash の 1 を使う。$\square$
$|\,\bot$ は成り立たないので、thm-ha-slash は $\mathsf{HA}$ の無矛盾性も与える。ただしこの証明は $\mathbb N$ の真理を使う外側の議論である。
thm-ha-pi2 は $\Pi_3$ には伸びない。
$K\subset\mathbb N$ を計算的に枚挙できるが決定可能でない集合とする。Hilbertの第10問題 の解決により、量化記号を含まない $P$ で $K=\{n\mid\exists m\ P(\underline n,\underline m)\text{ が真}\}$ となるものがある。ここでは $y,z,m$ は同じ長さの有限列とし、$\exists y,\forall z$ もその列についての量化とする。
$$
\sigma:=\forall x\exists y\forall z\bigl(P(x,y)\lor\lnot P(x,z)\bigr)
$$
とおく。
$\rho$ を $\mathsf{PA}$ から独立な文とする(Gödelの不完全性定理 の第 $1$ 不完全性定理。$\mathsf{PA}$ の無矛盾性を仮定する)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 論理が直観主義(選言性) | $\mathsf{PA}$ と $\rho\lor\lnot\rho$ | 証明できるのに、どちらの選言肢も証明できない |
| 論理が直観主義(存在性) | $\mathsf{PA}$ と $\exists x((x=0\land\rho)\lor(x=S0\land\lnot\rho))$ | 証明できるのに、証拠の数項がない |
| 文が $\Pi_2$ | ex-ha-pi3 の $\sigma$ | $\mathsf{PA}$ から $\mathsf{HA}$ への保存 |
| 原子論理式が安定 | 算術でない言語の命題変数 $p$ | $\lnot\lnot p\to p$ は $\mathrm{NJ}$ で証明できず、翻訳 $A^g$ は lem-ha-stable を満たさない |
第 $2$ 行の文は、数項 $\underline n$ を代入すると、$n=0$ なら $\rho$、$n=1$ なら $\lnot\rho$、それ以外なら矛盾と同値になる。最後の行のような言語では原子にも $\lnot\lnot$ を付ける必要があり、それが 証明論 の定義「Gödel–Gentzen の否定翻訳」の $A^N$ である。
$\mathsf{HA}$ の定理には、数による計算的な読み方がある。Kleene の実現可能性は、文 $A$ に「$e$ が $A$ を実現する」という関係を与え、$\mathsf{HA}$ の定理がすべて実現されることを示す(vOo02)。排中律とは両立しない Church の提言の算術版と Markov の原理を、同時に $\mathsf{HA}$ に加えても無矛盾である(Mos22 §5.2。この記事では証明しない)。
意味論の側には Kripke意味論 と Heyting代数 がある。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する