All realizability is relative

Abstract

We introduce a category of basic combinatorial objects, encompassing PCAs and locales. Such a basic combinatorial object is to be thought of as a pre-realizability notion. To each such object we can associate an indexed preorder, generalizing the construction of triposes for various notions of realizability. There are two main results: first, the characterization of triposes which arise in this way, in terms of ordered PCAs equipped with a filter. This will include “Effective Topos-like” triposes, but also the triposes for relative, modified and extensional realizability and the dialectica tripos. Localic triposes can be identified as those arising from ordered PCAs with a trivial filter. Second, we give a classification of geometric morphisms between such triposes in terms of maps of the underlying combinatorial objects. Altogether, this shows that the category of ordered PCAs with non-trivial filters serves as a framework for studying a wide variety of realizability notions.