TCS Journal 2023 Journal Article
Higher-order concepts for the potential infinite
- Matthias Eberl
The lambda calculus can be seen as a language that connects mathematics with computer science. However, the models used in both disciplines have different basic properties. In computer science these models are mainly based on domain theory with its partial functions and its fixed point property. In mathematics the models use total functions and relations and allow the integration of logic. Typically, mathematical models are based on set theory with its actual infinite sets, which are incongruous with computer science. We will present a dynamic model that is based consequently on the potential infinite. It uses total functions, whereby functions and the function spaces are seen as interdependent, increasing finite entities. It moreover allows the integration of higher-order logic (to be demonstrated in a separate paper), provided the universal quantifier is interpreted in a specific, dynamic way. Such a model can serve as a common denotational semantics of the lambda calculus for both, mathematics and computer science.