http://www.rssboard.org/rss-specification720Recent berkeleylogic items
https://escholarship.org/uc/berkeleylogic/rss
Recent eScholarship items from Group in Logic and the Methodology of ScienceThu, 19 Sep 2019 02:20:40 +0000A note on the consistency operator
https://escholarship.org/uc/item/40j0v0hb
A note on the consistency operatorhttps://escholarship.org/uc/item/40j0v0hbThu, 9 May 2019 00:00:00 +0000Algebraic and topological semantics for inquisitive logic via choice-free duality
https://escholarship.org/uc/item/69f4t1wg
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...https://escholarship.org/uc/item/69f4t1wgWed, 17 Apr 2019 00:00:00 +0000A Semantic Hierarchy for Intuitionistic Logic
https://escholarship.org/uc/item/2vp2x4rx
Brouwer's views on the foundations of mathematics have inspired the study of intuitionistic logic, including the study of the intuitionistic propositional calculus and its extensions. The theory of these systems has become an independent branch of logic with connections to lattice theory, topology, modal logic and other areas. This paper aims to present a modern account of semantics for intuitionistic propositional systems. The guiding idea is that of a hierarchy of semantics, organized by increasing generality: from the least general Kripke semantics on through Beth semantics, topological semantics, Dragalin semantics, and finally to the most general algebraic semantics. While the Kripke, topological, and algebraic semantics have been extensively studied, the Beth and Dragalin semantics have received less attention. We bring Beth and Dragalin semantics to the fore, relating them to the concept of a nucleus from pointfree topology, which provides a unifying perspective on the...https://escholarship.org/uc/item/2vp2x4rxSat, 3 Nov 2018 00:00:00 +0000Complete Additivity and Modal Incompleteness
https://escholarship.org/uc/item/01p9x1hv
In this paper, we tell a story about incompleteness in modal logic. The story weaves together a paper of van Benthem [1979], “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely ad- ditive modal algebras, or as we call them, V-BAOs. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s paper resolves the open question in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to V-BAOs, namely the provability logic GLB [Japaridze, 1988, Boolos, 1993]. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is V-complete....https://escholarship.org/uc/item/01p9x1hvWed, 19 Sep 2018 00:00:00 +0000Arrow's Decisive Coalitions
https://escholarship.org/uc/item/9hd0g86c
In his classic monograph, <em>Social Choice and Individual Values</em>, Arrow introduced the notion of a decisive coalition of voters as part of his mathematical framework for social choice theory. The subsequent literature on Arrow’s Impossibility Theorem has shown the importance for social choice theory of reasoning about coalitions of voters with different grades of decisiveness. The goal of this paper is a fine-grained analysis of reasoning about decisive coalitions, formalizing how the concept of a decisive coalition gives rise to a social choice theoretic language and logic all of its own. We show that given Arrow’s axioms of the Independence of Irrelevant Alternatives and Universal Domain, rationality postulates for social preference correspond to strong axioms about decisive coalitions. We demonstrate this correspondence with results of a kind familiar in economics—representation theorems—as well as results of a kind coming from mathematical logic—completeness theorems....https://escholarship.org/uc/item/9hd0g86cFri, 7 Sep 2018 00:00:00 +0000Choice-free Stone duality
https://escholarship.org/uc/item/00p6t2v4
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 paper, 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...https://escholarship.org/uc/item/00p6t2v4Fri, 7 Sep 2018 00:00:00 +0000On the Logics with Propositional Quantifiers Extending S5Π
https://escholarship.org/uc/item/1bf3g4fn
Scroggs's theorem on the extensions of S5 is an early landmark in the modern mathematical studies of modal logics. From it, we know that the lattice of normal extensions of S5 is isomorphic to the inverse order of the natural numbers with infinity and that all extensions of S5 are in fact normal. In this paper, we consider extending Scroggs's theorem to modal logics with propositional quantifiers governed by the axioms and rules analogous to the usual ones for ordinary quantifiers. We call them Π-logics. Taking S5Π, the smallest normal Π-logic extending S5, as the natural counterpart to S5 in Scroggs's theorem, we show that all normal Π-logics extending S5Π are complete with respect to their complete simple S5 algebras, that they form a lattice that is isomorphic to the lattice of the open sets of the disjoint union of two copies of the one-point compactification of N, that they have arbitrarily high Turing-degrees, and that there are non-normal Π-logics extending S5Π.https://escholarship.org/uc/item/1bf3g4fnMon, 20 Aug 2018 00:00:00 +0000The Logic of Comparative Cardinality
https://escholarship.org/uc/item/2nn3c35x
This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and omplementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.https://escholarship.org/uc/item/2nn3c35xTue, 7 Aug 2018 00:00:00 +0000One Modal Logic to Rule Them All?
https://escholarship.org/uc/item/46w023hs
One Modal Logic to Rule Them All?https://escholarship.org/uc/item/46w023hsTue, 26 Jun 2018 00:00:00 +0000Operationalism Meets Modal Logic
https://escholarship.org/uc/item/3dg565gq
<p>Guided by a desire to eliminate language that refers to unobservable structure from mechanics, Ernst Mach proposed a definition of mass in terms of more directly observable data. A great deal of literature surrounds the question of whether this proposed definition accomplishes its stated goal, or even whether it constitutes a definition. In this talk we aim to bring clarity to this debate by using methods from model theory and from modal logic to classify, reconstruct, and evaluate these arguments. In particular, we exhibit a general construction of first-order modal frames for appropriately presented scientific theories with epistemic constraints. These frames allow us to characterize which properties are “modally definable” in the sense of Bressan.</p>https://escholarship.org/uc/item/3dg565gqSat, 23 Jun 2018 00:00:00 +0000Reflection ranks and ordinal analysis
https://escholarship.org/uc/item/1159j6ck
It is well-known that natural axiomatic theories are well-ordered by consistency strength. However, it is possible to construct descending chains of artificial theories with respect to consistency strength. We provide an explanation of this well-orderness phenomenon by studying a coarsening of the consistency strength order, namely, the $\Pi^1_1$ reflection strength order. We prove that there are no descending sequences of $\Pi^1_1$ sound extensions of $\mathsf{ACA}_0$ in this order. Accordingly, we can attach a rank in this order, which we call reflection rank, to any $\Pi^1_1$ sound extension of $\mathsf{ACA}_0$. We prove that for any $\Pi^1_1$ sound theory $T$ extending $\mathsf{ACA}_0^+$, the reflection rank of $T$ equals the proof-theoretic ordinal of $T$. We also prove that the proof-theoretic ordinal of $\alpha$ iterated $\Pi^1_1$ reflection is $\varepsilon_\alpha$. Finally, we use our results to provide straightforward well-foundedness proofs of ordinal notation systems...https://escholarship.org/uc/item/1159j6ckSat, 23 Jun 2018 00:00:00 +0000One Modal Logic to Rule Them All? (Extended Technical Report)
https://escholarship.org/uc/item/07v9360j
One Modal Logic to Rule Them All? (Extended Technical Report)https://escholarship.org/uc/item/07v9360jMon, 26 Mar 2018 00:00:00 +0000Fine's canonicity theorem for some classes of neighborhood frames
https://escholarship.org/uc/item/1w71d5g8
Fine's canonicity theorem for some classes of neighborhood frameshttps://escholarship.org/uc/item/1w71d5g8Thu, 22 Feb 2018 00:00:00 +0000Modal Correspondence Theory for Possibility Semantics
https://escholarship.org/uc/item/7t12914n
New version: <a href="/uc/item/2kf0p9bg">https://escholarship.org/uc/item/2kf0p9bg</a>https://escholarship.org/uc/item/7t12914nWed, 21 Feb 2018 00:00:00 +0000Possibility Frames and Forcing for Modal Logic (February 2018)
https://escholarship.org/uc/item/0tm6b30q
Possibility Frames and Forcing for Modal Logic (February 2018)https://escholarship.org/uc/item/0tm6b30qSat, 17 Feb 2018 00:00:00 +0000A Representation Theorem for Possibility Models
https://escholarship.org/uc/item/881757qn
This paper is about the relation between two kinds of models for propositional modal logic: possibility models in the style of Humberstone and possible world models in the style of Kripke. We show that every countable possibility model <em>M</em> is completed by a Kripke model <em>K</em>, its <em>worldization</em>; every total world of <em>K</em> is the limit of more and more refined possibilities in <em>M</em>, and every possibility in <em>M</em> is realized by some total world of <em>K</em>. In addition, we define a general notion of a <em>possibilization</em> of a Kripke model, which is a possibility model whose possibilities are sets of worlds from the Kripke model. We then characterize the class of possibility models that are isomorphic to the possibilization of some Kripke model. In particular, every possibility model in this class can be represented as a possibilization of one of its worldizations; and every possibility model can be naturally transformed into one in this...https://escholarship.org/uc/item/881757qnSat, 30 Dec 2017 00:00:00 +0000Arrow's Decisive Coalitions
https://escholarship.org/uc/item/5mr296jp
<p>In his classic monograph, Social Choice and Individual Values, Arrow introduced the notion of a decisive coalition of voters as part of his mathematical framework for social choice theory. The subsequent literature on Arrow’s Impossibility Theorem has shown the importance for social choice theory of reasoning about coalitions of voters with different grades of decisiveness. The goal of this paper is a fine-grained analysis of reasoning about decisive coalitions, formalizing how the concept of a decisive coalition gives rise to a social choice theoretic language and logic all of its own. We show that given Arrow’s axioms of the Independence of Irrelevant Alternatives and Universal Domain, rationality postulates for social preference correspond to strong axioms about decisive coalitions. We demonstrate this correspondence with results of a kind familiar in economics—representation theorems—as well as results of a kind coming from mathematical logic—completeness theorems. We present...https://escholarship.org/uc/item/5mr296jpSun, 8 Oct 2017 00:00:00 +0000On the inevitability of the consistency operator
https://escholarship.org/uc/item/1fm9h9bq
On the inevitability of the consistency operatorhttps://escholarship.org/uc/item/1fm9h9bqSun, 8 Oct 2017 00:00:00 +0000Results in Modal Correspondence Theory for Possibility Semantics
https://escholarship.org/uc/item/2kf0p9bg
Results in Modal Correspondence Theory for Possibility Semanticshttps://escholarship.org/uc/item/2kf0p9bgThu, 5 Oct 2017 00:00:00 +0000Indicative Conditionals and Dynamic Epistemic Logic
https://escholarship.org/uc/item/7sc8x8c4
Recent ideas about epistemic modals and indicative conditionals in formal semantics have significant overlap with ideas in modal logic and dynamic epistemic logic. The purpose of this paper is to show how greater interaction between formal semantics and dynamic epistemic logic in this area can be of mutual benefit. In one direction, we show how concepts and tools from modal logic and dynamic epistemic logic can be used to give a simple, complete axiomatization of Yalcin's [16] semantic consequence relation for a language with epistemic modals and indicative conditionals. In the other direction, the formal semantics for indicative conditionals due to Kolodny and MacFarlane [9] gives rise to a new dynamic operator that is very natural from the point of view of dynamic epistemic logic, allowing succinct expression of dependence (as in dependence logic) or supervenience statements. We prove decidability for the logic with epistemic modals and Kolodny and MacFarlane's indicative conditional...https://escholarship.org/uc/item/7sc8x8c4Sat, 5 Aug 2017 00:00:00 +0000Axiomatization in the Meaning Sciences
https://escholarship.org/uc/item/5jw0p2mz
While much of semantic theorizing is based on intuitions about logical phenomena associated with linguistic constructions—phenomena such as consistency and entailment—it is rare to see axiomatic treatments of linguistic fragments. Given a fragment interpreted in some class of formally specified models, it is often possible to ask for a characterization of the reasoning patterns validated by the class of models. Axiomatizations provide such a characterization, often in a perspicuous and efficient manner. In this paper, we highlight some of the benefits of providing axiomatizations for the purpose of semantic theorizing. We illustrate some of these benefits using three examples from the study of modality.https://escholarship.org/uc/item/5jw0p2mzFri, 7 Apr 2017 00:00:00 +0000A Note on Algebraic Semantics for S5 with Propositional Quantifiers
https://escholarship.org/uc/item/303338xr
In two of the earliest papers on extending modal logic with propositional quantifiers, R. A. Bull and K. Fine studied a modal logic S5Π extending S5 with axioms and rules for propositional quantification. Surprisingly, there seems to have been no proof in the literature of the completeness of S5Π with respect to its most natural algebraic semantics, with propositional quantifiers interpreted by meets and joins over all elements in a complete Boolean algebra. In this note, we give such a proof. This result raises the question: for which normal modal logics L can one axiomatize the quantified propositional modal logic determined by the complete modal algebras for L?https://escholarship.org/uc/item/303338xrMon, 13 Mar 2017 00:00:00 +0000Preferential Structures for Comparative Probabilistic Reasoning
https://escholarship.org/uc/item/40c139d1
Qualitative and quantitative approaches to reasoning about uncertainty can lead to different logical systems for formalizing such reasoning, even when the language for expressing uncertainty is the same. In the case of reasoning about relative likelihood, with statements of the form φ ≥ ψ expressing that φ is at least as likely as ψ, a standard qualitative approach using preordered preferential structures yields a dramatically different logical system than a quantitative ap- proach using probability measures. In fact, the standard pref- erential approach validates principles of reasoning that are incorrect from a probabilistic point of view. However, in this paper we show that a natural modification of the preferential approach yields exactly the same logical system as a probabilistic approach—not using single probability measures, but rather sets of probability measures. Thus, the same preferential structures used in the study of non-monotonic logics and belief revision may be...https://escholarship.org/uc/item/40c139d1Sat, 11 Feb 2017 00:00:00 +0000Inferring Probability Comparisons
https://escholarship.org/uc/item/8br2b074
The problem of inferring probability comparisons between events from an initial set of comparisons arises in several contexts, ranging from decision theory to artificial intelligence to formal semantics. In this paper, we treat the problem as follows: beginning with a binary relation $\succsim$ on events that does not preclude a probabilistic interpretation, in the sense that $\succsim$ has extensions that are probabilistically representable, we characterize the extension $\succsim^+$ of $\succsim$ that is exactly the <em>intersection</em> of all probabilistically representable extensions of $\succsim$. This extension $\succsim^+$ gives us all the additional comparisons that we are entitled to infer from $\succsim$, based on the assumption that there is some probability measure of which $\succsim$ gives us partial qualitative information. We pay special attention to the problem of extending an order on states to an order on events. In addition to the probabilistic interpretation,...https://escholarship.org/uc/item/8br2b074Fri, 18 Nov 2016 00:00:00 +0000Complete Additivity and Modal Incompleteness
https://escholarship.org/uc/item/8pp4d94t
In this paper, we tell a story about incompleteness in modal logic. The story weaves together a paper of van Benthem [1979], “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of <em>completely additive</em> modal algebras, or as we call them, V-BAOs. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s paper resolves the open question in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to V-BAOs, namely the provability logic GLB [Japaridze, 1988, Boolos, 1993]. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is V-complete....https://escholarship.org/uc/item/8pp4d94tThu, 29 Sep 2016 00:00:00 +0000On the Modal Logic of Subset and Superset: Tense Logic over Medvedev Frames
https://escholarship.org/uc/item/0379725f
On the Modal Logic of Subset and Superset: Tense Logic over Medvedev Frameshttps://escholarship.org/uc/item/0379725fSun, 18 Sep 2016 00:00:00 +0000A Bimodal Perspective on Possibility Semantics
https://escholarship.org/uc/item/2h5069pq
In this paper we develop a bimodal perspective on <em>possibility semantics</em>, a framework allowing partiality of states that provides an alternative modeling for classical propositional and modal logics [Humberstone 1981, Holliday 2015]. In particular, we define a full and faithful <em>translation</em> of the basic modal logic <strong>K</strong> 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...https://escholarship.org/uc/item/2h5069pqSat, 6 Aug 2016 00:00:00 +0000Partiality and Adjointness in Modal Logic
https://escholarship.org/uc/item/9pm9t4vp
Following a proposal of Humberstone, this paper studies a semantics for modal logic based on partial “possibilities” rather than total “worlds.” There are a number of reasons, philosophical and mathematical, to find this alternative semantics attractive. Here we focus on the construction of possibility models with a finitary flavor. Our main completeness result shows that for a number of standard modal logics, we can build a canonical possibility model, wherein every logically consistent formula is satisfied, by simply taking each <em>individual finite formula</em> (modulo equivalence) to be a possibility, rather than each infinite maximally consistent set of formulas as in the usual canonical world models. Constructing these locally finite canonical models involves solving a problem in general modal logic of independent interest, related to the study of <em>adjoint</em> pairs of modal operators: for a given modal logic L, can we find for every formula φ a formula f(φ) such that...https://escholarship.org/uc/item/9pm9t4vpWed, 13 Jul 2016 00:00:00 +0000A computability theoretic equivalent to Vaught's conjecture
https://escholarship.org/uc/item/9910d3kq
A computability theoretic equivalent to Vaught's conjecturehttps://escholarship.org/uc/item/9910d3kqWed, 29 Jun 2016 00:00:00 +0000The complexity of computable categoricity
https://escholarship.org/uc/item/0zv7r0p3
The complexity of computable categoricityhttps://escholarship.org/uc/item/0zv7r0p3Wed, 29 Jun 2016 00:00:00 +0000Possibility Frames and Forcing for Modal Logic (June 2016)
https://escholarship.org/uc/item/9v11r0dq
New version: https://escholarship.org/uc/item/0tm6b30qhttps://escholarship.org/uc/item/9v11r0dqTue, 21 Jun 2016 00:00:00 +0000Locales, Nuclei, and Dragalin Frames
https://escholarship.org/uc/item/2s0134zx
It is a classic result in lattice theory that a poset is a complete lattice iff it can be realized as fixpoints of a closure operator on a powerset. Dragalin [9,10] observed that a poset is a locale (complete Heyting algebra) iff it can be realized as fixpoints of a nucleus on the locale of upsets of a poset. He also showed how to generate a nucleus on upsets by adding a structure of “paths” to a poset, forming what we call a Dragalin frame. This allowed Dragalin to introduce a semantics for intuitionistic logic that generalizes Beth and Kripke semantics. He proved that every spatial locale (locale of open sets of a topological space) can be realized as fixpoints of the nucleus generated by a Dragalin frame. In this paper, we strengthen Dragalin’s result and prove that every locale—not only spatial locales—can be realized as fixpoints of the nucleus generated by a Dragalin frame. In fact, we prove the stronger result that for every nucleus on the upsets of a poset, there is a...https://escholarship.org/uc/item/2s0134zxSun, 12 Jun 2016 00:00:00 +0000First-order possibility models and finitary completeness proofs
https://escholarship.org/uc/item/8ht6w3kk
This paper builds on Humberstone's idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, we show that this is impossible to do in the first-order case. However, one can still construct a canonical model where every possibility consists of a computable set of formulas and thus still of finitely much information.https://escholarship.org/uc/item/8ht6w3kkWed, 24 Feb 2016 00:00:00 +0000Scott Ranks of Models of a Theory
https://escholarship.org/uc/item/5q9634jv
<p>The Scott rank of a countable structure is a measure, coming from the proof of Scott's isomorphism theorem, of the complexity of that structure. The Scott spectrum of a theory (by which we mean a sentence of $\mc{L}_{\omega_1 \omega}$) is the set of Scott ranks of countable models of that theory. In $ZFC + PD$ we give a descriptive-set-theoretic classification of the sets of ordinals which are the Scott spectrum of a theory: they are particular $\bfSigma^1_1$ classes of ordinals.</p><p>Our investigation of Scott spectra leads to the resolution (in $ZFC$) of a number of open problems about Scott ranks. We answer a question of Montalb\'an by showing, for each $\alpha < \omega_1$, that there is a $\Pi^{\infi}_2$ theory with no models of Scott rank less than $\alpha$. We also answer a question of Knight and Calvert by showing that there are computable models of high Scott rank which are not computably approximable by models of low Scott rank. Finally, we answer a question of...https://escholarship.org/uc/item/5q9634jvWed, 24 Feb 2016 00:00:00 +0000Possibility Frames and Forcing for Modal Logic
https://escholarship.org/uc/item/5462j5b6
New version: https://escholarship.org/uc/item/0tm6b30qhttps://escholarship.org/uc/item/5462j5b6Fri, 1 Jan 2016 00:00:00 +0000