The first six sections of this work were distributed as a set of notes in January 1989.As explained in Section 7, an unsatisfactory aspect of the subject was then noticed and that prevented me from producing a more finished product.But the editors of 7'heorrtical Computer Science convinced me to provide this more permanent form of what I had insisted on thinking of as a transient work.(The manuscript received, in this process.the benefit of a masterly referee.)

The authors consider the idea of treating a parametrized type as an arbitrary functor from some parametrizing category to a category of types, and giving elements semantics as natural transformations. They show that under reasonable hypotheses this is only possible when the parametrizing category is a groupoid. This suggests a semantics for a semiparametric form of polymorphism. They discuss the interpretation of this form of parametricity in a PER model, and show that it coincides with the ostensibly stronger form derived from dinaturality.>

A class of Partial Equivalence Relations (PERs) is described such that the resulting full subcategory of the realizability universe has the expected properties of a good category of CPOs; that is, it is a Cartesian closed category and every endomorphism has a canonical fixed point. Moreover, the reflection functor into the subcategory of strict maps (usually called the “lifting operation”) yields a good notion of “partial map,” a necessary condition if one wishes to maintain a connection between strict maps and partial maps. It is shown that all functors that arise in practice have canonical invariant objects; hence a host of domain equations are guaranteed to have solutions.

A setting called complete partial ordering (CPO) categories and the notion of dialgebra are described. Free dialgebras on CPO-categories are shown to be the same as minimal invariant objects. In the case that the bifunctor is independent of its contravariant variable (hence construable as a covariant functor), it is shown that minimal invariant objects serve simultaneously as initial algebras and final coalgebras. The reduction to inductive types is shown in a two-step process. First let T be a bifunctor contravariant in its first variable, convariant in the second. For each A it is possible to consider the convariant functor that sends X to TAX. If FA denotes a minimal invariant object of this covariant functor, one for each A, then F becomes a contrainvariant functor. It is shown that the minimal invariant objects of F are minimal invariant objects of the original bifunctor T. Secondly, let T be a contrainvariant functor. It is shown that the square of the functor (necessarily covariant) has the same minimal invariant objects.>

A search is conducted for a class of PERs (partial equivalence relations on the natural numbers) such that the resulting full subcategory has the expected properties of any good category of CPOs: it should be a CCC (Cartesian closed category) and every endomorphism should have a canonical fixed point. Moreover the reflection functor (usually called the lifting operation) should yield a good notion of partial map. The following topics are discussed: conventions, partial-map classifiers, ExPERS, ExPERS as domains, reflectivity of strict maps, multicorreflectivity of strict maps, the extensional natural numbers, domain equations, and intrinsic descriptions.>

A semantic condition necessary for the parametricity of polymorphic functions is considered. One of its instances is the stability condition for elements of variable type in the coherent domains semantics. A larger setting is presented that does not use retract pairs and keeps intact a basic feature of a certain function-type constructor. Polymorphic lambda terms are semantically parametric because of normalization.>

It is one thing to say that the axiom of choice implies that everything may be well-ordered.It is quite another thing to say that if a set has a choice function then it has a well-ordering.Even in the classical setting the difference shows in the length of proof: using the (global) axiom of choice one may quickly apply a Zorn's lemma argument to the family of partial well-orderings on a set to obtain an entire well-ordering.The difference is clearest in the intuitionistic setting, so clear that a number of us have been searching for a counterexample.The main purpose of the following is to end that search.