This paper consists primarily of a survey of results of Harvey Friedman about some proof-theoretic aspects of various forms of Kruskal's tree theorem, and in particular the connection with the ordinal Γ0. We also include a fairly extensive treatment of normal functions on the countable ordinals, and we give a glimpse of Verlen hierarchies, some subsystems of second-order logic, slow-growing and fast-growing hierarchies including Girard's result, and Goodstein sequences. The central theme of this paper is a powerful theorem due to (...) Kruskal, the ‘tree theorem’, as well as a ‘finite miniaturization’ of Kruskal's theorem due to Harvey Friedman. These versions of Kruskal's theorem are remarkable from a proof-theoretic point of view because they are not provable in relatively strong logical systems. They are examples of so-called ‘natural independence phenomena’, which are considered by most logicians as more natural than the metamathematical incompleteness results first discovered by Gödel. Kruskal's tree theorem also plays a fundamental role in computer science, because it is one of the main tools for showing that certain orderings on trees are well founded. These orderings play a crucial role in proving the termination of systems of rewrite rules and the correctness of Knuth-Bendix completion procedures. There is also a close connection between a certain infinite countable ordinal called Γo and Kruskal's theorem. Previous definitions of the function involved in this connection are known to be incorrect, in that, the function is not monotonic. We offer a repaired definition of this function, and explore briefly the consequences of its existence. (shrink)

This paper investigates the determinacy of mathematics. We begin by clarifying how we are understanding the notion of determinacy before turning to the questions of whether and how famous independence results bear on issues of determinacy in mathematics. From there, we pose a metasemantic challenge for those who believe that mathematical language is determinate, motivate two important constraints on attempts to meet our challenge, and then use these constraints to develop an argument against determinacy and discuss a particularly popular approach (...) to resolving indeterminacy, before offering some brief closing reflections. We believe our discussion poses a serious challenge for most philosophical theories of mathematics, since it puts considerable pressure on all views that accept a non-trivial amount of determinacy for even basic arithmetic. (shrink)

Guessing the outcome of iterations of even most simple arithmetical functions could be an extremely hazardous experience. Not less harder, if at all possible, might be to prove the veracity of even a "sure" guess concerning iterations : this is the case of the famous 3x+1 conjecture. Our purpose here is to study and conceptualize some intuitive insights related to the ultimate (un)solvability of this conjecture.

"The definitive clarification of the nature of the infinite has become necessary, not merely for the special interests of the individual sciences, but rather for the honour of the human understanding itself. The infinite has always stirred the emotions of mankind more deeply than any other question; the infinite has stimulated and fertilized reason as few other ideas have ; but also the infinite, more than other notion, is in need of clarification." (David Hilbert 1925).

It is argued, by use of specific examples, that mathematical understanding is something which cannot be modelled in terms of entirely computational procedures. Our conception of a natural number (a non-negative integer: 0, 1, 2, 3,…) is something which goes beyond any formulation in terms of computational rules. Our ability to perceive the properties of natural numbers depends upon our awareness, and represents just one of the many ways in which awareness provides an essential ingredient to our ability to understand. (...) There is no bar to the quality of understanding being the result of natural selection, but only so long as the physical laws contain a non-computational ingredient. (shrink)

Leon Horsten has recently claimed that the class of mathematical truths coincides with the class of theorems of ZFC. I argue that the naturalistic character of Horsten’s proposal undermines his contention that this claim constitutes an analogue of a thesis that Daniel Isaacson has advanced for PA. I argue, moreover, that Horsten’s defence of his claim against an obvious objection makes use of a distinction which is not available to him given his naturalistic approach. I suggest a way out of (...) the objection which is in line with the naturalistic spirit of Horsten’s proposal but which further weakens the analogy with Isaacson’s Thesis. I conclude by evaluating the prospects for providing an analogue of Isaacson’s Thesis for ZFC. (shrink)

Following our [6], though with somewhat different methods here, further variants of Goodstein sequences are introduced in terms of parameterized Ackermann–Péter functions. Each of the sequences is shown to terminate, and the proof-theoretic strengths of these facts are calibrated by means of ordinal assignments, yielding independence results for a range of theories: PRA, PA,$\Sigma ^1_1$-DC$_0$, ATR$_0$, up to ID$_1$. The key is the so-called “Hardy hierarchy” of proof-theoretic bounding finctions, providing a uniform method for associating Goodstein-type sequences with parameterized normal (...) form representations of positive integers. (shrink)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

