This paper presents a recent formalization of a Henkin-style completeness proof for the propositional modal logic S5 using the Lean theorem prover. The proof formalized is close to that of Hughes and Cresswell, but the system, based on a different choice of axioms, is better described as a Mendelson system augmented with axiom schemes for K, T, S4, and B, and the necessitation rule as a rule of inference. The language has the false and implication as the only primitive (...) logical connectives and necessity as the only primitive modal operator. The full source code is available online and has been typechecked with Lean 3.4.2. (shrink)

In this article, I argue that it is impossible to complete infinitely many tasks in a finite time. A key premise in my argument is that the only way to get to 0 tasks remaining is from 1 task remaining, when tasks are done 1-by-1. I suggest that the only way to deny this premise is by begging the question, that is, by assuming that supertasks are possible. I go on to present one reason why this conclusion (that supertasks are (...) impossible) is important, namely that it implies a new verdict on a decision puzzle propounded by Jeffrey Barrett and Frank Arntzenius. (shrink)

There is a long tradition of logic, from Aristotle to Gödel, of understanding a proof from the concepts of necessity and causality. Gödel's attempts to define provability in terms of necessity led him to the distinction of formal and absolute (abstract) provability. Turing's definition of mechanical procedure by means of a Turing machine (TM) and Gödel's definition of a formal system as a mechanical procedure for producing formulas prompt us to understand formal provability as a mechanical causality. We propose a (...) formalism which makes explicit the mechanical causal nature of a TM's work. We claim that Gödel's axiomatised ontotheology and his ontological proof give a clue for the understanding of the concept of absolute provability and the pattern of the corresponding absolute completeness proof, respectively. (shrink)

This paper presents a formalization of the classical proof of completeness in Henkin-style developed by Troelstra and van Dalen for intuitionistic logic with respect to Kripke models. The completeness proof incorporates their insights in a fresh and elegant manner that is better suited for mechanization. We discuss details of our implementation in the Lean theorem prover with emphasis on the prime extension lemma and construction of the canonical model. Our implementation is restricted to a system of intuitionistic propositional (...) logic with implication, conjunction, disjunction, and falsity given in terms of a Hilbert-style axiomatization. As far as we know, our implementation is the first verified Henkin-style proof of completeness for intuitionistic logic following Troelstra and van Dalen's method in the literature. (shrink)

I explain why model theory is unsatisfactory as a semantic theory and has drawbacks as a tool for proofs on logic systems. I then motivate and develop an alternative, the truth-valuational substitutional approach (TVS), and prove with it the soundness and completeness of the first order Predicate Calculus with identity and of Modal Propositional Calculus. Modal logic is developed without recourse to possible worlds. Along the way I answer a variety of difficulties that have been raised against TVS (...) and show that, as applied to several central questions, model-theoretic semantics can be considered TVS in disguise. The conclusion is that the truth-valuational substitutional approach is an adequate tool for many of our logic inquiries, conceptually preferable over model-theoretic semantics. Another conclusion is that formal logic is independent of semantics, apart from its use of the notion of truth, but that even with respect to it its assumptions are minimal. (shrink)

Computational tools might tempt us to renounce complete cer- tainty. By forgoing of rigorous proof, we could get (very) probable results for a fraction of the cost. But is it really true that proofs (as we know and love them) can lead us to certainty? Maybe not. Proofs do not wear their correct- ness on their sleeve, and we are not infallible in checking them. This suggests that we need help to check our results. When our fellow mathematicians (...) will be too tired or too busy to scrutinize our putative proofs, computer proof assistants could help. But feeding a mathematical argument to a computer is hard. Still, we might be willing to undertake the endeavor in view of the extra perks that formalization may bring—chiefly among them, an enhanced mathematical understanding. (shrink)

This work provides proof-search algorithms and automated counter-model extraction for a class of STIT logics. With this, we answer an open problem concerning syntactic decision procedures and cut-free calculi for STIT logics. A new class of cut-free complete labelled sequent calculi G3LdmL^m_n, for multi-agent STIT with at most n-many choices, is introduced. We refine the calculi G3LdmL^m_n through the use of propagation rules and demonstrate the admissibility of their structural rules, resulting in auxiliary calculi Ldm^m_nL. In the single-agent case, we (...) show that the refined calculi Ldm^m_nL derive theorems within a restricted class of (forestlike) sequents, allowing us to provide proof-search algorithms that decide single-agent STIT logics. We prove that the proof-search algorithms are correct and terminate. (shrink)

