A relative PCF-definability result for strongly stable functions and some corollaries (Extended abstract)⋆ ⋆The results presented in this extended abstract have already been published in Information and Computation, under the same title. From this original article [10], we have kept all the informal discussions, the statements of the main results as well as those of the intermediate lemmas, but most proofs have been suppressed.

AbstractWe prove that, in the hierarchy of simple types based on the type of natural numbers, any finite strongly stable function is equal to the application of the semantics of a PCF-definable functional to some strongly stable (generally not PCF-definable) functionals of type two. Applying a logical relation technique, we derive from this result that the strongly stable model of PCF is the extensional collapse of its sequential algorithms model