Skip to content
scrambled
Programming Language Theory Flashcard

Define successor, addition, multiplication, zero test, subtraction, predecessor, equality for church numerals?

Question

Define successor, addition, multiplication, zero test, subtraction, predecessor, equality for church numerals?

Answer

Church numerals:

cn=λa. λz. a (a (⋯(a⏟n z)⋯))
  • Successor:

    succ=λc. λa. λz. a (c a z).

  • Addition:

    plus=λm. λn. λa. λz. (m a (n a z)).

  • Multiplication:

    time=λm. λn. m plus n.

  • Zero test:

    iszero=λc. c (λ_. fls) tru

  • Predecessor:

    pred=λc. fst (c (λp. pair (snd p) (succ (snd p))) (pair c0 c0))

  • Subtraction:

    sub=λm. λn. n pred m.

  • Equality:

    eq=λm. λn. (and (iszero (sub m n)) (iszero (sub n m)))