Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...

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)

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.

Working in the language of first-order arithmetic we consider models of the base theory P - . Suppose M is a model of P - and let M satisfy induction for σ 1 -formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the "amount" of induction needed to perform the known finite (...) injury priority arguments is Σ 1 -induction. (shrink)

In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.