Stalnaker, 169–199 2006) introduced a combined epistemic-doxastic logic that can formally express a strong concept of belief, a concept of belief as ‘subjective certainty’. In this paper, we provide a topological semantics for belief, in particular, for Stalnaker’s notion of belief defined as ‘epistemic possibility of knowledge’, in terms of the closure of the interior operator on extremally disconnected spaces. This semantics extends the standard topological interpretation of knowledge with a new topological semantics for belief. We prove that the belief (...) logic KD45 is sound and complete with respect to the class of extremally disconnected spaces and we compare our approach to a different topological setting in which belief is interpreted in terms of the derived set operator. We also study belief revision as well as belief dynamics by providing a topological semantics for conditional belief and belief update modalities, respectively. Our setting based on extremally disconnected spaces, however, encounters problems when extended with dynamic updates. We then propose a solution consisting in interpreting belief in a similar way based on hereditarily extremally disconnected spaces, and axiomatize the belief logic of hereditarily extremally disconnected spaces. Finally, we provide a complete axiomatization of the logic of conditional belief and knowledge, as well as a complete axiomatization of the corresponding dynamic logic. (shrink)

This paper explores a new language of neighbourhood structures where existential information can be given about what kind of worlds occur in a neighbourhood of a current world. The resulting system of ‘instantial neighbourhood logic’ INL has a nontrivial mix of features from relational semantics and from neighbourhood semantics. We explore some basic model-theoretic behavior, including a matching notion of bisimulation, and give a complete axiom system for which we prove completeness by a new normal form technique. In addition, we (...) relate INL to other modal logics by means of translations, and determine its precise SAT complexity. Finally, we discuss proof-theoretic fine-structure of INL in terms of semantic tableaux and some expressive fine-structure in terms of fragments, while discussing concrete illustrations of the instantial neighborhood language in topological spaces, in games with powers for players construed in a new way, as well as in dynamic logics of acquiring or deleting evidence. We conclude with some coalgebraic perspectives on what is achieved in this paper. Many of these final themes suggest follow-up work of independent interest. (shrink)

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

In this article, we develop a bimodal perspective on possibility semantics, a framework allowing partiality of states that provides an alternative modelling for classical propositional and modal logics. In particular, we define a full and faithful translation of the basic modal logic K over possibility models into a bimodal logic of partial functions over partial orders, and we show how to modulate this analysis by varying across logics and model classes that have independent topological motivations. This relates the two realms (...) under comparison both semantically and syntactically at the level of derivations. Moreover, our analysis clarifies the interplay between the complexity of translations and axiomatizations of the corresponding logics: adding axioms to the target bimodal logic simplifies translations, or vice versa, complex translations can simplify frame conditions. We also investigate a transfer of first-order correspondence theory between possibility semantics and its bimodal counterpart. Finally, we discuss the conceptual trade-off between giving translations and giving new semantics for logical systems, and we identify a number of further research directions to which our analysis gives rise. (shrink)

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

We develop the theory of Krull dimension forS4-algebras and Heyting algebras. This leads to the concept of modal Krull dimension for topological spaces. We compare modal Krull dimension to other well-known dimension functions, and show that it can detect differences between topological spaces that Krull dimension is unable to detect. We prove that for aT1-space to have a finite modal Krull dimension can be described by an appropriate generalization of the well-known concept of a nodec space. This, in turn, can (...) be described by modal formulaszemnwhich generalize the well-known Zeman formulazem. We show that the modal logicS4.Zn:=S4+ zemnis the basic modal logic ofT1-spaces of modal Krull dimension ≤n, and we construct a countable dense-in-itselfω-resolvable Tychonoff spaceZnof modal Krull dimensionnsuch thatS4.Znis complete with respect toZn. This yields a version of the McKinsey-Tarski theorem forS4.Zn. We also show that no logic in the interval [S4n+1S4.Zn) is complete with respect to any class ofT1-spaces. (shrink)

