Lowness of higher randomness notions

被引：14
作者：
Chong, C. T. [1 ]
Nies, Andre [2 ]
Yu, Liang [3 ]
机构：
[1] Natl Univ Singapore, Fac Sci, Dept Math, Singapore 117543, Singapore
[2] Univ Auckland, Dept Comp Sci, Auckland 1, New Zealand
[3] Nanjing Univ, Inst Math Sci, Nanjing 210093, Peoples R China
来源：
ISRAEL JOURNAL OF MATHEMATICS | 2008年 / 166卷 / 01期
关键词：
D O I：
10.1007/s11856-008-1019-9
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We study randomness notions given by higher recursion theory, establishing the relationships Pi(1)(1)-randomness subset of Pi(1)(1)-Martin-Lof randomness subset of Delta(1)(1)-randomness = Delta(1)(1)-Martin-Lof randomness. We characterize the set of reals that are low for Delta(1)(1) randomness as precisely those that are Delta(1)(1)-traceable. We prove that there is a perfect set of such reals.
引用
收藏
页码：39 / 60
页数：22
相关论文
共 23 条
  • [1] COHEN PJ, 1966, SET THEORY CONTINUUM
  • [2] Feferman S., 1965, Fundamenta Mathematicae, V56, P325
  • [3] FEFERMAN S, 1962, J SYMBOLIC LOGIC, V27, P383
  • [4] GANDY RO, 1960, B ACAD POLONAIS SMAP, V8, P571
  • [5] Randomness via effective descriptive set theory
    Hjorth, Greg
    Nies, Andre
    [J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2007, 75 : 495 - 508
  • [6] Kechris A. S., 1973, Ann. Math. Logic, V5, P337
  • [7] THEORY OF COUNTABLE ANALYTICAL SETS
    KECHRIS, AS
    [J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 202 (FEB) : 259 - 297
  • [8] KECHRIS AS, 1983, LECT NOTES MATH, V1019, P199
  • [9] KJOSHANSSEN B, 2005, J COMPUTING, V35, P647
  • [10] Kurtz Stuart Alan, 1981, THESIS U ILLINOIS UR
123