Random reals and Martin-Löf randomness

504 Views Asked by At

My questions are about the relationship between the following notions of randomness:

  1. A real $r$ is random over the model $M$ if $r\notin B$ for every null Borel set $B$ coded in $M$.

  2. A real $r$ is Martin-Löf random if $r\notin U$ for every $G_{\delta}$ set $U$ determined by a constructive null cover (you can read the complete definition here).

Although these two definitions are obviously different, they do share some similarities.

Question 1: Are there any interesting theorems that shed some light on the relationship between these two notions of randomness?

Question 2: Define the real $r$ to be Martin-Löf over $M$ if $r$ avoids every $G_{\delta}$ set coded in $M$ that is determined by a constructive null cover. What interesting forcing notions have generic reals that are Martin-Löf over the original model (you may restrict yourself to the case of nicely defined forcing notions, such as Suslin forcing notions or nep forcing)? Are there any interesting characterizations for such reals?

Question 3: Has any interesting work been done on the effective version of random real forcing, where the Borel sets are replaced by $\Pi_n^0$ sets of positive measure?

As I'm quite a newbie to algorithmic randomness, I suspect that the above questions are either trivial or well known, so feel free to simply give references to works that answer these questions.

1

There are 1 best solutions below

0
On

Any transitive model M of ZFC contains a code for every "constructive" null G-delta set and much more. So if a real is random over M, then it is not only ML random but also n-random for every n. Furthermore, the set of non ML randoms is a null (lightface) $\Pi_2^0$ set so it is coded in M. Hence, any forcing notion that adds a real outside this set (for example, Sacks forcing below a perfect set avoiding the non MLR's), adds an ML random. One major issue that I see with "effectivizing" random forcing is that any effective collection is countable and the only non trivial countable forcing is Cohen forcing. What is generally done is to only require the generic to meet some effective family of dense sets and not all dense sets in M. This gives rise to n-random and n-generic hierarchies.