We propose a new perspective on logics of computation by combining instantial neighborhood logic \ with bisimulation safe operations adapted from \. \ is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve invariance for (...) instantial neighborhood bisimulations, the appropriate bisimulation concept for \. We also prove that our extended logic \ is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for \, and establish its finite model property and decidability. (shrink)

We introduce new algebraic and topological semantics for inquisitive logic. The algebraic semantics is based on special Heyting algebras, which we call inquisitive algebras, with propositional valuations ranging over only the ¬¬-fixpoints of the algebra. We show how inquisitive algebras arise from Boolean algebras: for a given Boolean algebra B, we define its inquisitive extension H(B) and prove that H(B) is the unique inquisitive algebra having B as its algebra of ¬¬-fixpoints. We also show that inquisitive algebras determine Medvedev’s logic (...) of finite problems. In addition to the algebraic characterization of H(B), we give a topological characterization of H(B) in terms of the recently introduced choice-free duality for Boolean algebras using so-called upper Vietoris spaces (UV-spaces). In particular, while a Boolean algebra B is realized as the Boolean algebra of compact regular open elements of a UV-space dual to B, we show that H(B) is realized as the algebra of compact open elements of this space. This connection yields a new topological semantics for inquisitive logic. (shrink)

The variety of Heyting algebras has two well-behaved locally finite reducts, the variety of bounded distributive lattices and the variety of implicative semilattices. The variety of bounded distributive lattices is generated by the →-free reducts of Heyting algebras, while the variety of implicative semilattices is generated by the ∨-free reducts. Each of these reducts gives rise to canonical formulas that generalize Jankov formulas and provide an axiomatization of all superintuitionistic logics. The ∨-free reducts of Heyting algebras give rise to the (...) -canonical formulas that we studied in an earlier work. Here we introduce the -canonical formulas, which are obtained from the study of the →-free reducts of Heyting algebras. We prove that every si-logic is axiomatizable by -canonical formulas. We also discuss the similarities and differences between these two kinds of canonical formulas. One of the main ingredients of these formulas is a designated subset D of pairs of elements of a finite subdirectly irreducible Heyting algebra A. When D=A2, we show that the -canonical formula of A is equivalent to the Jankov formula of A. On the other hand, when D=∅, the -canonical formulas produce a new class of si-logics we term stable si-logics. We prove that there are continuum many stable si-logics and that all stable si-logics have the finite model property. We also compare stable si-logics to splitting and subframe si-logics. (shrink)

This article provides an algebraic study of the propositional system $\mathtt {InqB}$ of inquisitive logic. We also investigate the wider class of $\mathtt {DNA}$ -logics, which are negative variants of intermediate logics, and the corresponding algebraic structures, $\mathtt {DNA}$ -varieties. We prove that the lattice of $\mathtt {DNA}$ -logics is dually isomorphic to the lattice of $\mathtt {DNA}$ -varieties. We characterise maximal and minimal intermediate logics with the same negative variant, and we prove a suitable version of Birkhoff’s classic variety (...) theorems. We also introduce locally finite $\mathtt {DNA}$ -varieties and show that these varieties are axiomatised by the analogues of Jankov formulas. Finally, we prove that the lattice of extensions of $\mathtt {InqB}$ is dually isomorphic to the ordinal $\omega +1$ and give an axiomatisation of these logics via Jankov $\mathtt {DNA}$ -formulas. This shows that these extensions coincide with the so-called inquisitive hierarchy of [9].1. (shrink)

We propose a new perspective on logics of computation by combining instantial neighborhood logic $$\mathsf {INL}$$ INL with bisimulation safe operations adapted from $$\mathsf {PDL}$$ PDL. $$\mathsf {INL}$$ INL is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial (...) neighborhood semantics to preserve invariance for instantial neighborhood bisimulations, the appropriate bisimulation concept for $$\mathsf {INL}$$ INL. We also prove that our extended logic $$\mathsf {IPDL}$$ IPDL is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for $$\mathsf {IPDL}$$ IPDL, and establish its finite model property and decidability. (shrink)

