SUPERVALUATION FIXED-POINT LOGICS OF TRUTH

Michael Kremer defines fixed-point logics of truth based on Saul Kripke’s fixed point semantics for languages expressing their own truth concepts. Kremer axiomatizes the strong Kleene fixed-point logic of truth and the weak Kleene fixed-point logic of truth, but leaves the axiomatizability question open for the supervaluation fixed-point logic of truth and its variants. We show that the principal supervaluation fixed point logic of truth, when thought of as consequence relation, is highly complex: it is not even analytic. We also consider variants, engendered by a stronger notion of ‘fixed point’, and by variant supervaluation schemes. A ‘logic’ is often thought of, not as a consequence relation, but as a set of sentences – the sentences true on each interpretation. We axiomatize the supervaluation fixed-point logics so conceived.     

The original sin of proof-theoretic semantics

Proof-theoretic semantics is an alternative to model-theoretic semantics. It aims at explaining the meaning of the logical constants in terms of the inference rules that govern their behaviour in proofs. We argue that this must be construed as the task of explaining these meanings relative to a logic, i.e., to a consequence relation. Alas, there is no agreed set of properties that a relation must have in order to qualify as a consequence relation. Moreover, the association of a consequence relation to a logical calculus is not as straightforward as it may seem. We show that these facts are problematic for the proof-theoretic project but the problems can be solved. Our thesis is that the consequence relation relevant for proof-theoretic semantics is the one given by the sequent-to-sequent derivability relation in Gentzen systems.

     

Supervaluation-Style Truth Without Supervaluations

Kripke’s theory of truth is arguably the most influential approach to self-referential truth and the semantic paradoxes. The use of a partial evaluation scheme is crucial to the theory and the most prominent schemes that are adopted are the strong Kleene and the supervaluation scheme. The strong Kleene scheme is attractive because it ensures the compositionality of the notion of truth. But under the strong Kleene scheme classical tautologies do not, in general, turn out to be true and, as a consequence, classical reasoning is no longer admissible once the notion of truth is involved. The supervaluation scheme adheres to classical reasoning but violates compositionality. Moreover, it turns Kripke’s theory into a rather complicated affair: to check whether a sentence is true we have to look at all admissible precisification of the interpretation of the truth predicate we are presented with. One consequence of this complicated evaluation condition is that under the supervaluation scheme a more proof-theoretic characterization of Kripke’s theory becomes inherently difficult, if not impossible. In this paper we explore the middle ground between the strong Kleene and the supervaluation scheme and provide an evaluation scheme that adheres to classical reasoning but retains many of the attractive features of the strong Kleene scheme. We supplement our semantic investigation with a novel axiomatic theory of truth that matches the semantic theory we have put forth.     

Excluded middle and bivalence

I consider two related objections to the claim that the law of excluded middle does not imply bivalence. One objection claims that the truth predicate captured by supervaluation semantics is not properly motivated. The second objection says that even if it is, LEM still implies bivalence. I show that LEM does not imply bivalence in a supervaluational language. I also argue that considering supertruth as truth can be reasonably motivated.     

Truth in Applicative Theories

We give a survey on truth theories for applicative theories. It comprises Frege structures, universes for Frege structures, and a theory of supervaluation. We present the proof-theoretic results for these theories and show their syntactical expressive power. In particular, we present as a novelty a syntactical interpretation of ID₁ in a applicative truth theory based on supervaluation.     

On the Algebraizability of the Implicational Fragment of Abelian Logic

In this paper we consider the implicational fragment of Abelian logic \({{{\sf A}_{\rightarrow}}}\) . We show that although the Abelian groups provide an semantics for the set of theorems of \({{{\sf A}_{\rightarrow}}}\) they do not for the associated consequence relation. We then show that the consequence relation is not algebraizable in the sense of Blok and Pigozzi (Mem Am Math Soc 77, 1989). In the second part of the paper, we investigate an extension of \({{{\sf A}_{\rightarrow}}}\) in the same language and having the same set of theorems and show that this new consequence relation is algebraizable with the Abelian groups as its equivalent algebraic semantics. Finally, we show that although \({{{\sf A}_{\rightarrow}}}\) is not algebraizable, it is order-algebraizable in the sense of Raftery (Ann Pure Appl Log 164:251–283, 2013).     

Pinning down polysemy: A formalisation for a Brazilian Portuguese preposition

This paper presents a formal definition for a number of distinct cases where the preposition “em” (in) can be applied in Brazilian Portuguese. The aim of this work is to establish a mathematical model using qualitative spatial reasoning formalisms within the idea of precisification from supervaluation semantics. Our long term goal is to implement this model into artificial intelligent systems to allow for seamless communication with humans in a common speech.     

