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.     

Iterative and fixed point common belief

We define infinitary extensions to classical epistemic logic systems, and add also a common belief modality, axiomatized in a finitary, fixed-point manner. In the infinitary K system, common belief turns to be provably equivalent to the conjunction of all the finite levels of mutual belief. In contrast, in the infinitary monotonic system, common belief implies every transfinite level of mutual belief but is never implied by it. We conclude that the fixed- point notion of common belief is more powerful than the iterative notion of common belief.     

Extension Properties and Subdirect Representation in Abstract Algebraic Logic

This paper continues the investigation, started in Lávi?ka and Noguera (Stud Log 105(3): 521–551, 2017), of infinitary propositional logics from the perspective of their algebraic completeness and filter extension properties in abstract algebraic logic. If follows from the Lindenbaum Lemma used in standard proofs of algebraic completeness that, in every finitary logic, (completely) intersection-prime theories form a basis of the closure system of all theories. In this article we consider the open problem of whether these properties can be transferred to lattices of filters over arbitrary algebras of the logic. We show that in general the answer is negative, obtaining a richer hierarchy of pairwise different classes of infinitary logics that we separate with natural examples. As by-products we obtain a characterization of subdirect representation for arbitrary logics, develop a fruitful new notion of natural expansion, and contribute to the understanding of semilinear logics.     

Infinitary Belief Revision

This paper extends the AGM theory of belief revision to accommodate infinitary belief change. We generalize both axiomatization and modeling of the AGM theory. We show that most properties of the AGM belief change operations are preserved by the generalized operations whereas the infinitary belief change operations have their special properties. We prove that the extended axiomatic system for the generalized belief change operators with a Limit Postulate properly specifies infinite belief change. This framework provides a basis for first-order belief revision and the theory of revising a belief state by a belief state.     

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.     

Quantum Logic in Intuitionistic Perspective

In their seminal paper Birkhoff and von Neumann revealed the following dilemma:[ ] whereas for logicians the orthocomplementation properties of negation were the ones least able to withstand a critical analysis, the study of mechanics points to the distributive identities as the weakest link in the algebra of logic.In this paper we eliminate this dilemma, providing a way for maintaining both. Via the introduction of the "missing" disjunctions in the lattice of properties of a physical system while inheriting the meet as a conjunction we obtain a complete Heyting algebra of propositions on physical properties. In particular there is a bijective correspondence between property lattices and propositional lattices equipped with a so called operational resolution, an operation that exposes the properties on the level of the propositions. If the property lattice goes equipped with an orthocomplementation, then this bijective correspondence can be refined to one with propositional lattices equipped with an operational complementation, as such establishing the claim made above. Formally one rediscovers via physical and logical considerations as such respectively a specification and a refinement of the purely mathematical result by Bruns and Lakser (1970) on injective hulls of meet-semilattices. From our representation we can derive a truly intuitionistic functional implication on property lattices, as such confronting claims made in previous writings on the matter. We also make a detailed analysis of disjunctivity vs. distributivity and finitary vs. infinitary conjunctivity, we briefly review the Bruns-Lakser construction and indicate some questions which are left open.     

From Modal Discourse to Possible Worlds

The possible-worlds semantics for modality says that a sentence is possibly true if it is true in some possible world. Given classical prepositional logic, one can easily prove that every consistent set of propositions can be embedded in a ‘maximal consistent set’, which in a sense represents a possible world. However the construction depends on the fact that standard modal logics are finitary, and it seems false that an infinite collection of sets of sentences each finite subset of which is intuitively ‘possible’ in natural language has the property that the whole set is possible. The argument of the paper is that the principles needed to shew that natural language possibility sentences involve quantification over worlds are analogous to those used in infinitary modal logic.     

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     

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.     

On quasivarieties and varieties as categories

Finitary quasivarieties are characterized categorically by the existence of colimits and of an abstractly finite, regularly projective regular generator G. Analogously, infinitary quasivarieties are characterized: one drops the assumption that G be abstractly finite. For (finitary) varieties the characterization is similar: the regular generator is assumed to be exactly projective, i.e., hom(G, –) is an exact functor. These results sharpen the classical characterization theorems of Lawvere, Isbell and other authors.Supported by the Czech Grant Agency (Project 201/02/0148).Special issue of Studia Logica: Algebraic Theory of Quasivarieties Presented by M. E. Adams, K. V. Adaricheva, W. Dziobiak, and A. V. Kravchenko     

Continuity in Semantic Theories of Programming

Continuity is perhaps the most familiar characterization of the finitary character of the operations performed in computation. We sketch the historical and conceptual development of this notion by interpreting it as a unifying theme across three main varieties of semantical theories of programming: denotational, axiomatic and event-based. Our exploration spans the development of this notion from its origins in recursion theory to the forms it takes in the context of the more recent event-based analyses of sequential and concurrent computations, touching upon the relations of continuity with non-determinism.     

Game logic and its applications I