The standard topological representation of a Boolean algebra via the clopen sets of a Stone space requires a nonconstructive choice principle, equivalent to the Boolean Prime Ideal Theorem. In this article, we describe a choice-free topological representation of Boolean algebras. This representation uses a subclass of the spectral spaces that Stone used in his representation of distributive lattices via compact open sets. It also takes advantage of Tarski’s observation that the regular open sets of any topological space form a Boolean (...) algebra. We prove without choice principles that any Boolean algebra arises from a special spectral space X via the compact regular open sets of X; these sets may also be described as those that are both compact open in X and regular open in the upset topology of the specialization order of X, allowing one to apply to an arbitrary Boolean algebra simple reasoning about regular opens of a separative poset. Our representation is therefore a mix of Stone and Tarski, with the two connected by Vietoris: the relevant spectral spaces also arise as the hyperspace of nonempty closed sets of a Stone space endowed with the upper Vietoris topology. This connection makes clear the relation between our point-set topological approach to choice-free Stone duality, which may be called the hyperspace approach, and a point-free approach to choice-free Stone duality using Stone locales. Unlike Stone’s representation of Boolean algebras via Stone spaces, our choice-free topological representation of Boolean algebras does not show that every Boolean algebra can be represented as a field of sets; but like Stone’s representation, it provides the benefit of a topological perspective on Boolean algebras, only now without choice. In addition to representation, we establish a choice-free dual equivalence between the category of Boolean algebras with Boolean homomorphisms and a subcategory of the category of spectral spaces with spectral maps. We show how this duality can be used to prove some basic facts about Boolean algebras. (shrink)

We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.

We introduce relativized modal algebra homomorphisms and show that the category of modal algebras and relativized modal algebra homomorphisms is dually equivalent to the category of modal spaces and partial continuous p-morphisms, thus extending the standard duality between the category of modal algebras and modal algebra homomorphisms and the category of modal spaces and continuous p-morphisms. In the transitive case, this yields an algebraic characterization of Zakharyaschev’s subreductions, cofinal subreductions, dense subreductions, and the closed domain condition. As a consequence, we (...) give an algebraic description of canonical, subframe, and cofinal subframe formulas, and provide a new algebraic proof of Zakharyaschev’s theorem that each logic over K4 is axiomatizable by canonical formulas. (shrink)

In this paper we define the notion of frame based formulas. We show that the well-known examples of formulas arising from a finite frame, such as the Jankov-de Jongh formulas, subframe formulas and cofinal subframe formulas, are all particular cases of the frame based formulas. We give a criterion for an intermediate logic to be axiomatizable by frame based formulas and use this criterion to obtain a simple proof that every locally tabular intermediate logic is axiomatizable by Jankov-de Jongh formulas. (...) We also show that not every intermediate logic is axiomatizable by frame based formulas. (shrink)

In 1995 Visser, van Benthem, de Jongh, and Renardel de Lavalette introduced NNIL-formulas, showing that these are exactly the formulas preserved under taking submodels of Kripke models. In this article we show that NNIL-formulas are up to frame equivalence the formulas preserved under taking subframes of frames, that NNIL-formulas are subframe formulas, and that subframe logics can be axiomatized by NNIL-formulas. We also define a new syntactic class of ONNILLI-formulas. We show that these are the formulas preserved in monotonic images (...) of frames and that ONNILLI-formulas are stable formulas as introduced by Bezhanishvili and Bezhanishvili in 2013. Thus, ONNILLI is a syntactically defined set of formulas axiomatizing all stable logics. This resolves a problem left open in 2013. (shrink)

We generalize the theory of canonical formulas for K4, the logic of transitive frames, to wK4, the logic of weakly transitive frames. Our main result establishes that each logic over wK4 is axiomatizable by canonical formulas, thus generalizing Zakharyaschev’s theorem for logics over K4. The key new ingredients include the concepts of transitive and strongly cofinal subframes of weakly transitive spaces. This yields, along with the standard notions of subframe and cofinal subframe logics, the new notions of transitive subframe and (...) strongly cofinal subframe logics over wK4. We obtain axiomatizations of all four kinds of subframe logics over wK4. We conclude by giving a number of examples of different kinds of subframe logics over wK4. (shrink)

