Wesley H. Holliday

Much of the theoretical work on strategic voting makes strong assumptions about what voters know about the voting situation. A strategizing voter is typically assumed to know how other voters will vote and to know the rules of the voting method. A growing body of literature explores strategic voting when there is uncertainty about how others will vote. In this paper, we study strategic voting when there is uncertainty about the voting method. We introduce three notions of manipulability for a set of voting methods: sure, safe, and expected manipulability. With the help of a computer program, we identify voting scenarios in which uncertainty about the voting method may reduce or even eliminate a voter's incentive to misrepresent her preferences. Thus, it may be in the interest of an election designer who wishes to reduce strategic voting to leave voters uncertain about which of several reasonable voting methods will be used to determine the winners of an election.

The early literature on epistemic logic in philosophy focused on reasoning about the knowledge or belief of a single agent, especially on controversies about "introspection axioms" such as the 4 and 5 axioms. By contrast, the later literature on epistemic logic in computer science and game theory has focused on multi-agent epistemic reasoning, with the single-agent 4 and 5 axioms largely taken for granted. In the relevant multi-agent scenarios, it is often important to reason about what agent A believes about what agent B believes about what agent A believes; but it is rarely important to reason just about what agent A believes about what agent A believes. This raises the question of the extent to which single-agent introspection axioms actually matter for multi-agent epistemic reasoning. In this paper, we formalize and answer this question. To formalize the question, we first define a set of multi-agent formulas that we call agent-alternating formulas, including formulas like Box_a Box_b Box_a p but not formulas like Box_a Box_a p. We then prove, for the case of belief, that if one starts with multi-agent K or KD, then adding both the 4 and 5 axioms (or adding the B axiom) does not allow the derivation of any new agent-alternating formulas—in this sense, introspection axioms do not matter. By contrast, we show that such conservativity results fail for knowledge and multi-agent KT, though they hold with respect to a smaller class of agent-nonrepeating formulas.

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.

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.

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

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal 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 article 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 ${\cal V}$-baos, namely the provability logic $GLB$. 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 ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness.

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.

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.

Unlike standard modal logics, many dynamic epistemic logics are not closed under uniform substitution. A distinction therefore arises between the logic and its substitu- tion core, the set of formulas all of whose substitution instances are valid. The classic example of a non-uniform dynamic epistemic logic is Public Announcement Logic (PAL), and a well-known open problem is to axiomatize the substitution core of PAL. In this paper we solve this problem for PAL over the class of all relational models with infinitely many agents, PAL-Kω , as well as standard extensions thereof, e.g., PAL-Tω , PAL-S4ω, and PAL-S5ω. We introduce a new Uniform Public Announcement Logic (UPAL), prove completeness of a deductive system with respect to UPAL semantics, and show that this system axiomatizes the substitution core of PAL.

FoLLI-LNCS is the publication platform for the Association of Logic, Language and Information. The Association was founded in 1991 to advance research and education on the interface between logic, linguistics, computer science, and cognitive science. The FoLLI Publications on Logic, Language and Information aim to disseminate results of cutting-edge research and tutorial materials in these interdisciplinary areas. This LNCS volume is part of FoLLi book serie and contains the papers presented at the 5th International Workshop on Logic, Rationality and Interaction/, held in October 2015 in Taipei, Taiwan. The topics covered in this program well represent the span and depth that hasby now become a trademark of the LORI workshop series, where logic interfaceswith disciplines as diverse as game theory and decision theory, philosophyand epistemology, linguistics, computer science and artificial intelligence.

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.

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 ≥ on events that does not preclude a probabilistic interpretation, in the sense that ≥ has extensions that are probabilistically representable, we characterize the extension ≥+ of ≥ that is exactly the intersection of all probabilistically representable extensions of ≥. This extension ≥+ gives us all the additional comparisons that we are entitled to infer from ≥, based on the assumption that there is some probability measure of which ≥ 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, this problem has a more general interpretation involving measurement of any additive quantity: e.g., given comparisons between the weights of individual objects, what comparisons between the weights of groups of objects can we infer?

