This paper treats a kind of a modal logic based on the intuitionistic propositional logic which arose from the provability predicate in the first order arithmetic. The semantics of this calculus is presented in both a relational and an algebraic way.Completeness theorems, existence of a characteristic model and of a characteristic frame, properties of FMP and FFP and decidability are proved.

Quine has argued that modal logic began with the sin of confusing use and mention. Anderson and Belnap, on the other hand, have offered us a way out through a strategy of nominahzation. This paper reviews the history of Lewis's early work in modal logic, and then proves some results about the system in which "A is necessary" is intepreted as "A is a classical tautology.".

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that (...) initiated by Turing in his “ordinal logics” and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach. (shrink)

Representationalist accounts of mental content face the threat of the homunculus fallacy. In collapsing the distinction between the conscious state and the conscious subject, self-representational accounts of consciousness possess the means to deal with this objection. We analyze a particular sort of self-representational theory, built on the work of John von Neumann on self-reproduction, using tools from mathematical logic. We provide an explicit theory of the emergence of referential beliefs by means of modal fixed points, grounded in intrinsic properties yielding (...) the subjective aspects of experience. Furthermore, we study complications introduced by allowing for the modification of such symbolic content by environmental influences. (shrink)

In Honour of John Crossley’s 85th Birthday.

The proof of the Second Incompleteness Theorem consists essentially of proving the uniqueness and explicit definability of the sentence asserting its own unprovability. This turns out to be a rather general phenomenon: Every instance of self-reference describable in the modal logic of the standard proof predicate obeys a similar uniqueness and explicit definability law. The efficient determination of the explicit definitions of formulae satisfying a given instance of self-reference reduces to a simple algebraic problem-that of solving the corresponding fixed-point equation (...) in the modal logic. We survey techniques for the efficient calculation of such fixed-points. (shrink)

Wilfred Sieg and Clinton Field. Automated Search for Gödel's Proofs.

The recovery of Aristotle’s logic during the twelfth century was a great stimulus to medieval thinkers. Among their own theories developed to explain Aristotle’s theories of valid and invalid reasoning was a theory of consequence, of what arguments were valid, and why. By the fourteenth century, two main lines of thought had developed, one at Oxford, the other at Paris. Both schools distinguished formal from material consequence, but in very different ways. In Buridan and his followers in Paris, formal consequence (...) was that preserved under uniform substitution. In Oxford, in contrast, formal consequence included analytic consequences such as ‘If it’s a man, then it’s an animal’. Aristotle’s notion of syllogistic consequence was subsumed under the treatment of formal consequence. Buridan developed a general theory embracing the assertoric syllogism, the modal syllogism and syllogisms with oblique terms. The result was a thoroughly systematic and extensive treatment of logical theory and logical consequence which repays investigation. (shrink)

Hartry Field's revised logic for the theory of truth in his new book, Saving Truth from Paradox , seeking to preserve Tarski's T-scheme, does not admit a full theory of negation. In response, Crispin Wright proposed that the negation of a proposition is the proposition saying that some proposition inconsistent with the first is true. For this to work, we have to show that this proposition is entailed by any proposition incompatible with the first, that is, that it is the (...) weakest proposition incompatible with the proposition whose negation it should be. To show that his proposal gave a full intuitionist theory of negation, Wright appealed to two principles, about incompatibility and entailment, and using them Field formulated a paradox of validity (or more precisely, of inconsistency). The medieval mathematician, theologian and logician, Thomas Bradwardine, writing in the fourteenth century, proposed a solution to the paradoxes of truth which does not require any revision of logic. The key principle behind Bradwardine's solution is a pluralist doctrine of meaning, or signification, that propositions can mean more than they explicitly say. In particular, he proposed that signification is closed under entailment. In light of this, Bradwardine revised the truth-rules, in particular, refining the T-scheme, so that a proposition is true only if everything that it signifies obtains. Thereby, he was able to show that any proposition which signifies that it itself is false, also signifies that it is true, and consequently is false and not true. I show that Bradwardine's solution is also able to deal with Field's paradox and others of a similar nature. Hence Field's logical revisions are unnecessary to save truth from paradox. (shrink)

