In the study of modal and nonclassical logics, translations have frequently been employed as a way of measuring the inferential capabilities of a logic. It is sometimes claimed that two logics are “notational variants” if they are translationally equivalent. However, we will show that this cannot be quite right, since first-order logic and propositional logic are translationally equivalent. Others have claimed that for two logics to be notational variants, they must at least be compositionally intertranslatable. The definition of compositionality these (...) accounts use, however, is too strong, as the standard translation from modal logic to first-order logic is not compositional in this sense. In light of this, we will explore a weaker version of this notion that we will call schematicity and show that there is no schematic translation either from first-order logic to propositional logic or from intuitionistic logic to classical logic. (shrink)

When embedding data are used to argue against semantic theory A and in favor of semantic theory B, it is important to ask whether A could make sense of those data. It is possible to ask that question on a case-by-case basis. But suppose we could show that A can make sense of all the embedding data which B can possibly make sense of. This would, on the one hand, undermine arguments in favor of B over A on the basis (...) of embedding data. And, provided that the converse does not hold—that is, that A can make sense of strictly more embedding data than B can—it would also show that there is a precise sense in which B is more constrained than A, yielding a pro tanto simplicity-based consideration in favor of B. In this paper I develop tools which allow us to make comparisons of this kind, which I call comparisons of potential expressive power. I motivate the development of these tools by way of exploration of the recent debate about epistemic modals. Prominent theories which have been developed in response to embedding data turn out to be strictly less expressive than the standard relational theory, a fact which necessitates a reorientation in how to think about the choice between these theories. (shrink)

Proof-theoretical notions and techniques, developed on the basis of sentential/symbolic representations of formal proofs, are applied to Euler diagrams. A translation of an Euler diagrammatic system into a natural deduction system is given, and the soundness and faithfulness of the translation are proved. Some consequences of the translation are discussed in view of the notion of free ride, which is mainly discussed in the literature of cognitive science as an account of inferential efficacy of diagrams. The translation enables us to (...) formalize and analyze free ride in terms of proof theory. The notion of normal form of Euler diagrammatic proofs is investigated, and a normalization theorem is proved. Some consequences of the theorem are further discussed: in particular, an analysis of the structure of normal diagrammatic proofs; a diagrammatic counterpart of the usual subformula property; and a characterization of diagrammatic proofs compared with natural deduction proofs. (shrink)

Saturated models constitute one of the powerful methods of conventional model theory, with many applications. Here we develop a categorical abstract model theoretic approach to saturated models within the theory of institutions. The most important consequence is that the method of saturated models becomes thus available to a multitude of logical systems from logic or from computing science. In this paper we define the concept of saturated model at an abstract institution-independent level and develop the fundamental existence and uniqueness theorems. (...) As an application we prove a general institution-independent version of the Keisler–Shelah isomorphism theorem “any two elementarily equivalent models have isomorphic ultrapowers” (assuming Generalized Continuum Hypothesis). (shrink)

This paper addresses questions of universality related to ontological engineering, namely aims at substantiating (negative) answers to the following three basic questions: (i) Is there a ‘universal ontology’?, (ii) Is there a ‘universal formal ontology language’?, and (iii) Is there a universally applicable ‘mode of reasoning’ for formal ontologies? To support our answers in a principled way, we present a general framework for the design of formal ontologies resting on two main principles: firstly, we endorse Rudolf Carnap’s principle of logical (...) tolerance by giving central stage to the concept of logical heterogeneity, i.e. the use of a plurality of logical languages within one ontology design. Secondly, to structure and combine heterogeneous ontologies in a semantically well-founded way, we base our work on abstract model theory in the form of institutional semantics, as forcefully put forward by Joseph Goguen and Rod Burstall. In particular, we employ the structuring mechanisms of the heterogeneous algebraic specification language HetCasl for defining a general concept of heterogeneous, distributed, highly modular and structured ontologies, called hyperontologies. Moreover, we distinguish, on a structural and semantic level, several different kinds of combining and aligning heterogeneous ontologies, namely integration, connection, and refinement. We show how the notion of heterogeneous refinement can be used to provide both a general notion of sub-ontology as well as a notion of heterogeneous equivalence of ontologies, and finally sketch how different modes of reasoning over ontologies are related to these different structuring aspects. (shrink)

Composition-nominative logics are program-oriented logics. They are based on algebras of partial predicates which do not have fixed arity. The aim of this work is to present CNL as institutions. Homomorphisms of first-order CNL are introduced, satisfaction condition is proved. Relations with institutions for classical first-order logic are considered. Directions for further investigation are outlined.

In this paper we study interpretations and equivalences of propositional deductive systems by using a quantale-theoretic approach introduced by Galatos and Tsinakis. Our aim is to provide a general order-theoretic framework which is able to describe and characterize both strong and weak forms of interpretations among propositional deductive systems also in the cases where the systems have different underlying languages.

After observing that the truth conditions of connectives of non–classical logics are generally defined in terms of formulas of first–order logic, we introduce ‘protologics’, a class of logics whose connectives are defined by arbitrary first–order formulas. Then, we introduce atomic and molecular logics, which are two subclasses of protologics that generalize our gaggle logics and which behave particularly well from a theoretical point of view. We also study and introduce a notion of equi-expressivity between two logics based on different classes (...) of models. We prove that, according to that notion, every pure predicate logic with \ variables and constants is as expressive as a predicate atomic logic, some sort of atomic logic. Then, we prove that the class of protologics is equally expressive as the class of molecular logics. That formally supports our claim that atomic and molecular logics are somehow ‘universal’. Finally, we identify a subclass of molecular logics that we call predicate molecular logics and which constitutes its representative core: every molecular logic is as expressive as a predicate molecular logic. (shrink)

We study the notion of conservative translation between logics introduced by (Feitosa & D’Ottaviano2001). We show that classical propositional logic (CPC) is universal in the sense that every finitary consequence relation over a countable set of formulas can be conservatively translated into CPC. The translation is computable if the consequence relation is decidable. More generally, we show that one can take instead of CPC a broad class of logics (extensions of a certain fragment of full Lambek calculus FL) including most (...) nonclassical logics studied in the literature, hence in a sense, (almost) any two reasonable deductive systems can be conservatively translated into each other. We also provide some counterexamples, in particular the paraconsistent logic LP is not universal. (shrink)

In Computer Science stepwise refinement of algebraic specifications is a well-known formal methodology for rigorous program development. This paper illustrates how techniques from Algebraic Logic, in particular that of interpretation, understood as a multifunction that preserves and reflects logical consequence, capture a number of relevant transformations in the context of software design, reuse, and adaptation, difficult to deal with in classical approaches. Examples include data encapsulation and the decomposition of operations into atomic transactions. But if interpretations open such a new (...) research avenue in program refinement, (conceptual) tools are needed to reason about them. In this line, the paper’s main contribution is a study of the correspondence between logical interpretations and morphisms of a particular kind of coalgebras. This opens way to the use of coalgebraic constructions, such as simulation and bisimulation, in the study of interpretations between (abstract) logics. (shrink)