Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?

  • 5
    $\begingroup$ If I understand what you mean by "get away with", yes, since only three variables are needed to encode a complete combinator basis such as SKI or BCKW. Conversely, Richard Statman proved that two variables are not enough, as explained in my answer here. $\endgroup$ Aug 29 at 13:21
  • 1
    $\begingroup$ Good point. That was my intuition about it. Thanks $\endgroup$ Aug 29 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.