Bisimulations and bisimulation games between Verbrugge models

Interpretability logic is a modal formalization of relative interpretability between first-order arithmetical theories. Verbrugge semantics is a generalization of Veltman semantics, the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. We study various notions of bisimulation between Verbrugge models and develop a new one, which we call w-bisimulation. We show that the new notion, while keeping the basic property that bisimilarity implies modal equivalence, is weak enough to allow the converse to hold in the finitary case. To do this, we develop and use an appropriate notion of bisimulation games between Verbrugge models.     

Model-theoretic Imaginaries and Coherent Sheaves

We show the equivalence of categories of model-theoretic imaginaries (of various kinds) with categories of “small” (finitely generated, finitely presented, coherent) functors. We do this first for certain locally finitely presented categories and then, by localising, for much more general “definable categories” (categories of models of coherent theories). We also investigate the corresponding notion of interpretation.     

Abstract Logics, Logic Maps, and Logic Homomorphisms

What is a logic? Which properties are preserved by maps between logics? What is the right notion for equivalence of logics? In order to give satisfactory answers we generalize and further develop the topological approach of [4] and present the foundations of a general theory of abstract logics which is based on the abstract concept of a theory. Each abstract logic determines a topology on the set of theories. We develop a theory of logic maps and show in what way they induce (continuous, open) functions on the corresponding topological spaces. We also establish connections to well-known notions such as translations of logics and the satisfaction axiom of institutions [5]. Logic homomorphisms are maps that behave in some sense like continuous functions and preserve more topological structure than logic maps in general. We introduce the notion of a logic isomorphism as a (not necessarily bijective) function on the sets of formulas that induces a homeomorphism between the respective topological spaces and gives rise to an equivalence relation on abstract logics. Therefore, we propose logic isomorphisms as an adequate and precise notion for equivalence of logics. Finally, we compare this concept with another recent proposal presented in [2]. This research was supported by the grant CNPq/FAPESB 350092/2006-0.     

Stream-based inconsistency measurement

Inconsistency measures have been proposed to assess the severity of inconsistencies in knowledge bases of classical logic in a quantitative way. In general, computing the value of inconsistency is a computationally hard task as it is based on the satisfiability problem which is itself NP-complete. In this work, we address the problem of measuring inconsistency in knowledge bases that are accessed in a stream of propositional formulæ. That is, the formulæ of a knowledge base cannot be accessed directly but only once through processing of the stream. This work is a first step towards practicable inconsistency measurement for applications such as Linked Open Data, where huge amounts of information is distributed across the web and a direct assessment of the quality or inconsistency of this information is infeasible due to its size. Here we discuss the problem of stream-based inconsistency measurement on classical logic, in order to make use of existing measures for classical logic. However, it turns out that inconsistency measures defined on the notion of minimal inconsistent subsets are usually not apt to be used in the streaming scenario. In order to address this issue, we adapt measures defined on paraconsistent logics and also present a novel inconsistency measure based on the notion of a hitting set. We conduct an extensive empirical analysis on the behavior of these different inconsistency measures in the streaming scenario, in terms of runtime, accuracy, and scalability. We conclude that for two of these measures, the stream-based variant of the new inconsistency measure and the stream-based variant of the contension inconsistency measure, large-scale inconsistency measurement in streaming scenarios is feasible.     

The two‐variable fragment with counting and equivalence

We consider the two‐variable fragment of first‐order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime ‐complete. We further show that the corresponding problems for two‐variable first‐order logic with counting and two equivalences are both undecidable.     

Weak Equivalence of Internal Categories

Weak equivalence is defined as equivalence in the bicategory of modules between internal categories. It is known that two categories are weakly equivalent if and only if their Cauchy completions are equivalent. We prove that this condition can be generalized to a suitable notion of intermediate category, stable under composition with weak equivalences. Applications to categorical Morita theory are given.     

Negation and Paraconsistent Logics

Does there exist any equivalence between the notions of inconsistency and consequence in paraconsistent logics as is present in the classical two valued logic? This is the key issue of this paper. Starting with a language where negation (?{\neg}) is the only connective, two sets of axioms for consequence and inconsistency of paraconsistent logics are presented. During this study two points have come out. The first one is that the notion of inconsistency of paraconsistent logics turns out to be a formula-dependent notion and the second one is that the characterization (i.e. equivalence) appears to be pertinent to a class of paraconsistent logics which have double negation property.     

Homotopy theory of spectral categories

We construct a Quillen model structure on the category of spectral categories, where the weak equivalences are the symmetric spectra analogue of the notion of equivalence of categories.     

Relativized Grothendieck topoi

In this paper we define a notion of relativization for higher order logic. We then show that there is a higher order theory of Grothendieck topoi such that all Grothendieck topoi relativizes to all models of set theory with choice.     

A model category structure on the category of simplicial categories

In this paper we put a cofibrantly generated model category structure on the category of small simplicial categories. The weak equivalences are a simplicial analogue of the notion of equivalence of categories.

     

On intuitionistic modal and tense logics and their classical companion logics: Topological semantics and bisimulations

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order (or partial-order) with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show that their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics.     

Crossed Semimodules and Schreier Internal Categories in the Category of Monoids

We introduce the notion of a Schreier internal category in the category of monoids and prove that the category of Schreier internal categories in the category of monoids is equivalent to the category of crossed semimodules. This extends a well-known equivalence of categories between the category of internal categories in the category of groups and the category of crossed modules.     

The bicategories of corings

To a B-coring and a (B,A)-bimodule that is finitely generated and projective as a right A-module an A-coring is associated. This new coring is termed a base ring extension of a coring by a module. We study how the properties of a bimodule such as separability and the Frobenius properties are reflected in the induced base ring extension coring. Any bimodule that is finitely generated and projective on one side, together with a map of corings over the same base ring, lead to the notion of a module-morphism, which extends the notion of a morphism of corings (over different base rings). A module-morphism of corings induces functors between the categories of comodules. These functors are termed pull-back and push-out functors, respectively, and thus relate categories of comodules of different corings. We study when the pull-back functor is fully faithful and when it is an equivalence. A generalised descent associated to a morphism of corings is introduced. We define a category of module-morphisms, and show that push-out functors are naturally isomorphic to each other if and only if the corresponding module-morphisms are mutually isomorphic. All these topics are studied within a unifying language of bicategories and the extensive use is made of interpretation of corings as comonads in the bicategory Bim of bimodules and module-morphisms as 1-cells in the associated bicategories of comonads in Bim.     

相似剩余格及其对应逻辑系统的完备性

引入了相似剩余格的概念,讨论了剩余格上相似算子和等价算子的关系,并得到了真值剩余格和相似剩余格相互转化的方法.其次,研究了相似剩余格上的相似滤子,利用相似滤子刻画了可表示的相似剩余格.最后,引入了相似剩余格对应的逻辑系统,证明了其完备性定理,并得到了其成为半线性逻辑的条件.     

Homomorphisms and chains of Kripke models

In this paper we define a suitable version of the notion of homomorphism for Kripke models of intuitionistic first-order logic and characterize theories that are preserved under images and also those that are preserved under inverse images of homomorphisms. Moreover, we define a notion of union of chain for Kripke models and define a class of formulas that is preserved in unions of chains. We also define similar classes of formulas and investigate their behavior in Kripke models. An application to intuitionistic first-order arithmetic is also given.     

Mixed Hodge structures and equivariant sheaves on the projective plane

We describe an equivalence of categories between the category of mixed Hodge structures and a category of equivariant vector bundles on a toric model of the complex projective plane which verify some semistability condition. We then apply this correspondence to define an invariant which generalizes the notion of R ‐split mixed Hodge structure and give calculations for the first group of cohomology of possibly non smooth or non‐complete curves of genus 0 and 1. Finally, we describe some extension groups of mixed Hodge structures in terms of equivariant extensions of coherent sheaves. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Observing,reporting, and deciding in networks of sentences

In prior work [7] we considered networks of agents who have knowledge bases in first order logic, and report facts to their neighbors that are in their common languages and are provable from their knowledge bases, in order to help a decider verify a single sentence. In report complete networks, the signatures of the agents and the links between agents are rich enough to verify any decider?s sentence that can be proved from the combined knowledge base. This paper introduces a more general setting where new observations may be added to knowledge bases and the decider must choose a sentence from a set of alternatives. We consider the question of when it is possible to prepare in advance a finite plan to generate reports within the network. We obtain conditions under which such a plan exists and is guaranteed to produce the right choice under any new observations.     

A note on equality in finite‐type arithmetic

We present a version of arithmetic in all finite types based on a systematic use of an internally definable notion of observational equivalence for dealing with equalities at higher types. For this system both intensional and extensional models are possible, the deduction theorem holds and the soundness of the Dialectica interpretation is provable inside the system itself.     

Cartesian Differential Categories as Skew Enriched Categories

We exhibit the cartesian differential categories of Blute, Cockett and Seely as a particular kind of enriched category. The base for the enrichment is the category of commutative monoids—or in a straightforward generalisation, the category of modules over a commutative rig k. However, the tensor product on this category is not the usual one, but rather a warping of it by a certain monoidal comonad Q. Thus the enrichment base is not a monoidal category in the usual sense, but rather a skew monoidal category in the sense of Szlachányi. Our first main result is that cartesian differential categories are the same as categories with finite products enriched over this skew monoidal base. The comonad Q involved is, in fact, an example of a differential modality. Differential modalities are a kind of comonad on a symmetric monoidal k-linear category with the characteristic feature that their co-Kleisli categories are cartesian differential categories. Using our first main result, we are able to prove our second one: that every small cartesian differential category admits a full, structure-preserving embedding into the cartesian differential category induced by a differential modality (in fact, a monoidal differential modality on a monoidal closed category—thus, a model of intuitionistic differential linear logic). This resolves an important open question in this area.

     

Preservation theorems for Kripke models

There are several ways for defining the notion submodel for Kripke models of intuitionistic first‐order logic. In our approach a Kripke model A is a submodel of a Kripke model B if they have the same frame and for each two corresponding worlds A^α and B^α of them, A^α is a subset of B^α and forcing of atomic formulas with parameters in the smaller one, in A and B, are the same. In this case, B is called an extension of A. We characterize theories that are preserved under taking submodels and also those that are preserved under taking extensions as universal and existential theories, respectively. We also study the notion elementary submodel defined in the same style and give some results concerning this notion. In particular, we prove that the relation between each two corresponding worlds of finite Kripke models A ≤ B is elementary extension (in the classical sense) (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)