Problems - Jan 19 2024 - Reading topics

Sum operator

Definition. We say that a rational sequence (a_i) is {} if it is computable, a_i < \sum_{j>i} a_j and \sum_{j>i} a_j is a computable real <1.

We fix admissible (a_i) and let \mathsf{A}[X]:=\sum_{i\in X} a_i.


Question. Is it true that:

Question. Is it true that:

About random left c.e. reals

Definition. Let \leq_s be the Solovay reducibility on the left c.e. reals and

For left c.e. reals, \alpha<_s\gamma iff there exists rational c>0 and left c.e. \beta with c\cdot \gamma=\alpha+\beta.

Exercise. Show that there are \emptyset'-left c.e. reals \alpha,\gamma such that \alpha is random, \beta is not random and \alpha\leq_s^1 \gamma?

Remark 1. This says that 1-randomness is not upward \leq_s^1-closed in the \emptyset'-left c.e. reals. In contrast, 2-randomness is upward \leq_s^1-closed in the \emptyset'-left c.e. reals.

Hint. You need to produce \emptyset'-left c.e. \alpha,\gamma which are not \emptyset'-random, and although \alpha is less compressible than \gamma, relative to oracle \emptyset' it is more compressible than \gamma. For example, \alpha=\Omega and \gamma=\Omega^{\emptyset'}\oplus \emptyset. Here you need to use the fact that if \alpha\ll_K^1\gamma then \alpha\ll_s^1\gamma; this is a relativization of a known fact due to Stephan.

Remark 2. By the hint above, there exists \beta\leq_T\emptyset' such that \Omega+\beta is not random. By the result in `differences of halting probabilities’, this \beta can be chosen to be random and a d.c.e. real (the difference of two left c.e. reals). So the sum of two (positive) random reals may not be random. In this case, it is necessary that one of them is left c.e. and the other is a real. For each random left c.e. \alpha there exists random \beta such that \alpha-\beta is not random.

Question. Is it true that for each nonrandom left c.e. real \alpha there exists:

The question if, given left c.e. \alpha there exists left c.e. \beta with \alpha+\beta having a certain property is the same as asking if there exists left c.e. \gamma\geq_s \alpha with the said property.

So we ask if for each nonrandom left c.e. real \alpha there exists:

Push game

Two players produce an increasing sequence r_s by adding increases in turn. Player 2 wins if r:=\lim_s r_s is outside a given open set V. The increases available to Player 1 are chosen (without repetition) from the terms of a given admissible (a_i) (many a_i can be chosen at once). Similarly for Player 2 with respect to admissible (b_i).

Formally, given an effectively open set V with \mu(V)=1/2 and admissible sequences (a_i), (b_i), two players pick sets F_0, G_0, F_1, G_1,\dots in turns, so that

Player 2 wins if there exists increasing (t_s) with \forall s,\ r_{2s}\not\in V_{t_s}. Who wins?