This paper is the first in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual (...) set-theoretic semantics so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with respect to (...) a version of the bundle semantics. (shrink)

The type of completeness Whitehead and Russell aimed for in their Principia Mathematica was what I call descriptive completeness. This is completeness with respect to the propositions that have been proved in traditional mathematics. The notion of completeness addressed by Gödel in his famous work of 1930 and 1931 was completeness with respect to the truths expressible in a given language. What are the relative significances of these different conceptions of completeness for traditional mathematics? (...) What, if any, effects does incompleteness of the type Gödel had in mind have for the evaluation of the Principia Mathematica project and other projects like it? (shrink)

This paper sets out a new way of combining Kripke-complete modal logics: lexicographic product. It discusses some basic properties of the lexicographic product construction and proves axiomatization/completeness results.

This paper is the first in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual (...) set-theoretic semantics so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

The standard axiomatization of quantum mechanics (QM) is not fully explicit about the role of the time-parameter. Especially, the time reference within the probability algorithm (the Born Rule, BR) is unclear. From a probability principle P1 and a second principle P2 affording a most natural way to make BR precise, a logical conflict with the standard expression for the completeness of QM can be derived. Rejecting P1 is implausible. Rejecting P2 leads to unphysical results and to a conflict with (...) a generalization of P2, a principle P3. All three principles are shown to be without alternative. It is thus shown that the standard expression of QM completeness must be revised. An absolutely explicit form of the axioms is provided, including a precise form of the projection postulate. An appropriate expression for QM completeness, reflecting the restrictions of the Gleason and Kochen-Specker theorems is proposed. (shrink)

In this paper we give a differential lifting principle which provides a general method to geometrically axiomatize the model companion (if it exists) of some theories of differential topological fields. The topological fields we consider here are in fact topological systems in the sense of van den Dries, and the lifting principle we develop is a generalization of the geometric axiomatization of the theory DCF₀ given by Pierce and Pillay. Moreover, it provides a geometric alternative to the axiomatizations obtained by (...) Tressl and Guzy/Point in separate papers where the authors also build general schemes of axioms for some model complete theories of differential fields. We first characterize the existentially closed models of a given theory of differential topological fields and then, under an additional hypothesis of largeness, we show how to modify this characterization to get a general scheme of first-order axioms for the model companion of any large theory of differential topological fields. We conclude with an application of this lifting principle proving that, in existentially closed models of a large theory of differential topological fields, the jet-spaces are dense in their ambient topological space. (shrink)

In previous works, we presented a modification of the usual possible world semantics by introducing an independent temporal structure in each world and using accessibility functions to represent the relation among them. Different properties ofthe accessibility functions have been considered and axiomatic systems which define these properties have been given. Only a few ofthese systems have been proved tobe complete. The aim ofthis paper is to make a progress in the study ofcompleteness for functional systems. For this end, we (...) use indexes as names for temporal flows and give new proofs of completeness. Specifically, we focus our attention on the system which defines injectivity, because the system which defines this property without using indexes was proved to be incomplete in previous works. The only system considered which remains incomplete is the one which defines surjectivity, even ifwe consider a sequence ofnatural extensions ofthe previous one. (shrink)

One of the important extensions of PDL is PDL with intersection of programs. We devote this paper to its complete axiomatization.

ABSTRACT We consider the question of the complete axiomatization of a relative modal logic with composition and intersection.

The paper studies the containment companion of a logic \. This consists of the consequence relation \ which satisfies all the inferences of \, where the variables of the conclusion are contained into those of the set of premises, in case this is not inconsistent. In accordance with the work started in [10], we show that a different generalization of the Płonka sum construction, adapted from algebras to logical matrices, allows to provide a matrix-based semantics for containment logics. In particular, (...) we provide an appropriate completeness theorem for a wide family of containment logics, and we show how to produce a complete Hilbert style axiomatization. (shrink)

The present note is a reworking and streamlining of Daigneault and Monk's Representation Theory for Polyadic Algebras. MSC: 03G15.

Dynamic Topological Logic (DFH) is a multimodal system for reasoning about dynamical systems. It is defined semantically and, as such, most of the work done in the field has been model-theoretic. In particular, the problem of finding a complete axiomatization for the full language of DFH over the class of all dynamical systems has proven to be quite elusive. Here we propose to enrich the language to include a polyadic topological modality, originally introduced by Dawar and Otto in a different (...) context. We then provide a sound axiomatization for DFH over this extended language, and prove that it is complete. The polyadic modality is used in an essential way in our proof. (shrink)

