A Map of Common Knowledge Logics

In order to capture the concept of common knowledge, various extensions of multi-modal epistemic logics, such as fixed-point ones and infinitary ones, have been proposed. Although we have now a good list of such proposed extensions, the relationships among them are still unclear. The purpose of this paper is to draw a map showing the relationships among them. In the propositional case, these extensions turn out to be all Kripke complete and can be comparable in a meaningful manner. F. Wolter showed that the predicate extension of the Halpern-Moses fixed-point type common knowledge logic is Kripke incomplete. However, if we go further to an infinitary extension, Kripke completeness would be recovered. Thus there is some gap in the predicate case. In drawing the map, we focus on what is happening around the gap in the predicate case. The map enables us to better understand the common knowledge logics as a whole.     

Partial isomorphisms and intuitionistic logic

A game for testing the equivalence of Kripke models with respect to finitary and infinitary intuitionistic predicate logic is introduced and applied to discuss a concept of categoricity for intuitionistic theories.     

Partially Interpreted Relations and Partially Interpreted Quantifiers

Logics in which a relation R is semantically incomplete in a particular universe E, i.e. the union of the extension of R with its anti-extension does not exhaust the whole universe E, have been studied quite extensively in the last years. (Cf. van Benthem (1985), Blamey (1986), and Langholm (1988), for partial predicate logic; Muskens (1996), for the applications of partial predicates to formal semantics, and Doherty (1996) for applications to modal logic.) This is not so with semantically incomplete generalized quantifiers which constitute the subject of the present paper. The only systematic study of these quantifiers from a purely logical point of view, is, to the best of my knowledge, that by van Eijck (1995). We shall take here a different approach than that of van Eijck and mention some of the abstract properties of the resulting logic. Finally we shall prove that the two approaches are interdefinable.     

An Institution-Independent Proof of the Robinson Consistency Theorem

We prove an institutional version of A. Robinson’s Consistency Theorem. This result is then appliedto the institution of many-sorted first-order predicate logic and to two of its variations, infinitary and partial, obtaining very general syntactic criteria sufficient for a signature square in order to satisfy the Robinson consistency and Craig interpolation properties. Presented by Robert Goldblatt     

Truth,Partial Logic and Infinitary Proof Systems

In this paper we apply proof theoretic methods used for classical systems in order to obtain upper bounds for systems in partial logic. We focus on a truth predicate interpreted in a Kripke style way via strong Kleene; whereas the aim is to connect harmoniously the partial version of Kripke–Feferman with its intended semantics. The method we apply is based on infinitary proof systems containing an \(\omega \)-rule.     

On the Proof Theory of the Modal mu-Calculus

We study the proof-theoretic relationship between two deductive systems for the modal mu-calculus. First we recall an infinitary system which contains an omega rule allowing to derive the truth of a greatest fixed point from the truth of each of its (infinitely many) approximations. Then we recall a second infinitary calculus which is based on non-well-founded trees. In this system proofs are finitely branching but may contain infinite branches as long as some greatest fixed point is unfolded infinitely often along every branch. The main contribution of our paper is a translation from proofs in the first system to proofs in the second system. Completeness of the second system then follows from completeness of the first, and a new proof of the finite model property also follows as a corollary. Presented by Heinrich Wansing     

Constructive Logic with Strong Negation is a Substructural Logic. I

The goal of this two-part series of papers is to show that constructive logic with strong negation N is definitionally equivalent to a certain axiomatic extension NFL _ew of the substructural logic FL _ew . In this paper, it is shown that the equivalent variety semantics of N (namely, the variety of Nelson algebras) and the equivalent variety semantics of NFL _ew (namely, a certain variety of FL _ew -algebras) are term equivalent. This answers a longstanding question of Nelson [30]. Extensive use is made of the automated theorem-prover Prover9 in order to establish the result. The main result of this paper is exploited in Part II of this series [40] to show that the deductive systems N and NFL _ew are definitionally equivalent, and hence that constructive logic with strong negation is a substructural logic over FL _ew . Presented by Heinrich Wansing     

Constructing a continuum of predicate extensions of each intermediate propositional logic

