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, 2021 at 13:21
  • 1
    $\begingroup$ Good point. That was my intuition about it. Thanks $\endgroup$ Aug 29, 2021 at 14:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.