We generalize the \}\)-canonical formulas to \}\)-canonical rules, and prove that each intuitionistic multi-conclusion consequence relation is axiomatizable by \}\)-canonical rules. This yields a convenient characterization of stable superintuitionistic logics. The \}\)-canonical formulas are analogues of the \}\)-canonical formulas, which are the algebraic counterpart of Zakharyaschev’s canonical formulas for superintuitionistic logics. Consequently, stable si-logics are analogues of subframe si-logics. We introduce cofinal stable intuitionistic multi-conclusion consequence relations and cofinal stable si-logics, thus answering the question of what the analogues of cofinal (...) subframe logics should be. This is done by utilizing the \}\)-reduct of Heyting algebras. We prove that every cofinal stable si-logic has the finite model property, and that there are continuum many cofinal stable si-logics that are not stable. We conclude with several examples showing the similarities and differences between the classes of stable, cofinal stable, subframe, and cofinal subframe si-logics. (shrink)

We show that every proper normal extension of the bi-modal system S5 2 has the poly-size model property. In fact, to every proper normal extension L of S5 2 corresponds a natural number b(L) - the bound of L. For every L, there exists a polynomial P(·) of degree b(L) + 1 such that every L-consistent formula is satisfiable on an L-frame whose universe is bounded by P(||), where || denotes the number of subformulas of . It is shown that (...) this bound is optimal. (shrink)

We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.

We generalize the notion of a monadic algebra to that of a pseudomonadic algebra. In the same way as monadic algebras serve as algebraic models of epistemic modal system S5, pseudomonadic algebras serve as algebraic models of doxastic modal system KD45. The main results of the paper are: Characterization of subdirectly irreducible and simple pseudomonadic algebras, as well as Tokarz's proper filter algebras; Ordertopological representation of pseudomonadic algebras; Complete description of the lattice of subvarieties of the variety of pseudomonadic algebras.

We show that every proper normal extension of the bi-modal system S5⁲ has the poly-size model property. In fact, to every proper normal extension L of S5⁲ corresponds a natural number b-the bound of L. For every L, there exists a polynomial P of degree b + 1 such that every L-consistent formula φ is satisfiable on an L-frame whose universe is bounded by P, where |φ| denotes the number of subformulas of φ. It is shown that this bound is (...) optimal. (shrink)

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n-universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We give a systematic method of constructing extensions of the Kuznetsov-Gerčiu logic KG without the finite model property (fmp for short), and show that there are continuum many such. We also introduce a new technique of gluing of cyclic intuitionistic descriptive frames and give a new simple proof of Gerčiu’s result [9, 8] that all extensions of the Rieger-Nishimura logic RN have the fmp. Moreover, we show that each extension of RN has the poly-size model property, thus improving on [9]. (...) Furthermore, for each function f: omega -> omega, we construct an extension Lf of KG such that Lf has the fmp, but does not have the f-size model property. We also give a new simple proof of another result of Gerčiu [9] characterizing the only extension of KG that bounds the fmp for extensions of KG. We conclude the paper by proving that RN.KC = RN + (¬p vee ¬¬p) is the only pre-locally tabular extension of KG, introduce the internal depth of an extension L of RN, and show that L is locally tabular if and only if the internal depth of L is finite. (shrink)

We prove that the existence of a measurable cardinal is equivalent to the existence of a normal space whose modal logic coincides with the modal logic of the Kripke frame isomorphic to the powerset of a two element set.

We establish the dichotomy property for stable canonical multi-conclusion rules for IPC, K4, and S4. This yields an alternative proof of existence of explicit bases of admissible rules for these logics.

We prove that every normal extension of the bi-modal system S52 is finitely axiomatizable and that every proper normal extension has NP-complete satisfiability problem.