Self-reference has played a prominent role in the development of metamathematics in the past century, starting with Gödel’s first incompleteness theorem. Given the nature of this and other results in the area, the informal understanding of self-reference in arithmetic has sufficed so far. Recently, however, it has been argued that for other related issues in metamathematics and philosophical logic a precise notion of self-reference and, more generally, reference is actually required. These notions have been so far elusive and are surrounded (...) by an aura of scepticism that has kept most philosophers away. In this paper I suggest we shouldn’t give up all hope. First, I introduce the reader to these issues. Second, I discuss the conditions a good notion of reference in arithmetic must satisfy. Accordingly, I then introduce adequate notions of reference for the language of first-order arithmetic, which I show to be fruitful for addressing the aforementioned issues in metamathematics. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

Let n be a positive integer. By a $\beta_{n}-model$ we mean an $\omega-model$ which is elementary with respect to $\sigma_{n}^{1}$ formulas. We prove the following $\beta_{n}-model$ version of $G\ddot{o}del's$ Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a $\beta_{n}-model$ of S, then there exists a $\beta_{n}-model$ of S + "there is no countable $\beta_{n}-model$ of S". We also prove a $\beta_{n}-model$ version of $L\ddot{o}b's$ Theorem. As a corollary, we obtain (...) a $\beta_{n}-model$ which is not a $\beta_{n+1}-model$. (shrink)

This paper is devoted to the algebraization of an arithmetical predicate introduced by S. Feferman. To this purpose we investigate the equational class of Boolean algebras enriched with an operation (g=rtail), which translates such predicate, and an operation τ, which translates the usual predicate Theor. We deduce from the identities of this equational class some properties of (g=rtail) and some ties between (g=rtail) and τ; among these properties, let us point out a fixed-point theorem for a sufficiently large class of (...) (g=rtail)-τ polynomials. The last part of this paper concerns the duality theory for (g=rtail)-τ algebras. (shrink)

This paper is devoted to the algebraization of theories in which, as in Peano arithmetic, there is a formula, Theor(x), numerating the set of theorems, and satisfying Hilbert-Bernays derivability conditions. In particular, we study the diagonalizable algebras, which are been introduced by R. Magari in [6], [7]. We prove that for every natural number n, the n-freely generated algebra $\germ{J}_{n}$ is not functionally free in the equational class of diagonalizable algebras; we also prove that the diagonalizable algebra of Peano arithmetic (...) is not an element of the equational class generated by $\{\germ{J}_{n}\}$. (shrink)

In a note appended to the translation of “On consistency and completeness” (), Gödel reexamined the problem of the unprovability of consistency. Gödel here focuses on an alternative means of expressing the consistency of a formal system, in terms of what would now be called a ‘reflection principle’, roughly, the assertion that a formula of a certain class is provable in the system only if it is true. Gödel suggests that it is this alternative means of expressing consistency that we (...) should be interested in from a foundational point of view, and he gives a result that shows certain reflection principles to be underivable in extensions of elementary number theory under conditions significantly weaker than the Hilbert-Bernays derivability conditions. In this paper I shall discuss the background to Gödel's result and the foundational significance he claims for it. Along the way, I shall present a new proof of the result which places it in an even more general context than the one considered by Gödel in the 1960s. (shrink)

