2009-04-08

MULT

Japanese version

Multiplication is defined as the following.

MULT := λ m n f . m (n f)

Since

2 := λ f x. f (f x)
3 := λ f x. f (f (f x)),

MULT 2 3 := (λ m n f . m (n f)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n f . (λ f x. f (f x)) (n f)) (λ f x. f (f (f x)))

You can see that (n f) is copied as many as f-s.

= (λ n f . (λ x. (n f) ((n f) x))) (λ f x. f (f (f x)))

(n f) is copied the first argument (=2) times. The second argument (=3)
is replaced with n of (n f).

= (λ f . (λ x. ((λ f x. f (f (f x))) f) (((λ f x. f (f (f x))) f) x)))

= (λ f . (λ x. (λ x. f (f (f x))) (((λ x. f (f (f x)))) x)))

= (λ f . (λ x. f (f (f (((λ x. f (f (f x)))) x) x))))

= (λ f . (λ x. f (f (f (f (f (f x))) x))))

= (λ f . f (f (f (f (f (f x))))))

= 6


There is another multiplication definition.


MULT := λ m n. m (PLUS n) 0

I thought this 0 is just number 0 instead of Church number 0, when I saw
this in Wilipedia. This is not easy for beginners.


MULT 2 3 := (λ m n. m (PLUS n) (λ f x. x)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n. (λ f x. f (f x)) (PLUS n) (λ f x. x)) (λ f x. f (f (f x)))

You can find the similar pattern as the first definition, (PLUS n) is
copied k-times (k = the first argument number).

= (λ n. (λ x. (PLUS n) ((PLUS n) x)) (λ f x. x)) (λ f x. f (f (f x)))

= (λ n. (PLUS n) ((PLUS n) (λ f x. x))) (λ f x. f (f (f x)))

= (PLUS (λ f x. f (f (f x)))) ((PLUS (λ f x. f (f (f x)))) (λ f x. x))

The underline part, PLUS 3 0 is 3 (= 3 + 0). Therefore,

= (PLUS (λ f x. f (f (f x)))) (λ f x. f (f (f x))).

This is 3 + 3, then,

= 6.

No comments: