1,721,007 research outputs found
Topological Structure of Diagonalizable Algebras and Corresponding Logical Properties of Theories
No full textThis paper studies the topological duality between diagonalizable algebras and bi-topological spaces. In particular, the correspondence between algebraic properties of a diagonalizable algebra and topological properties of its dual space is investigated. Since the main example of a diagonalizable algebra is the Lindenbaum algebra of an r.e. theory extending Peano Arithmetic, endowed with an operator defined by means of the provability predicate of the theory, this duality gives the possibility to study arithmetical properties of theories from a topological point of view. We find topological characterization of -sound theories and of sentences that are -conservative over such a theory
Cayley graph of virtualy free groups
No full textA geometrical characterization of the Cayley graphs of certain presentations of virtually free and plain groups is given
Interpolation in non classical logic
No full textWe discuss the interpolation property on some important families of non classical logics, such as intuitionistic, modal, fuzzy, and linear logics. A special paragraph is devoted to a generalization of the interpolation property, uniform interpolation
Characterizing interpolation pairs in infinitary graded logics
No full textIn this paper the problem of interpolation for the family of countable infinitary graded modal logics is considered. It is well known that interpolation fails in general for these logics and it is then natural to ask for a semantical characterization (stronger than entailment) of pairs of graded formulae having an interpolant. This is obtained using the notion of entailment along elementary equivalence. More precisely, we prove that if L is a graded modal logic then a pair (φ, ψ) of graded formulae in L have an interpolant in L if, and only if, φ entails ψ along elementary equivalence with respect to L. This characterization is obtained by adapting to graded modal logics the method of consistency property modulo bisimulation, which was previously used in Infinitary Logic and Infinitary Modal Logic. In the case of full Countable Infinitary Graded Modal Logic we improve this result and show that this logic enjoys Craig interpolation. This is done using a characterization of graded bisimulation between models via isomorphism of their unravellings
Uniform interpolation, bisimulation quantifiers and fixed points
No full textIn this paper we consider some basic questions regarding the extensions of modal logics with bisimulation quantifiers. In particular, we consider the relation between bisimualtion quantifiers and uniform interpolation for modal logic and the μ-calculus. We first consider these questions over the whole class of frames, and then we restrict to specific classes, where we see that the results obtained before can be easily falsified. Finally, we introduce classes of frames where we found the same good behaviour than in the whole class of frames. The results presented in this paper have been obtained in collaboration with other authors during the last years; in alphabetical order: Tim French, Marco Hollenberg, and Giacomo Lenzi
On Non-Well-founded Multisets: Scott Collapse in the Multiworld, in Liber Amicorum for the Fiftieth Birthday of J. F. A. K. van Benthem
No full text
Bisimulation quantifiers and uniform interpolation for guarded first order logic
Full text linkThe idea that the good model-theoretic and algorithmic properties of Modal Logics are due to the guarded nature of their quantification was put forward by Andreka, van Benthem and Nemeti in a series of papers in the 1990s, exploiting the satisfiability problem, the tree model property, and other similar properties of the Guarded Fragment of First Order Logic(GF).
Since then, further work on the Guarded Fragment has been done by various authors, in some cases reinforcing this idea, in some others not. At least at first sight, Craig interpolation is on the negative side: there are implications in GF without an interpolant in GF, while Modal Logic (and even the μ-calculus, a powerful extension of Modal Logic) enjoys a much stronger form of interpolation, the uniform one, in which the interpolant of a valid implication not only exists, but only depends on the antecedent and on the common language of antecedent and consequent. However, Hoogland and Marx proved that Craig interpolation is restored in GFif we consider the modal character of GFwith more attention, that is, if relations appearing on guards are viewed as “modalities” and the rest as “propositions”, and only the latter enter in the common language. In this paper we strengthen this result by showing that GF enjoys a Modal Uniform Interpolation Theorem (in the sense of Hoogland and Marx)
- …