Poincaré in a 1909 lecture in Göttingen proposed a solution to the apparent incompatibility of two results as viewed from a definitionist perspective: on the one hand, Richard’s proof that the definitions of real numbers form a countable set and, on the other, Cantor’s proof that the real numbers make up an uncountable class. Poincaré argues that, Richard’s result notwithstanding, there is no enumeration of all definable real numbers. We apply previous research by Luna and Taylor on Richard’s paradox, indefinite (...) extensibility and unrestricted quantification to evaluate Poincaré’s proposal. We emphasize that Poincaré’s solution involves an early recourse to indefinite extensibility and argue that his proposal, if it is to completely avoid Richard’s paradox, requires rejecting absolutely unrestricted quantification: Richard’s paradox provides a context in which paradox seems inescapable if unrestricted quantification is possible. In proposing his solution to the apparent conflict between Richard’s and Cantor’s results, Poincaré employs temporal expressions whose exact meaning he does not clarify. We suggest an interpretation of these expressions in terms of order of availability and briefly discuss its explanatory power in topics like paradoxes, limitation theorems and indefinite extensibility. (shrink)

Although the notion of common or mutual belief plays a crucial role in game theory, economics and social philosophy, no thoroughly representational account of it has yet been developed. In this paper, I propose two desiderata for such an account, namely, that it take into account the possibility of inconsistent data without portraying the human mind as logically and mathematically omniscient. I then propose a definition of mutual belief which meets these criteria. This account takes seriously the existence of computational (...) limitations. Finally, I point out that the epistemic logic (or theory) needed to make the definition work is subject to the Kaplan/Montague Paradox of the Knower. I argue that this is not a defect of the account, and I discuss briefly the bearing of recent work on the paradox of the Liar upon this problem. (shrink)

Turing progressions have been often used to measure the proof-theoretic strength of mathematical theories: iterate adding consistency of some weak base theory until you “hit” the target theory. Turing progressions based on n-consistency give rise to a \ proof-theoretic ordinal \ also denoted \. As such, to each theory U we can assign the sequence of corresponding \ ordinals \. We call this sequence a Turing-Taylor expansion or spectrum of a theory. In this paper, we relate Turing-Taylor expansions of sub-theories (...) of Peano Arithmetic to Ignatiev’s universal model for the closed fragment of the polymodal provability logic \. In particular, we observe that each point in the Ignatiev model can be seen as Turing-Taylor expansions of formal mathematical theories. Moreover, each sub-theory of Peano Arithmetic that allows for a Turing-Taylor expansion will define a unique point in Ignatiev’s model. (shrink)

The provability logic of a theory $T$ is the set of modal formulas, which under any arithmetical realization are provable in $T$. We slightly modify this notion by requiring the arithmetical realizations to come from a specified set $\Gamma$. We make an analogous modification for interpretability logics. We first study provability logics with restricted realizations and show that for various natural candidates of $T$ and restriction set $\Gamma$, the result is the logic of linear frames. However, for the theory Primitive (...) Recursive Arithmetic (PRA), we define a fragment that gives rise to a more interesting provability logic by capitalizing on the well-studied relationship between PRA and I$\Sigma_1$. We then study interpretability logics, obtaining upper bounds for IL(PRA), whose characterization remains a major open question in interpretability logic. Again this upper bound is closely related to linear frames. The technique is also applied to yield the nontrivial result that IL(PRA) $\subset$ ILM. (shrink)

Cook regards Sorenson’s so-called ‘the no-no paradox’ as only a kind of ‘meta-paradox’ or ‘quasi-paradox’ because the symmetry principle that Sorenson imposes on the paradox is meta-theoretic. He rebuilds this paradox at the object-language level by replacing the symmetry principle with some ‘background principles governing the truth predicate’. He thus argues that the no-no paradox is a ‘new type of paradox’ in that its paradoxicality depends on these principles. This paper shows that any theory is inconsistent with the T-schema instances (...) for the no-no sentences, plus the T-schema instance for a Curry sentence associated with the symmetry of the no-no sentences. It turns out that the no-no paradox still depends on the problematic instances of the T-schema in a way that the liar paradox does. What distinguishes the no-no paradox is the T-schema instance for the above Curry sentence, which encodes Sorensen’s symmetry principle at the object-language level. (shrink)