Propositional dynamic logic is complete but not compact. As a consequence, strong completeness requires an infinitary proof system. In this paper, we present a short proof for strong completeness of $$\mathsf{PDL}$$ relative to an infinitary proof system containing the rule from [α; β n ]φ for all $$n \in {\mathbb{N}}$$, conclude $$[\alpha;\beta^*] \varphi$$. The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. (...) Also, we show that the universal canonical model of $$\mathsf{PDL}$$ lacks the property of modal harmony, the analogue of the Truth lemma for modal operators. (shrink)

This paper contends that Stoic logic (i.e. Stoic analysis) deserves more attention from contemporary logicians. It sets out how, compared with contemporary propositional calculi, Stoic analysis is closest to methods of backward proof search for Gentzen-inspired substructural sequent logics, as they have been developed in logic programming and structural proof theory, and produces its proof search calculus in tree form. It shows how multiple similarities to Gentzen sequent systems combine with intriguing dissimilarities that may enrich contemporary discussion. Much of Stoic (...) logic appears surprisingly modern: a recursively formulated syntax with some truth-functional propositional operators; analogues to cut rules, axiom schemata and Gentzen’s negation-introduction rules; an implicit variable-sharing principle and deliberate rejection of Thinning and avoidance of paradoxes of implication. These latter features mark the system out as a relevance logic, where the absence of duals for its left and right introduction rules puts it in the vicinity of McCall’s connexive logic. Methodologically, the choice of meticulously formulated meta-logical rules in lieu of axiom and inference schemata absorbs some structural rules and results in an economical, precise and elegant system that values decidability over completeness. (shrink)

I explore, from a proof-theoretic perspective, the hierarchy of classical and paraconsistent logics introduced by Barrio, Pailos and Szmuc in (Journal o f Philosophical Logic,49, 93-120, 2021). First, I provide sequent rules and axioms for all the logics in the hierarchy, for all inferential levels, and establish soundness and completeness results. Second, I show how to extend those systems with a corresponding hierarchy of validity predicates, each one of which is meant to capture “validity” at a different inferential level. (...) Then, I point out two potential philosophical implications of these results. (i) Since the logics in the hierarchy differ from one another on the rules, I argue that each such logic maintains its own distinct identity (contrary to arguments like the one given by Dicher and Paoli in 2019). (ii) Each validity predicate need not capture “validity” at more than one metainferential level. Hence, there are reasons to deny the thesis (put forward in Barrio, E., Rosenblatt, L. & Tajer, D. (Synthese, 2016)) that the validity predicate introduced in by Beall and Murzi in (Journal o f Philosophy,110(3), 143–165, 2013) has to express facts not only about what follows from what, but also about the metarules, etc. (shrink)

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued ‘functions’. The ‘functions’ are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on well-developed methods of (...) functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce’s reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there. (shrink)

The first aim of this paper is to prove a topological completeness theorem for a weak version of Stalnaker’s logic KB of knowledge and belief. The weak version of KB is characterized by the assumption that the axioms and rules of KB have to be satisfied with the exception of the axiom (NI) of negative introspection. The proof of a topological completeness theorem for weak KB is based on the fact that nuclei (as defined in the framework of (...) point-free topology) give rise to a profusion of topological belief operators that are compatible with the familiar topological knowledge operator. Thereby a canonical topological model for weak KB can be constructed. For this canonical model a truth lemma for the K and B holds such that a completeness theorem for KB can be proved in the familiar way. The second aim of this paper is to show that the topological interpretation of knowledge K comes along with a complete Heyting algebra of belief operators B that all fit the knowledge operator K in the sense that the pairs (K, B) satisfy all axioms of weak KB. This amounts to a pluralistic relation between knowledge and belief: Knowledge does not fully determine belief, rather it designs a conceptual space for belief operators where different (competing) belief operators coexist. (shrink)

This book presents a (new) attempt to apply the notion of an underlying logic to Aristotle’s Organon and certain passages of the Metaphysics. The author situates his approach as part of a ‘deductio...

This paper presents a sequent calculus and a dual domain semantics for a theory of definite descriptions in which these expressions are formalised in the context of complete sentences by a binary quantifier I. I forms a formula from two formulas. Ix[F, G] means ‘The F is G’. This approach has the advantage of incorporating scope distinctions directly into the notation. Cut elimination is proved for a system of classical positive free logic with I and it is shown to be (...) sound and complete for the semantics. The system has a number of novel features and is briefly compared to the usual approach of formalising ‘the F ’ by a term forming operator. It does not coincide with Hintikka’s and Lambert’s preferred theories, but the divergence is well-motivated and attractive. (shrink)

