Arithmetical Measure
Sebastiaan A. Terwijn, Leen Torenvliet · Mathematical logic quarterly · 1998
Abstract We develop arithmetical measure theory along the lines of Lutz [10]. This yields the same notion of measure 0 set as considered before by Martin‐Löf, Schnorr, and others. We prove that the class of sets constructible by r.e.‐constructors, a direct analogue of the classes Lutz devised his resource bounded measures for in [10], is not equal to RE, the class of r.e. sets, and we locate this class exactly in terms of the common recursion‐theoretic reducibilities below K. We note that the class of sets that bounded truth‐table reduce to K has r.e.‐measure 0, and show that this cannot be improved to truth‐table. For Δ2‐measure the borderline between measure zero and measure nonzero lies between weak truth‐table reducibility and Turing reducibility to K. It follows that there exists a Martin‐Löf random set that is tt‐reducible to K, and that no such set is btt‐reducible to K. In fact, by a result of Kautz, a much more general result holds.