This book reports on the results of the third edition of the premier conference in the field of philosophy of artificial intelligence, PT-AI 2017, held on November 4 - 5, 2017 at the University of Leeds, UK. It covers: advanced knowledge on key AI concepts, including complexity, computation, creativity, embodiment, representation and superintelligence; cutting-edge ethical issues, such as the AI impact on human dignity and society, responsibilities and rights of machines, as well as AI threats to humanity and AI safety; (...) and cutting-edge developments in techniques to achieve AI, including machine learning, neural networks, dynamical systems. The book also discusses important applications of AI, including big data analytics, expert systems, cognitive architectures, and robotics. It offers a timely, yet very comprehensive snapshot of what is going on in the field of AI, especially at the interfaces between philosophy, cognitive science, ethics and computing. (shrink)

We show how removing faith-based beliefs in current philosophies of classical and constructive mathematics admits formal, evidence-based, definitions of constructive mathematics; of a constructively well-defined logic of a formal mathematical language; and of a constructively well-defined model of such a language. -/- We argue that, from an evidence-based perspective, classical approaches which follow Hilbert's formal definitions of quantification can be labelled `theistic'; whilst constructive approaches based on Brouwer's philosophy of Intuitionism can be labelled `atheistic'. -/- We then adopt what may (...) be labelled a finitary, evidence-based, `agnostic' perspective and argue that Brouwerian atheism is merely a restricted perspective within the finitary agnostic perspective, whilst Hilbertian theism contradicts the finitary agnostic perspective. -/- We then consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary, evidence-based, definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways. -/- We show that the two definitions correspond to two distinctly different---not necessarily evidence-based but complementary---assignments of satisfaction and truth to the compound formulas of PA over N. -/- We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both the complementary interpretations; and conclude some unsuspected constructive consequences of such complementarity for the foundations of mathematics, logic, philosophy, and the physical sciences. -/- . (shrink)

We examine some of Connes’ criticisms of Robinson’s infinitesimals starting in 1995. Connes sought to exploit the Solovay model S as ammunition against non-standard analysis, but the model tends to boomerang, undercutting Connes’ own earlier work in functional analysis. Connes described the hyperreals as both a “virtual theory” and a “chimera”, yet acknowledged that his argument relies on the transfer principle. We analyze Connes’ “dart-throwing” thought experiment, but reach an opposite conclusion. In S , all definable sets of reals are (...) Lebesgue measurable, suggesting that Connes views a theory as being “virtual” if it is not definable in a suitable model of ZFC. If so, Connes’ claim that a theory of the hyperreals is “virtual” is refuted by the existence of a definable model of the hyperreal field due to Kanovei and Shelah. Free ultrafilters aren’t definable, yet Connes exploited such ultrafilters both in his own earlier work on the classification of factors in the 1970s and 80s, and in Noncommutative Geometry, raising the question whether the latter may not be vulnerable to Connes’ criticism of virtuality. We analyze the philosophical underpinnings of Connes’ argument based on Gödel’s incompleteness theorem, and detect an apparent circularity in Connes’ logic. We document the reliance on non-constructive foundational material, and specifically on the Dixmier trace −∫ (featured on the front cover of Connes’ magnum opus) and the Hahn–Banach theorem, in Connes’ own framework. We also note an inaccuracy in Machover’s critique of infinitesimal-based pedagogy. (shrink)

In the Handbook of Mathematical Logic, the Paris-Harrington variant of Ramsey's theorem is celebrated as the first result of a long ‘search’ for a purely mathematical incompleteness result in first-order Peano arithmetic. This paper questions the existence of any such search and the status of the Paris-Harrington result as the first mathematical incompleteness result. In fact, I argue that Gentzen gave the first such result, and that it was restated by Goodstein in a number-theoretic form.

On the occasion of the 150th birthday of Georg Cantor (1845–1918), the founder of the theory of sets, the development of the logical foundations of this theory is described as a sequence of catastrophes and of trials to save it. Presently, most mathematicians agree that the set theory exactly defines the subject of mathematics, i.e., any subject is a mathematical one if it may be defined in the language (i.e., in the notions) of set theory. Hence the nature of formal (...) definitions plays an important role within the logical foundations of mathematics. Its study is also helpful to answer the question of how it is possible that the set theory as a universal new ontology for the subject of mathematics (as people hoped around 1900) totally failed but nevertheless the language of set theory is successful in all the mathematical practice. (shrink)

This paper consists primarily of a survey of results of Harvey Friedman about some proof-theoretic aspects of various forms of Kruskal's tree theorem, and in particular the connection with the ordinal Γ0. We also include a fairly extensive treatment of normal functions on the countable ordinals, and we give a glimpse of Verlen hierarchies, some subsystems of second-order logic, slow-growing and fast-growing hierarchies including Girard's result, and Goodstein sequences. The central theme of this paper is a powerful theorem due to (...) Kruskal, the ‘tree theorem’, as well as a ‘finite miniaturization’ of Kruskal's theorem due to Harvey Friedman. These versions of Kruskal's theorem are remarkable from a proof-theoretic point of view because they are not provable in relatively strong logical systems. They are examples of so-called ‘natural independence phenomena’, which are considered by most logicians as more natural than the metamathematical incompleteness results first discovered by Gödel. Kruskal's tree theorem also plays a fundamental role in computer science, because it is one of the main tools for showing that certain orderings on trees are well founded. These orderings play a crucial role in proving the termination of systems of rewrite rules and the correctness of Knuth-Bendix completion procedures. There is also a close connection between a certain infinite countable ordinal called Γo and Kruskal's theorem. Previous definitions of the function involved in this connection are known to be incorrect, in that, the function is not monotonic. We offer a repaired definition of this function, and explore briefly the consequences of its existence. (shrink)

We introduce strong Goodstein principles which are true but unprovable in strong impredicative theories like IDn.

The crux of the dispute between formalism and intuitionism, it is held, is not whether certain entities exist or not, but how the term function shall be used in mathematics. The identification of effective definition with general recursion fails because an undefined function lies concealed beneath the requirement of a finite number of substitutions, and a fresh characterization of effective definition is sought in terms of a hierarchy of ordinal recursions.A correspondence exists between primitive recursive properties and direct proofs, of (...) irrationality and transcendence for instance, and between general recursive properties and indirect proofs.Mathematics is a concept creating activity and the distinction between a formal mathematics devoid of meaning, at one level, and a meaningful metamathematics at the next is considered to be untenable.RésuméLa controverse entre les formalistes et les intuitionistes ne repose pas, considére‐t‐on, sur l'existence ou la non‐existence de certaines entités, mail sur l'usage du terme fonction en mathématiques. L'identification de la définition effective avec la récursion générate n'est pas valable parce qu'une fonction indéfinié est dissimulée sous la nécessité d'un nombre fini de substitutions, et une nouvelle caractérisation de définition effective est recherchée sous forme de hiérarchie de récursions ordinates.II existe, d'une part, une correspondance entre les propriétés primitives récursives et les preuves directes, d'irrationalité et de transcendance par exemple, et, d'autre part, entre les propriétés récursives générates et les preuves par l'absurde.Les mathématiques sont une activité créatrice de concepts, et la distinction entre les mathématiques formelles dépourvues de sens et, sur le plan supérieur, une méta‐mathématique chargée de sens, ne semble pas justifiée. (shrink)

We show that the well partial orderedness of the finite downwards closed subsets of, ordered by inclusion, is equivalent to the well foundedness of the ordinal. Since we use Friedman's adjacent Ramsey theorem for fixed dimensions in the upper bound, we also give a treatment of the reverse mathematical status of that theorem.

Goodstein’s theorem states that certain sequences based on exponential notation for the natural numbers are always finite. The result is independent of Peano arithmetic and is a prototypical example of a proof of termination by transfinite induction. A variant based instead on the Ackermann function has more recently been proposed by Arai, Fernández-Duque, Wainer, and Weiermann, and instead is independent of the more powerful theory ATR0. However, this result is contingent on rather elaborate normal forms for natural numbers based on (...) a “sandwiching” procedure. This leaves open both the question of whether the sandwiching procedure can be eliminated while retaining the full strength of the Ackermannian Goodstein principle, and whether other normal forms can lead to nontermination. In this article we settle these questions by showing that any Goodstein process based on the Ackermann function is terminating, and indeed the sandwiching procedure gives rise to Goodstein principles of maximal length. We thus obtain an equivalent principle which does not involve normal forms at all and immediately implies all Ackermannian Goodstein principles that have been considered. Our techniques provide a new approach to termination proofs, where terms in a sequence do not necessarily decrease in complexity, but instead are majorized by some “master” process, already known to be terminating. (shrink)