We suggest an algebraic approach to proof-theoretic analysis based on the notion of graded provability algebra, that is, Lindenbaum boolean algebra of a theory enriched by additional operators which allow for the structure to capture proof-theoretic information. We use this method to analyze Peano arithmetic and show how an ordinal notation system up to 0 can be recovered from the corresponding algebra in a canonical way. This method also establishes links between proof-theoretic ordinal analysis and the work which has been (...) done in the last two decades on provability logic and reflection principles. Because of its abstract algebraic nature, we hope that it will also be of interest for non-prooftheorists. (shrink)

Progressions of iterated reflection principles can be used as a tool for the ordinal analysis of formal systems. We discuss various notions of proof-theoretic ordinals and compare the information obtained by means of the reflection principles with the results obtained by the more usual proof-theoretic techniques. In some cases we obtain sharper results, e.g., we define proof-theoretic ordinals relevant to logical complexity Π1 0 and, similarly, for any class Π n 0 . We provide a more general version of the (...) fine structure relationships for iterated reflection principles (due to U. Schmerl [25]). This allows us, in a uniform manner, to analyze main fragments of arithmetic axiomatized by restricted forms of induction, including IΣ n , IΣ n − , IΠ n − and their combinations. We also obtain new conservation results relating the hierarchies of uniform and local reflection principles. In particular, we show that (for a sufficiently broad class of theories T) the uniform Σ1-reflection principle for T is Σ2-conservative over the corresponding local reflection principle. This bears some corollaries on the hierarchies of restricted induction schemata in arithmetic and provides a key tool for our generalization of Schmerl's theorem. (shrink)

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. This (...) calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

We introduce the logics GLP Λ, a generalization of Japaridze’s polymodal provability logic GLP ω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP ω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLP Λ and the decidability of GLP Λ for recursive orderings Λ. Further, we give a restricted axiomatization of the variable-free fragment (...) of GLP Λ. (shrink)

Many topics have not been covered, in most cases because I don't know quite what to say about them. Would it be possible to add a decidability predicate to the language? What about stronger connectives, like exclusion negation or Lukasiewicz implication? Would an expanded language do better at expressing its own semantics? Would it contain new and more terrible paradoxes? Can the account be supplemented with a workable notion of inherent truth (see note 36)? In what sense does stage semantics (...) lie “between” fixed point and stability semantics? In what sense, exactly, are our semantical rules inconsistent? In what sense, if any, does their inconsistency resolve the problem of the paradoxes?The ideals of strength, grounding, and closure together define an intuitively appealing conception of truth. Nothing would be gained by insisting that it was the intuitive conception of truth, and in fact recent developments make me wonder whether such a thing exists. However that may be, until the alternatives are better understood it would be foolish to attempt to decide between them. Truth gives up her secrets slowly and grudgingly, and loves to confound our presumptions. (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)

We highlight that the connection of well-foundedness and recursive definitions is more than just convenience. While the consequences of making well-foundedness a sufficient condition for the existence of hierarchies have been extensively studied, we point out that well-foundedness is a necessary condition for the existence of hierarchies e.g. that even in an intuitionistic setting α⊢wfwhereα\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${_\alpha \vdash \mathsf{wf}\, {\rm where}\, _\alpha}$$\end{document} stands for the iteration of Π10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...) \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} comprehension along some ordinal α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\alpha}$$\end{document} and wf\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{wf}}$$\end{document} stands for the well-foundedness of α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\alpha}$$\end{document}. (shrink)

For any ordinal $\Lambda$, we can define a polymodal logic $\mathsf{GLP}_\Lambda$, with a modality $[\xi]$ for each $\xi < \Lambda$. These represent provability predicates of increasing strength. Although $\mathsf{GLP}_\Lambda$ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted $\mathsf{GLP}^0_\omega$. Later, Icard defined a topological model for $\mathsf{GLP}^0_\omega$ which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary $\Lambda$. (...) More generally, for each $\Theta,\Lambda$ we build a Kripke model $\mathfrak I^\Theta_\Lambda$ and a topological model $\mathfrak T^\Theta_\Lambda$, and show that $\mathsf{GLP}^0_\Lambda$ is sound for both of these structures, as well as complete, provided $\Theta$ is large enough. (shrink)

This paper is divided into two parts. Part I provides a resumé of the evolution of the notion of predicativity. Part II describes our own work on the subject.Part I§1. Conceptions of sets.Statements about sets lie at the heart of most modern attempts to systematize all (or, at least, all known) mathematics. Technical and philosophical discussions concerning such systematizations and the underlying conceptions have thus occupied a considerable portion of the literature on the foundations of mathematics.

The unfolding of schematic formal systems is a novel concept which was initiated in Feferman , Gödel ’96, Lecture Notes in Logic, Springer, Berlin, 1996, pp. 3–22). This paper is mainly concerned with the proof-theoretic analysis of various unfolding systems for non-finitist arithmetic . In particular, we examine two restricted unfoldings and , as well as a full unfolding, . The principal results then state: is equivalent to ; is equivalent to ; is equivalent to . Thus is proof-theoretically equivalent (...) to predicative analysis. (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)