Arboreal coreflections

Abstract

Arboreal categories are categories of objects with an intrinsic, tree-like process structure giving rise to a bisimilarity relation between objects. This relation can then be transported along an adjunction into an “extensional” category, whose objects are usually relational structures. In this way, the main examples of these so-called arboreal adjunctions recover logical equivalence for various fragments of infinitary first-order logic. This abstract framework provides a solid foundation for game comonads and has been used to obtain extensions and variations of substantial resource-sensitive model-theoretic results such as Rossman’s equirank preservation theorem. However, a key open question is whether we can systematically chart the landscape of the correspondence between logics and arboreal adjunctions.
In this talk, we explore this landscape by focusing on coreflective arboreal adjunctions. As is well known, the theory of (co)monads simplifies greatly in the idempotent case and, accordingly, known idempotent game comonads correspond to variants of basic modal logic, which sit on the lower end of the expressive power spectrum. After reviewing the definition of arboreal categories, we will introduce the concept of a “seed”: a full subcategory of structures generating an arboreal coreflective subcategory via colimit. We will explain some results that help us identify seeds and hence move towards a potential classification theorem. In particular, we will leverage density comonads to characterize coreflective subcategories without explicitly constructing the coreflector. Finally, we will show some examples of arboreal categories that can be obtained employing our results.