Heyting算術

同義語:ハイティング算術Heyting arithmetic直観主義算術intuitionistic arithmetic

概要

Heyting算術(Heyting arithmetic)とは、Peano算術と同じ公理を直観主義論理の上に置いた算術の理論である。Gödel–Gentzen の二重否定翻訳により Peano算術の定理は Heyting算術の定理に翻訳され、両者の無矛盾性は同値である。Friedman の翻訳により $\forall x\exists y$ の形で本体に量化記号を含まない文の証明可能性は両者で一致する。一方 Heyting算術は、閉じた選言の一方と閉じた存在文の証拠の数項を証明できるという、Peano算術にはない性質をもつ。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 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$ つの結果と、選言性・存在性を証明する。

定義と決定可能性

Heyting 算術

言語を $L_A=\{0,S,+,\cdot,<\}$ とする。Peano算術 の公理 $1$〜$8$ と帰納法の公理、および等号の公理 $x=x$ と $x=y\to(\varphi(x)\to\varphi(y))$ を公理とする。
これらの公理のもとで、自然演繹 の直観主義の体系 $\mathrm{NJ}$ で証明できることを $\mathsf{HA}\vdash A$ と書く。背理法の規則を加えた $\mathrm{NK}$ で証明できることが $\mathsf{PA}\vdash A$ である。$\lnot A$ と $A\to\bot$ は同値である。

公理を書き下した形は Peano算術 と同じである。加法と乗法の結合則・交換則・分配則の証明は等式の帰納法だけで書けるので、$\mathsf{HA}$ の中でも成り立つ。$\underline n$ は数 $n$ の数項($0$ に $S$ を $n$ 回施した項)を表す。

算術の原子論理式の決定可能性

$\mathsf{HA}$ は次を証明する。

  1. $y=0\lor\exists z\,y=Sz$
  2. $x=y\lor\lnot x=y$
  3. $x< y\lor\lnot x< y$
  4. 量化記号を含まない論理式 $P$ について $P\lor\lnot P$ と $\lnot\lnot P\to P$

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$

Gödel–Gentzen の二重否定翻訳

二重否定翻訳

$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$ の導出がある。

導出の高さの帰納法で示す。翻訳と交換する結合子の規則は同じ規則に移る。残りの規則を確かめる。

  • 背理法:$\Gamma^g,\lnot A^g\vdash\bot$ から $\Gamma^g\vdash\lnot\lnot A^g$ を得て、lem-ha-stable により $A^g$ を得る。
  • $\lor$ の導入:$B^g$ から $\lnot(\lnot B^g\land\lnot C^g)$ は直ちに出る。
  • $\lor$ の除去:$\Gamma^g,B^g\vdash D^g$ と $\Gamma^g,C^g\vdash D^g$ から、$\Gamma^g,\lnot D^g\vdash\lnot B^g\land\lnot C^g$ を得る。$\lnot(\lnot B^g\land\lnot C^g)$ とあわせて $\lnot\lnot D^g$ を得て、lem-ha-stable を使う。
  • $\exists$ の導入:$B^g(t)$ から $\lnot\forall x\lnot B^g(x)$ は直ちに出る。
  • $\exists$ の除去:固有変数 $a$ について $\Gamma^g,B^g(a)\vdash D^g$ なら、$\Gamma^g,\lnot D^g\vdash\forall x\lnot B^g(x)$ である。$\lnot\forall x\lnot B^g$ とあわせて $\lnot\lnot D^g$ を得て、lem-ha-stable を使う。
    公理を確かめる。公理 $1,2,4,5,6,7$ と $x=x$ は翻訳で変わらない。$x=y\to(\varphi(x)\to\varphi(y))$ の翻訳は $\varphi^g$ についての同じ形の公理であり、$\varphi$ の帰納法の公理の翻訳は $\varphi^g$ の帰納法の公理である。翻訳は $\land,\to,\forall$ と交換し、項の代入とも交換するからである。公理 $3$ の翻訳は、公理 $3$ と $\exists yB\to\lnot\forall y\lnot B$ から出る。
    公理 $8$ の翻訳のうち、$x< y\to\lnot\forall z\lnot(Sz+x=y)$ は同様である。逆向きは次のように示す。$\lnot x< y$ なら公理 $8$ により $\forall z\lnot(Sz+x=y)$ である。よって $\lnot\forall z\lnot(Sz+x=y)$ から $\lnot\lnot x< y$ を得て、prop-ha-dec により $x< y$ である。$\square$