Nelson's Negation on the Base of Weaker Versions of Intuitionistic Negation

Constructive logic with Nelson negation is an extension of the intuitionistic logic with a special type of negation expressing some features of constructive falsity and refutation by counterexample. In this paper we generalize this logic weakening maximally the underlying intuitionistic negation. The resulting system, called subminimal logic with Nelson negation, is studied by means of a kind of algebras called generalized N-lattices. We show that generalized N-lattices admit representation formalizing the intuitive idea of refutation by means of counterexamples giving in this way a counterexample semantics of the logic in question and some of its natural extensions. Among the extensions which are near to the intuitionistic logic are the minimal logic with Nelson negation which is an extension of the Johansson's minimal logic with Nelson negation and its in a sense dual version — the co-minimal logic with Nelson negation. Among the extensions near to the classical logic are the well known 3-valued logic of Lukasiewicz, two 12-valued logics and one 48-valued logic. Standard questions for all these logics — decidability, Kripke-style semantics, complete axiomatizability, conservativeness are studied. At the end of the paper extensions based on a new connective of self-dual conjunction and an analog of the Lukasiewicz middle value ½ have also been considered.     

Identical Twins,Deduction Theorems,and Pattern Functions: Exploring the Implicative BCSK Fragment of S5

We recapitulate (Section 1) some basic details of the system of implicative BCSK logic, which has two primitive binary implicational connectives, and which can be viewed as a certain fragment of the modal logic S5. From this modal perspective we review (Section 2) some results according to which the pure sublogic in either of these connectives (i.e., each considered without the other) is an exact replica of the material implication fragment of classical propositional logic. In Sections 3 and 5 we show that for the pure logic of one of these implicational connectives two – in general distinct – consequence relations (global and local) definable in the Kripke semantics for modal logic turn out to coincide, though this is not so for the pure logic of the other connective, and that there is an intimate relation between formulas constructed by means of the former connective and the local consequence relation. (Corollary 5.8. This, as we show in an Appendix, is connected to the fact that the ‘propositional operations’ associated with both of our implicational connectives are close to being what R. Quackenbush has called pattern functions.) Between these discussions Section 4 examines some of the replacement-of-equivalents properties of the two connectives, relative to these consequence relations, and Section 6 closes with some observations about the metaphor of identical twins as applied to such pairs of connectives.     

A Closer Look at Manifest Consequence

Fine (2007) argues that Frege’s puzzle and its relatives demonstrate a need for a basic reorientation of the field of semantics. According to this reorientation, the domain of semantic facts would be closed not under the classical consequence relation but only under a stronger relation Fine calls “manifest consequence.” I examine Fine’s informally sketched analyses of manifest consequence, showing that each can be amended to determine a class of strong consequence relations. A best candidate relation emerges from each of the two classes, and I prove that the two candidates extensionally coincide. The resulting consequence relation is of independent interest, for it might be held to constitute a cogent standard of reasoning that proceeds under a deficient grasp on the identity of objects.     

Squares in Fork Arrow Logic

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares.     

Directions in generalized quantifier theory

We give a condensed survey of recent research on generalized quantifiers in logic, linguistics and computer science, under the following headings: Logical definability and expressive power, Polyadic quantifiers and linguistic definability, Weak semantics and axiomatizability, Computational semantics, Quantifiers in dynamic settings, Quantifiers and modal logic, Proof theory of generalized quantifiers.This paper was inspired by the symposium on Generalized Quantifiers held at the 5th European Summer School in Logic, Language and Information in Lisbon, August 1993. We feel that the work presented there motivates a survey of recent research areas and research problems in the field of generalized quantifiers. The speakers at the symposium, Natasha Alechina, Jaap van der Does, Lauri Hella, Michal Krynicki, Michiel van Lambalgen, Kerkko Luosto, Marcin Mostowski, and Jouko Väänänen, have cooperated and made (oral and/or written) contributions and comments to this research survey which we gratefully acknowledge, and without which it would not have been written. But it is easier to produce a paper with two authors than with ten, and so the present authors take full responsibility for the final formulation of the paper. In addition, we are grateful for comments received from some further colleagues, in particular, Dorit Ben-Shalom, Makoto Kanazawa, Victor Sanchez, Yde Venema and two anonymous referees.Presented byJan Zygmunt     

On Intermediate Predicate Logics of some Finite Kripke Frames,I. Levelwise Uniform Trees

An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.     

Truth, Dependence and Supervaluation: Living with the Ghost

