A Simple Adequate Categorical Model for PCF, II

Article type: Research Article

Authors: Braüner, Torben

Affiliations: Centre for Philosophy and Science-Theory, Aalborg University, Langagervej 6, DK-9220 Aalborg East, Denmark. E-Mail: torbenb@hum.auc.dk

Note: [] The work presented here was partially carried out during employment by BRICS, Aarhus University. The author is presently supported by the Danish Natural Science Research Council.

Abstract: Usually types of PCF are interpreted as cpos and terms as continuous functions. It is then the case that non-termination of a closed term of ground type corresponds to the interpretation being bottom; we say that the semantics is adequate. We shall here present an axiomatic approach to adequacy for PCF in the sense that we will introduce categorical axioms enabling an adequate semantics to be given. We assume the presence of certain “undefined” maps with the role of being the interpretation of non-terminating terms, but the order-structure is left out. This is different from previous approaches where some kind of order-theoretic structure has been considered as part of an adequate categorical model for PCF. We take the point of view that partiality is the fundamental notion from which order-structure should be derived, which is corroborated by the observation that our categorical model induces an order-theoretic model for PCF in a canonical way.

Keywords: Adequacy, PCF, categorical model

DOI: 10.3233/FI-1998-33402

Journal: Fundamenta Informaticae, vol. 33, no. 4, pp. 339-368, 1998