無矛盾性の同値と保存性
  1. $\mathsf{HA}$ が無矛盾であることと $\mathsf{PA}$ が無矛盾であることは同値である。
  2. $\sigma$ が $\lor,\exists$ を含まない文で $\mathsf{PA}\vdash\sigma$ なら、$\mathsf{HA}\vdash\sigma$ である。
  3. $P$ が量化記号を含まない論理式で $\mathsf{PA}\vdash\forall xP$ なら、$\mathsf{HA}\vdash\forall xP$ である。

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 にも述べられている。

Friedman の翻訳と $\Pi_2$ 文の保存

二重否定翻訳では $\exists yP$ は $\lnot\forall y\lnot P$ に移り、証拠が取り出せない。$\bot$ を別の論理式に置き換えると、これを克服できる。

Friedman の翻訳

論理式 $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$ とは交換する。

Friedman の翻訳の性質
  1. $\mathsf{HA}\vdash R\to A^R$ である。
  2. $P$ が量化記号を含まなければ $\mathsf{HA}\vdash P^R\leftrightarrow(P\lor R)$ である。
  3. $\mathsf{HA}\vdash A$ なら $\mathsf{HA}\vdash A^R$ である。

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 に移り、他の規則はそのまま移る。公理を確かめる。

  • $x=x$ と公理 $4$〜$7$ は、$\lor$ の導入で出る。
  • 公理 $1$ は、$Sx=Sy\lor R\to x=y\lor R$ である。公理 $2$ の翻訳 $(0=Sx\lor R)\to R$ は公理 $2$ から出る。
  • 公理 $3$ の翻訳 $((x=0\lor R)\to R)\to\exists y(x=Sy\lor R)$ は、prop-ha-dec の 1 で場合分けする。$x=0$ なら $R$ が出て、証拠は何でもよい。$x=Sz$ なら証拠は $z$ である。
  • 公理 $8$ は、$R$ の場合を $\lor$ の導入で処理する。
  • $x=y\to(\varphi(x)\to\varphi(y))$ の翻訳は、$R$ の場合を 1 で処理する。
  • 帰納法の公理の翻訳は $\varphi^R$ の帰納法の公理である。$\square$
$\Pi_2$ 文の保存

$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 の規則 と呼ばれる。

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)を算術に合わせた形である。真理と証明可能性を同時に要求する点が要点である。

slash

閉じた文 $A$ について、関係 $|\,A$ を $A$ の構成の帰納法で定める。

  • 閉じた原子論理式 $A$ について、$|\,A$ は $A$ が $\mathbb N$ で真であることとする。$|\,\bot$ は成り立たない。
  • $|\,B\land C$ は「$|\,B$ かつ $|\,C$」、$|\,B\lor C$ は「$|\,B$ または $|\,C$」、$|\,\exists xB(x)$ は「ある $n$ で $|\,B(\underline n)$」とする。
  • $|\,B\to C$ は「$\mathsf{HA}\vdash B\to C$ であり、$|\,B$ なら $|\,C$」とする。
  • $|\,\lnot B$ は「$\mathsf{HA}\vdash\lnot B$ であり、$|\,B$ でない」とする。
  • $|\,\forall xB(x)$ は「$\mathsf{HA}\vdash\forall xB(x)$ であり、すべての $n$ で $|\,B(\underline n)$」とする。
slash の基本性質
  1. $|\,A$ なら $\mathsf{HA}\vdash A$ である。
  2. 閉じた項 $t$ の値が $n$ なら、$|\,A(t)$ と $|\,A(\underline n)$ は同値である。

1 は $A$ の帰納法である。真な閉じた原子論理式の証明は Peano算術 の数項の計算による。$\land,\lor,\exists$ は帰納法の仮定から出て、残りは定義に含まれる。2 も $A$ の帰納法で、$\mathsf{HA}\vdash t=\underline n$ と等号の公理による。$\square$

slash の健全性

