Randomness via effective descriptive set theory
Greg Hjorth, André Nies · Journal of the London Mathematical Society · 2007
An analog of Martin-Löf randomness in the effective descriptive set theory setting is studied, where the recursively enumerable objects are replaced by their Π11 counterparts. We prove the analogs of the Kraft–Chaitin theorem and Schnorr's theorem. In the new setting, while K-trivial sets exist that are not hyperarithmetical, each low for random set is. Finally, we begin to study a very strong yet effective randomness notion: Z is Π11-random if Z is in no null Π11-class. There is a greatest Π11 null class, that is a universal test for this notion.