Logic Games are Complete for Game Logics

Game logics describe general games through powers of players for forcing outcomes. In particular, they encode an algebra of sequential game operations such as choice, dual and composition. Logic games are special games for specific purposes such as proof or semantical evaluation for first-order or modal languages. We show that the general algebra of game operations coincides with that over just logical evaluation games, whence the latter are quite general after all. The main tool in proving this is a representation of arbitrary games as modal or first-order evaluation games. We probe how far our analysis extends to product operations on games. We also discuss some more general consequences of this new perspective for standard logic.     

Program Constructions that are Safe for Bisimulation

It has been known since the seventies that the formulas of modal logic are invariant for bisimulations between possible worlds models — while conversely, all bisimulation-invariant first-order formulas are modally definable. In this paper, we extend this semantic style of analysis from modal formulas to dynamic program operations. We show that the usual regular operations are safe for bisimulation, in the sense that the transition relations of their values respect any given bisimulation for their arguments. Our main result is a complete syntactic characterization of all first-order definable program operations that are safe for bisimulation. This is a semantic functional completeness result for programming, which may be contrasted with the more usual analysis in terms of computational power. The 'Safety Theorem' can be modulated in several ways. We conclude with a list of variants, extensions, and further developments.     

Logics for Epistemic Programs

We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the semantics of an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as changes of the state model, called epistemic updates. Formally, an update consists of two operations: the first is called the update map, and it takes every state model to another state model, called the updated model; the second gives, for each input state model, a transition relation between the states of that model and the states of the updated model. Each variety of epistemic actions, such as public announcements or completely private announcements to groups, gives what we call an action signature, and then each family of action signatures gives a logical language. The construction of these languages is the main topic of this paper. We also mention the systems that capture the valid sentences of our logics. But we defer to a separate paper the completeness proof. The basic operation used in the semantics is called the update product. A version of this was introduced in Baltag et al. (1998), and the presentation here improves on the earlier one. The update product is used to obtain from any program model the corresponding epistemic update, thus allowing us to compute changes of information or belief. This point is of interest independently of our logical languages. We illustrate the update product and our logical languages with many examples throughout the paper.     

Departing from Classical Logic: A Logical Analysis of Personal Construct Theory

This article draws a parallel between personal construct theory and intuitionistic logic i, in order to account for Kelly's claim to have departed from classical logic. Assuming that different theoretical paradigms correspond to different logical languages, it is argued that the constructivist paradigm is linked to intuitionism. Similarities between some key syntactic and semantic features of i logic and the underlying logic of Kelly's theory are made explicit. The strengths and limitations of such an approach are discussed in light of issues emerging from clinical observation and from the philosophy of science.     

Why Combine Logics?

Combining logics has become a rapidly expanding entreprise that is inspired mainly by concerns about modularity and the wish to join together tailor made logical tools into more powerful but still manageable ones. A natural question is whether it offers anything new over and above existing standard languages.By analysing a number of applications where combined logics arise, we argue that combined logics are a potentially valuable tool in applied logic, and that endorsements of standard languages often miss the point. Using the history of quantified modal logic as our main example, we also show that the use of combined structures and logics is a recurring theme in the analysis of existing logical systems.     

Actuality, Necessity, and Logical Truth

The traditional view that all logical truths are metaphysically necessary has come under attack in recent years. The contrary claim is prominent in David Kaplan’s work on demonstratives, and Edward Zalta has argued that logical truths that are not necessary appear in modal languages supplemented only with some device for making reference to the actual world (and thus independently of whether demonstratives like ‘I’, ‘here’, and ‘now’ are present). If this latter claim can be sustained, it strikes close to the heart of the traditional view. I begin this paper by discussing and refuting Zalta’s argument in the context of a language for propositional modal logic with an actuality connective (section 1). This involves showing that his argument in favor of real world validity his preferred explication of logical truth, is fallacious. Next (section 2) I argue for an alternative explication of logical truth called general validity. Since the rule of necessitation preserves general validity, the argument of section 2 provides a reason for affirming the traditional view. Finally (section 3) I show that the intuitive idea behind the discredited notion of real world validity finds legitimate expression in an object language connective for deep necessity. Earlier versions of this paper were read at the universities of Graz, Maribor, and Salzburg, and at a workshop on the philosophy of logic at the National Autonomous University of Mexico (UNAM) in Mexico City. My thanks to those present at these events for many helpful suggestions. Thanks are also due to an anonymous referee for Philosophical Studies.     

