Truth-as-simulation : towards a coalgebraic perspective on logic and games
Building on the work of L. Moss on coalgebraic logic, I study in a general setting a class of infinitary modal logics for F-coalgebras, designed to capture simulation and bisimulation. For a notion of coalgebraic simulation, I use the work of A. Thijs on modelling simulation in terms of relators (extensions of SET-functors along some family of preoders): simulation is the analogue for relators of the notion of bisimulation for functors. I prove the logics introduced here can indeed capture coalgebraic simulation and bisimulation. Moreover, one can characterize any given coalgebra up to simulation (and, in certain conditions, up to bisimulation) by a single sentence. An interesting feature of this logics is that their notion of truth or satisfaction can be understood as a simulation relation itself, but with respect to a (relator associated to a) richer functor; moreover, truth is the largest simulation, i.e. the similarity relation between states of the coalgebra and elements of the language. This sheds a new perspective on the classical preservation and characterizability results, and also on logic games. The two kinds of games normally used in logic (``truth games'' to define the semantics dynamically, and ``similarity games'' between two structures) are seen to be the same kind of game at the level of coalgebras: simulation games.
|Mathematical Logic (acm F.4.1), Semantics of Programming Languages (acm F.3.2), Simulation Theory (acm I.6.1)|
|Software Engineering [SEN]|
Baltag, A. (1999). Truth-as-simulation : towards a coalgebraic perspective on logic and games. Software Engineering [SEN]. CWI.