This paper develops the philosophy and technology needed for adding a supremum operator to the interpretability logic ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document} of Peano Arithmetic. It is well-known that any theories extending PA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PA}$$\end{document} have a supremum in the interpretability ordering. While provable in PA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PA}$$\end{document}, this fact is not reflected in the theorems of the modal (...) system ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document}, due to limited expressive power. Our goal is to enrich the language of ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document} by adding to it a new modality for the interpretability supremum. We explore different options for specifying the exact meaning of the new modality. Our final proposal involves a unary operator, the dual of which can be seen as a provability predicate satisfying the axioms of the provability logic GL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {GL}$$\end{document}. (shrink)

This paper propounds a systematic examination of the link between the Knower Paradox and provability interpretations of modal logic. The aim of the paper is threefold: to give a streamlined presentation of the Knower Paradox and related results; to clarify the notion of a syntactical treatment of modalities; finally, to discuss the kind of solution that modal provability logic provides to the Paradox. I discuss the respective strength of different versions of the Knower Paradox, both in the framework of first-order (...) arithmetic and in that of modal logic with fixed point operators. It is shown that the notion of a syntactical treatment of modalities is ambiguous between a self-referential treatment and a metalinguistic treatment of modalities, and that these two notions are independent. I survey and compare the provability interpretations of modality respectively given by Skyrms, B. (1978, The Journal of Philosophy 75: 368–387) Anderson, C.A. (1983, The Journal of Philosophy 80: 338–355) and Solovay, R. (1976, Israel Journal of Mathematics 25: 287–304). I examine how these interpretations enable us to bypass the limitations imposed by the Knower Paradox while preserving the laws of classical logic, each time by appeal to a distinct form of hierarchy. (shrink)

This paper investigates the conditions under which diagonal sentences can be taken to constitute paradigmatic cases of self-reference. We put forward well-motivated constraints on the diagonal operator and the coding apparatus which separate paradigmatic self-referential sentences, for instance obtained via Gödel’s diagonalization method, from accidental diagonal sentences. In particular, we show that these constraints successfully exclude refutable Henkin sentences, as constructed by Kreisel.

The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introducedeviantnumberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of this paper however, these (...) “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class ofadmissiblenumberings is singled out, invariance is maintained. (shrink)

There is a well-known gap between metamathematical theorems and their philosophical interpretations. Take Tarski’s Theorem. According to its prevalent interpretation, the collection of all arithmetical truths is not arithmetically definable. However, the underlying metamathematical theorem merely establishes the arithmetical undefinability of a set of specific Gödel codes of certain artefactual entities, such as infix strings, which are true in the standard model. That is, as opposed to its philosophical reading, the metamathematical theorem is formulated (and proved) relative to a specific (...) choice of the Gödel numbering and the notation system. A similar observation applies to Gödel’s and Church’s theorems, which are commonly taken to impose severe limitations on what can be proved and computed using the resources of certain formalisms. The philosophical force of these limitative results heavily relies on the belief that these theorems do not depend on contingencies regarding the underlying formalisation choices. The main aim of this paper is to provide metamathematical facts which support this belief. While employing a fixed notation system, I showed in previous work (_Review of Symbolic Logic_, 2021, 14(1):51–84) how to abstract away from the choice of the Gödel numbering. In the present paper, I extend this work by establishing versions of Tarski’s, Gödel’s and Church’s theorems which are invariant regarding _both_ the notation system and the numbering. This paper thus provides a further step towards absolute versions of metamathematical results which do not rely on contingent formalisation choices. (shrink)

I attribute an 'intensional reading' of the second incompleteness theorem to its author, Kurt G del. My argument builds partially on an analysis of intensional and extensional conceptions of meta-mathematics and partially on the context in which G del drew two familiar inferences from his theorem. Those inferences, and in particular the way that they appear in G del's writing, are so dubious on the extensional conception that one must doubt that G del could have understood his theorem extensionally. However, (...) on the intensional conception, the inferences are straightforward. For that reason I conclude that G del had an intensional understanding of his theorem. Since this conclusion is in tension with the generally accepted view of G del's understanding of mathematical truth, I explain how to reconcile that view with the intensional reading of the theorem that I attribute to G del. The result is a more detailed account of G del's conception of meta-mathematics than is currently available. (shrink)

