Arytmetyka w rachunku lambda

Funkcja ${\displaystyle S}$

${\displaystyle S\equiv \lambda xyz.y(xyz).}$ 

Procedura ta nie robi nic innego jak „dodaje” jeszcze jedno wywołanie funkcji do pewnej liczby, przez co staje się ona liczbą o jeden większą.

Aby dodać dwie liczby naturalne Churcha ${\displaystyle K}$

${\displaystyle \oplus \equiv \lambda xy.xSy.}$ 

Z definicji liczb naturalnych Churcha wiemy, że wywołując funkcję pewnej liczby ${\displaystyle K}$

Mnożenie w rachunku lambda zdefiniowane jest następująco:

${\displaystyle \otimes \equiv \lambda xyz.x(yz).}$ 

Obliczając według tej funkcji iloczyn ${\displaystyle \otimes xy,}$

Poprzednikiem liczby ${\displaystyle K}$

${\displaystyle P(K)=L\iff S(L)=K,}$ 

${\displaystyle P(0)=0.}$ 

W rachunku lambda stworzenie takiej funkcji nie jest tak łatwe jak stworzenie funkcji następnika ${\displaystyle S.}$

Tworzymy funkcję ${\displaystyle \Psi ,}$

${\displaystyle \Psi \equiv \lambda pz.z(S(pT))(pT).}$ 

Funkcja poprzednika ${\displaystyle P}$

${\displaystyle P\equiv \lambda n.(n\Psi (\lambda z.z00))F.}$ 

Odejmowanie, podobnie jak w przypadku dodawania, jest zdefiniowane jako wielokrotna aplikacja funkcji poprzednika (w tym wypadku pamiętając o przemienności – odejmowanie przemienne nie jest):

${\displaystyle \ominus \equiv \lambda xy.yPx.}$ 

Aby policzyć potęgę ${\displaystyle x^{y}}$

${\displaystyle x^{y}=\underbrace {x*x*x*\ldots *x} _{y{\text{-razy}}}.}$ 

Tak więc na przykład ${\displaystyle x^{3}}$

${\displaystyle \otimes (\otimes (x)x)x.}$ 

Widzimy, że jest to parokrotna aplikacja funkcji ${\displaystyle \otimes }$

${\displaystyle \Xi \equiv \lambda pz.z(\otimes (pT)(pF))(pF).}$ 

Więc aplikując ${\displaystyle y}$

${\displaystyle {\mbox{pow}}\equiv \lambda xy.(y\Xi (\lambda z.z1x))T.}$