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 ?



Intuition behind the non-Borel Lusin example
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](https://en.wikipedia.org/wiki/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}$.


