以下是lambda微積分的合法繼承函數嗎？ （堂數字）

Question

我從書籍，爲Church數的繼任者是形式的閱讀： （\拉姆達NF X F（NFX）。）

昨晚我想出了這一點： （ \ abb。（ab）（bc））

我相信它也執行後繼函數的功能。但是，我不是100％肯定的，我的減少是正確的。有人可以檢查它並告訴我嗎？ （f（f（f））（f（f））的簡短版本，其中f（n） ））表示數字n，預期結果應爲n + 1，即（\ lambda f x。f^{n + 1} x）

（\ lambda ab c。（ab）（ BC））（\拉姆達˚FX。˚F^ NX）

=（\拉姆達b C。（（\拉姆達˚FX。˚F^ NX）b）（BC））//一個替換

= （\ lambda b c。（（\ lambda x。b^nx）（bc））// f替換爲

=（\ lambda b c。 （（\ lambda x。b^n x）（b c））//不是100％確定，我可以用（b c）替換x嗎？

=（\拉姆達B C。（B^N（BC））

=（\拉姆達B C。（B ^（N + 1）c）中

這是減少正確的，尤其從步驟3至4？ 謝謝！

Answer 1

是的，這是正確的。沒有與替換b c爲x沒有問題。見the substitution rule。雖然b和c綁定，他們在這兩個問題上面的條款約束，所以它們在兩個地方都有相同的含義。

Answer 2

瞭解後繼函數的兩個定義的方法是從和啓動：

plus = \n,m,x,y. n x (m x y) 

那麼我們可以定義

succ1 = \n. plus one n 
succ2 = \n. plus n one 

其中one = \x,y.x y

簡化了兩屆，我們得到

succ1 = \n,x,y. one x (n x y) 
     = \n,x,y. x (n x y) 
succ2 = \n,x,y. n x (one x y) 
     = \n,x,y. n x (x y)