Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability of Borel sets for (...) any finite Borel measure on a compact complete separable metric space. (shrink)

We develop measure theory in the context of subsystems of second order arithmetic with restricted induction. We introduce a combinatorial principleWWKL (weak-weak König's lemma) and prove that it is strictly weaker thanWKL (weak König's lemma). We show thatWWKL is equivalent to a formal version of the statement that Lebesgue measure is countably additive on open sets. We also show thatWWKL is equivalent to a formal version of the statement that any Borel measure on a compact metric space is countably additive (...) on open sets. (shrink)

Within a weak subsystem of second‐order arithmetic WKL0, we develop basic part of non‐standard analysis up to the Peano existence theorem.

The fundamental question in reverse mathematics is to determine which set existence axioms are required to prove particular theorems of mathematics. In addition to being interesting in their own right, answers to this question have consequences in both effective mathematics and the foundations of mathematics. Before discussing these consequences, we need to be more specific about the motivating question.Reverse mathematics is useful for studying theorems of either countable or essentially countable mathematics. Essentially countable mathematics is a vague term that is (...) best explained by an example. Complete separable metric spaces are essentially countable because, although the spaces may be uncountable, they can be understood in terms of a countable basis. Simpson gives the following list of areas which can be analyzed by reverse mathematics: number theory, geometry, calculus, differential equations, real and complex analysis, combinatorics, countable algebra, separable Banach spaces, computability theory, and the topology of complete separable metric spaces. Reverse mathematics is less suited to theorems of abstract functional analysis, abstract set theory, universal algebra, or general topology.Section 2 introduces the major subsystems of second order arithmetic used in reverse mathematics: RCA0, WKL0, ACA0, ATR0 and – CA0. Sections 3 through 7 consider various theorems of ordered group theory from the perspective of reverse mathematics. Among the results considered are theorems on ordered quotient groups, groups and semigroup conditions which imply orderability, the orderability of free groups, Hölder's Theorem, Mal'tsev's classification of the order types of countable ordered groups. (shrink)

The program of Reverse Mathematics (Simpson 2009) has provided us with the insight that most theorems of ordinary mathematics are either equivalent to one of a select few logical principles, or provable in a weak base theory. In this paper, we study the properties of the Dirac delta function (Dirac 1927; Schwartz 1951) in two settings of Reverse Mathematics. In particular, we consider the Dirac Delta Theorem, which formalizes the well-known property \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} (...) \begin{document}$${\int_\mathbb{R}f(x)\delta(x)\,dx=f(0)}$$\end{document} of the Dirac delta function. We show that the Dirac Delta Theorem is equivalent to weak König’s Lemma (see Yu and Simpson in Arch Math Log 30(3):171–180, 1990) in classical Reverse Mathematics. This further validates the status of WWKL0 as one of the ‘Big’ systems of Reverse Mathematics. In the context of ERNA’s Reverse Mathematics (Sanders in J Symb Log 76(2):637–664, 2011), we show that the Dirac Delta Theorem is equivalent to the Universal Transfer Principle. Since the Universal Transfer Principle corresponds to WKL, it seems that, in ERNA’s Reverse Mathematics, the principles corresponding to WKL and WWKL coincide. Hence, ERNA’s Reverse Mathematics is actually coarser than classical Reverse Mathematics, although the base theory has lower first-order strength. (shrink)

Elementary Recursive Nonstandard Analysis, in short ERNA, is a constructive system of nonstandard analysis with a PRA consistency proof, proposed around 1995 by Patrick Suppes and Richard Sommer. Recently, the author showed the consistency of ERNA with several transfer principles and proved results of nonstandard analysis in the resulting theories (see [12] and [13]). Here, we show that Weak König's lemma (WKL) and many of its equivalent formulations over RCA₀ from Reverse Mathematics (see [21] and [22]) can be 'pushed down' (...) into the weak theory ERNA, while preserving the equivalences, but at the price of replacing equality with equality 'up to infinitesimals'. It turns out that ERNA plays the role of RCA₀ and that transfer for universal formulas corresponds to WKL. (shrink)

In this paper, we show within ${\mathsf{RCA}_0}$ that both the Jordan curve theorem and the Schönflies theorem are equivalent to weak König’s lemma. Within ${\mathsf {WKL}_0}$ , we prove the Jordan curve theorem using an argument of non-standard analysis based on the fact that every countable non-standard model of ${\mathsf {WKL}_0}$ has a proper initial part that is isomorphic to itself (Tanaka in Math Logic Q 43:396–400, 1997).

After sketching the main lines of Hilbert's program, certain well-known andinfluential interpretations of the program are critically evaluated, and analternative interpretation is presented. Finally, some recent developments inlogic related to Hilbert's program are reviewed.

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.

We show how one can obtain solutions to the Arzelà‐Ascoli theorem using suitable applications of the Bolzano‐Weierstraß principle. With this, we can apply the results from and obtain a classification of the strength of instances of the Arzelà‐Ascoli theorem and a variant of it. Let be the statement that each equicontinuous sequence of functions contains a subsequence that converges uniformly with the rate and let be the statement that each such sequence contains a subsequence which converges uniformly but possibly without (...) any rate. We show that is instance‐wise equivalent, over, to the Bolzano‐Weierstraß principle and that is instance‐wise equivalent, over, to, and thus to the strong cohesive principle (). Moreover, we show that over the principles, and are equivalent. (shrink)