The aim of this paper is to provide a proof-theoretic characterization of relevant logics including fusion and fission connectives, as well as Ackermann’s truth constant. We achieve this by employing the well-established methodology of labelled sequent calculi. After having introduced several systems, we will conduct a detailed proof-theoretic analysis, show a cut-admissibility theorem, and establish soundness and completeness. The paper ends with a discussion that contextualizes our current work within the broader landscape of the proof theory of relevant logics.

Takeuti and Titani have introduced and investigated a logic they called intuitionistic fuzzy logic. This logic is characterized as the first-order Gödel logic based on the truth value set [0,1]. The logic is known to be axiomatizable, but no deduction system amenable to proof-theoretic, and hence, computational treatment, has been known. Such a system is presented here, based on previous work on hypersequent calculi for propositional Gödel logics by Avron. It is shown that the system is sound and complete, and (...) allows cut-elimination. A question by Takano regarding the eliminability of the Takeuti-Titani density rule is answered affirmatively. (shrink)

According to Kant, pure intuition is an indispensable ingredient of mathematical proofs. Kant‘s thesis has been considered as obsolete since the advent of modern relational logic at the end of 19th century. Against this logicist orthodoxy Cassirer’s “critical idealism” insisted that formal logic alone could not make sense of the conceptual co-evolution of mathematical and scientific concepts. For Cassirer, idealizations, or, more precisely, idealizing completions, played a fundamental role in the formation of the mathematical and empirical concepts. The aim (...) of this paper is to outline the basics of Cassirer’s idealizational account, and to point at some interesting similarities it has with Kant’s and Peirce’s philosophies of mathematics based on the key notions of pure intuition and theorematic reasoning, respectively. (shrink)

Gentzen’s approach by transfinite induction and that of intuitionist Heyting arithmetic to completeness and the self-foundation of mathematics are compared and opposed to the Gödel incompleteness results as to Peano arithmetic. Quantum mechanics involves infinity by Hilbert space, but it is finitist as any experimental science. The absence of hidden variables in it interpretable as its completeness should resurrect Hilbert’s finitism at the cost of relevant modification of the latter already hinted by intuitionism and Gentzen’s approaches for (...) class='Hi'>completeness. This paper investigates both conditions and philosophical background necessary for that modification. The main conclusion is that the concept of infinity as underlying contemporary mathematics cannot be reduced to a single Peano arithmetic, but to at least two ones independent of each other. Intuitionism, quantum mechanics, and Gentzen’s approaches to completeness an even Hilbert’s finitism can be unified from that viewpoint. Mathematics may found itself by a way of finitism complemented by choice. The concept of information as the quantity of choices underlies that viewpoint. Quantum mechanics interpretable in terms of information and quantum information is inseparable from mathematics and its foundation. (shrink)

Presumption is a complex concept in law, affecting the dialogue setting. However, it is not clear how presumptions work in everyday argumentation, in which the concept of “plausible argumentation” seems to encompass all kinds of inferences. By analyzing the legal notion of presumption, it appears that this type of reasoning combines argument schemes with reasoning from ignorance. Presumptive reasoning can be considered a particular form of reasoning, which needs positive or negative evidence to carry a probative weight on the conclusion. (...) For this reason, presumptions shift the burden of providing evidence or explanations onto the interlocutor. The latter can provide new information or fail to do so: whereas in the first case the new information rebuts the presumption, in the second case, the absence of information that the interlocutor could reasonably provide strengthen the conclusion of the presumptive reasoning. In both cases the result of the presumption is to strengthen the conclusion of the reasoning from lack of evidence. As shown in the legal cases, the effect of presumption is to shift the burden of proof to the interlocutor; however, the shift a presumption effects is only the shift of the evidential burden, or the burden of completing the incomplete knowledge from which the conclusion was drawn. The burden of persuasion remains on the proponent of the presumption. On the contrary, reasoning from definition in law is a conclusive proof, and shifts to the other party the burden to prove the contrary. This crucial difference can be applied to everyday argumentation: natural arguments can be divided into dialectical and presumptive arguments, leading to conclusions materially different in strength. -/- . (shrink)