I defend Putnam’s modal structuralist view of mathematics but reject his claims that Wittgenstein’s remarks on Dedekind, Cantor, and set theory are verificationist. Putnam’s “realistic realism” showcases the plasticity of our “fitting” words to the world. The applications of this—in philosophy of language, mind, logic, and philosophy of computation—are robust. I defend Wittgenstein’s nonextensionalist understanding of the real numbers, showing how it fits Putnam’s view. Nonextensionalism and extensionalism about the real numbers are mathematically, philosophically, and logically robust, but the two (...) perspectives are often confused with one another. I separate them, using Turing’s work as an example. (shrink)

By a well-known result of Kotlarski et al., first-order Peano arithmetic \ can be conservatively extended to the theory \ of a truth predicate satisfying compositional axioms, i.e., axioms stating that the truth predicate is correct on atomic formulae and commutes with all the propositional connectives and quantifiers. This result motivates the general question of determining natural axioms concerning the truth predicate that can be added to \ while maintaining conservativity over \. Our main result shows that conservativity fails even (...) for the extension of \ obtained by the seemingly weak axiom of disjunctive correctness \ that asserts that the truth predicate commutes with disjunctions of arbitrary finite size. In particular, \ implies \\). Our main result states that the theory \ coincides with the theory \ obtained by adding \-induction in the language with the truth predicate. This result strengthens earlier work by Kotlarski and Cieśliński. For our proof we develop a new general form of Visser’s theorem on non-existence of infinite descending chains of truth definitions and prove it by reduction to Gödel’s second incompleteness theorem, rather than by using the Visser–Yablo paradox, as in Visser’s original proof. (shrink)

The knower paradox states that the statement ‘We know that this statement is false’ leads to inconsistency. This article presents a fresh look at this paradox and some well-known solutions from the literature. Paul Égré discusses three possible solutions that modal provability logic provides for the paradox by surveying and comparing three different provability interpretations of modality, originally described by Skyrms, Anderson, and Solovay. In this article, some background is explained to clarify Égré’s solutions, all three of which hinge on (...) intricacies of provability logic and its arithmetical interpretations. To check whether Égré’s solutions are satisfactory, we use the criteria for solutions to paradoxes defined by Susan Haack and we propose some refinements of them. This article aims to describe to what extent the knower paradox can be solved using provability logic and to what extent the solutions proposed in the literature satisfy Haack’s criteria. Finally, the article offers some reflections on the relation between knowledge, proof, and provability, as inspired by the knower paradox and its solutions. (shrink)

-/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical point of view, provability logic is interesting because (...) the concept of provability in a fixed theory of arithmetic has a unique and non-problematic meaning, other than concepts like necessity and knowledge studied in modal and epistemic logic. Furthermore, provability logic provides tools to study the notion of self-reference. (shrink)

This paper aims to vindicate the thesis that cognitive computational properties are abstract objects implemented in physical systems. I avail of the equivalence relations countenanced in Homotopy Type Theory, in order to specify an abstraction principle for epistemic intensions. The homotopic abstraction principle for epistemic intensions provides an epistemic conduit into our knowledge of intensions as abstract objects. I examine, then, how intensional functions in Epistemic Modal Algebra are deployed as core models in the philosophy of mind, Bayesian perceptual psychology, (...) and the program of natural language semantics in linguistics, and I argue that this provides abductive support for the truth of homotopic abstraction. Epistemic modality can thus be shown to be both a compelling and a materially adequate candidate for the fundamental structure of mental representational states, comprising a fragment of the Language of Thought. (shrink)

This brief note corrects an error in one of the reduction steps in my paper 'Normalisation for Bilateral Classical Logic with some Philosophical Remarks' published in the Journal of Applied Logics 8/2 (2021): 531-556.

5.5. Every topos is linguistic: the equivalence theorem.