自然数$n$に対応するチャーチ数を$\overline{n}$とすると、

$$\overline{n}=\lambda sz.s(s(\cdot\cdot\cdot s(z)\cdot\cdot\cdot))=\lambda sz.s^n(z)$$

先行数取得関数Sの一般式

successor関数の一般式$\textbf{S}\overline{n}=\overline{n+1}$を示したい。
$$\textbf{S}\equiv\lambda n a b.a(nab)$$

であり、$\textbf{S}\overline{0}=\overline{1}$なので、$\textbf{S}\overline{n}$を示す。
$\textbf{S}\overline{n}
\rightarrow(\lambda nab.a(nab))(\lambda sz.s^n(z))
\rightarrow\lambda ab.a((\lambda sz.s^n(z))ab)$
$\rightarrow\lambda ab.a(a^n(b))
\rightarrow\lambda ab.a^{n+1}(b)
\rightarrow\overline{n+1}$
数学的帰納法により、$\textbf{S}\overline{n}=\overline{n+1}$が示されました。

補助関数Φの一般式

補助関数$\Phi$は、
$$\Phi\equiv(\lambda p z.z(\textbf{S}(p\textbf{T}))(p\textbf{T}))$$

と定義され、$\Phi^n(\lambda z.z\ \overline{0}\ \overline{0})=
\lambda z.z\ \overline{n}(\overline{n-1})$を示したい。
前のブログの結果から$\Phi(\lambda z.z\ \overline{0}\ \overline{0})=\lambda z.z\ \overline{1}\ \overline{0}$となる。
$n=k$の場合であれば、$n=k+1$の場合も成り立つことを示す。
$\Phi^k(\lambda z.z\ \overline{0}\ \overline{0})=
\lambda z.z\ \overline{k}(\overline{k-1})$ならば、$\Phi^{k+1}(\lambda z.z\ \overline{0}\ \overline{0})=
\lambda z.z(\overline{k+1})\overline{k}$であること示す。
従って、
$\Phi^{k+1}(\lambda z.z\ \overline{0}\ \overline{0})
\rightarrow\Phi(\Phi^n(\lambda z.z\ \overline{0}\ \overline{0}))
\rightarrow\Phi(\lambda z.z\ \overline{k}(\overline{k-1}))$
$\rightarrow(\lambda p z.z(\textbf{S}(p\textbf{T}))(p\textbf{T}))(\lambda z.z\ \overline{k}(\overline{k-1}))$
$p\leftarrow\lambda z.z\ \overline{k}(\overline{k-1})$と置き換えられるので、
$p\textbf{T}\rightarrow(\lambda z.z\ \overline{k}(\overline{k-1}))\textbf{T}\rightarrow\textbf{T}\overline{k}(\overline{k-1})\rightarrow\overline{k}$となるので、上式は、
$\rightarrow(\lambda z.z(\textbf{S}(\overline{k}))(\overline{k}))
\rightarrow(\lambda z.z(\overline{k+1})(\overline{k}))$
数学的帰納法によって全ての自然数$n\in\textbf{N}$において、$$\Phi^n(\lambda z.z\ \overline{0}\ \overline{0})=
\lambda z.z\ \overline{n}(\overline{n-1})$$が証明された。

predecessor先行値所得関数Pの一般式

$\textbf{P}(\overline{m})=\overline{m-1}$を示したい。
$$\textbf{P}\equiv(\lambda n.(n\Phi(\lambda z.z\ \overline{0}\ \overline{0}))\textbf{F})$$

なので、
$\textbf{P}(\overline{m})
\rightarrow(\lambda n.(n\Phi(\lambda z.z\ \overline{0}\ \overline{0}))\textbf{F})(\overline{m})
\rightarrow((\overline{m})\Phi(\lambda z.z\ \overline{0}\ \overline{0}))\textbf{F}$
$\rightarrow((\lambda sz.s^m(z))\Phi(\lambda z.z\ \overline{0}\ \overline{0}))\textbf{F}
\rightarrow(\Phi^m(\lambda z.z\ \overline{0}\ \overline{0}))\textbf{F}$
$\rightarrow(\lambda z.z(\overline{m})(\overline{m-1}))\textbf{F}
\rightarrow\textbf{F}(\overline{m})(\overline{m-1})
\rightarrow\overline{m-1}$

従って、$\textbf{P}(\overline{0})=\overline{1}$なので、数学的帰納法によりすべての自然数$m$に対して下記の式が成り立つ。
$$\textbf{P}(\overline{m})=\overline{m-1}$$

$\textbf{P}$はチャーチ数を１減らす働きをしている。

-- Haskell
churchToInt n = n (+1) 0

pair a b = \z -> (z a b)
true x y = x    -- $\lambda xy.x$
false x y = y   -- $\lambda xy.y$
zero s z = z
one s z = s(z)
two s z = s(s(z))
three s z = s(s(s(z)))
succ' n a b = a (n a b)

base = pair zero zero
phi p z = z (succ' (p true))(p true)

pred' n = n phi(base) false

main = do
    print "P3->"
    print $ churchToInt (pred' three)

*Main> main
"P3->"
2

参考図書

プログラミングHaskell 第2版