Non-Borel set/Advanced

Usually, it is rather easy to prove that a given set is Borel (see below). It is much harder to prove that the set A is non-Borel; see Advanced if you are acquainted with descriptive set theory. If you are not, you may find it instructive to try proving that A is Borel and observe a failure.

A. The set of all numbers x such that $a_{0}=3$ is an interval, therefore a Borel set.

B. The condition "$a_{1}=3$" leads to a countable union of intervals; still a Borel set.

C. The same holds for the condition "$a_{2}=3$" and, more generally, "$a_{k}=n$" for given k and n.

D. The condition "$a_{k}<n$" leads to the union of finitely many sets treated in C; still a Borel set.

E. The condition "$a_{k}>n$" leads to the complement of a set treated in D; still a Borel set.

F. The condition "$a_{k}>n$ for all k" leads to the intersection of countably many sets treated in E; still a Borel set. The same holds for the condition "$a_{k}>7$ for all $k>3$" and, more generally, "$a_{k}>n$ for all $k>m$ for given $m,n.$

G. The condition "$a_{k}>7$ for all k large enough" leads to the union of countably many sets treated in F; still a Borel set.

H. The condition "the sequence $a_{1},a_{2},a_{3},\dots$ tends to infinity" leads to the intersection of countably many sets of the form treated in G ("7" being replaced with arbitray natural number). Still a Borel set!

This list can be extended in many ways, but never reaches the set A. Indeed, the definition of A involves arbitrary subsequences. For given $k_{0}<k_{1}<k_{2}<\dots$ the corresponding set is Borel. However, A is the union of such sets over all $k_{0}<k_{1}<k_{2}<\dots$; a uncountable union!

Do not think, however, that uncountable union of Borel sets is always non-Borel. The matter is much more complicated since sometimes the same set may be represented also as a countable union (or countable intersection) of Borel sets. For instance, an interval is a uncountable union of single-point sets, which does not mean that the interval is non-Borel.