In this paper the numerical strength of fragments of arithmetical comprehension, choice and general uniform boundedness is studied systematically. These principles are investigated relative to base systems Tnω in all finite types which are suited to formalize substantial parts of analysis but nevertheless have provably recursive functions of low growth. We reduce the use of instances of these principles in Tnω-proofs of a large class of formulas to the use of instances of certain arithmetical principles thereby determining faithfully the arithmetical (...) content of the former. This is achieved using the method of elimination of Skolem functions for monotone formulas which was introduced by the author in a previous paper.As corollaries we obtain new conservation results for fragments of analysis over fragments of arithmetic which strengthen known purely first-order conservation results.We also characterize the provably recursive functions of type 2 of the extensions of Tnω based on these fragments of arithmetical comprehension, choice and uniform boundedness. (shrink)

Kohlenbach, U., Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallée Poussin's proof for Chebycheff approximation, Annals of Pure and Applied Logic 64 27–94.We consider uniqueness theorems in classical analysis having the form u ε U, v1, v2 ε Vu = 0 = G→v 1 = v2), where U, V are complete separable metric spaces, Vu is compact in V and G:U x V → is a constructive function.If is proved by arithmetical means from analytical assumptions x (...) εXy ε Yx z ε Z = 0) only , then we can extract from the proof of → an effective modulus of uniqueness, which depends on u, k but not on v1,v2, i.e., u ε U, v1, v2 ε Vu, k εG, G 2-φuk→dv2-itk). Such a modulus φ can e.g. be used to give a finite algorithm which computes the zero of G on Vu with prescribed precision if it exists classically.The extraction of φ uses a proof-theoretic combination of functional interpretation and pointwise majorization. If the proof of → uses only simple instances of induction, then φ is a simple mathematical operation. (shrink)

Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.

A rank function for a directed graph G assigns elements of a well ordering to the vertices of G in a fashion that preserves the order induced by the edges. While topological sortings require a one-to-one matching of vertices and elements of the ordering, rank functions frequently must assign several vertices the same value. Theorems stating basic properties of rank functions vary significantly in logical strength. Using the techniques of reverse mathematics, we present results that require the subsystems ${\ensuremath{\vec{RCA}_0}}$ , (...) ${{\vec{ACA}_0}}$ , ${{\vec{ATR}_0}}$ , and ${{\vec{\Pi^1_1 - CA}_0}}$. (shrink)

Simpson has claimed that “ATR0 is the weakest set of axioms which permits the development of a decent theory of countable ordinals” [8]. This paper provides empirical support for Simpson's claim. In particular, Cantor's Normal Form Theorem and Sherman's Inequality for countable well-orderings are both equivalent to ATR0. The proofs of these results require a substantial development of ordinal exponentiation and a strengthening of the comparability result in [3].

If there is a homeomorphic embedding of one set into another, the sets are said to be topologically comparable. Friedman and Hirst have shown that the topological comparability of countable closed subsets of the reals is equivalent to the subsystem of second order arithmetic denoted byATR 0. Here, this result is extended to countable closed locally compact subsets of arbitrary complete separable metric spaces. The extension uses an analogue of the one point compactification of ℝ.

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 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)

Two countable well orderings are weakly comparable if there is an order preserving injection of one into the other. We say the well orderings are strongly comparable if the injection is an isomorphism between one ordering and an initial segment of the other. In [5], Friedman announced that the statement “any two countable well orderings are strongly comparable” is equivalent to ATR 0 . Simpson provides a detailed proof of this result in Chapter 5 of [13]. More recently, Friedman has (...) proved that the statement “any two countable well orderings are weakly comparable” is equivalent to ATR 0 . The main goal of this paper is to give a detailed exposition of this result. (shrink)

Extrapolating from the work of Mahlo , one can prove that given any pair of countable closed totally bounded subsets of complete separable metric spaces, one subset can be homeomorphically embedded in the other. This sort of topological comparability is reminiscent of the statements concerning comparability of well orderings which Friedman has shown to be equivalent to ATR0 over the weak base system RCA0. The main result of this paper states that topological comparability is also equivalent to ATR0. In Section (...) 1, the pertinent subsystems of second-order arithmetic and results on well orderings are reviewed. Sections 2 and 3 overview the encoding of metric spaces and homeomorphisms in second-order arithmetic. Section 4 contains a proof of the topological comparability result in ATR0. Section 5 contains the reversal, a derivation of ATR0 from the topological comparability result. In Section 6, additional information about the structure of the embeddings is obtained, culminating in an application to closed subsets of the real numbers. (shrink)

We study the formalization within sybsystems of second-order arithmetic of theorems concerning periodic points in dynamical systems on the real line. We show that Sharkovsky's theorem is provable in WKL0. We show that, with an additional assumption, Sharkovsky's theorem is provable in RCA0. We show that the existence for all n of n-fold iterates of continuous mappings of the closed unit interval into itself is equivalent to the disjunction of Σ02 induction and weak König's lemma.

The corpus of physical theory is a paradigm of knowledge. The evolution of modern physical theory constitutes the clearest exemplar of the growth of knowledge. If the development of physical theory does not constitute an example of progress and growth in what we know about the Universe nothing does. So anyone interested in the theory of knowledge must be interested consequently in the evolution and content of physical theory. Crucial to the conception of physics as a paradigm of knowledge is (...) the way in which physical theory provides explanations of a vast diversity of natural phenomena on the basis of a very few fundamental principles. A central problem for the epistemologist is therefore what is theoretical explanation in physics? Here we can get good insight from what Redhead has said. Indeed one could agree with almost everything Redhead says and simply endorse much of his careful and extensive defence of the covering law account of explanation in the physical sciences at least as an ideal. However I shall, I fear, try the reader's patience by extending some of the considerations he introduced and raising those issues where we disagree, especially in the important area of statistical explanation. (shrink)

Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples of Σ04 complete sets.