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)

Arithmetical comprehension is proved to be equivalent to the enumerability of singular points of any measure on the Cantor space. It is provable in ACA0 that any perfect closed subset of [0, 1] is the support of some continuous positive linear functional on C[0, 1].

In this paper, we show within RCA 0 that weak Konig's lemma is necessary and sufficient to prove that any (separable) compact group has a Haar measure. Within WKL 0 , a Haar measure is constructed by a non-standard method based on a fact that every countable non-standard model of WKL 0 has a proper initial part isomorphic to itself [10].

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 uncountability of$\mathbb {R}$is one of its most basic properties, known far outside of mathematics. Cantor’s 1874 proof of the uncountability of$\mathbb {R}$even appears in the very first paper on set theory, i.e., a historical milestone. In this paper, we study the uncountability of${\mathbb R}$in Kohlenbach’shigher-orderReverse Mathematics (RM for short), in the guise of the following principle:$$\begin{align*}\mathit{for \ a \ countable \ set } \ A\subset \mathbb{R}, \mathit{\ there \ exists } \ y\in \mathbb{R}\setminus A. \end{align*}$$An important conceptual observation is (...) that the usual definition of countable set—based on injections or bijections to${\mathbb N}$—does not seem suitable for the RM-study of mainstream mathematics; we also propose a suitable (equivalent over strong systems) alternative definition of countable set, namelyunion over${\mathbb N}$of finite sets; the latter is known from the literature and closer to how countable sets occur ‘in the wild’. We identify a considerable number of theorems that are equivalent to the centred theorem based on our alternative definition. Perhaps surprisingly, our equivalent theorems involve most basic properties of the Riemann integral, regulated or bounded variation functions, Blumberg’s theorem, and Volterra’s early work circa 1881. Our equivalences are alsorobust, promoting the uncountability of${\mathbb R}$to the status of ‘big’ system in RM. (shrink)

For several subsystems of second order arithmetic T we show that the proof-theoretic strength of T + (bar rule) can be characterized in terms of T + (bar induction) □ , where the latter scheme arises from the scheme of bar induction by restricting it to well-orderings with no parameters. In addition, we demonstrate that ACA + 0 , ACA 0 + (bar rule) and ACA 0 + (bar induction) □ prove the same Π 1 1 -sentences.

In this paper, we investigate the logical strength of two types of fixed point theorems in the context of reverse mathematics. One is concerned with extensions of the Banach contraction principle. Among theorems in this type, we mainly show that the Caristi fixed point theorem is equivalent to math formula over math formula. The other is dedicated to topological fixed point theorems such as the Brouwer fixed point theorem. We introduce some variants of the Fan-Browder fixed point theorem and the (...) Kakutani fixed point theorem, which we call math formula and math formula, respectively. Then we show that math formula is equivalent to math formula and math formula is equivalent to math formula, over math formula. In addition, we also study the application of the Fan-Browder fixed point theorem to game systems. (shrink)

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.

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)

We continue the work of [14, 3, 1, 19, 16, 4, 12, 11, 20] investigating the strength of set existence axioms needed for separable Banach space theory. We show that the separation theorem for open convex sets is equivalent to WKL 0 over RCA 0 . We show that the separation theorem for separably closed convex sets is equivalent to ACA 0 over RCA 0 . Our strategy for proving these geometrical Hahn-Banach theorems is to reduce to the finite-dimensional case (...) by means of a compactness argument. (shrink)

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 ℝ.

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, (...) using only RCA0 and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman , which can be roughly characterized by the strength of their set comprehension axioms. RCA0 includes comprehension for Δmath image definable sets, ACA0 includes comprehension for arithmetical sets, and ATR0 appends to ACA0 a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99. (shrink)

We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement “every compact space is Lebesgue” is equivalent to $\hbox{\sf WKL}_0$ ; the statements “every perfect Lebesgue space is compact” and “every perfect Atsuji space is compact” are equivalent to (...) $\hbox{\sf ACA}_0$ ; the statement “every Lebesgue space is Atsuji” is provable in $\hbox{\sf RCA}_0$ ; the statement “every Atsuji space is Lebesgue” is provable in $\hbox{\sf ACA}_0$ . We also prove that the statement “the distance from a closed set is a continuous function” is equivalent to $\Pi^1_1\hbox{-\sf CA}_0$. (shrink)

Let X be a compact metric space. A closed set K $\subseteq$ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) $>$ r is Σ 0 1 allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA 0 , WKL (...) 0 and ACA 0 . We also give some applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA 0 version of this result for weakly located closed sets. (shrink)

We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the class (...) of Sep-computable multivalued functions. Extending work of Brattka, we show that a natural multivalued function associated with the Hahn-Banach Extension Theorem is Sep-complete. (shrink)

Recent technical developments in the logic of nominalism make it possible to improve and extend significantly the approach to mathematics developed in Mathematics without Numbers. After reviewing the intuitive ideas behind structuralism in general, the modal-structuralist approach as potentially class-free is contrasted broadly with other leading approaches. The machinery of nominalistic ordered pairing (Burgess-Hazen-Lewis) and plural quantification (Boolos) can then be utilized to extend the core systems of modal-structural arithmetic and analysis respectively to full, classical, polyadic third- and fourthorder number (...) theory. The mathenatics of many structures of central importance in functional analysis, measure theory, and topology can be recovered within essentially these frameworks. (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.

It is a striking fact from reverse mathematics that almost all theorems of countable and countably representable mathematics are equivalent to just five subsystems of second order arithmetic. The standard view is that the significance of these equivalences lies in the set existence principles that are necessary and sufficient to prove those theorems. In this article I analyse the role of set existence principles in reverse mathematics, and argue that they are best understood as closure conditions on the powerset of (...) the natural numbers. (shrink)

Continuing the investigations of X. Yu and others, we study the role of set existence axioms in classical Lebesgue measure theory. We show that pairwise disjoint countable additivity for open sets of reals is provable in RCA0. We show that several well-known measure-theoretic propositions including the Vitali Covering Theorem are equivalent to WWKL over RCA0.

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call RCA+ 0 and WKL+ 0, and show that RCA+ 0 suffices to prove B.C.T.II. Some model theory of WKL+ 0 and its importance in view of (...) Hilbert's program is discussed, as well as applications of our results to functional analysis. (shrink)

A logic-enriched type theory is a type theory extended with a primitive mechanism for forming and proving propositions. We construct two LTTs, named and , which we claim correspond closely to the classical predicative systems of second order arithmetic and . We justify this claim by translating each second order system into the corresponding LTT, and proving that these translations are conservative. This is part of an ongoing research project to investigate how LTTs may be used to formalise different approaches (...) to the foundations of mathematics.The two LTTs we construct are subsystems of the logic-enriched type theory , which is intended to formalise the classical predicative foundation presented by Herman Weyl in his monograph Das Kontinuum. The system has also been claimed to correspond to Weyl’s foundation. By casting and as LTTs, we are able to compare them with . It is a consequence of the work in this paper that is strictly stronger than .The conservativity proof makes use of a novel technique for proving one LTT conservative over another, involving defining an interpretation of the stronger system out of the expressions of the weaker. This technique should be applicable in a wide variety of different cases outside the present work. (shrink)