Randomness via effective descriptive set theory

被引：19

作者：

Hjorth, Greg ^{[1
]}

Nies, Andre

机构：

[1] Univ Melbourne, Dept Math & Stat, Parkville, Vic 3010, Australia

[2] Univ Auckland, Dept Comp Sci Off, Auckland 1, New Zealand

来源：

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES | 2007年 / 75卷

基金：

美国国家科学基金会;

关键词：

D O I：

10.1112/jlms/jdm022

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：495 / 508

页数：14