How to define numbers in a way that a number 'n' is equivalent to the function plus 'n'?

81 Views Asked by At

In lambda calculus, is it possible to define (or disprove the existence of) a number system alternative to church numerals such that each number is a function which on application, adds itself to it's parameter?

2

There are 2 best solutions below

2
On BEST ANSWER

The main problem with this representation is that it doesn't seem to give any way to observe the difference between numbers. Church numerals are useful because when you have one of those, you can apply it to functions of your own choosing to make an observable difference, but if all a number does is to take a number as argument and produce another one, there's no context you can put two numbers and -- based on this specification alone! -- expect that $2$ and $3$ will have observably different properties.

0
On

It is possible. Let $f_n$ denote the arithmetic operation "add $n$" where "$n$" and "add" are defined using church numerals. Now, $f_0$ can be identified as "zero" and composing $f_n$ with $f_1$ can be identified as "the successor of $f_n$" i.e. the successor of $f_n$ is an application of $f_n$ followed by $f_1$. Now you can verify that this does in fact give you a "number system".