The “four-color” theorem seems to be generalizable as follows. The four-letter alphabet is sufficient to encode unambiguously any set of well-orderings including a geographical map or the “map” of any logic and thus that of all logics or the DNA plan of any alive being. Then the corresponding maximally generalizing conjecture would state: anything in the universe or mind can be encoded unambiguously by four letters. That admits to be formulated as a “four-letter theorem”, and thus one can search for (...) a properly mathematical proof of the statement. It would imply the “four colour theorem”, the proof of which many philosophers and mathematicians believe not to be entirely satisfactory for it is not a “human proof”, but intermediated by computers unavoidably since the necessary calculations exceed the human capabilities fundamentally. It is furthermore rather unsatisfactory because it consists in enumerating and proving all cases one by one. Sometimes, a more general theorem turns out to be much easier for proving including a general “human” method, and the particular and too difficult for proving theorem to be implied as a corollary in certain simple conditions. The same approach will be followed as to the four colour theorem, i.e. to be deduced more or less trivially from the “four-letter theorem” if the latter is proved. References are only classical and thus very well-known papers: their complete bibliographic description is omitted. (shrink)

In this paper we introduce a Gentzen calculus for (a functionally complete variant of) Belnap's logic in which establishing the provability of a sequent in general requires \emph{two} proof trees, one establishing that whenever all premises are true some conclusion is true and one that guarantees the falsity of at least one premise if all conclusions are false. The calculus can also be put to use in proving that one statement \emph{necessarily approximates} another, where necessary approximation is a natural dual (...) of entailment. The calculus, and its tableau variant, not only capture the classical connectives, but also the `information' connectives of four-valued Belnap logics. This answers a question by Avron. (shrink)

In their recent paper Bi-facial truth: a case for generalized truth values Zaitsev and Shramko [7] distinguish between an ontological and an epistemic interpretation of classical truth values. By taking the Cartesian product of the two disjoint sets of values thus obtained, they arrive at four generalized truth values and consider two “semi-classical negations” on them. The resulting semantics is used to define three novel logics which are closely related to Belnap’s well-known four valued logic. A syntactic characterization of these (...) logics is left for further work. In this paper, based on our previous work on a functionally complete extension of Belnap’s logic, we present a sound and complete tableau calculus for these logics. It crucially exploits the Cartesian nature of the four values, which is reflected in the fact that each proof consists of two tableaux. The bi-facial notion of truth of Z&S is thus augmented with a bi-facial notion of proof. We also provide translations between the logics for semi-classical negation and classical logic and show that an argument is valid in a logic for semi-classical negation just in case its translation is valid in classical logic. (shrink)

In a previous paper, an elementary and thoroughly arithmetical proof of Fermat’s last theorem by induction has been demonstrated if the case for “n = 3” is granted as proved only arithmetically (which is a fact a long time ago), furthermore in a way accessible to Fermat himself though without being absolutely and precisely correct. The present paper elucidates the contemporary mathematical background, from which an inductive proof of FLT can be inferred since its proof for the case for “n (...) = 3” has been known for a long time. It needs “Hilbert mathematics”, which is inherently complete unlike the usual “Gödel mathematics”, and based on “Hilbert arithmetic” to generalize Peano arithmetic in a way to unify it with the qubit Hilbert space of quantum information. An “epoché to infinity” (similar to Husserl’s “epoché to reality”) is necessary to map Hilbert arithmetic into Peano arithmetic in order to be relevant to Fermat’s age. Furthermore, the two linked semigroups originating from addition and multiplication and from the Peano axioms in the final analysis can be postulated algebraically as independent of each other in a “Hamilton” modification of arithmetic supposedly equivalent to Peano arithmetic. The inductive proof of FLT can be deduced absolutely precisely in that Hamilton arithmetic and the pransfered as a corollary in the standard Peano arithmetic furthermore in a way accessible in Fermat’s epoch and thus, to himself in principle. A future, second part of the paper is outlined, getting directed to an eventual proof of the case “n=3” based on the qubit Hilbert space and the Kochen-Specker theorem inferable from it. (shrink)

Kant claims that Aristotles logic as complete, explain the historical and philosophical considerations that commit him to proving the completeness claim and sketch the proof based on materials from his logic corpus. The proof will turn out to be an integral part of Kant’s larger reform of formal logic in response to a foundational crisis facing it.

