Skip to main content
eScholarship
Open Access Publications from the University of California

Faculty Publications

For information about the Group in Logic and the Methodology of Science at UC Berkeley, please visit http://logic.berkeley.edu.

Cover page of Inquisitive Intuitionistic Logic

Inquisitive Intuitionistic Logic

(2020)

Inquisitive logic is a research program seeking to expand the purview of logic beyond declarative sentences to include the logic of questions. To this end, inquisitive propositional logic extends classical propositional logic for declarative sentences with principles governing a new binary connective of inquisitive disjunction, which allows the formation of questions. Recently inquisitive logicians have considered what happens if the logic of declarative sentences is assumed to be intuitionistic rather than classical. In short, what should inquisitive logic be on an intuitionistic base? In this paper, we provide an answer to this question from the perspective of nuclear semantics, an approach to classical and intuitionistic semantics pursued in our previous work. In particular, we show how Beth semantics for intuitionistic logic naturally extends to a semantics for inquisitive intuitionistic logic. In addition, we show how an explicit view of inquisitive intuitionistic logic comes via a translation into propositional lax logic, whose completeness we prove with respect to Beth semantics.

Cover page of A note on Murakami’s theorems and incomplete social choice without the Pareto principle

A note on Murakami’s theorems and incomplete social choice without the Pareto principle

(2020)

In Arrovian social choice theory assuming the independence of irrelevant alternatives, Murakami (1968) proved two theorems about complete and transitive collective choice rules that satisfy strict non-imposition (citizens’ sovereignty), one being a dichotomy theorem about Paretian or anti-Paretian rules and the other a dictator-or-inverse-dictator impossibility theorem without the Pareto principle. It has been claimed in the later literature that a theorem of Malawski and Zhou (1994) is a generalization of Murakami’s dichotomy theorem and that Wilson’s (1972) impossibility theorem is stronger than Murakami’s impossibility theorem, both by virtue of replacing Murakami’s assumption of strict non-imposition with the assumptions of non-imposition and non-nullness. In this note, we first point out that these claims are incorrect: non-imposition and non-nullness are together equivalent to strict non-imposition for all transitive collective choice rules. We then generalize Murakami’s dichotomy and impossibility theorems to the setting of incomplete social preference. We prove that if one drops completeness from Murakami’s assumptions, his remaining assumptions imply (i) that a collective choice rule is either Paretian, anti-Paretian, or dis-Paretian (unanimous individual preference implies noncomparability) and (ii) that adding proposed constraints on noncomparability, such as the regularity axiom of Eliaz and Ok (2006), restores Murakami’s dictator-or-inverse-dictator result.

Cover page of Complete Additivity and Modal Incompleteness

Complete Additivity and Modal Incompleteness

(2019)

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. After these results, we generalize the Blok Dichotomy [Blok, 1978] to degrees of V-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness.

Cover page of Algebraic and topological semantics for inquisitive logic via choice-free duality

Algebraic and topological semantics for inquisitive logic via choice-free duality

(2019)

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.

Cover page of Arrow's Decisive Coalitions

Arrow's Decisive Coalitions

(2018)

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 a complete logic for reasoning about decisive coalitions, along with formal proofs of Arrow’s and Wilson’s theorems. In addition, we prove the correctness of an algorithm for calculating, given any social rationality postulate of a certain form in the language of binary preference, the corresponding axiom in the language of decisive coalitions. These results suggest for social choice theory new perspectives and tools from logic.

Cover page of A Semantic Hierarchy for Intuitionistic Logic

A Semantic Hierarchy for Intuitionistic Logic

(2018)

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 semantic hierarchy.

Cover page of A Note on Algebraic Semantics for S5 with Propositional Quantifiers

A Note on Algebraic Semantics for S5 with Propositional Quantifiers

(2017)

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?

Cover page of Axiomatization in the Meaning Sciences

Axiomatization in the Meaning Sciences

(2017)

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.

Indicative Conditionals and Dynamic Epistemic Logic

(2017)

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 via a full and faithful computable translation from their logic to the modal logic K45.