In the literature, different axiomatizations of Public Announcement Logic (PAL) have been proposed. Most of these axiomatizations share a “core set” of the so-called “reduction axioms”. In this paper, by designing non-standard Kripke semantics for the language of PAL, we show that the proof system based on this core set of axioms does not completely axiomatize PAL without additional axioms and rules. In fact, many of the intuitive axioms and rules we took for granted could not be derived from the (...) core set. Moreover, we also propose and advocate an alternative yet meaningful axiomatization of PAL without the reduction axioms. The completeness is proved directly by a detour method using the canonical model where announcements are treated as merely labels for modalities as in normal modal logics. This new axiomatization and its completeness proof may sharpen our understanding of PAL and can be adapted to other dynamic epistemic logics. (shrink)

The monoidal t-norm based logic MTL is obtained from Hájek''s Basic Fuzzy logic BL by dropping the divisibility condition for the strong (or monoidal) conjunction. Recently, Jenei and Montgana have shown MTL to be standard complete, i.e. complete with respect to the class of residuated lattices in the real unit interval [0,1] defined by left-continuous t-norms and their residua. Its corresponding algebraic semantics is given by pre-linear residuated lattices. In this paper we address the issue of standard and rational (...) class='Hi'>completeness (rational completeness meaning completeness with respect to a class of algebras in the rational unit interval [0,1]) of some important axiomatic extensions of MTL corresponding to well-known parallel extensions of BL. Moreover, we investigate varieties of MTL algebras whose linearly ordered countable algebras embed into algebras whose lattice reduct is the real and/or the rational interval [0,1]. These embedding properties are used to investigate finite strong standard and/or rational completeness of the corresponding logics. (shrink)

Betweenness as a relation between three individual points has been widely studied in geometry and axiomatized by several authors in different contexts. The article proposes a more general notion of betweenness as a relation between three sets of points. The main technical result is a sound and complete logical system describing universal properties of this relation between sets of vertices of a graph.

Substructural logics extending the full Lambek calculus FL have largely benefited from a systematical algebraic approach based on the study of their algebraic counterparts: residuated lattices. Recently, a nonassociative generalization of FL has been studied by Galatos and Ono as the logic of lattice-ordered residuated unital groupoids. This paper is based on an alternative Hilbert-style presentation for SL which is almost MP -based. This presentation is then used to obtain, in a uniform way applicable to most substructural logics, a form (...) of local deduction theorem, description of filter generation, and proper forms of generalized disjunctions. A special stress is put on semilinear substructural logics. Axiomatizations of the weakest semilinear logic over SL and other prominent substructural logics are provided and their completeness with respect to chains defined over the real unit interval is proved. (shrink)

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators (...) is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

The modern notion of the axiomatic method developed as a part of the conceptualization of mathematics starting in the nineteenth century. The basic idea of the method is the capture of a class of structures as the models of an axiomatic system. The mathematical study of such classes of structures is not exhausted by the derivation of theorems from the axioms but includes normally the metatheory of the axiom system. This conception of axiomatization satisfies the crucial requirement that (...) the derivation of theorems from axioms does not produce new information in the usual sense of the term called depth information. It can produce new information in a different sense of information called surface information. It is argued in this paper that the derivation should be based on a model-theoretical relation of logical consequence rather than derivability by means of mechanical (recursive) rules. Likewise completeness must be understood by reference to a model-theoretical consequence relation. A correctly understood notion of axiomatization does not apply to purely logical theories. In the latter the only relevant kind of axiomatization amounts to recursive enumeration of logical truths. First-order “axiomatic” set theories are not genuine axiomatizations. The main reason is that their models are structures of particulars, not of sets. Axiomatization cannot usually be motivated epistemologically, but it is related to the idea of explanation. (shrink)

A certain type of inference rules in modal logics, generalizing Gabbay's Irreflexivity rule, is introduced and some general completeness results about modal logics axiomatized with such rules are proved.

We provide a complete axiomatization of modal inclusion logic—team-based modal logic extended with inclusion atoms. We review and refine an expressive completeness and normal form theorem for the logic, define a natural deduction proof system, and use the normal form to prove completeness of the axiomatization. Complete axiomatizations are also provided for two other extensions of modal logic with the same expressive power as modal inclusion logic: one augmented with a might operator and the other with a single-world (...) variant of the might operator. (shrink)

In, a deontic logic is proposed which explicates the idea that a formulaφis obligatory if and only if it is the weakest permission. We give a sound and strongly complete, Hilbert style axiomatization for this logic. As a corollary, it is compact, contradicting earlier claims from Anglbergeret al.. In addition, we prove that our axiomatization is equivalent to Anglberger et al.’s infinitary proof system, and show that our results are robust w.r.t. certain changes in the underlying semantics.

