### Jonas Frey, Basic relational objects and partial combinatory algebras

#### Schedule

- Feb. 16, 2012, 16:15 - 17:00

#### Abstract

Categorical logic attempts to understand realizability constructions by asso- ciating ﬁbred preorders (functors of type Setop → Preord, e.g. triposes or more general hyperdoctrines) to them which abstract their essential features. These ﬁbred preorders can then be analyzed using various tools and constructions such as categories of partial equivalence relations, assemblies and exact completions. A special class of of ﬁbred preorders is given by those which are represented by ordinary preorders, i.e. are of the form Set(−, D) for a preorder D. The 2-category of representable ﬁbred preorders (being equivalent to the 2-category of preorders and monotone functions) and its relation to categorical logic via presheaf and sheaf constructions is fairly well understood, but the 2-category of general ﬁbred preorders is more diﬃcult to handle. To overcome these diﬃculties, we introduce basic relational objects (BROs), which are representations of ﬁbred preorders that generalize (and in our opinion simplify) Hofstra’s basic combinatory objects [1]. The 2-category BRO of BROs, which is equivalent to a full sub-2-category of the 2-category of ﬁbred posets, has good closure properties – in particular it has an involution (−)op : BROco → BRO corresponding to ﬁbrewise (−)op on the level of ﬁbred preorders, which allows us to dualize Hofstra’s existential quantiﬁcation monad D to obtain a monad which classiﬁes universal quantiﬁcation. Moreover, BRO is suﬃciently large to contain all triposes. We argue that BROs provide a good conceptual framework to understand and relate the constructions of exact completion, assemblies and partial equiv- alence relations, and to understand the relation to the (pre)sheaf theoretic con- structions in the representable case. Furthermore, the framework of basic relational objects permits to give an extensional characterization of realizability over partial combinatory algebras.

**References**

[1] P.J.W. Hofstra. All realizability is relative. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 141, pages 239–264. Cambridge Univ Press, 2006.