Wajsberg and Jankov provided us with methods of constructing a continuum of logics. However, their methods are not suitable for super-intuitionistic and modal predicate logics. The aim of this paper is to present simple ways of modification of their methods appropriate for such logics. We give some concrete applications as generic examples. Among others, we show that there is a continuum of logics (1) between the intuitionistic predicate logic and the logic of constant domains, (2) between a predicate extension ofS4 andS4 with the Barcan formula. Furthermore, we prove that (3) there is a continuum of predicate logics with equality whose equality-free fragment is just the intuitionistic predicate logic.Dedicated to the memory of the late Professor S. MaeharaThis research was supported in part by Grant-in Aid for Encouragement of Young Scientists No. 06740140, Ministry of Education, Science and Culture, Japan.Presented byHiroakira Ono     

Nonmonotonic reasoning: from finitary relations to infinitary inference operations

A. Tarski [22] proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations is inspired by the results of [12] on nonmonotonic inference relations, and relies on some of the definitions found there.This work was partially supported by a grant from the Basic Research Foundation, Israel Academy of Sciences and Humanities and by the Jean and Helene Alfassa fund for research in Artificial Intelligence. Its final write-up was performed while the second author visited the Laboratoire d'Informatique Théorique et de Programmation, Université Paris 6.Presented byDov M. Gabbay     

Dialektik Und Formalisierung

Dialectics and Formalization. In an appendix to his article Can the concept of dialectic be made clear? (JGPS 27: 131–165) the author critically examined an attempt by D. Wandschneider of reconstructing Hegelian dialectical logic by displaying antinomic structures. The main steps of this reconstruction were formalized within the framework of second order predicate logic. In his reply (JGPS 27: 347–352) Wandschneider argues that formalization is the wrong way of interpreting and judging his reconstruction project on the ground that the understanding of predication is already presupposed by predicate logic and, therefore, cannot be formalized. In the present contribution it is shown that Wandschneider's criticism is based on a fundamentally mistaken conception of formalization and formal logic and that the problems posed by his project remain completely unresolved.     

Constructive Logic with Strong Negation is a Substructural Logic. II

The goal of this two-part series of papers is to show that constructive logic with strong negation N is definitionally equivalent to a certain axiomatic extension NFL _ew of the substructural logic FL _ew . The main result of Part I of this series [41] shows that the equivalent variety semantics of N (namely, the variety of Nelson algebras) and the equivalent variety semantics of NFL _ew (namely, a certain variety of FL _ew -algebras) are term equivalent. In this paper, the term equivalence result of Part I [41] is lifted to the setting of deductive systems to establish the definitional equivalence of the logics N and NFL _ew . It follows from the definitional equivalence of these systems that constructive logic with strong negation is a substructural logic. Presented by Heinrich Wansing     

On structural completeness of implicational logics

We consider the notion of structural completeness with respect to arbitrary (finitary and/or infinitary) inferential rules. Our main task is to characterize structurally complete intermediate logics. We prove that the structurally complete extension of any pure implicational in termediate logic C can be given as an extension of C with a certain family of schematically denned infinitary rules; the same rules are used for each C. The cardinality of the family is continuum and, in the case of (the pure implicational fragment of) intuitionistic logic, the family cannot be reduced to a countable one. It means that the structurally complete extension of the intuitionistic logic is not countably axiomatizable by schematic rules.This work was supported by the Polish Academy of Sciences, CPBP 08.15, Struktura logiczna rozumowa niesformalizowanych.     

Eine Auch Sich Selbst Missverstehende Kritik: Über das Reflexionsdefizit Formaler Explikationen

The criticism formulated by L. B. Puntel concerning the theory of dialectic proposed by the author is rejected. Puntel's attempt at explicating predication by means of (second order) predicate logic fails: It misjudges predication being already presupposed for the possibility of predicate logic, thus belonging to the transcendental conditions of formal predicate logic, so that predication itself cannot be further explicated by means of such logic. What is in fact criticized by Puntel is something like an artefact of formalization. The unreflected application of formal logic here generates problems instead of solving them.     

Deontic Interpreted Systems

We investigate an extension of the formalism of interpreted systems by Halpern and colleagues to model the correct behaviour of agents. The semantical model allows for the representation and reasoning about states of correct and incorrect functioning behaviour of the agents, and of the system as a whole. We axiomatise this semantic class by mapping it into a suitable class of Kripke models. The resulting logic, KD45_n ^i-j, is a stronger version of KD, the system often referred to as Standard Deontic Logic. We extend this formal framework to include the standard epistemic notions defined on interpreted systems, and introduce a new doubly-indexed operator representing the knowledge that an agent would have if it operates under the assumption that a group of agents is functioning correctly. We discuss these issues both theoretically and in terms of applications, and present further directions of work.     

Existence,Negation, and Abstraction in the Neoplatonic Hierarchy 1