$\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$ である。
規則の場合を見る。

  • $\land,\lor$ の規則は定義のとおりである。$\lor$ の除去では、成り立つ選言肢の側の帰納法の仮定を使う。
  • $\to$ の導入:上の注意で $\mathsf{HA}\vdash(B\to C)\sigma$ である。$|\,B\sigma$ なら帰納法の仮定で $|\,C\sigma$ である。$\to$ の除去は定義から出る。
  • $\lnot$ の導入:$\mathsf{HA}\vdash\lnot B\sigma$ であり、$|\,B\sigma$ なら帰納法の仮定で $|\,\bot$ となるので、$|\,B\sigma$ でない。$\lnot$ の除去と $\bot$ からの導出は、仮定が成り立たないので何も示すことがない。
  • $\forall$ の導入:$\mathsf{HA}\vdash(\forall xB)\sigma$ であり、各 $n$ で、固有変数に $\underline n$ を代入した $\sigma$ に帰納法の仮定を使う。$\forall$ の除去と $\exists$ の導入は、lem-ha-slash の 2 で項を数項に替える。
  • $\exists$ の除去:$|\,(\exists xB)\sigma$ の証拠 $n$ を固有変数に代入して帰納法の仮定を使う。
    公理の場合を見る。どの閉じた代入例も $\mathsf{HA}$ で証明できる。
  • 公理 $1$:$|\,S\underline m=S\underline n$ なら $m=n$ である。公理 $2$:$0=S\underline n$ は偽である。公理 $4$〜$7$ と $x=x$ は真な原子論理式である。
  • 公理 $3$:$|\,\lnot\underline n=0$ なら $n\ne0$ で、$n=k+1$ とすれば $k$ が証拠である。
  • 公理 $8$:$m< n$ の証拠は $n-m-1$ である。逆も数の計算である。
  • $\underline m=\underline n\to(\varphi(\underline m)\to\varphi(\underline n))$:$|\,\underline m=\underline n$ なら $m=n$ で、結論は $\varphi(\underline m)\to\varphi(\underline m)$ の形である。この文は証明でき、$|$ の条件も明らかである。
  • 帰納法の公理:$|\,\varphi(0)$ と $|\,\forall x(\varphi(x)\to\varphi(Sx))$ を仮定する。外側の帰納法ですべての $n$ に $|\,\varphi(\underline n)$ が成り立つ。仮定は lem-ha-slash の 1 により証明できるので、帰納法の公理により $\mathsf{HA}\vdash\forall x\varphi$ である。$\square$
選言性と存在性

$B\lor C$、$\exists xB(x)$ を閉じた文とする。

  1. $\mathsf{HA}\vdash B\lor C$ なら、$\mathsf{HA}\vdash B$ または $\mathsf{HA}\vdash C$ である(選言性)。
  2. $\mathsf{HA}\vdash\exists xB(x)$ なら、ある $n$ で $\mathsf{HA}\vdash B(\underline n)$ である(存在性)。

thm-ha-slash で $|$ を得て、定義と lem-ha-slash の 1 を使う。$\square$

$|\,\bot$ は成り立たないので、thm-ha-slash は $\mathsf{HA}$ の無矛盾性も与える。ただしこの証明は $\mathbb N$ の真理を使う外側の議論である。
thm-ha-pi2 は $\Pi_3$ には伸びない。

反例:$\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) $$
とおく。

  • 満たすこと:$\mathsf{PA}\vdash\sigma$ である。$\exists yP(x,y)$ か否かで場合分けする。$\sigma$ は $\Pi_3$ 文である。
  • 満たさないこと:$\mathsf{HA}\nvdash\sigma$ である。証明できたとすると、cor-ha-dp により各 $n$ に $m$ があり $\mathsf{HA}\vdash\forall z(P(\underline n,\underline m)\lor\lnot P(\underline n,z))$ である。$\mathbb N$ は $\mathsf{HA}$ のモデルなので、$P(\underline n,\underline m)$ が偽なら $n\notin K$ である。$\mathsf{HA}$ の証明を順に調べ、この形の証明で $P(\underline n,\underline m)$ が偽であるものを探す。$n\in K$ なら $m$ は $P$ を真にするしかなく、$n\notin K$ なら $P$ は偽なので、この探索は $K$ の補集合を枚挙する。これは $K$ が決定可能でないことに反する。
  • 成り立たない含意:thm-ha-pi2 の $\forall x\exists y$ の形を $\forall x\exists y\forall z$ に広げることはできない。

反例:条件を外すと成り立たないこと

$\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代数 がある。

関連項目

参考文献

[2]
Jeremy Avigad, Interpreting classical theories in constructive ones, The Journal of Symbolic Logic, 2000, pp. 1785–1812(著者版 p. 1)
[3]
Jaap van Oosten, Realizability: A Historical Essay, Mathematical Structures in Computer Science, 2002, pp. 239–263(著者版 pp. 5–7)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する