Gödel's incompleteness theorems establish the stunning result that mathematics cannot be fully formalized and, further, that any formal system containing a modicum of number or set theory cannot establish its own consistency. Wilfried Sieg and Clinton Field, in their paper Automated Search for Gödel's Proofs, presented automated proofs of Gödel's theorems at an abstract axiomatic level; they used an appropriate expansion of the strategic considerations that guide the search of the automated theorem prover AProS. The representability conditions that (...) allow the syntactic notions of the metalanguage to be represented inside the object language were taken as axioms in the automated proofs. The concrete task I am taking on in this project is to extend the search by formally verifying these conditions. Using a formal metatheory defined in the language of binary trees, the syntactic objects of the metatheory lend themselves naturally to a direct encoding in Zermelo's theory of sets. The metatheoretic notions can then be inductively defined and shown to be representable in the object-theory using appropriate inductive arguments. Formal verification of the representability conditions is the first step towards an automated proof thereof which, in turn, brings the automated verification of Gödel's theorems one step closer to completion. (shrink)

The Earth is positioned at the center of the universe in the Ptolemaic model of the universe. The center of the Earth is at the same time the center of the universe in this model. This system, which was constructed according to Aristotelian physics, was accepted as the prevailing theory up to the adoption of the heliocentric universal model in the 16th century. The Earth was at the same time assumed to be completely stationary in the geocentric theory. Movement around (...) its own axis or around another celestial body was out of the question for it. In Antiquity and the Middle Ages when observational instruments like the telescope were not yet in use, this theory was seen to be rationally based on data obtained directly from the senses. In this context, various justifications had been provided about the world being stationary and existing at the center. Representatives from the Peripatetic philosophy in the Muslim world also were seen to accept the geocentric model. In The Book of Healing, Ibn Sīnā (d. 1038 CE) subjected the proofs that had come to him about the Earth being stationary by distinguishing an independent chapter. The 14th century follower of Ibn Sīnā’s philosophy, Najm al-Dīn al-Kātibī addressed this topic in Ḥikmat al-‘ain, and the work’s principle commentators also commented on his assessments. This study will address Ibn Sīnā’s assessments on the Earth being stationary in the geocentric model of the universe and will discuss the reflections of these assessments in Ḥikmat al-‘ain as an Avicennan text. (shrink)

In the later Fichte the reflection splits the world into a fivefoldness of its possible view. To get through all the a priori arranged levels from sensuality to the Doctrine of Science means to use up all the possibilities of the views of the world. I will examine whether Fichte can offer us a direct proof of completeness of the standpoints or at least show indirectly that there must be exactly five of them. Which answer would he give us (...) if we argued that history, skepticism and nonentity could complement the array? -/- Keywords Fivefoldness-worldviews-completeness-proof-history-skepticism -/- Die Reflexion spaltet nach Fichte die Welt in eine Fünffachheit ihrer möglichen Ansicht. Das Durchlaufen der a priori geordneten Stufen von der Sinnlichkeit bis zur Wissenschaftslehre stellt zugleich ein Ausschöpfen der Möglichkeiten dar, sich zur Welt zu verhalten. Ich werde prüfen, ob Fichte uns einen direkten Beweis der Vollständigkeit der Standpunkte geben oder zumindest indirekt dafür argumentieren kann, dass es genau fünf sein müssen. Was würde er uns antworten, wenn wir behaupteten, die Geschichte, der Skeptizismus und die Nullität könnten die Reihe ergänzen? -/- Schlüsselbegriffe Fünffachheit-Weltansichten-Vollständigkeit-Beweis-Geschichte-Skeptizismus. (shrink)

A simulating halt decider correctly predicts whether or not its correctly simulated input can possibly reach its own final state and halt. It does this by correctly recognizing several non-halting behavior patterns in a finite number of steps of correct simulation. Inputs that do terminate are simply simulated until they complete.

Aristotelian causal theories incorporate some philosophically important features of the concept of cause, including necessity and essential character. The proposed formalization is restricted to one-place predicates and a finite domain of attributes (without individuals). Semantics is based on a labeled tree structure, with truth defined by means of tree paths. A relatively simple causal prefixing mechanism is defined, by means of which causes of propositions and reasoning with causes are made explicit. The distinction of causal and factual explanation are elaborated, (...) and examples of cyclic and convergent causation are given. Soundness and completeness proofs are sketched. (shrink)

We give a complete axiomatization of the identities of the basic game algebra valid with respect to the abstract game board semantics. We also show that the additional conditions of termination and determinacy of game boards do not introduce new valid identities.En route we introduce a simple translation of game terms into plain modal logic and thus translate, while preserving validity both ways, game identities into modal formulae.The completeness proof is based on reduction of game terms to a certain (...) ‘minimal canonical form’, by using only the axiomatic identities, and on showing that the equivalence of two minimal canonical terms can be established from these identities. (shrink)

