Church Numerals

Church numerals are a way of representing natural numbers using lambda calculus. a foundational framework in mathematical logic and computer science. In essence, they encode numbers using functions rather than conventional numeric symbols.

Why study Church Numerals?

1. Demonstrate how basic arithmetic and logic can be constructed purely from functions, highlighting the expressive power of lambda calculus.
2. Lambda calculus underpins modern functional programming languages like Haskell.
3. They help in studying the theoretical limits of computation.
4. Mathematical Elegance: Church numerals are an example of how seemingly abstract systems like functions can represent concrete entities like numbers.

The Basics of Church Numerals

A church numeral is a higher order function that takes two arguments:

1. a function
2. a value x
3. The number n is represented as the function that applies f to x, n times.
4. O Apply f 0 times 0 -> λfx.x
5. 1: Apply f 1 time -> λfx.fx

Basic Definition

1. Zero:

• Represented as a function that takes two arguments (a function f and an argument x) and returns x:

zero = \f x. x

• Explanation: This definition means that when zero is called with a function f and an argument x, it simply returns x without applying f at all. Thus, it represents the number zero because it indicates that no application of f occurs.

2. One:

• Represents a function that applies f once to x:

one = \f x. f x

• Explanation: Here, one takes a function f and an argument x, and applies f to x exactly once. This represents the number one because it indicates that f is applied once.

3. Two:

• Applies f twice to x:

two = \f x. f (f x)

• Explanation: Here, two takes a function f and an argument x, and applies f to x exactly twice. This represents the number two because it indicates that f is applied two.

4. Three:

• Applies f twice to x:

three = \f x. f (f (f x))

• Explanation: Here, three takes a function f and an argument x, and applies f to x exactly three. This represents the number three because it indicates that f is applied three times.

In general, a Church numeral n is defined as:

n = \f x. f (f (... (f x) ...)) // f applied n times

Operations on Church Numerals:

To perform arithmetic operations using church numeral, we define functions that manipulate these numerals.

1. Sucessor Function (succ) :

This function takes church numerals and returns the next church numeral by applying f one more time.

succ = \n f x. f (n f x)
two = \f x. f (f x)

succ two?
(\n f x. f (n f x)) (\f x. f (f x))

1. n -> is a church numeral
2. The function succ takes this numeral and applies the function f one additional time.