A Categorical Account of Composition Methods in Logic: Prelimenariesby@escholar

A Categorical Account of Composition Methods in Logic: Prelimenaries

tldt arrow

Too Long; Didn't Read

In this paper, we present a categorical theory of the composition methods in finite model theory – a key technique enabling modular reasoning.
featured image - A Categorical Account of
Composition Methods in Logic: Prelimenaries
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture

This paper is available on arxiv under CC BY-SA 4.0 DEED license.


(1) Tomáš Jakl, Czech Academy of Sciences and Czech Technical University;

(2) Dan Marsden, School of Computer Science University of Nottingham;

(3) Nihil Shah, Department of Computer Science University of Oxford.


A. Categories of Relational Structures

We assume the basic definitions of category theory, including categories, functors and natural transformations, as can be found in any standard introduction such as [29] or [30]. Background on comonads, and any less standard material is introduced as needed.

troduced as needed. A relational signature σ is a set of relation symbols, each with an associated strictly positive natural number arity. A σstructure A consists of a universe set, also denoted A, and for each relation symbol R ∈ σ of arity n, an n-ary relation RA on A. A morphism of σ-structures f : A → B is a function of type A → B, preserving relations, in the sense that for n-ary R ∈ σ

For a fixed σ, σ-structures and their morphisms form our main category of interest R(σ). We will also have need of the category of pointed relational structures R∗(σ). Here the objects (A, a) are a σ-structure A with a distinguished element a ∈ A. The morphisms are σ-structure morphisms that also preserve the distinguished element.

B. Comonads

The intuition for each of these comonads is that they encode the moves within one structure during the corresponding model comparison game. We shall introduce their mathematical properties as needed in later sections. See [11] for detailed discussions of all three comonads.