A semantics is presented for Storrs McCall's separate axiomatizations of Aristotle's accepted and rejected polysyllogisms. The polysyllogisms under discussion are made up of either assertoric or apodeictic propositions. The semantics is given by associating a property with a pair of sets: one set consists of things having the property essentially and the other of things having it accidentally. A completeness proof and a semantic decision procedure are given.

In some recent works, Crupi and Iacona have outlined an analysis of ‘if’ based on Chrysippus’ idea that a conditional holds whenever the negation of its consequent is incompatible with its antecedent. This paper presents a sound and complete system of conditional logic that accommodates their analysis. The soundness and completeness proofs that will be provided rely on a general method elaborated by Raidl, which applies to a wide range of systems of conditional 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.

Cathoristic logic is a multi-modal logic where negation is replaced by a novel operator allowing the expression of incompatible sentences. We present the syntax and semantics of the logic including complete proof rules, and establish a number of results such as compactness, a semantic characterisa- tion of elementary equivalence, the existence of a quadratic-time decision pro- cedure, and Brandom’s incompatibility semantics property. We demonstrate the usefulness of the logic as a language for knowledge representation.

In the 1920s, David Hilbert proposed a research program with the aim of providing mathematics with a secure foundation. This was to be accomplished by first formalizing logic and mathematics in their entirety, and then showing---using only so-called finitistic principles---that these formalizations are free of contradictions. ;In the area of logic, the Hilbert school accomplished major advances both in introducing new systems of logic, and in developing central metalogical notions, such as completeness and decidability. The analysis of unpublished material (...) presented in Chapter 2 shows that a completeness proof for propositional logic was found by Hilbert and his assistant Paul Bernays already in 1917--18, and that Bernays's contribution was much greater than is commonly acknowledged. Aside from logic, the main technical contribution of Hilbert's Program are the development of formal mathematical theories and proof-theoretical investigations thereof, in particular, consistency proofs. In this respect Wilhelm Ackermann's 1924 dissertation is a milestone both in the development of the Program and in proof theory in general. Ackermann gives a consistency proof for a second-order version of primitive recursive arithmetic which, surprisingly, explicitly uses a finitistic version of transfinite induction up to www . He also gave a faulty consistency proof for a system of second-order arithmetic based on Hilbert's &egr;-substitution method. Detailed analyses of both proofs in Chapter 3 shed light on the development of finitism and proof theory in the 1920s as practiced in Hilbert's school. ;In a series of papers, Charles Parsons has attempted to map out a notion of mathematical intuition which he also brings to bear on Hilbert's finitism. According to him, mathematical intuition fails to be able to underwrite the kind of intuitive knowledge Hilbert thought was attainable by the finitist. It is argued in Chapter 4 that the extent of finitistic knowledge which intuition can provide is broader than Parsons supposes. According to another influential analysis of finitism due to W. W. Tait, finitist reasoning coincides with primitive recursive reasoning. The acceptance of non-primitive recursive methods in Ackermann's dissertation presented in Chapter 3, together with additional textual evidence presented in Chapter 4, shows that this identification is untenable as far as Hilbert's conception of finitism is concerned. Tait's conception, however, differs from Hilbert's in important respects, yet it is also open to criticisms leading to the conclusion that finitism encompasses more than just primitive recursive reasoning. (shrink)

Standpoint logic is a recently proposed formalism in the context of knowledge integration, which advocates a multi-perspective approach permitting reasoning with a selection of diverse and possibly conflicting standpoints rather than forcing their unification. In this paper, we introduce nested sequent calculi for propositional standpoint logics---proof systems that manipulate trees whose nodes are multisets of formulae---and show how to automate standpoint reasoning by means of non-deterministic proof-search algorithms. To obtain worst-case complexity-optimal proof-search, we introduce a novel technique in the context (...) of nested sequents, referred to as "coloring," which consists of taking a formula as input, guessing a certain coloring of its subformulae, and then running proof-search in a nested sequent calculus on the colored input. Our technique lets us decide the validity of standpoint formulae in CoNP since proof-search only produces a partial proof relative to each permitted coloring of the input. We show how all partial proofs can be fused together to construct a complete proof when the input is valid, and how certain partial proofs can be transformed into a counter-model when the input is invalid. These "certificates" (i.e. proofs and counter-models) serve as explanations of the (in)validity of the input. (shrink)