This paper provides a logic framework for investigations of game theoretical problems. We adopt an infinitary extension of classical predicate logic as the base logic of the framework. The reason for an infinitary extension is to express the common knowledge concept explicitly. Depending upon the choice of axioms on the knowledge operators, there is a hierarchy of logics. The limit case is an infinitary predicate extension of modal propositional logic KD4, and is of special interest in applications. In Part I, we develop the basic framework, and show some applications: an epistemic axiomatization of Nash equilibrium and formal undecidability on the playability of a game. To show the formal undecidability, we use a term existence theorem, which will be proved in Part II.The authors thank Hiroakira Ono for helpful discussions and encouragements from the early stage of this research project, and Philippe Mongin, Mitio Takano and a referee of this journal for comments on earlier versions of this paper. The first and second authors are partially supported, respectively, by Tokyo Center of Economic Research and Grant-in-Aids for Scientific Research 04640215, Ministry of Education, Science and Culture.Presented by H. Ono     

Contraction,Infinitary Quantifiers,and Omega Paradoxes

Our main goal is to investigate whether the infinitary rules for the quantifiers endorsed by Elia Zardini in a recent paper are plausible. First, we will argue that they are problematic in several ways, especially due to their infinitary features. Secondly, we will show that even if these worries are somehow dealt with, there is another serious issue with them. They produce a truth-theoretic paradox that does not involve the structural rules of contraction.     

A Theory of Infinitary Relations Extending Zermelo’s Theory of Infinitary Propositions

An idea attributable to Russell serves to extend Zermelo’s theory of systems of infinitely long propositions to infinitary relations. Specifically, relations over a given domain \({\mathfrak{D}}\) of individuals will now be identified with propositions over an auxiliary domain \({\mathfrak{D}^{\mathord{\ast}}}\) subsuming \({\mathfrak{D}}\). Three applications of the resulting theory of infinitary relations are presented. First, it is used to reconstruct Zermelo’s original theory of urelements and sets in a manner that achieves most, if not all, of his early aims. Second, the new account of infinitary relations makes possible a concise characterization of parametric definability with respect to a purely relational structure. Finally, based on his foundational philosophy of the primacy of the infinite, Zermelo rejected Gödel’s First Incompleteness Theorem; it is shown that the new theory of infinitary relations can be brought to bear, positively, in that connection as well.     

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     

Contextual Deduction Theorems

Logics that do not have a deduction-detachment theorem (briefly, a DDT) may still possess a contextual DDT??a syntactic notion introduced here for arbitrary deductive systems, along with a local variant. Substructural logics without sentential constants are natural witnesses to these phenomena. In the presence of a contextual DDT, we can still upgrade many weak completeness results to strong ones, e.g., the finite model property implies the strong finite model property. It turns out that a finitary system has a contextual DDT iff it is protoalgebraic and gives rise to a dually Brouwerian semilattice of compact deductive filters in every finitely generated algebra of the corresponding type. Any such system is filter distributive, although it may lack the filter extension property. More generally, filter distributivity and modularity are characterized for all finitary systems with a local contextual DDT, and several examples are discussed. For algebraizable logics, the well-known correspondence between the DDT and the equational definability of principal congruences is adapted to the contextual case.     

Higher-Order Contingentism,Part 3: Expressive Limitations

Two expressive limitations of an infinitary higher-order modal language interpreted on models for higher-order contingentism – the thesis that it is contingent what propositions, properties and relations there are – are established: First, the inexpressibility of certain relations, which leads to the fact that certain model-theoretic existence conditions for relations cannot equivalently be reformulated in terms of being expressible in such a language. Second, the inexpressibility of certain modalized cardinality claims, which shows that in such a language, higher-order contingentists cannot express what is communicated using various instances of talk of ‘possible things’, such as ‘there are uncountably many possible stars’.     

Extensions of the Finitist Point of View

Hilbert developed his famous finitist point of view in several essays in the 1920s. In this paper, we discuss various extensions of it, with particular emphasis on those suggested by Hilbert and Bernays in Grundlagen der Mathematik (vol. I 1934, vol. II 1939). The paper is in three sections. The first deals with Hilbert's introduction of a restricted ω -rule in his 1931 paper ‘Die Grundlegung der elementaren Zahlenlehre’. The main question we discuss here is whether the finitist (meta-)mathematician would be entitled to accept this rule as a finitary rule of inference. In the second section, we assess the strength of finitist metamathematics in Hilbert and Bernays 1934. The third and final section is devoted to the second volume of Grundlagen der Mathematik. For preparatory reasons, we first discuss Gentzen's proposal of expanding the range of what can be admitted as finitary in his esssay ‘Die Widerspruchsfreiheit der reinen Zahlentheorie’ (1936). As to Hilbert and Bernays 1939, we end on a ‘critical’ note: however considerable the impact of this work may have been on subsequent developments in metamathematics, there can be no doubt that in it the ideals of Hilbert's original finitism have fallen victim to sheer proof-theoretic pragmatism.     

Definability of Leibniz Equality

Given a structure for a first-order language L, two objects of its domain can be indiscernible relative to the properties expressible in L, without using the equality symbol, and without actually being the same. It is this relation that interests us in this paper. It is called Leibniz equality. In the paper we study systematically the problem of its definibility mainly for classes of structures that are the models of some equality-free universal Horn class in an infinitary language L_κκ, where κ is an infinite regular cardinal. This revised version was published online in June 2006 with corrections to the Cover Date.