Arithmetical Measure

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.