It is argued that the goal of Hilbert's program was to prove the model-theoretical consistency of different axiom systems. This Hilbert proposed to do by proving the deductive consistency of the relevant systems. In the extended independence-friendly logic there is a complete proof method for the contradictory negations of independence-friendly sentences, so the existence of a single proposition that is not disprovable from arithmetic axioms can be shown formally in the extended independence-friendly logic. It can also be proved by means (...) of independence-friendly logic that proof-theoretical consistency of a sentence S implies the existence of a model in which S is not false. Hence the consistency of the axioms of arithmetic in the sense of being not-false in a model can be proved. (shrink)

In proof-theoretic semantics, meaning is based on inference. It may be seen as the mathematical expression of the inferentialist interpretation of logic. Much recent work has focused on base-extension semantics, in which the validity of formulas is given by an inductive definition generated by provability in a ‘base’ of atomic rules. Base-extension semantics for classical and intuitionistic propositional logic have been explored by several authors. In this paper, we develop base-extension semantics for the classical propositional modal systems K, KT , (...) K4, and S4, with □ as the primary modal operator. We establish appropriate soundness and completeness theorems and establish the duality between □ and a natural presentation of ♢. We also show that our semantics is in its current form not complete with respect to euclidean modal logics. Our formulation makes essential use of relational structures on bases. (shrink)

This document presents a Gentzen-style deductive calculus and proves that it is complete with respect to a 3-valued semantics for a language with quantifiers. The semantics resembles the strong Kleene semantics with respect to conjunction, disjunction and negation. The completeness proof for the sentential fragment fills in the details of a proof sketched in Arnon Avron (2003). The extension to quantifiers is original but uses standard techniques.

In previous work, I introduced a complete axiomatization of classical non-tautologies based essentially on Łukasiewicz’s rejection method. The present paper provides a new, Hilbert-type axiomatization (along with related systems to axiomatize classical contradictions, non-contradictions, contingencies and non-contingencies respectively). This new system is mathematically less elegant, but the format of the inferential rules and the structure of the completeness proof possess some intrinsic interest and suggests instructive comparisons with the logic of tautologies.

In the proof-theoretic semantics approach to meaning, harmony , requiring a balance between introduction-rules (I-rules) and elimination rules (E-rules) within a meaning conferring natural-deduction proof-system, is a central notion. In this paper, we consider two notions of harmony that were proposed in the literature: 1. GE-harmony , requiring a certain form of the E-rules, given the form of the I-rules. 2. Local intrinsic harmony : imposes the existence of certain transformations of derivations, known as reduction and expansion . We propose (...) a construction of the E-rules (in GE-form) from given I-rules, and prove that the constructed rules satisfy also local intrinsic harmony. The construction is based on a classification of I-rules, and constitute an implementation to Gentzen’s (and Pawitz’) remark, that E-rules can be “read off” I-rules. (shrink)

This paper deals with a collection of concerns that, over a period of time, led the author away from the Routley–Meyer semantics, and towards proof- theoretic approaches to relevant logics, and indeed to the weak relevant logic MC of meaning containment.

The first degree entailment (FDE) family is a group of logics, a many-valued semantics for each system of which is obtained from classical logic by adding to the classical truth-values true and false any subset of {both, neither, indeterminate}, where indeterminate is an infectious value (any formula containing a subformula with the value indeterminate itself has the value indeterminate). In this paper, we see how to extend a version of star semantics for the logics whose many-valued semantics lack indeterminate to (...) star semantics for logics whose many-valued semantics include indeterminate. The equivalence of the many-valued semantics and star semantics is established by way of a soundness and completeness proof. The upshot of the novel semantics in terms of the applied semantics of these logics, and specifically infectiousness, is explored, settling on the idea that infectiousness concerns ineffability. (shrink)

This article is intended to examine the structure and scope of the argumentation drawn in Metaphysics Γ 4, 1006a18-b34. As we shall see, though this passage does not bring a complete proof of the Principle of Non-Contradiction, it corresponds to its first step, which consists in determining the conditions of meaning necessary for discourse. That passage encloses in nuce the reasons which underlie Aristotelian conviction con- cerning the conventional nature of names and also brings to light the way this conven- (...) tional nature of names must be understood according to Aristotle. (shrink)

