-
23The FAN principle and weak König's lemma in herbrandized second-order arithmeticAnnals of Pure and Applied Logic 171 (9): 102843. 2020.We introduce a herbrandized functional interpretation of a first-order semi-intuitionistic extension of Heyting Arithmetic and study its main properties. We then extend the interpretation to a certain system of second-order arithmetic which includes a (classically false) formulation of the FAN principle and weak König's lemma. It is shown that any first-order formula provable in this system is classically true. It is perhaps worthy of note that, in our interpretation, second-order variables are …Read more
-
23On the Consistency of the Δ1 1-CA Fragment of Frege's GrundgesetzeJournal of Philosophical Logic 31 (4): 301-311. 2002.It is well known that Frege's system in the Grundgesetze der Arithmetik is formally inconsistent. Frege's instantiation rule for the second-order universal quantifier makes his system, except for minor differences, full (i.e., with unrestricted comprehension) second-order logic, augmented by an abstraction operator that abides to Frege's basic law V. A few years ago, Richard Heck proved the consistency of the fragment of Frege's theory obtained by restricting the comprehension schema to predicat…Read more
-
22The abstract type of the real numbersArchive for Mathematical Logic 60 (7): 1005-1017. 2021.In finite type arithmetic, the real numbers are represented by rapidly converging Cauchy sequences of rational numbers. Ulrich Kohlenbach introduced abstract types for certain structures such as metric spaces, normed spaces, Hilbert spaces, etc. With these types, the elements of the spaces are given directly, not through the mediation of a representation. However, these abstract spaces presuppose the real numbers. In this paper, we show how to set up an abstract type for the real numbers. The ap…Read more
-
21Injecting uniformities into Peano arithmeticAnnals of Pure and Applied Logic 157 (2-3): 122-129. 2009.We present a functional interpretation of Peano arithmetic that uses Gödel’s computable functionals and which systematically injects uniformities into the statements of finite-type arithmetic. As a consequence, some uniform boundedness principles are interpreted while maintaining unmoved the -sentences of arithmetic. We explain why this interpretation is tailored to yield conservation results
-
21Review: Mitsuru Tada, Makoto Tatsuta, The Function $lfloor a/m rfloor$ in Sharply Bounded Arithmetic (review)Bulletin of Symbolic Logic 7 (3): 391-391. 2001.
-
20Interpretability in Robinson's QBulletin of Symbolic Logic 19 (3): 289-317. 2013.Edward Nelson published in 1986 a book defending an extreme formalist view of mathematics according to which there is animpassable barrierin the totality of exponentiation. On the positive side, Nelson embarks on a program of investigating how much mathematics can be interpreted in Raphael Robinson's theory of arithmetic. In the shadow of this program, some very nice logical investigations and results were produced by a number of people, not only regarding what can be interpreted inbut also what…Read more
-
19A herbrandized functional interpretation of classical first-order logicArchive for Mathematical Logic 56 (5-6): 523-539. 2017.We introduce a new typed combinatory calculus with a type constructor that, to each type σ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma $$\end{document}, associates the star type σ∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{a…Read more
-
19Arithmetic, proof theory, and computational complexity, edited by Peter Clote and Krajíček Jan, Oxford logic guides, no. 23, Clarendon Press, Oxford University Press, Oxford and New York1993, xiii + 428 pp (review)Journal of Symbolic Logic 60 (3): 1014-1017. 1995.
-
18Two General Results on Intuitionistic Bounded TheoriesMathematical Logic Quarterly 45 (3): 399-407. 1999.We study, within the framework of intuitionistic logic, two well-known general results of bounded arithmetic. Firstly, Parikh's theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to bounded theories does not yield new II2 consequences
-
18Interpreting weak Kőnig's lemma in theories of nonstandard arithmeticMathematical Logic Quarterly 63 (1-2): 114-123. 2017.We show how to interpret weak Kőnig's lemma in some recently defined theories of nonstandard arithmetic in all finite types. Two types of interpretations are described, with very different verifications. The celebrated conservation result of Friedman's about weak Kőnig's lemma can be proved using these interpretations. We also address some issues concerning the collecting of witnesses in herbrandized functional interpretations.
-
18What are the ∀∑1 b-consequences of T 2 1 and T 2 2?Annals of Pure and Applied Logic 75 (1): 79-88. 1995.We formulate schemes and of the “typical” ∀∑ 1 b -sentences that are provable in T 2 1, respectively T 2 2. As an application, we reprove a recent result of Buss and Krajíček which describes witnesses for the ∀∑ 1 b -sentences provable in T 2 1 in terms of solutions to PLS-problems.
-
17A short note on Spector's proof of consistency of analysisIn S. Barry Cooper (ed.), How the World Computes, . pp. 222--227. 2012.
-
16Counting as integration in feasible analysisMathematical Logic Quarterly 52 (3): 315-320. 2006.Suppose that it is possible to integrate real functions over a weak base theory related to polynomial time computability. Does it follow that we can count? The answer seems to be: obviously yes! We try to convince the reader that the severe restrictions on induction in feasible theories preclude a straightforward answer. Nevertheless, a more sophisticated reflection does indeed show that the answer is affirmative
-
15Categoricity and Mathematical KnowledgeRevista Portuguesa de Filosofia 73 (3-4): 1423-1436. 2017.We argue that the basic notions of mathematics can only be properly formulated in an informal way. Mathematical notions transcend formalizations and their study involves the consideration of other mathematical notions. We explain the fundamental role of categoricity theorems in making these studies possible. We arrive at the conclusion that the enterprise of mathematics is not infallible and that it ultimately relies on degrees of evidence.
-
15Interpretability in Robinson's QAssociation for Symbolic Logic: The Bulletin of Symbolic Logic. forthcoming.Edward Nelson published in 1986 a book defending an extreme formalist view of mathematics according to which there is an impassable barrier in the totality of exponentiation. On the positive side, Nelson embarks on a program of investigating how much mathematics can be interpreted in Raphael Robinson's theory of arithmetic Q. In the shadow of this program, some very nice logical investigations and results were produced by a number of people, not only regarding what can be interpreted in Q but al…Read more
-
15Bounds for indexes of nilpotency in commutative ring theory: A proof mining approachBulletin of Symbolic Logic 26 (3-4): 257-267. 2020.It is well-known that an element of a commutative ring with identity is nilpotent if, and only if, it lies in every prime ideal of the ring. A modification of this fact is amenable to a very simple proof mining analysis. We formulate a quantitative version of this modification and obtain an explicit bound. We present an application. This proof mining analysis is the leitmotif for some comments and observations on the methodology of computational extraction. In particular, we emphasize that the f…Read more
-
14Elementary Proof of Strong Normalization for Atomic FBulletin of the Section of Logic 45 (1): 1-15. 2016.We give an elementary proof of the strong normalization of the atomic polymorphic calculus Fat.
-
14Review: Peter Clote, Jan Krajicek, Arithmetic, proof theory, and computational complexity (review)Journal of Symbolic Logic 60 (3): 1014-1017. 1995.
-
12Programs, proofs, processes: 6th Conference on Computability in Europe, CiE, 2010, Ponta Delgada, Azores, Portugal, June 30-July 4, 2010 ; proceedings (edited book, review)Springer. 2010.The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form.
-
12A Most Artistic Package of a Jumble of IdeasDialectica 62 (2): 205-222. 2008.In the course of ten short sections, we comment on Gödel's seminal dialectica paper of fifty years ago and its aftermath. We start by suggesting that Gödel's use of functionals of finite type is yet another instance of the realistic attitude of Gödel towards mathematics, in tune with his defense of the postulation of ever increasing higher types in foundational studies. We also make some observations concerning Gödel's recasting of intuitionistic arithmetic via the dialectica interpretation, dis…Read more
-
11Zigzag and Fregean ArithmeticIn Hassan Tahiri (ed.), The Philosophers and Mathematics: Festschrift for Roshdi Rashed, Springer Verlag. pp. 81-100. 2018.In Frege’s logicism, numbers are logical objects in the sense that they are extensions of certain concepts. Frege’s logical system is inconsistent, but Richard Heck showed that its restriction to predicative quantification is consistent. This predicative fragment is, nevertheless, too weak to develop arithmetic. In this paper, I will consider an extension of Heck’s system with impredicative quantifiers. In this extended system, both predicative and impredicative quantifiers co-exist but it is on…Read more
-
11What are the ∀∑1b-consequences of T21 and T22?Annals of Pure and Applied Logic 75 (1-2): 79-88. 1995.We formulate schemes and of the “typical” ∀∑ 1 b -sentences that are provable in T 2 1 , respectively T 2 2 . As an application, we reprove a recent result of Buss and Krajíček which describes witnesses for the ∀∑ 1 b -sentences provable in T 2 1 in terms of solutions to PLS-problems
-
10Review: Thomas Strahm, Polynomial Time Operations in Explicit Mathematics ; Andrea Cantini, Feasible Operations and Applicative Theories Based on $\lambda \eta $ (review)Bulletin of Symbolic Logic 8 (4): 534-535. 2002.
-
8Feasible Operations and Applicative Theories Based on ληBulletin of Symbolic Logic 8 (4): 534. 2002.
-
1A Substitutional Framework for Arithmetical ValidityGrazer Philosophische Studien 56 (1): 133-149. 1998.