The paper is a study of the logic of existence, negation, and order in the Neoplatonic tradition. The central idea is that Neoplatonists assume a logic in which the existence predicate is a comparative adjective and in which monadic predicates function as scalar adjectives that nest the background order. Various scalar predicate negations are then identifiable with various Neoplatonic negations, including a privative negation appropriate for the lower orders of reality and a hyper-negation appropriate for the higher. Reversion to the One can then be explained as the logical inference of hyper-negations from mundane knowledge. Part I develops the relevant linguistic and logical theory, and Part II defends Wolfson and the scalar interpretation against the more traditional Aristotelian understanding of Whittaker and others of reversion as intensional abstraction     

Incompleteness and the Barcan formula

A (normal) system of prepositional modal logic is said to be complete iff it is characterized by a class of (Kripke) frames. When we move to modal predicate logic the question of completeness can again be raised. It is not hard to prove that if a predicate modal logic is complete then it is characterized by the class of all frames for the propositional logic on which it is based. Nor is it hard to prove that if a propositional modal logic is incomplete then so is the predicate logic based on it. But the interesting question is whether a complete propositional modal logic can have an incomplete extension. In 1967 Kripke announced the incompleteness of a predicate extension of S4. The purpose of the present article is to present several such systems. In the first group it is the systemswith the Barcan Formula which are incomplete, while those without are complete. In the second group it is thosewithout the Barcan formula which are incomplete, while those with the Barcan Formula are complete. But all these are based on propositional systems which are characterized by frames satisfying in each case a single first-order sentence.     

Truth,Predication and a Family of Contingent Paradoxes

In truth theory one aims at general formal laws governing the attribution of truth to statements. Gupta’s and Belnap’s revision-theoretic approach provides various well-motivated theories of truth, in particular T* and T#, which tame the Liar and related paradoxes without a Tarskian hierarchy of languages. In property theory, one similarly aims at general formal laws governing the predication of properties. To avoid Russell’s paradox in this area a recourse to type theory is still popular, as testified by recent work in formal metaphysics by Williamson and Hale. There is a contingent Liar that has been taken to be a problem for type theory. But this is because this Liar has been presented without an explicit recourse to a truth predicate. Thus, type theory could avoid this paradox by incorporating such a predicate and accepting an appropriate theory of truth. There is however a contingent paradox of predication that more clearly undermines the viability of type theory. It is then suggested that a type-free property theory is a better option. One can pursue it, by generalizing the revision-theoretic approach to predication, as it has been done by Orilia with his system P*, based on T*. Although Gupta and Belnap do not explicitly declare a preference for T# over T*, they show that the latter has some advantages, such as the recovery of intuitively acceptable principles concerning truth and a better reconstruction of informal arguments involving this notion. A type-free system based on T# rather than T* extends these advantages to predication and thus fares better than P* in the intended applications of property theory.

     

An Infinitary Extension of Jankov’s Theorem

It is known that for any subdirectly irreducible finite Heyting algebra A and any Heyting algebra B, A is embeddable into a quotient algebra of B, if and only if Jankov’s formula χ _A for A is refuted in B. In this paper, we present an infinitary extension of the above theorem given by Jankov. More precisely, for any cardinal number κ, we present Jankov’s theorem for homomorphisms preserving infinite meets and joins, a class of subdirectly irreducible complete κ-Heyting algebras and κ-infinitary logic, where a κ-Heyting algebra is a Heyting algebra A with # ≥  κ and κ-infinitary logic is the infinitary logic such that for any set Θ of formulas with # Θ ≥  κ, ∨Θ and ∧Θ are well defined formulas.     

On the Existence of Continua of Logics Between Some Intermediate Predicate Logics

A method for constructing continua of logics squeezed between some intermediate predicate logics, developed by Suzuki [8], is modified and applied to intervals of the form [L, L+ ¬¬S], where Lis a predicate logic, Sis a closed predicate formula. This solves one of the problems from Suzuki's paper.     

因果型连动结构的逻辑刻画

逻辑学以及形式语义学对汉语连动结构的研究一般都停留在一阶逻辑的层面上,即通过一阶逻辑中的形式化方法给出连动结构的形式化构造。但是在对不同类型连动结构进行更为深入的研究时,一阶逻辑这一工具就显的不够了。本文中,作者将以因果型连动结构为研究对象,利用一阶模态逻辑为其构建形式系统并尝试给出因果型连动结构和途径–目的型连动结构之间的区别和联系。