Interesting as they are by themselves in philosophy and mathematics, paradoxes can be made even more fascinating when turned into proofs and theorems. For example, Russell’s paradox, which overthrew Frege’s logical edifice, is now a classical theorem in set theory, to the effect that no set contains all sets. Paradoxes can be used in proofs of some other theorems—thus Liar’s paradox has been used in the classical proof of Tarski’s theorem on the undefinability of truth in sufficiently rich languages. This (...) paradox (as well as Richard’s paradox) appears implicitly in Gödel’s proof of his celebrated first incompleteness theorem. In this paper, we study Yablo’s paradox from the viewpoint of first- and second-order logics. We prove that a formalization of Yablo’s paradox (which is second order in nature) is non-first-orderizable in the sense of George Boolos (1984). (shrink)

We study the structure of the partial order induced by the definability relation on definitions of truth for the language of arithmetic. Formally, a definition of truth is any sentence $$\alpha $$ which extends a weak arithmetical theory (which we take to be $${{\,\mathrm{I\Delta _{0}+\exp }\,}}$$ ) such that for some formula $$\Theta $$ and any arithmetical sentence $$\varphi $$, $$\Theta (\ulcorner \varphi \urcorner )\equiv \varphi $$ is provable in $$\alpha $$. We say that a sentence $$\beta $$ is definable (...) in a sentence $$\alpha $$, if there exists an unrelativized translation from the language of $$\beta $$ to the language of $$\alpha $$ which is identity on the arithmetical symbols and such that the translation of $$\beta $$ is provable in $$\alpha $$. Our main result is that the structure consisting of truth definitions which are conservative over the basic arithmetical theory forms a countable universal distributive lattice. Additionally, we generalize the result of Pakhomov and Visser showing that the set of (Gödel codes of) definitions of truth is not $$\Sigma _2$$ -definable in the standard model of arithmetic. We conclude by remarking that no $$\Sigma _2$$ -sentence, satisfying certain further natural conditions, can be a definition of truth for the language of arithmetic. (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)

We investigate the theory Peano Arithmetic with Indiscernibles ( \(\textrm{PAI}\) ). Models of \(\textrm{PAI}\) are of the form \(({\mathcal {M}},I)\), where \({\mathcal {M}}\) is a model of \(\textrm{PA}\), _I_ is an unbounded set of order indiscernibles over \({\mathcal {M}}\), and \(({\mathcal {M}},I)\) satisfies the extended induction scheme for formulae mentioning _I_. Our main results are Theorems A and B following. _Theorem A._ _Let_ \({\mathcal {M}}\) _be a nonstandard model of_ \(\textrm{PA}\) _ of any cardinality_. \(\mathcal {M }\) _has an expansion (...) to a model of _ \(\textrm{PAI}\) _iff_ \( {\mathcal {M}}\) _has an inductive partial satisfaction class._ Theorem A yields the following corollary, which provides a new characterization of countable recursively saturated models of \(\textrm{PA}\) : _Corollary._ _A countable model_ \({\mathcal {M}}\) of \(\textrm{PA}\) _is recursively saturated iff _ \({\mathcal {M}}\) _has an expansion to a model of _ \(\textrm{PAI}\). _Theorem B._ _There is a sentence _ \(\alpha \) _ in the language obtained by adding a unary predicate_ _I_(_x_) _to the language of arithmetic such that given any nonstandard model _ \({\mathcal {M}}\) _of_ \(\textrm{PA}\) _ of any cardinality_, \({\mathcal {M}}\) _has an expansion to a model of _ \(\text {PAI}+\alpha \) _iff_ \({\mathcal {M}}\) _has a inductive full satisfaction class._. (shrink)

Vardanyan’s Theorems [36, 37] state that $\mathsf {QPL}(\mathsf {PA})$ —the quantified provability logic of Peano Arithmetic—is $\Pi ^0_2$ complete, and in particular that this already holds when the language is restricted to a single unary predicate. Moreover, Visser and de Jonge [38] generalized this result to conclude that it is impossible to computably axiomatize the quantified provability logic of a wide class of theories. However, the proof of this fact cannot be performed in a strictly positive signature. The system $\mathsf (...) {QRC_1}$ was previously introduced by the authors [1] as a candidate first-order provability logic. Here we generalize the previously available Kripke soundness and completeness proofs, obtaining constant domain completeness. Then we show that $\mathsf {QRC_1}$ is indeed complete with respect to arithmetical semantics. This is achieved via a Solovay-type construction applied to constant domain Kripke models. As corollaries, we see that $\mathsf {QRC_1}$ is the strictly positive fragment of $\mathsf {QGL}$ and a fragment of $\mathsf {QPL}(\mathsf {PA})$. (shrink)

The current paper studies the formal properties of the Global Reflection Principle, to wit the assertion “All theorems of$\mathrm {Th}$are true,” where$\mathrm {Th}$is a theory in the language of arithmetic and the truth predicate satisfies the usual Tarskian inductive conditions for formulae in the language of arithmetic. We fix the gap in Kotlarski’s proof from [15], showing that the Global Reflection Principle for Peano Arithmetic is provable in the theory of compositional truth with bounded induction only ($\mathrm {CT}_0$). Furthermore, we (...) extend the above result showing that$\Sigma _1$-uniform reflection over a theory of uniform Tarski biconditionals ($\mathrm {UTB}^-$) is provable in$\mathrm {CT}_0$, thus answering the question of Beklemishev and Pakhomov [2]. Finally, we introduce the notion of a prolongable satisfaction class and use it to study the structure of models of$\mathrm {CT}_0$. In particular, we provide a new model-theoretical characterization of theories of finite iterations of uniform reflection and present a new proof characterizing the arithmetical consequences of$\mathrm {CT}_0$. (shrink)

The notion of implicit commitment has played a prominent role in recent works in logic and philosophy of mathematics. Although implicit commitment is often associated with highly technical studies, it remains an elusive notion. In particular, it is often claimed that the acceptance of a mathematical theory implicitly commits one to the acceptance of a Uniform Reflection Principle for it. However, philosophers agree that a satisfactory analysis of the transition from a theory to its reflection principle is still lacking. We (...) provide an axiomatization of the minimal commitments implicit in the acceptance of a mathematical theory. The theory entails that the Uniform Reflection Principle is part of one’s implicit commitments, and sheds light on why this is so. We argue that the theory has significant epistemological consequences in that it explains how justified belief in the axioms of a theory can be preserved to the corresponding reflection principle. The theory also improves on recent analyses of implicit commitment based on truth or epistemic notions. (shrink)