We present epistemic multilateral logic, a general logical framework for reasoning involving epistemic modality. Standard bilateral systems use propositional formulae marked with signs for assertion and rejection. Epistemic multilateral logic extends standard bilateral systems with a sign for the speech act of weak assertion (Incurvati and Schlöder 2019) and an operator for epistemic modality. We prove that epistemic multilateral logic is sound and complete with respect to the modal logic S5 modulo an appropriate translation. The logical framework developed provides the (...) basis for a novel, proof-theoretic approach to the study of epistemic modality. To demonstrate the fruitfulness of the approach, we show how the framework allows us to reconcile classical logic with the contradictoriness of so-called Yalcin sentences and to distinguish between various inference patterns on the basis of the epistemic properties they preserve. (shrink)

This paper studies the relationship between labelled and nested calculi for propositional intuitionistic logic, first-order intuitionistic logic with non-constant domains and first-order intuitionistic logic with constant domains. It is shown that Fitting’s nested calculi naturally arise from their corresponding labelled calculi—for each of the aforementioned logics—via the elimination of structural rules in labelled derivations. The translational correspondence between the two types of systems is leveraged to show that the nested calculi inherit proof-theoretic properties from their associated labelled calculi, such as (...) completeness, invertibility of rules and cut admissibility. Since labelled calculi are easily obtained via a logic’s semantics, the method presented in this paper can be seen as one whereby refined versions of labelled calculi (containing nested calculi as fragments) with favourable properties are derived directly from a logic’s semantics. (shrink)

Reverse mathematics studies which subsystems of second order arithmetic are equivalent to key theorems of ordinary, non-set-theoretic mathematics. The main philosophical application of reverse mathematics proposed thus far is foundational analysis, which explores the limits of different foundations for mathematics in a formally precise manner. This paper gives a detailed account of the motivations and methodology of foundational analysis, which have heretofore been largely left implicit in the practice. It then shows how this account can be fruitfully applied in the (...) evaluation of major foundational approaches by a careful examination of two case studies: a partial realization of Hilbert’s program due to Simpson [1988], and predicativism in the extended form due to Feferman and Schütte. -/- Shore [2010, 2013] proposes that equivalences in reverse mathematics be proved in the same way as inequivalences, namely by considering only omega-models of the systems in question. Shore refers to this approach as computational reverse mathematics. This paper shows that despite some attractive features, computational reverse mathematics is inappropriate for foundational analysis, for two major reasons. Firstly, the computable entailment relation employed in computational reverse mathematics does not preserve justification for the foundational programs above. Secondly, computable entailment is a Pi-1-1 complete relation, and hence employing it commits one to theoretical resources which outstrip those available within any foundational approach that is proof-theoretically weaker than Pi-1-1-CA0. (shrink)

This paper considers Rumfitt’s bilateral classical logic (BCL), which is proposed to counter Dummett’s challenge to classical logic. First, agreeing with several authors, we argue that Rumfitt’s notion of harmony, used to justify logical rules by a purely proof theoretical manner, is not sufficient to justify coordination rules in BCL purely proof-theoretically. For the central part of this paper, we propose a notion of proof-theoretical validity similar to Prawitz for BCL and proves that BCL is sound and complete respect to (...) this notion of validity. The major difficulty in defining validity for BCL is that validity of positive +A appears to depend on negative −A, and vice versa. Thus, the straightforward inductive definition does not work because of this circular dependance. However, Knaster-Tarski’s fixed point theorem can resolve this circularity. Finally, we discuss the philosophical relevance of our work, in particular, the impact of the use of fixed point theorem and the issue of decidability. (shrink)

Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic (...) Analysis of Variable Binding Term Operators” (Co-author John Herring), Logique et Analyse 55, 646–57. MR0307874 (46 #6989). A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. Kalish-Montague 1964 proposed using vbtos to formalize definite descriptions “the x: x+x=2”, set abstracts {x: F}, minimization in recursive function theory “the least x: x+x>2”, etc. However, they gave no semantics for vbtos. Hatcher 1968 gave a semantics but one that has flaws described in the 1971 paper and admitted by Hatcher. In 1971 we give a correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture, proved in this paper with Hatcher’s help, was proved independently about the same time by Newton da Costa. (shrink)

Developing a suggestion of Wittgenstein, I provide an account of truth tables as formulas of a formal language. I define the syntax and semantics of TPL (the language of Tabular Propositional Logic), and develop its proof theory. Single formulas of TPL, and finite groups of formulas with the same top row and TF matrix (depiction of possible valuations), are able to serve as their own proofs with respect to metalogical properties of interest. The situation is different, however, for groups (...) of formulas whose top rows differ. For them I provide (i) a tree-style system of ‘row tree proofs’, which is shown to be sound and complete, and (ii) an alternative, re-writing strategy. (shrink)