Exponentiation

Exponentiation Is Just Application

Exponentiation of Church numerals is defined as:

EXP = λm.λn. n m

That is the entire definition. To compute $m^n$, you apply n to m. No helper functions. No additional lambdas beyond the arguments themselves. Just application.

Why does this work? A Church numeral n is a function that applies something n times. If you hand it m -- which itself applies f m times -- then n applies "apply f m times" n times. Applying f m times, n times over, gives f applied $m^n$ times.

• ADD required composing two iterations
• MUL required nesting one iteration inside another
• EXP requires nothing. Application itself is exponentiation.

Why EXP Works

EXP = λm.λn. n m

To understand why n m computes $m^n$, recall what Church numerals do:

• m = λf.λx. f applied m times to x
• n = λg.λy. g applied n times to y

When we compute n m, we are applying n to m. The numeral n takes "something" and applies it n times. That "something" is m -- a function that itself applies f m times.

So n applies "apply f m times" n times:

• m times, repeated n times = $m^n$ times

The result is a function that applies f exactly $m^n$ times -- which is the Church numeral for $m^n$.

EXP TWO THREE

Recall EXP = λm.λn. n m.

To compute 2^3, we apply EXP to TWO and THREE:

EXP TWO THREE = THREE TWO

THREE is "apply something three times." TWO applies f twice. Applying "apply f twice" three times:

• First application of TWO: f applied 2 times
• Second application of TWO: 2 * 2 = 4 times
• Third application of TWO: 2 * 2 * 2 = 8 times

The result applies f eight times. That is the Church numeral for 8.

Why Is EXP So Simple?

Compare the three arithmetic operations on Church numerals:

• ADD = λm.λn.λf.λx. m f (n f x) -- compose two iterations
• MUL = λm.λn.λf. m (n f) -- nest one iteration inside another
• EXP = λm.λn. n m -- just apply n to m

ADD and MUL both introduce new lambdas (λf, λx) to wire the numerals together. EXP doesn't. Its body is just n m -- bare application.

Why? Because a Church numeral is already a higher-order function. The numeral n takes a function and applies it n times. When that function is itself a numeral m, n is applying "iterate m times" n times -- which is exactly exponentiation. No wiring needed.

The Arithmetic Pattern

The three arithmetic operations on Church numerals form a pattern of decreasing complexity:

• ADD = λm.λn.λf.λx. m f (n f x) -- concatenates m's and n's applications of f end to end
• MUL = λm.λn.λf. m (n f) -- nests n's iteration of f inside m's iteration
• EXP = λm.λn. n m -- applies n directly to m

ADD wires two numerals together with explicit plumbing. MUL uses one numeral as the other's function argument. EXP does nothing beyond bare application.

Each operation moves up one level of abstraction. ADD works at the level of f and x. MUL works at the level of f. EXP works at the level of the numerals themselves.

EXP THREE TWO

Recall EXP = λm.λn. n m.

To compute 3^2, we apply EXP to THREE and TWO:

EXP THREE TWO = TWO THREE

TWO is "apply something twice." THREE applies f three times. Applying "apply f three times" twice:

• First application of THREE: f applied 3 times
• Second application of THREE: 3 × 3 = 9 times

The result applies f nine times. That is the Church numeral for 9.