Multiplication

What Is Multiplication?

Recall that addition concatenated iterations. ADD m n applies f a total of m + n times by running one numeral's iterations after the other's.

Multiplication works differently. Instead of concatenating iterations, it nests them. To multiply m by n, we don't just run m's iterations and then n's. We take the entire process "apply f n times" and repeat THAT process m times.

• If n means "apply f three times," then (n f) is the operation "apply f three times."
• If m means "repeat a process twice," then m (n f) means "repeat the operation 'apply f three times' twice" -- which is six applications of f.

MUL Definition

The multiplication function takes two Church numerals m and n and produces a new Church numeral that applies f exactly m * n times:

MUL = λm.λn.λf. m (n f)

Reading this definition:

• n f produces the operation "apply f n times"
• m (n f) repeats that operation m times
• The result is a function waiting for an x, which will have f applied to it m * n times

Notice: MUL takes m, n, and f -- but not x. The numeral m takes care of x internally, since m receives (n f) as its "function" argument and will apply it m times to whatever x comes next.

MUL TWO THREE

MUL = λm.λn.λf. m (n f)

Applying MUL to TWO and THREE:

• MUL TWO THREE = λf. TWO (THREE f)
• THREE f is the operation "apply f three times"
• TWO (THREE f) repeats that operation twice
• Two rounds of three applications = six applications of f

The result is a Church numeral that applies f exactly six times. That is SIX.

MUL vs ADD

Both ADD and MUL combine two Church numerals into one, but they structure the combination differently:

• ADD = λm.λn.λf.λx. m f (n f x) Concatenation: n applies f n times to x, then m applies f m more times to that result. Total: m + n applications.

• MUL = λm.λn.λf. m (n f) Nesting: (n f) is the compound operation "apply f n times." Then m repeats that compound operation m times. Total: m * n applications.

ADD treats f as the same single-step operation for both numerals. MUL treats (n f) -- an entire multi-step process -- as the operation that m iterates.

MUL ZERO

MUL = λm.λn.λf. m (n f)

What happens when m is ZERO?

• MUL ZERO n = λf. ZERO (n f)
• ZERO = λf.λx.x -- apply any function zero times, just return x
• So ZERO (n f) = λx.x -- regardless of what (n f) is, ZERO ignores it and returns the identity

The result λf.λx.x applies f zero times. That is ZERO.

It doesn't matter what n is. Zero repetitions of any process -- even a billion applications of f -- produces nothing.

MUL ONE

MUL = λm.λn.λf. m (n f)

What happens when m is ONE?

• MUL ONE n = λf. ONE (n f)
• ONE = λf.λx.f x -- apply any function exactly once
• So ONE (n f) = λx.(n f) x -- apply the operation (n f) once

Applying (n f) once to x gives the same result as n f x -- exactly n applications of f. The result is n.

One iteration of any process is just the process itself. MUL ONE n = n and MUL n ONE = n -- ONE is the identity for multiplication, just as ZERO is the identity for addition.

MUL ONE THREE

MUL = λm.λn.λf. m (n f)

Applying MUL to ONE and THREE:

• MUL ONE THREE = λf. ONE (THREE f)
• THREE f is the operation "apply f three times"
• ONE (THREE f) applies that operation once
• One round of three applications = three applications of f

The result is a Church numeral that applies f exactly three times.