Switch to: Citations

References in:

A measure-theoretic proof of Turing incomparability

Chris J. Conidis

Annals of Pure and Applied Logic 162 (1):83-88 (2010)

Add references

You must login to add references.

Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.details 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) Download Export citation Bookmark 34 citations
The baire category theorem in weak subsystems of second-order arithmetic.Douglas K. Brown & Stephen G. Simpson - 1993 - Journal of Symbolic Logic 58 (2):557-578.details 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 (...) Download Export citation Bookmark 15 citations
On relative randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.details Kuera, A., On relative randomness, Annals of Pure and Applied Logic 63 61–67. It is the aim of the paper to answer a question raised by M. van Lambalgen and D. Zambella whether there can be a nonrecursive set A having the property that there is a set B such that B is 1-random relative to A and simultaneously A is recursive in B. We give apositive answer to this question as well as further information about relative randomness. Download Export citation Bookmark 12 citations

1