In J Philos Logic 34:155–192, 2005, Leitgeb provides a theory of truth which is based on a theory of semantic dependence. We argue here that the conceptual thrust of this approach provides us with the best way of dealing with semantic paradoxes in a manner that is acceptable to a classical logician. However, in investigating a problem that was raised at the end of J Philos Logic 34:155–192, 2005, we discover that something is missing from Leitgeb’s original definition. Moreover, we show that once the appropriate repairs have been made, the resultant definition is equivalent to a version of the supervaluation definition suggested in J Philos 72:690–716, 1975 and discussed in detail in J Symb Log 51(3):663–681, 1986. The upshot of this is a philosophical justification for the simple supervaluation approach and fresh insight into its workings.     

Obligation as Optimal Goal Satisfaction

Formalising deontic concepts, such as obligation, prohibition and permission, is normally carried out in a modal logic with a possible world semantics, in which some worlds are better than others. The main focus in these logics is on inferring logical consequences, for example inferring that the obligation O q is a logical consequence of the obligations O p and O (p → q). In this paper we propose a non-modal approach in which obligations are preferred ways of satisfying goals expressed in first-order logic. To say that p is obligatory, but may be violated, resulting in a less than ideal situation s, means that the task is to satisfy the goal p ∨ s, and that models in which p is true are preferred to models in which s is true. Whereas, in modal logic, the preference relation between possible worlds is part of the semantics of the logic, in this non-modal approach, the preference relation between first-order models is external to the logic. Although our main focus is on satisfying goals, we also formulate a notion of logical consequence, which is comparable to the notion of logical consequence in modal deontic logic. In this formalisation, an obligation O p is a logical consequence of goals G, when p is true in all best models of G. We show how this non-modal approach to the treatment of deontic concepts deals with problems of contrary-to-duty obligations and normative conflicts, and argue that the approach is useful for many other applications, including abductive explanations, defeasible reasoning, combinatorial optimisation, and reactive systems of the production system variety.     

A concept approach to input/output logic

This paper provides a semantics for input/input output logic based on formal concept analysis. The central result shows that an input/output logic axiomatised by a relation R is the same as the logic induced by deriving pairs from the concept lattice generated by R using a ∧- and ∨-classical Scott consequence relation. This correspondence offers powerful analytical techniques for classifying, visualising and analysing input/output relations, revealing implicit hierarchical structure and/or natural clusterings and dependencies. The application of all formal developments are illustrated by a worked example towards the end.     

Preferential Semantics using Non-smooth Preference Relations

This paper studies the properties of eight semantic consequence relations defined from a Tarski-logic L and a preference relation ? . They are equivalent to Shoham’s so-called preferential entailment for smooth model structures, but avoid certain problems of the latter in non-smooth configurations. Each of the logics can be characterized in terms of what we call multi-selection semantics. After discussing this type of semantics, we focus on some concrete proposals from the literature, checking a number of meta-theoretic properties and elaborating on their intuitive motivation. As it turns out, many of their meta-properties only hold in case ? is transitive. To tackle this problem, we propose slight modifications of each of the systems, showing the resulting logics to behave better at the intuitive level and in metatheoretic terms, for arbitrary ? .     

Inexact Knowledge with Introspection

Standard Kripke models are inadequate to model situations of inexact knowledge with introspection, since positive and negative introspection force the relation of epistemic indiscernibility to be transitive and euclidean. Correlatively, Williamson’s margin for error semantics for inexact knowledge invalidates axioms 4 and 5. We present a new semantics for modal logic which is shown to be complete for K45, without constraining the accessibility relation to be transitive or euclidean. The semantics corresponds to a system of modular knowledge, in which iterated modalities and simple modalities are not on a par. We show how the semantics helps to solve Williamson’s luminosity paradox, and argue that it corresponds to an integrated model of perceptual and introspective knowledge that is psychologically more plausible than the one defended by Williamson. We formulate a generalized version of the semantics, called token semantics, in which modalities are iteration-sensitive up to degree n and insensitive beyond n. The multi-agent version of the semantics yields a resource-sensitive logic with implications for the representation of common knowledge in situations of bounded rationality.     

An Institution-independent Proof of Craig Interpolation Theorem

We formulate a general institution-independent (i.e. independent of the details of the actual logic formalised as institution) version of the Craig Interpolation Theorem and prove it in dependence of Birkhoff-style axiomatizability properties of the actual logic.We formalise Birkhoff-style axiomatizability within the general abstract model theoretic framework of institution theory by the novel concept of Birkhoff institution.Our proof destills a set of conditons behind the Craig Interpolation Property, which are easy to establish in the applications. Together with the generality of our approach, this leads to a wide range of applications for our result, including conventional and non-conventional logics (many of them from algebraic specification theory), such as general algebra, classical model theory, partial algebra, rewriting logic, membership algebra, etc. all of them in various versions and with various types of sentences (including infinitary ones). In dependence of axiomatizability properties many other applications are expected for various institutions or logics.