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.

$\endgroup$

1 Answer 1

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.

$\endgroup$
8
  • $\begingroup$ Can someone provide a better reference for Solovay's result? $\endgroup$ May 27, 2015 at 14:58
  • $\begingroup$ Doesn't it appears in his paper about all sets measurable? $\endgroup$
    – Asaf Karagila
    May 27, 2015 at 15:21
  • 2
    $\begingroup$ It is exercise 14.4 in Kanamori's book together with a reasonable hint. $\endgroup$ 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$ 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$ Sep 25, 2017 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.