Editing Borel set (section)

== Non-Borel sets ==
{{anchor|counterexample}}
An example of a subset of the reals that is non-Borel, due to [[Nikolai Luzin|Lusin]],<ref>{{Citation | language=fr | last=Lusin | first=Nicolas | year=1927 | title=Sur les ensembles analytiques | journal=[[Fundamenta Mathematicae]] | volume=10 |url=https://www.impan.pl/en/publishing-house/journals-and-series/fundamenta-mathematicae/all/25/0/93222/sur-les-ensembles-analytiques-nuls|pages=Sect. 62, pages 76–78| doi=10.4064/fm-10-1-1-95 | doi-access=free }}</ref> is described below. In contrast, an example of a [[non-measurable set]] cannot be exhibited, although the existence of such a set is implied, for example, by the [[axiom of choice]].

Every [[irrational number]] has a unique representation by an infinite [[simple continued fraction]]

:<math>x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}} </math>

where <math>a_0</math> is some [[integer]] and all the other numbers <math>a_k</math> are ''positive'' integers. Let <math>A</math> be the set of all irrational numbers that correspond to sequences <math>(a_0,a_1,\dots)</math> with the following property: there exists an infinite [[subsequence]] <math>(a_{k_0},a_{k_1},\dots)</math> such that each element is a [[divisor]] of the next element. This set <math>A</math> is not Borel. However, it is [[analytic set|analytic]] (all Borel sets are also analytic), and complete in the class of analytic sets. For more details see [[descriptive set theory]] and the book by [[Alexander S. Kechris|A. S. Kechris]] (see References), especially Exercise (27.2) on page 209, Definition (22.9) on page 169, Exercise (3.4)(ii) on page 14, and on page 196.

It's important to note, that while [[Zermelo–Fraenkel axioms]] (ZF) are sufficient to formalize the construction of <math>A</math>, it cannot be proven in ZF alone that <math>A</math> is non-Borel. In fact, it is consistent with ZF that <math>\mathbb{R}</math> is a countable union of countable sets,<ref>{{cite book |last=Jech |first=Thomas |author-link=Thomas Jech |date=2008 |title=The Axiom of Choice | pages=142| publisher=Courier Corporation.}}</ref> so that any subset of <math>\mathbb{R}</math> is a Borel set.

Another non-Borel set is an inverse image <math>f^{-1}[0]</math> of an [[infinite parity function]] <math>f\colon \{0, 1\}^{\omega} \to \{0, 1\}</math>. However, this is a proof of existence (via the axiom of choice), not an explicit example.