7
$\begingroup$

Throughout the question ITTM refers to Hamkins' infinite Turing machines, though I will be interested in results related to stronger models.

Recently I was wondering, is it consistent that there is an ITTM which recognizes a set of reals which is not Lebesgue measurable? Here with "recognizable" I mean that the set has a form $\{r:$M halts on $r\}$ for some ITTM M.

It is consistent (relative to an inaccessible) that there are no non-measurable sets, so it's consistent that every recognizable set is measurable.

Very similar questions can be asked about sets with Baire or perfect set properties. I have tried to find something about complexity of measurable sets that could resolve this, but I couldn't find anything.

Thanks in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

Nice question!

The answer is no, because if a set of reals $A$ is infinite time semi-decidable, then it is $\Delta^1_2$, and not only $\Delta^1_2$, but absolutely $\Delta^1_2$, in the sense that the equivalent $\Sigma^1_2$ and $\Pi^1_2$ characterizations continue to be equivalent in all forcing extensions. This can be seen by using the fact that every infinite time computation either halts in some countable ordinal number of steps or repeats (in the suitably strong sense of repeating that we mention in the main paper on ITTMs). That is, for the $\Sigma^1_2$ side, a real $x$ is in $A$ just in case there is a well-founded computation according to program $p$ accepting $x$; and for the $\Pi^1_2$ side, $x$ is not in $A$ just in case there is a well-founded computation according to program $p$ that either rejects $x$ or else is strongly repeating. But it is an old result of Bob Solovay (see Kanamori exercise 14.4) that every absolutely $\Delta^1_2$ set of reals is Lebesgue measurable.

This argument appears in my joint article:

In that article, Sam and I undertake to develop the analogue of Borel equivalence relation theory, but using infinite time computable reductions in place of Borel reductions. So it is a nice blend of descriptive set theory and infinitary computability. Along the way we prove the following, using essentially the same argument I gave above.

Theorem 2.6 Every infinite time eventually computable function is absolutely $\Delta^1_2$.

Corollary 2.7 Every infinite time eventually decidable set is measurable. Every infinite time eventually computable function is a measurable function.

Note that eventually decidable is a weaker property than semi-decidable, but there are some subtle issues with partial functions, as mentioned in the article.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Can someone provide a better reference for Solovay's result? $\endgroup$
    – Joel David Hamkins
    Commented May 27, 2015 at 14:58
  • $\begingroup$ Doesn't it appears in his paper about all sets measurable? $\endgroup$
    – Asaf Karagila ♦
    Commented May 27, 2015 at 15:21
  • 2
    $\begingroup$ It is exercise 14.4 in Kanamori's book together with a reasonable hint. $\endgroup$
    – Stefan Hoffelner
    Commented May 27, 2015 at 16:14
  • 1
    $\begingroup$ @StefanHoffelner Thanks for that, and I see now that Sam and I cited that exercise in our paper when giving this same argument there. I knew the question seemed familiar! $\endgroup$
    – Joel David Hamkins
    Commented May 27, 2015 at 17:16
  • 1
    $\begingroup$ @Wojowu For Ordinal Turing Machines (OTM), decidable sets of reals are exactly $Δ^1_2$ and thus cannot be proved to be measurable in ZFC (without large cardinal axioms). Absolutely $Δ^1_2$ sets are precisely those that are accepted by some OTM that halts (accepting or rejecting) for every real in every generic extension of V. Also, absolutely $Δ^1_2$ sets are universally Baire (which implies measurability). $\endgroup$
    – Dmytro Taranovsky
    Commented Sep 25, 2017 at 20:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .