6
$\begingroup$

Among the concrete examples of a non-borel subset of $\mathbb{R}$, I know only the Lusin example.

This is the set $L$ of all irrational numbers whose continued fraction representation $(a_0,a_1,\cdots)$ is such that there exist an infinite subsequence $(a_{k_0},a_{k_1},\cdots)$ such that each for all $j$, $a_{k_j}$ divides $a_{k_{j+1}}$.

Knowing this, I am totally unable to see why this set $L$ would not be Borel, is there some intuition behind this ? What is the idea behind the proof of this fact ?

$\endgroup$
1
  • $\begingroup$ The more natural examples of analytic non-Borel sets in Polish spaces have the disadvantage of being in Polish spaces other than $\mathbb R$. Even this one is sort of artificially inserted into $\mathbb R$ by taking an example in the Baire space $\mathbb N^\mathbb N$ and using continued fractions to map it into $\mathbb R$. $\endgroup$ Commented Nov 3, 2016 at 12:49

1 Answer 1

3
$\begingroup$

I definitely don't think this is a good "first example" of an analytic non-Borel set. It does, however, make more sense when put in comparison with the standard example of a co-analytic, non-Borel set:

Given a binary relation $R$ on $\mathbb{N}$, we can code $R$ by a set $X_R\subseteq\mathbb{N}$: let $\langle \cdot,\cdot\rangle$ be a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ (e.g. the Cantor pairing function), and let $$X_R=\{\langle m, n\rangle: mRn\}.$$ Now for a property $\mathfrak{P}$ of relations, let $S_\mathfrak{P}$ be the family of sets coding relations with that property. E.g. $S_{\mbox{linear}}$ is the family of sets which code linear orders of $\mathbb{N}$, and so forth.

It's not hard to see that $S_{\mbox{linear}}$ is Borel, indeed closed. It turns out that a good way to get Borel sets of high complexity, and non-Borel sets, is to look at sets of the form $S_\mathfrak{P}$ for more complicated properties $\mathfrak{P}$.

One important property of relations is well-foundedness: call a relation $R$ well-founded if there is no infinite sequence $a_0R a_1R a_2R...$. And the associated family of sets is $S_{WF}$.

It's not hard to show that $S_{WF}$ is co-analytic. (Strictly speaking, I've described $S_{WF}$ as a subset of $2^\omega$, not $\mathbb{R}$; but it's easy to switch it over, e.g. via the standard bijection between $2^\omega$ and the middle-thirds Cantor set.) But it turns out that $S_{WF}$ is not Borel!

Why? Well, remember that the Borel sets are arranged in a hierarchy, indexed by countable ordinals (the $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ sets, as $\alpha\in\omega_1$). Now, a well-founded relation has a rank - a countable ordinal that measures how complicated it is. Bigger ranks mean, intuitively, that the relation is "closer to being ill-founded". The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations. And this means that the set $S_{WF}$ is not, in fact, Borel.

This is of course not a proof - the details are much more complicated. But this is the idea: there's a connection between the complexity of a Borel set, and its ability to distinguish well-founded relations from ill-founded ones.

This motivates the following general intuition:

If I have a set defined in terms of quantification over infinite sequences, rather than only over natural numbers, then that set probably isn't Borel.

There are of course counterexamples, but this is a good rule of thumb. And the example you mention, of course, is of this kind. It's kind of the opposite of $S_{WF}$: $S_{WF}$ was defined by saying that there is no sequence of a certain form, whereas your set is defined by saying that there is a sequence of a certain form. So a natural thing to do is try to find a Borel isomorphism between your set and the complement of $S_{WF}$.

$\endgroup$
13
  • 1
    $\begingroup$ Unless I overlooked a negation somewhere in the definitions, $S_{WF}$ is not analytic but co-analytic. $\endgroup$ Commented Nov 3, 2016 at 2:34
  • $\begingroup$ @AndreasBlass Dangit! Of course you're right, I was typing too fast. Fixed. $\endgroup$ Commented Nov 3, 2016 at 2:46
  • $\begingroup$ Thank you for your answer, it helps giving a better idea of what is behind. I think that the difficulty I have to understand intuitively the failure of being Borel starts early in the argument. I have only a very basic intuition of being Borel, which is based on the topology of $\mathbb{R}$. $\endgroup$
    – Jon-S
    Commented Nov 3, 2016 at 14:01
  • $\begingroup$ ... Basically, I "feel" (intuitively) that a Borel is something that can be constructed by iteration of a process of the form : take countable unions or intersections of sets built from taking countable unions or intersections of sets built from... (etc.) ...from open or closed sets of $\mathbb{R}$. When we work with $2^\omega$ instead, I kind of lose my (topological) intuition. For example, I don't "see" why $S_{linear}$ is closed. $\endgroup$
    – Jon-S
    Commented Nov 3, 2016 at 14:05
  • 1
    $\begingroup$ @WillBrian It's just $\Sigma^1_1$-bounding relativized to the Borel code. Suppose $\sigma$ is a real coding a Borel set $B_\sigma$ which contains only (reals that represent) well-founded relations. Let $\alpha$ be the least $\sigma$-noncomputable ordinal. If any well-ordering of ordertype $\ge\alpha$ were in $B_\sigma$, we would be able to determine which $\sigma$-computable linear orders are well-orders in a $\Sigma^1_1$-in-$\sigma$ way, namely by asking whether the order in question embedded into some element fo $B_\sigma$. This can't happen, by (relativized) $\Sigma^1_1$ bounding. $\endgroup$ Commented Apr 3, 2023 at 16:44

You must log in to answer this question.

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