In this paper, we introduce a logic based on team semantics, called $\mathbf {FOT} $, whose expressive power is elementary, i.e., coincides with first-order logic both on the level of sentences and (possibly open) formulas, and we also show that a sublogic of $\mathbf {FOT} $, called $\mathbf {FOT}^{\downarrow } $, captures exactly downward closed elementary (or first-order) team properties. We axiomatize completely the logic $\mathbf {FOT} $, and also extend the known partial axiomatization of dependence logic to dependence logic (...) enriched with the logical constants in $\mathbf {FOT}^{\downarrow } $. (shrink)

We give a sound and complete axiomatization for the full computation tree logic, CTL*, of R-generable models. This solves a long standing open problem in branching time temporal logic.

According to the analysis of concessive conditionals suggested by Crupi and Iacona, a concessive conditional $$p{{\,\mathrm{\hookrightarrow }\,}}q$$ p ↪ q is adequately formalized as a conjunction of conditionals. This paper presents a sound and complete axiomatic system for concessive conditionals so understood. The soundness and completeness proofs that will be provided rely on a method that has been employed by Raidl, Iacona, and Crupi to prove the soundness and completeness of an analogous system for evidential conditionals.

In this work, we study Hilbert-style proof systems for logics based on the data-aware language CoreDataXPath(↓) where the comparison relation between nodes is not necessarily an equivalence relation. We give a sound and complete axiomatization of the class of tree-like Kripke frames endowed with a general comparison relation between nodes. Modular extensions of this axiomatization are also discussed, including cases where the comparison relation is reflexive, symmetric, transitive and an equivalence. A notable highlight that we recover an axiomatization for CoreDataXPath(↓) (...) over any data-tree when the comparison is by ‘equal data’. Moreover, we prove that all these systems are decidable by leveraging the finite model property of their corresponding frame classes. (shrink)

We introduce two novel frameworks for choice under complete uncertainty. These frameworks employ intervals to represent uncertain utility attaching to outcomes. In the first framework, utility intervals arising from one act with multiple possible outcomes are aggregated via a set-based approach. In the second framework the aggregation of utility intervals employs multi-sets. On the aggregated utility intervals, we then introduce min–max decision rules and lexicographic refinements thereof. The main technical results are axiomatic characterizations of these min–max decision rules and (...) these refinements. We also briefly touch on the independence of introduced axioms. Furthermore, we show that such characterizations give rise to novel axiomatic characterizations of the well-known min–max decision rule?mnx?mnx in the classical framework of choice under complete uncertainty. (shrink)

Boolean connexive logic is an extension of Boolean logic that is closed under Modus Ponens and contains Aristotle’s and Boethius’ theses. According to these theses a sentence cannot imply its negation and the negation of a sentence cannot imply the sentence; and if the antecedent implies the consequent, then the antecedent cannot imply the negation of the consequent and if the antecedent implies the negation of the consequent, then the antecedent cannot imply the consequent. Such a logic was first introduced (...) by Jarmużek and Malinowski, by means of so-called relating semantics and tableau systems. Subsequently its modal extension was determined by means of the combination of possible-worlds semantics and relating semantics. In the following article we present axiomatic systems of some basic and modal Boolean connexive logics. Proofs of completeness will be carried out using canonical models defined with respect to maximal consistent sets. (shrink)

Trees with indistinguishability relations provide a semantics for a temporal language “composed by” the Peircean tense operators and the Ockhamist modal operator. In this paper, a finite axiomatization with a non standard rule for this language interpreted over bundled trees with indistinguishability relations is given. This axiomatization is proved to be sound and strongly complete.

In a recent paper Berto introduces a semantic system for a logic of imagination, intended as positive conceivability, and aboutness of imaginative acts. This system crucially adopts elements of both the semantics of conditionals and the semantics of analytical implications in order to account for the central logical traits of the notion of truth in an act of imagination based on an explicit input. The main problem left unsolved is to put forward a complete set of axioms for the proposed (...) system. In the present paper I offer a solution to this problem by providing a complete axiomatization of a generalization of the original semantics. The difficulty in proving completeness lies in the fact that the modalities that capture the notion of truth in an act of imagination are neither standard nor minimal, so that the construction of the canonical model and the proof of the truth lemma are to be substantially modified. (shrink)