Language evolution by iterated learning with bayesian agents

Languages are transmitted from person to person and generation to generation via a process of iterated learning: people learn a language from other people who once learned that language themselves. We analyze the consequences of iterated learning for learning algorithms based on the principles of Bayesian inference, assuming that learners compute a posterior distribution over languages by combining a prior (representing their inductive biases) with the evidence provided by linguistic data. We show that when learners sample languages from this posterior distribution, iterated learning converges to a distribution over languages that is determined entirely by the prior. Under these conditions, iterated learning is a form of Gibbs sampling, a widely-used Markov chain Monte Carlo algorithm. The consequences of iterated learning are more complicated when learners choose the language with maximum posterior probability, being affected by both the prior of the learners and the amount of information transmitted between generations. We show that in this case, iterated learning corresponds to another statistical inference algorithm, a variant of the expectation-maximization (EM) algorithm. These results clarify the role of iterated learning in explanations of linguistic universals and provide a formal connection between constraints on language acquisition and the languages that come to be spoken, suggesting that information transmitted via iterated learning will ultimately come to mirror the minds of the learners.     

Naïve Comprehension and Contracting Implications

In his paper [6], Greg Restall conjectured that a logic supports a naïve comprehension scheme if and only if it is robustly contraction free, that is, if and only if no contracting connective is definable in terms of the primitive connectives of the logic. In this paper, we present infinitely many counterexamples to Restall's conjecture, in the form of purely implicational logics which are robustly contraction free, but which trivialize naïve comprehension.     

Language Evolution Can Be Shaped by the Structure of the World

Human languages vary in many ways but also show striking cross‐linguistic universals. Why do these universals exist? Recent theoretical results demonstrate that Bayesian learners transmitting language to each other through iterated learning will converge on a distribution of languages that depends only on their prior biases about language and the quantity of data transmitted at each point; the structure of the world being communicated about plays no role (Griffiths & Kalish, 2005 , 2007 ). We revisit these findings and show that when certain assumptions about the relationship between language and the world are abandoned, learners will converge to languages that depend on the structure of the world as well as their prior biases. These theoretical results are supported with a series of experiments showing that when human learners acquire language through iterated learning, the ultimate structure of those languages is shaped by the structure of the meanings to be communicated.     

On the Epistemic Foundation for Iterated Weak Dominance: An Analysis in a Logic of Individual and Collective attitudes

This paper proposes a logical framework for representing static and dynamic properties of different kinds of individual and collective attitudes. A complete axiomatization as well as a decidability result for the logic are given. The logic is applied to game theory by providing a formal analysis of the epistemic conditions of iterated deletion of weakly dominated strategies (IDWDS), or iterated weak dominance for short. The main difference between the analysis of the epistemic conditions of iterated weak dominance given in this paper and other analysis is that we use a semi-qualitative approach to uncertainty based on the notion of plausibility first introduced by Spohn, whereas other analysis are based on a quantitative representation of uncertainty in terms of probabilities.     

Standard Gödel Modal Logics

We prove strong completeness of the □-version and the ?-version of a Gödel modal logic based on Kripke models where propositions at each world and the accessibility relation are both infinitely valued in the standard Gödel algebra [0,1]. Some asymmetries are revealed: validity in the first logic is reducible to the class of frames having two-valued accessibility relation and this logic does not enjoy the finite model property, while validity in the second logic requires truly fuzzy accessibility relations and this logic has the finite model property. Analogues of the classical modal systems D, T, S4 and S5 are considered also, and the completeness results are extended to languages enriched with a discrete well ordered set of truth constants.     

The Evolution of Principia Mathematica; Bertrand Russell's Manuscripts and Notes for the Second Edition

