Notes on Partial Combinatory Algebras
Ingemarie Bethke

Abstract:
This dissertation is a collection of five loosely connected papers on various subjects within the framework of so-called combinatorial algebras, ie. models of combinatorial logic. The articles are preceded by a general introduction and a brief survey of some of the basic notions for combinatory algebras.
In chapter 3 we present a construction method for extensional combinatory algebras based on probably the simplest known model construction, the graph model D_A. This construction is based on the technique of the extensional collapse.
In chapter 4 we modify this approach in order to construct nontotal extensional combinatorial algebras. We introduce the notion of a p-reflexive complete partial order and describe a construction method for such structions. The final section of chapter 4 comprises some properties of the models constructed in this way.
Chapter 5 deals with cardinality aspects of topological models; in particular, it is shown that non-total topological combinatorial algebras are uncountable.
In chapter 6 we show that every partial applicative structure can be embedded in an extensional topological model. We use the constructions from chapter 3 and 4.
The last and most extensive chapter deals with finite type structures within combinatorial algebras. The central theme here is finite-type extensionality, ie. extensionality on finite types. Well-known models are tested against this property. It is shown that most of the literature examples are ft-extensional regardless of their degree of global extensionality. To show that there is no connection between local and global extensionality, an extensional model is constructed that is not ft-extensional.