17
$\begingroup$

Robin Chapman introduced me to Conway's Base 13 Function. Now, my real analysis is a tiny bit rusty, so maybe my question has a really simple and quick answer, but here it goes:

Consider the support set of the base-13 function, is the set Lebesgue measurable? And if so, does it have non-zero measure?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ (a bit sheepishly) uh, yes guys. Thanks. Got it now. At least five people have told me that the set is Borel, and at least 3 of them with proofs (which all boils down to essentially the same argument). So while I do appreciate all the attention, you don't have to keep on reminding me that I learned measure theory "funny". =) $\endgroup$
    – Willie Wong
    Commented Jul 20, 2010 at 21:55
  • 1
    $\begingroup$ I know that this is an old question, but do you maybe know if it is true that all functions satisfying the intermediate value theorem measurable? $\endgroup$
    – Marko Karbevski
    Commented Dec 6, 2015 at 23:43

4 Answers 4

Reset to default
16
$\begingroup$

Call the support set $S$. The answer is yes it is Lebesgue measurable and no, it has zero measure. It is even Borel measurable, which would take a tiny bit more effort to prove.

Note that $S$ is included in the set $T$ of numbers in which the "digits" '+','-', and '.' appear finitely many times in the "base 13 expansion". But almost all numbers are normal, hence have all digits appearing infinitely often. So the Borel set $T$ has measure zero, hence $S$ is Lebesgue measurable with measure zero.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah. I got as far as the lack of normality of the tredecimal expansion. But I forgot that real numbers are almost surely normal. (Now off to tracking down Borel's original proof of this fact, since I've never actually seen it.) $\endgroup$
    – Willie Wong
    Commented Jul 20, 2010 at 15:00
  • 3
    $\begingroup$ Well we don't even really need the full version of normality, just that every digit occurs infinitely often. To see this it is enough to note if we select a number in [0,1) at random according to Lebesgue measure, then its digits in base n are i.i.d. uniform over $\{0,\ldots, n-1\}$. Therefore the probability that any given digit doesn't occur is zero. There are countably many digits and bases, so a.s. in any base all digits will occur. This means they will all occur infinitely often, because if say $5$ only occurred $k$ times then $5\cdots 5$ ($k+1$ times) would never occur in $\endgroup$
    – Noah Stein
    Commented Jul 20, 2010 at 15:40
  • $\begingroup$ the base $10^{k+1}$ representation. $\endgroup$
    – Noah Stein
    Commented Jul 20, 2010 at 15:41
  • 3
    $\begingroup$ The probability that the base-13 expansion of a uniformly distributed random number in (0,1) has contains only digits 0-9 starting at the N-th digit is $\prod_{n=N}^\infty(10/13)=0$. This is also a Borel set (intersection of a countable sequence of Borel sets defined by the $n$-th digit). A countable union of measure zero Borel sets is a measure zero Borel set. $\endgroup$
    – Robin Chapman
    Commented Jul 20, 2010 at 17:59
9
$\begingroup$

The function is easily seen to be Borel, since the graph of the function can be defined using only natural number quantifiers. In particular, a number is in the support if and only if there is a last place in its digits where $+$ or $-$ appears, followed eventually by ., but then after this, +, - and . do not appear again. That is,

  • $x\in S\iff\exists n_1\exists n_2\gt n_1\forall m\geq n_1$ the $m^{\rm th}$ digit of $x$ in base 13 is neither $+$ nor $-$ nor ., except at $n_1$, where it is either $+$ or $-$ and and $n_2$, where it is .

Any set of reals that is definable using only natural number quantification is Borel, since existential quantification over the naturals corresponds to a countable union and universal quantification corresponds to countable intersection. Such sets lie in the arithmetic hierarchy, which is a very low part of the hyperarithmetic hiearchy, which leads ultimately to the Borel sets.

