Comparing Expressiveness of Logics Defined within Different Classes of Models

An analysis of some formal conditions

Abstrakt

It is possible to understand the expressive power of a logic as issuing from its capacity to express properties of its models. There are some ways to formally capture whether a property of models is expressible, among them is one based on the notion of definability, and one based on the notion of discrimination. If the logics to be compared are defined within the same class of models, one can employ the notions of definability and discrimination directly to obtain formal conditions for relative expressiveness. This paper studies generalizations of these formal conditions to cases where the compared logics are defined within different classes of models. There have been proposed in the literature formal conditions of two main kinds: with forward and with backward model-mappings. It is shown that none of them is adequate, despite their initial reasonableness. Moreover, we argue that general and reasonable formal conditions for relative expressiveness involving forward mappings are not likely to be found, given that they turn out to be highly dependent on specific features of the compared logics. On the other hand, it will be argued that there is a reasonable formal condition involving backward model-mappings.