Extracting randomness within a subset is hard
- PDF / 339,448 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 175 Views
Extracting randomness within a subset is hard Bjørn Kjos-Hanssen1 · Lu Liu2 Received: 17 December 2018 / Revised: 10 May 2019 / Accepted: 11 July 2019 © Springer Nature Switzerland AG 2019
Abstract The tree forcing method of Liu enables the cone avoiding of bounded enumeration of a given tree, within subsets or co-subsets of an arbitrary given set, provided the given tree does not admit computable bounded enumeration. Using this result, he settled and reproduced a series of problems and results in reverse mathematics and the theory of algorithmic randomness, including showing that every 1-random set has an infinite subset or co-subset which computes no 1-random set. In this paper, we show that for any given 1-random set A, there exists an infinite subset G of A such that G does not compute any set with positive effective Hausdorff dimension. In particular, we answer in the affirmative Kjos-Hanssen’s 2006 question whether each 1-random set has an infinite subset which computes no 1-random set. The result is surprising in that the tree forcing technique seems to heavily rely on subset co-subset combinatorics, whereas this result does not. Keywords Computability theory · Algorithmic randomness · Mathias forcing Mathematics Subject Classification 68Q30 · 03D32 · 03D80 · 28A78
This work was partially supported by a Grant from the Simons Foundation (# 315188 to Bjørn Kjos-Hanssen). Lu Liu is partially supported by the Natural Science Foundation of Hunan Province of China 2018JJ3623.
B
Lu Liu [email protected] Bjørn Kjos-Hanssen [email protected]
1
Department of Mathematics, University of Hawai‘i at M¯anoa, Honolulu 96822, USA
2
Department of Mathematics and Statistics, Central South University, Changsha 410083, People’s Republic of China
123
B. Kjos-Hanssen, L. Liu
1 Introduction Computability theory aims to classify real numbers, or equivalently infinite binary sequences, by their relative computational power. This is done by means of several orderings, the most fundamental of which may be that of the Turing degrees. For instance, 0 is the Turing degree of computable sequences, which are all regarded as trivial. Next, 0 is the Turing degree of the sequence of answers for the halting problem for Turing machines. It is also the Turing degree of many natural problems such as solvability of diophantine equations. On the other hand, if we choose the bits of our sequence randomly enough to have no computable pattern, roughly speaking, we get a collection of Turing degrees r that are called Martin–Löf random. Some of these are comparable with 0, but most are not. Such a degree r consists of a random sequence R, which can also be viewed as a set R ⊆ ω = N, together with all sequences that are computationally equivalent to R. The problem of computing a Martin–Löf random set also arises in reverse mathematics in the guise of the formal system WWKL0 (Weak Weak König’s Lemma), discussed below. Martin–Löf random sets are also known as 1-random, and can be contrasted with “more random” sets (2-random an
Data Loading...
