Expressivity of Coalgebraic Modal Languages Raul Andres Leal Rodriguez Abstract: Through history logic has been used for several purposes, for example as foundation of mathematics or in philosophy to provide an controlled environment of argumentation. In this thesis we are interested in using logic to describe mathematical structures. For example, it is well know that algebraic logic can be used to describe algebraic structures. Birkhoff Theorem clarifies under what conditions a class of algebraic structures can be characterized using algebraic logic. The dual concept of algebraic structure is that of coalgebraic structure. In the last decade there has been a development of different logical languages to describe coalgebraic structures. There is no agreement in which of these language is the most appropriate to describe coalgebras. This disagreement is partially based on the fact that there is not much work comparing these languages. In this thesis we will do some steps on this direction comparing two languages to describe coalgebraic structures. Coalgebras and algebras are formally dual concepts, i.e. given a functor T, a coalgebra is a function \alpha : A -> TA and an algebra is a function \alpha : TA -> A. Peter Gumm claims that coalgebras as direct duals of algebras have been in scene for more than 30 years, but did not receive much attention primarily due to the lack of vital examples. The vital examples came from computer science. Various kind of transitions systems, automata and functional programming languages are naturally represented as coalgebraic structures. These new examples demonstrated that a better intuition to understand universal coalgebra is to conceive it as a general and uniform theory to describe dynamic systems. Our starting point is that of basic modal logic and Kripke structures, frames and models. It is well known that modal logic is an expressive language to talk about Kripke structures or relational structures. Using modal logic we can provide an internal local perspective on relational structures. Now Kripke frames and Kripke models can be naturally represented in coalgebraic terms. For example, a Kripke frame (A,R) is represented by a function R : A -> PA, where P is the covariant power set functor and R(s) is the the successors of s. Here, we can see that modal logic is a language to talk about coalgebraic structures. This immediately rises interesting questions. Are there other formal languages like basic modal logic for other coalgebras? Is the modal language an isolated language or is it an example of a more general concept? Since there are many languages to talk about coalgebras what is the relation between them? The first question can be answered through abstract model theory. A language for coalgebras is a set with a class of satisfaction relations. The satisfaction of a modal formula on some point of a Kripke frame can be seen as a process executed over some Kripke structure. Here, we can say that from the point of modal logic Kripke structures are dynamic systems, therefore coalgebras are a generalization of Kripke frames, but there is no natural interpretation of basic modal formulas over arbitrary coalgebras. Pattinson and Schroeder solved this problem showing that there is a direct generalization of modal logic, see Chapter 4 here, using the concept of relation lifting; we call those languages coalgebraic modal languages. These language can be uniformly defined for a large class of functors. Hence modal logic is a particular instance of a more general phenomenon. Historically, coalgebraic modal languages were not the first languages invented to talk about coalgebras in a uniform framework and as a generalization of modal logic. The first language with this features was invented by Lawerence S. Moss; we call this language Moss' language. The presence of at least two different languages to talk about coalgebras explain the third question. What is the relation between them? We have no general answer for this question. Out here we do answer the third question in the particular case of Moss' language and coalgebraic modal languages. To return to our starting point, it is usually claimed that in the particular case of the covariant power set functor, Moss' language and the coalgebraic modal language are equally expressive. Unfortunately in the literature used for this thesis, there is no much material explaining what it means for two languages to be equally expressive. This thesis will not provide such general theory. Instead we will compare Moss' language and coalgebraic modal languages at a semantical level and at a syntactical level. One way to define the expressiveness of a language is using its semantics. A language L1 is said to be more expressive than a language L2 if L1 can express differences between coalgebras that the language L2 cannot. Using this criterion, we will then show that Moss' language and coalgebraic modal languages are equally expressive. Another way to compare the expressiveness of two languages is trough translations. Using the notation from the previous paragraph, this means that each formula in the language L2 is translated into an equivalent formula in L1. Using this criterion, we will show that in the case of Kripke polynomial functors every predicate lifting can be translated into Moss' language. The structure of the thesis is as follows: In the proceeding chapter we introduce the formal context in which this thesis is located, we discuss some basics of category theory and universal coalgebra. We also establish the background related to languages and translations, including expressive languages. In Chapter 3 we define Moss' language, provide examples in the case of Kripke polynomial functors, and finally we show how to extend Moss' language with disjunctions and negations. In Chapter 4 we show how to generalize modal logic to coalgebraic modal languages, provide examples in the case of Kripke polynomial functors, and show, in an original work, that coalgebraic modal languages can be represented as initial algebras. With these preliminaries out of the way, we are ready to compare Moss' language and coalgebraic modal languages. In Chapter 5 we demonstrate that the existence of expressive languages is equivalent to the existence of a final object. We present a new elementary proof developed by the author and Clemens Kupke. Using this result, we define non constructive translations between Moss' Language and coalgebraic modal languages. In the final chapter, we refine such translations, defying constructive finitary translations for the particular case of Kripke polynomial functors.