Premium
Arithmetical Measure
Author(s) -
Terwijn Sebastiaan A.,
Torenvliet Leen
Publication year - 1998
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19980440211
Subject(s) - measure (data warehouse) , mathematics , arithmetic function , null set , class (philosophy) , turing machine , bounded function , discrete mathematics , recursion (computer science) , set (abstract data type) , computability theory , combinatorics , computer science , algorithm , mathematical analysis , database , artificial intelligence , computation , programming language
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.