An analog of Martin-Lof randomness in the effective descriptive set theory setting is studied, where the recursively enumerable objects are replaced by their Pi(1)(1) 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 Pi(1)(1)-random if Z is in no null Pi(1)(1)-class. There is a greatest Pi(1)(1) null class, that is a universal test for this notion.
展开▼
