Given $Succ = \lambda n. \lambda fx. f(n f(x))$ and
church's numeral: $n = \lambda fx.f^n(x)$
Show that $ m\ Succ\ n = m + n$
I don't get how it can be shown. I get stuck on this step:
$\lambda fx. f^m(x) \ \lambda fx.f^{n+1}(x)$
Many thanks.
Asked
Active
Viewed 213 times
0
-
Shouldn't that be $m=\lambda fx.f^{m}(x)$? You have $n=$ with $m$. – Thomas Andrews Apr 20 '15 at 12:07
-
yes, sorry about the typo – Laurykninu Apr 20 '15 at 12:25
1 Answers
0
Hint: $m\,Succ\,n=(m\,Succ)n =(Succ^m)(n)$
Ultimately, it will be a proof by induction.
Thomas Andrews
- 177,126