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)

We investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA 0 whose principal axioms are ▵ 0 1 comprehension and Σ 0 1 induction. Our main result is that, over RCA 0 , the Cauchy/Peano Theorem is provably equivalent to weak Konig's lemma, i.e. the statement that every infinite {0, 1}-tree (...) has a path. We also show that, over RCA 0 , the Ascoli lemma is provably equivalent to arithmetical comprehension, as is Osgood's theorem on the existence of maximum solutions. At the end of the paper we digress to relate our results to degrees of unsolvability and to computable analysis. (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)