In this work, we study Hilbert-style proof systems for logics based on the data-aware language CoreDataXPath(↓) where the comparison relation between nodes is not necessarily an equivalence relation. We give a sound and complete axiomatization of the class of tree-like Kripke frames endowed with a general comparison relation between nodes. Modular extensions of this axiomatization are also discussed, including cases where the comparison relation is reflexive, symmetric, transitive and an equivalence. A notable highlight that we recover an axiomatization for CoreDataXPath(↓) (...) over any data-tree when the comparison is by ‘equal data’. Moreover, we prove that all these systems are decidable by leveraging the finite model property of their corresponding frame classes. (shrink)

We formulate a Hilbert-style axiomatic system and a tableau calculus for the STIT-based logic of imagination recently proposed in Wansing. Completeness of the axiom system is shown by the method of canonical models; completeness of the tableau system is also shown by using standard methods.

An axiomatization is presented of the denotational semantics for first order language of Apt [1]. The goal is to obtain a rational reconstruction of the intuitions underlying this semantics. The axiomatization combines ideas about four valued logic with facts about substitutions. Soundness and completeness of the axiomatization are established. From the completeness proof a decision procedure is obtained that shows how four valued logic and order sensitivity of substitution together add up in a natural way to the denotational (...) semantics for the language of first order logic as proposed by Apt. (shrink)

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. (shrink)

Dependence logic, introduced in Väänänen [11], cannot be axiomatized. However, first-order consequences of dependence logic sentences can be axiomatized, and this is what we shall do in this paper. We give an explicit axiomatization and prove the respective Completeness Theorem.

This paper exhibits a general and uniform method to prove axiomatic completeness for certain modal fixpoint logics. Given a set Γ of modal formulas of the form γ, where x occurs only positively in γ, we obtain the flat modal fixpoint language by adding to the language of polymodal logic a connective γ for each γΓ. The term γ is meant to be interpreted as the least fixed point of the functional interpretation of the term γ. We consider (...) the following problem: given Γ, construct an axiom system which is sound and complete with respect to the concrete interpretation of the language on Kripke structures. We prove two results that solve this problem.First, let be the logic obtained from the basic polymodal by adding a Kozen–Park style fixpoint axiom and a least fixpoint rule, for each fixpoint connective γ. Provided that each indexing formula γ satisfies a certain syntactic criterion, we prove this axiom system to be complete.Second, addressing the general case, we prove the soundness and completeness of an extension of . This extension is obtained via an effective procedure that, given an indexing formula γ as input, returns a finite set of axioms and derivation rules for γ, of size bounded by the length of γ. Thus the axiom system is finite whenever Γ is finite. (shrink)

We give a Hilbert style axiomatization for the set of formulas in the temporal language with Until and Since which are valid over the real number flow of time. The axiomatization, which is orthodox in the sense of only having the usual temporal rules of inference, is complete with respect to single formulas.

We give a general account of the goals of axiomatization, introducing a variant on Detlefsen’s notion of ‘complete descriptive axiomatization’. We describe how distinctions between the Greek and modern view of number, magnitude, and proportion impact the interpretation of Hilbert’s axiomatization of geometry. We argue, as did Hilbert, that Euclid’s propositions concerning polygons, area, and similar triangles are derivable from Hilbert’s first-order axioms. We argue that Hilbert’s axioms including continuity show much more than the geometrical propositions of Euclid’s theorems and (...) thus are an immodest complete descriptive axiomatization of that subject. (shrink)

In this paper we consider the modal logic with both $$\Box$$ and $$\Diamond$$ arising from Kripke models with a crisp accessibility and whose propositions are valued over the standard Gödel algebra $$[0,1]_G$$. We provide an axiomatic system extending the one from Caicedo and Rodriguez (J Logic Comput 25(1):37–55, 2015) for models with a valued accessibility with Dunn axiom from positive modal logics, and show it is strongly complete with respect to the intended semantics. The axiomatizations of the (...) most usual frame restrictions are given too. We also prove that in the studied logic it is not possible to get $$\Diamond$$ as an abbreviation of $$\Box$$, nor vice-versa, showing that indeed the axiomatic system we present does not coincide with any of the mono-modal fragments previously axiomatized in the literature. (shrink)

We investigate under what conditions a given set of collective judgments can arise from a specific voting procedure. In order to answer this question, we introduce a language similar to modal logic for reasoning about judgment aggregation procedures. In this language, the formula expresses that is collectively accepted, or that is a group judgment based on voting. Different judgment aggregation procedures may be underlying the group decision making. Here we investigate majority voting, where holds if a majority of individuals accepts, (...) consensus voting, where holds if all individuals accept, and dictatorship. We provide complete axiomatizations for judgment sets arising from all three aggregation procedures. (shrink)