According to the Principle of the Fixity of the Past (FP), no one can now do anything that would require the past to have unfolded differently than it actually did, for the past is fixed, over and done with. Why might doing something in the future require the past to be different? Because if determinism is true—if the laws of nature and the initial conditions of the Big Bang determined a unique future for our universe—then doing anything other than what you are determined to do would require one of two things: either a miracle, a violation of the actual laws of nature, or a different past, all the way back to the Big Bang or beyond. Which would it be? Those who reject miracles accept a Backtracking Principle (BT), according to which the past would (have to) be different. If this is correct, then it follows by (FP) that you cannot now do anything other than what you are determined to do. The conclusion of this much-discussed argument is that the freedom to do otherwise is incompatible with determinism. In order to break a stalemate between incompatibilists and compatibilists in the debate over (FP), this article presents a new Action-Type Argument for (FP). The aim is to refute Backtracking Compatibilism, the view that (BT) is true and yet the freedom to do otherwise is compatible with determinism. The form of the Action-Type Argument for (FP) also leads to a Simple Argument for incompatibilism, which does not assume (BT). What the Simple Argument does assume is a “governing” view of laws of nature, a view of laws as more than mere regularities that turn out to be exceptionless over all time. Incompatibilism follows.

A well-known open problem in epistemic logic is to give a syntactic characterization of the successful formulas. Semantically, a formula is successful if and only if for any pointed model where it is true, it remains true after deleting all points where the formula was false. The classic example of a formula that is not successful in this sense is the “Moore sentence” p ∧ ¬BOXp, read as “p is true but you do not know p.” Not only is the Moore sentence unsuccessful, it is self-refuting, for it never remains true as described. We show that in logics of knowledge and belief for a single agent (extended by S5), Moorean phenomena are the source of all self-refutation; moreover, in logics for an introspective agent (extending KD45), Moorean phenomena are the source of all unsuccessfulness as well. This is a distinctive feature of such logics, for with a non-introspective agent or multiple agents, non-Moorean unsuccessful formulas appear. We also consider how successful and self-refuting formulas relate to the Cartesian and learnable formulas, which have been discussed in connection with Fitch’s “paradox of knowability.” We show that the Cartesian formulas are exactly the formulas that are not eventually self-refuting and that not all learnable formulas are successful. In an appendix, we give syntactic characterizations of the successful and the self-refuting formulas.

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 Dragalin frame based on that poset that generates the given nucleus. We then compare Dragalin’s approach to generating nuclei with the relational approach of Fairtlough and Mendler [11], based on what we call FM-frames. Surprisingly, every Dragalin frame can be turned into an equivalent FM-frame, albeit on a different poset. Thus, every locale can be realized as fixpoints of the nucleus generated by an FM-frame. Finally, we consider the relational approach of Goldblatt [13] and characterize the locales that can be realized using Goldblatt frames.

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.

This chapter argues that epistemologists should replace a “standard alternatives” picture of knowledge, assumed by many fallibilist theories of knowledge, with a new “multipath” picture of knowledge. The chapter first identifies a problem for the standard picture: fallibilists working with this picture cannot maintain even the most uncontroversial epistemic closure principles without making extreme assumptions about the ability of humans to know empirical truths without empirical investigation. The chapter then shows how the multipath picture, motivated by independent arguments, saves fallibilism from this problem. The multipath picture is based on taking seriously the idea that there can be multiple paths to knowing some propositions about the world. An overlooked consequence of fallibilism is that these multiple paths to knowledge may involve ruling out different sets of alternatives, which should be represented in a fallibilist picture of knowledge. The chapter concludes by considering inductive knowledge and strong epistemic closure from this multipath perspective.

The picture of information acquisition as the elimination of possibilities has proven fruitful in many domains, serving as a foundation for formal models in philosophy, linguistics, computer science, and economics. While the picture appears simple, its formalization in dynamic epistemic logic reveals subtleties: given a valid principle of information dynamics in the language of dynamic epistemic logic, substituting complex epistemic sentences for its atomic sentences may result in an invalid principle. In this article, we explore such failures of uniform substitution. First, we give epistemic examples inspired by Moore, Fitch, and Williamson. Second, we answer affirmatively a question posed by van Benthem: can we effectively decide when every substitution instance of a given dynamic epistemic principle is valid? In technical terms, we prove the decidability of this schematic validity problem for public announcement logic (PAL and PAL-RC) over models for finitely many fully introspective agents, as well as models for infinitely many arbitrary agents. The proof of this result illuminates the reasons for the failure of uniform substitution.