The same idea shows that the graph of the function, as a set of pairs, is Borel.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Joel: thanks for the great answer. I'm not that great with logic and set theory, but am I correct in interpreting that in this specific instance, using the fact that semi-closed intervals are Borel, and that $S$ can be defined by a countable union (over $n_1,n_2$) of countable intersections (over the tredecimal levels) of countable union (for each level there are finitely many allowed semi-closed intervals), we have that $S$ is automatically Borel. And that this notion has a proper generalization in the theorem that you stated? $\endgroup$
    – Willie Wong
    Commented Jul 20, 2010 at 20:51
  • 2
    $\begingroup$ Yes, that's right. It is easier generally from this perspective to work with Cantor space, and think about reals explicitly as sequences. The basic finitary features of the sequences correspond to open sets, and quantification over naturals gives countable unions and intersections. Of course, this doesn't exhaust the Borel sets, but only the arithmetic sets. But this way of thinking provides a quick sufficient criterion for being Borel. $\endgroup$
    – Joel David Hamkins
    Commented Jul 20, 2010 at 20:58
  • $\begingroup$ You also need to know that a function being Borel in the pre-image sense is the same as its graph being a Borel subset of the plane. $\endgroup$
    – Joel David Hamkins
    Commented Jul 20, 2010 at 20:59
  • $\begingroup$ Joel: thanks again for the clarification. It is very illuminating. I am now certainly glad to have asked the question. $\endgroup$
    – Willie Wong
    Commented Jul 20, 2010 at 21:11
6
$\begingroup$

It seems that the definition of the function doesn't use the axiom of choice. This implies that the support set should be Lebesgue measurable.

Improve this answer
$\endgroup$
13
  • 3
    $\begingroup$ I agree with that as heuristics, but is that actually a theorem? :) $\endgroup$
    – Willie Wong
    Commented Jul 20, 2010 at 15:01
  • 4
    $\begingroup$ Andrey, Solovay's result does not give this implication. It is, however, a theorem that (assuming large cardinals) the fact that the function is explicitly described implies measurability. Depending on the actual large cardinals one assumes, credits may vary. It is safe to call it a theorem of Shelah-Woodin. $\endgroup$
    – Andrés E. Caicedo
    Commented Jul 20, 2010 at 16:28
  • 1
    $\begingroup$ This previous question mathoverflow.net/questions/23834/… seems also relevant. $\endgroup$
    – damiano
    Commented Jul 20, 2010 at 16:56
  • 1
    $\begingroup$ In fact this function is Borel measurable, so no need to worry about AC and inaccessible cardinals and such. $\endgroup$
    – Gerald Edgar
    Commented Jul 20, 2010 at 19:40
  • 1
    $\begingroup$ @Andres: why the sarcasm? When a result in number theory is shown to follow from an extremely convincing "axiom", such as the Riemann hypothesis or (cf. the $\pi(x+y)$ subadditivity conjecture) the prime k-tuplets conjecture, this is clearly distinguished from a proof in the intended/standard/tacit system, such as number theory using ordinary axioms, or ZF, or PA. And that distinction is as significant as the difference between what Solovay and Shelah+Woodin proved. $\endgroup$
    – T..
    Commented Jul 23, 2010 at 7:32
1
$\begingroup$

The function is certainly Borel measurable, and hence so it its support set. The function $f_k(x)$ which gives the $k$th tredigit of $x$ is clearly a Borel function, and it should be a straightforward if tedious exercise to write the base-13 function in terms of the $f_k$, using only common Borel functions (arithmetic, max/min, indicators) and limits.

Of course the fact that no "nonconstructive" arguments are used in its definition is strong evidence that such a procedure should be possible, and if you know enough logic, as others have mentioned, this can even be a proof. I just wanted to point out that one can prove the measurability from first principles with a little elbow grease.

Improve this answer
$\endgroup$
1
  • $\begingroup$ re: "this can even be a proof" --- the results from logic don't quite show that a reasonably defined $f$ has a proof (in the system that defined it) of its Lebesgue measurability. They do show consistency of $f$ being measurable, and that there are natural axioms that, when added to the system, provide a universal proof (not referring to the construction details of any specific $f$) that any reasonable function is measurable. $\endgroup$
    – T..
    Commented Jul 20, 2010 at 22:23

You must log in to answer this question.

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