Modalities Through the Looking Glass: A study on coalgebraic modal logic and their applications
Raul Andres Leal
Abstract:
This thesis hovers over the interaction of coalgebras and modal
logics.
Intuitively, coalgebras are machines from the point of view of the
user. They arise from computer science as a promising mathematical
foundation for computer systems. Colagebras study different
state-based systems, where the set of states can be understood as a
black box to which one has limited access. For an intuitive
illustration of this, think of a coffee vending machine. Most people
do not really know what the inner mechanism of the machine is, or even
haven ever seen such mechanism. Nevertheless, they can use the machine
efficiently. Here we have an interaction with a system in the black
box perspective. The coffee machine is a coalgebra.
Modal languages provide an internal, local perspective on relational
structures. They origin in philosophy as the informal study of
modalities like "it is necessary that...", "it is possible that...",
"at some point in the future...". However, thanks to the so-called
relational semantics, modal logics have found their way to areas such
as linguistics, artificial intelligence, and computer science. This
versatility has helped to place modal languages as the appropriate
choice of languages to describe coalgebras. Moreover, nowadays, it is
also fair to say that modal logics are coalgebraic.
This thesis has two parts: Modalities in de Stone age and Coalgebraic
modal logics at work.
In the first part of this manuscript we investigate coalgebraic modal
logics. These logics have become one of the main currents of modal
logics for coalgebras. Coalgebraic modal logics bring uniformity to
the rising wave of modal logics in computer science and provide
generality to the interactions of coalgebras and modal logics. More
concretely, the structure of the first part is as follows: we first
introduce coalgebraic modal logics as a generalisation of basic modal
logic using so-called predicate liftings or concrete modalities. We
develop these modalities to introduce the so-called functorial
framework for coalgebraic modal logics. This accounts to give an
algebraic semantics of modal logics. We then use this perspective to
compare different coalgebraic modal logics by means of translations.
We devote special attention to the so-called Moss logic. We finish
this part with a representation theorem which states that each
coalgebraic modal logic within the functorial framework is an
axiomatization of a logic of predicate liftings.
In the second part of this manuscript we investigate how coalgebraic
modal logics can be used to study coalgebras. We work three case
studies. In the first case we investigate the use of logics for
coalgebras to build coalgebras. More concretely we study the relation
between final coalgebras and the Hennessy-Milener property. In the
second case we investigate how coalgebraic modal logics align with
so-called dynamic logics, dynamic logics are often used to reason
about programs. In the third place we study coalgebraic modal logics
to describe the ongoing behaviour of a state in a coalgebra. We focus
on logics of predicate liftings with fixpoint operators. We give a
game semantics and prove a bounded modal property for these logics.