Closed Sets of Higher-Order Functions
Evan Marzion

Abstract:
In universal algebra, clones may be viewed as a way of studying definability between functions within the presence of certain natural operations, namely projection and composition. We show how the simply typed lambda calculus provides a suitable framework for extending this study to higher-order functions as well. We define what we call a combinatory clone, a higher-order analogue of regular clones, and establish some basic results about them. Inspired by Post’s classification of the boolean clones, boolean combinatory clones are studied. Finally, we consider an extension of the simply typed lambda calculus with product types, and show how they do not affect anything from the point of view of combinatory clones.