Δᵇᵢ-論理式の帰納法図式

$ i \ge 1とする

定義

$ \mathrm S_2^i \vdash (\forall x \le a)[\phi(x) \leftrightarrow \psi(x)] の成り立つ$ \Sigma^b_i論理式$ \phi, $ \Pi^b_i論理式$ \psiについて図式

$ \text{IND}_a\phi := \phi(0) \land (\forall x \le a)[\phi(x) \to \phi(x+1)] \to \phi(a)

を$ \Delta^b_i\text{-IND}という

定理

$ \mathrm S_2^i \vdash \Delta^b_i\text{-IND}

Proof.

$ \Sigma^b_i論理式$ \phi, $ \Pi^b_i論理式$ \psiについて

$ \mathrm S_2^i \vdash (\forall x \le a)[\phi(x) \leftrightarrow \psi(x)]

とする

Hzs: $ \phi(0) \land (\forall x < a)[\phi(x) \to \phi(x + 1)]

を仮定する

$ \Phi (v) \coloneqq (\forall x < a)(\phi(x) \to x + v \le a \to \psi(x + v) )

これは$ \Pi^b_i論理式

多項式帰納法図式$ \Pi^b_i\text{-PIND}によって$ (\forall v)\Phi(v)を示す

$ \Phi(0)

あきらか

$ \Phi(v) \implies \Phi(2v)

IH: $ \Phi(v)を仮定する

ある$ x < aについて$ \phi(x), $ x + 2v \le aとする

IHを２回使って$ \phi(x + 2v)を得る

$ \Phi(v) \implies \Phi(v + 1)

Hzsより

$ \phi(0)と$ \Phi(a)より$ \phi(a)を得る．