Non-Borel set: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Boris Tsirelson
(Undo revision 100516166 by Boris Tsirelson (Talk) Oops)
imported>Boris Tsirelson
(Undo revision 100737190 by Boris Tsirelson (Talk) end of the experiment)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{subpages}}
{{subpages}}


A '''non-Borel set''' is a [[set]] that cannot be obtained from ''simple'' sets by taking [[complement_(set theory)|complements]] and [[countable set|at most countable]] [[union_(set theory)|unions]] and [[intersection_(set theory)|intersections]]. (For the definition see [[Borel set]].) Only sets of real numbers are considered in this article. Accordingly, by ''simple'' sets one may mean just [[interval (mathematics)|intervals]]. All Borel sets are [[measurable set|measurable]], moreover, [[universally measurable]]; however, some universally measurable sets are not Borel.
A '''non-Borel set''' is a set that cannot be obtained from ''simple'' sets by taking complements and at most countable unions and intersections. (For the definition see [[Borel set]].) Only sets of real numbers are considered in this article. Accordingly, by ''simple'' sets one may mean just intervals. All Borel sets are [[measurable set|measurable]], moreover, [[universally measurable]]; however, some universally measurable sets are not Borel.


An example of a non-Borel set, due to [[Nikolai_Luzin|Lusin]], is described below. In contrast, an example of a non-measurable set cannot be given (rather, its existence can be proved), see [[non-measurable set]].
An example of a non-Borel set, due to [[Nikolai Luzin|Lusin]], is described below. In contrast, an example of a non-measurable non-Borel set can only be proved to exist, but it cannot be constructed (because the existence see [[non-measurable set|non-measurable sets]] is not constructive).


==The example==
==The example==
Every [[irrational number]] has a unique representation by a [[continued fraction]]
Every irrational number has a unique representation by a [[continued fraction]]
:<math>x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}} </math>
:<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. For more details see [[descriptive set theory]] and the book by [[Alexander_S._Kechris|Kechris]], especially Exercise (27.2) on page 209, Definition (22.9) on page 169, and Exercise (3.4)(ii) on page 14.
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.
 
While the construction of this set is elementary, the proof that it indeed is not a Borel set
requires advanced results from [[descriptive set theory]].  
(The result follows since the set is analytic, and complete in the class of analytic sets.)

Latest revision as of 11:44, 2 December 2010

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
Advanced [?]
 
This editable Main Article is under development and subject to a disclaimer.

A non-Borel set is a set that cannot be obtained from simple sets by taking complements and at most countable unions and intersections. (For the definition see Borel set.) Only sets of real numbers are considered in this article. Accordingly, by simple sets one may mean just intervals. All Borel sets are measurable, moreover, universally measurable; however, some universally measurable sets are not Borel.

An example of a non-Borel set, due to Lusin, is described below. In contrast, an example of a non-measurable non-Borel set can only be proved to exist, but it cannot be constructed (because the existence see non-measurable sets is not constructive).

The example

Every irrational number has a unique representation by a continued fraction

where is some integer and all the other numbers are positive integers. Let be the set of all irrational numbers that correspond to sequences with the following property: there exists an infinite subsequence such that each element is a divisor of the next element. This set is not Borel.

While the construction of this set is elementary, the proof that it indeed is not a Borel set requires advanced results from descriptive set theory. (The result follows since the set is analytic, and complete in the class of analytic sets.)