This paper deals with Popper's little-known work on deductive logic, published between 1947 and 1949. According to his theory of deductive inference, the meaning of logical signs is determined by certain rules derived from ‘inferential definitions’ of those signs. Although strong arguments have been presented against Popper's claims (e.g. by Curry, Kleene, Lejewski and McKinsey), his theory can be reconstructed when it is viewed primarily as an attempt to demarcate logical from non-logical constants rather than as a semantic foundation for logic. A criterion of logicality is obtained which is based on conjunction, implication and universal quantification as fundamental logical operations.     

On the factivity of implicit intersubjective knowledge

The concept of knowledge can be modelled in epistemic modal logic and, if modelled by using a standard modal operator, it is subject to the problem of logical omniscience. The classical solution to this problem is to distinguish between implicit and explicit knowledge and to construe the knowledge operator as capturing the concept of implicit knowledge. In addition, since a proposition is said to be implicitly known just in case it is derivable from the set of propositions that are explicitly known by using a certain set of logical rules, the concept of implicit knowledge is definable on the basis of the concept of explicit knowledge. In any case, both implicit and explicit knowledge are typically characterized as factive, i.e. such that it is always the case that what is known is also true. The aim of the present paper is twofold: first, we will develop a dynamic system of explicit intersubjective knowledge that allows us to introduce the operator of implicit knowledge by definition; secondly, we will show that it is not possible to hold together the following two theses: (1) the concept of implicit knowledge is definable along the lines indicated above and (2) the concept of implicit knowledge is factive.     

The Undecidability of Iterated Modal Relativization

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 ¹₁–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 ⁰₁–complete. These results go via reduction to problems concerning domino systems.     

Laws of language use and formal logic

After a review of recent work connected with Grice's maxims of conversation, special attention is paid to the principles related to the concept of informativeness. The operation of those principles constrains logic by limiting the meaning of logical particles and, more importantly, by contradicting axioms and many theorems of the propositional calculus. It is argued that, as the development of the individual's formal operations proceeds, a conflict with laws of language use arises. The notion of a conflict between two subsystems, logical and linguistic, is used in a developmental perspective to account, in a unified manner, for the observed discrepancy between subjects' behavior in deductive and inductive reasoning tasks and predictions based on formal logic.     

How Do Logics Explain?

Anti-exceptionalists about logic maintain that it is continuous with the empirical sciences. Taking anti-exceptionalism for granted, we argue that traditional approaches to explanation are inadequate in the case of logic. We argue that Andrea Woody's functional analysis of explanation is a better fit with logical practice and accounts better for the explanatory role of logical theories.     

On Sahlqvist Formulas in Relevant Logic

This paper defines a Sahlqvist fragment for relevant logic and establishes that each class of frames in the Routley-Meyer semantics which is definable by a Sahlqvist formula is also elementary, that is, it coincides with the class of structures satisfying a given first order property calculable by a Sahlqvist-van Benthem algorithm. Furthermore, we show that some classes of Routley-Meyer frames definable by a relevant formula are not elementary.     

Is there a neutral metalanguage?

Logical pluralists are committed to the idea of a neutral metalanguage, which serves as a framework for debates in logic. Two versions of this neutrality can be found in the literature: an agreed upon collection of inferences, and a metalanguage that is neutral as such. I discuss both versions and show that they are not immune to Quinean criticism, which builds on the notion of meaning. In particular, I show that (i) the first version of neutrality is sub-optimal, and hard to reconcile with the theories of meaning for logical constants, and (ii) the second version collapses mathematically, if rival logics, as object languages, are treated with charity in the metalanguage. I substantiate (ii) by proving a collapse theorem that generalizes familiar results. Thus, the existence of a neutral metalanguage cannot be taken for granted, and meaning-invariant logical pluralism might turn out to be dubious.

     

Bilattices with Implications

In a previous work we studied, from the perspective of Abstract Algebraic Logic, the implicationless fragment of a logic introduced by O. Arieli and A. Avron using a class of bilattice-based logical matrices called logical bilattices. Here we complete this study by considering the Arieli-Avron logic in the full language, obtained by adding two implication connectives to the standard bilattice language. We prove that this logic is algebraizable and investigate its algebraic models, which turn out to be distributive bilattices with additional implication operations. We axiomatize and state several results on these new classes of algebras, in particular representation theorems analogue to the well-known one for interlaced bilattices.