In this paper, we explore semantics for comparative epistemic modals that avoid the entailment problems shown to result from Kratzer’s (1991) semantics by Yalcin (2006, 2009, 2010). In contrast to the alternative semantics presented by Yalcin and Lassiter (2010, 2011), based on finitely additive probability measures, we introduce semantics based on qualitatively additive measures, as well as semantics based on purely qualitative orderings, including orderings on propositions derived from orderings on worlds in the tradition of Kratzer (1991). All of these semantics avoid the entailment problems that result from Kratzer’s semantics. Our discussion focuses on methodological issues concerning the choice between different semantics.

Epistemic closure has been a central issue in epistemology over the last forty years. According to versions of the relevant alternatives and subjunctivist theories of knowledge, epistemic closure can fail: an agent who knows some propositions can fail to know a logical consequence of those propositions, even if the agent explicitly believes the consequence (having “competently deduced” it from the known propositions). In this sense, the claim that epistemic closure can fail must be distinguished from the fact that agents do not always believe, let alone know, the consequences of what they know—a fact that raises the “problem of logical omniscience” that has been central in epistemic logic. This paper, part I of II, is a study of epistemic closure from the perspective of epistemic logic. First, I introduce models for epistemic logic, based on Lewis’s models for counterfactuals, that correspond closely to the pictures of the relevant alternatives and subjunctivist theories of knowledge in epistemology. Second, I give an exact characterization of the closure properties of knowledge according to these theories, as formalized. Finally, I consider the relation between closure and higher-order knowledge. The philosophical repercussions of these results and results from part II, which prompt a reassessment of the issue of closure in epistemology, are discussed further in companion papers. As a contribution to modal logic, this paper demonstrates an alternative approach to proving modal completeness theorems, without the standard canonical model construction. By “modal decomposition” I obtain completeness and other results for two non-normal modal logics with respect to new semantics. One of these logics, dubbed the logic of ranked relevant alternatives, appears not to have been previously identified in the modal logic literature. More broadly, the paper presents epistemology as a rich area for logical study.

Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A well-known example from the literature on intuitionistic logic is the class of Medvedev frames $\langle W,R\rangle$ where $W$ is the set of nonempty subsets of some nonempty finite set $S$, and $xRy$ iff $x\supseteq y$, or more liberally, where $\langle W,R\rangle$ is isomorphic as a directed graph to $\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle$. Prucnal [32] proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those $y$ such that $x\not= y$), or a complement modality (for quantifying over those $y$ such that $x\not\supseteq y$). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable---which would answer the open question of whether Medvedev's [31] "logic of finite problems'' is decidable---or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frame-incomplete logics.

The Paradox of the Surprise Examination has been a testing ground for a variety of frameworks in formal epistemology, from epistemic logic to probability theory to game theory and more. In this paper, I treat a related paradox, the Paradox of the Undiscoverable Position, as a test case for the possible-worlds style representation of epistemic states. I argue that the paradox can be solved in this framework, further illustrating the power of possible-worlds style modeling. The solution also illustrates an important distinction between anti-performatory and unassimilable announcements of information.

Unlike standard modal logics, many dynamic epistemic logics are not closed under uniform substitution. A distinction therefore arises between the logic and its substitution core, the set of formulas all of whose substitution instances are valid. The classic example of a non-uniform dynamic epistemic logic is Public Announcement Logic (PAL), and a well-known open problem is to axiomatize the substitution core of PAL. In this paper we solve this problem for PAL over the class of all relational models with infinitely many agents, PAL-K_omega, as well as standard extensions thereof, e.g., PAL-T_omega, PAL-S4_omega, and PAL-S5_omega. We introduce a new Uniform Public Announcement Logic (UPAL), prove completeness of a deductive system with respect to UPAL semantics, and show that this system axiomatizes the substitution core of PAL.