Truth, Logic and Invariance

In the spirit of Klein's Erlanger program logical notions have been characterized as the invariant of some suitably motivated similarity relations S over structures. Not every authors agree on a choice of a similarity relation (e.g., Tarski [3], Feferman [2], Bonnay [1]) but one might argue that any plausible candidate should abide by a constraint of closure under definability: every operator which is definable in a language L whose logical constants are interpreted by S-invariant operators should be S-invariant. If L is a logic, being generated by a similarity relation closed under definability amounts to a kind of functional completeness of L with respect to a target notion of logicality. On the other hand we can define alethic extensions of a given model-theoretic logic L as the logics that one may obtain from L by adding to it the expressive power of an interpreted Tarskian truth predicate. We say that a logic L is truth-complete if every class of structures which is elementary (i.e., definable by one sentence) in an alethic extension of L is elementary in L. Eventually, we prove the following: a logic is truth complete if and only if it is generated by a similarity relation which is closed under definability