Non-Borel set/Advanced: Difference between revisions
imported>Boris Tsirelson mNo edit summary |
imported>D. Matt Innis (make a fake edit to update merged history) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
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 [[Non-Borel_set/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. | 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 [[Non-Borel_set/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. | ||
| Line 13: | Line 14: | ||
E. The condition "<math> a_k>n </math>" leads to the complement of a set treated in D; still a Borel set. | E. The condition "<math> a_k>n </math>" leads to the complement of a set treated in D; still a Borel set. | ||
F. The condition "<math> a_k>n </math> for all ''k''" leads to the intersection of countably many sets treated in E; still a Borel set. The same holds for the condition "<math> a_k>7 </math> for all <math> k>3 </math>" and, more generally, "<math> a_k>n </math> for all <math> k>m </math> for given <math> m,n. </math> | F. The condition "<math> a_k>n </math> for all ''k''" leads to the intersection of countably many sets treated in E; still a Borel set. The same holds for the condition "<math> a_k>7 </math> for all <math> k>3 </math>" and, more generally, "<math> a_k>n </math> for all <math> k>m </math>" for given <math> m,n. </math> | ||
G. The condition "<math> a_k>7 </math> for all ''k'' large enough" leads to the union of countably many sets treated in F; still a Borel set. | G. The condition "<math> a_k>7 </math> 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 <math> a_1, a_2, a_3, \dots </math> tends to infinity" leads to the intersection of countably many sets of the form treated in G ("7" being replaced with | H. The condition "the sequence <math> a_1, a_2, a_3, \dots </math> tends to infinity" leads to the intersection of countably many sets of the form treated in G ("7" being replaced with arbitrary natural number). Still a Borel set! | ||
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 <math> k_0 < k_1 < k_2 < \dots </math> the corresponding set is Borel. However, ''A'' is the union of such sets over all <math> k_0 < k_1 < k_2 < \dots </math>; a uncountable union! | This list can be extended in many ways, but never reaches the set ''A''. Indeed, the definition of ''A'' involves arbitrary subsequences. For given <math> k_0 < k_1 < k_2 < \dots </math> the corresponding set is Borel. However, ''A'' is the union of such sets over all <math> k_0 < k_1 < k_2 < \dots </math>; 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. | 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. | ||
Latest revision as of 19:47, 30 June 2009
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 Non-Borel_set/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 is an interval, therefore a Borel set.
B. The condition "" leads to a countable union of intervals; still a Borel set.
C. The same holds for the condition "" and, more generally, "" for given k and n.
D. The condition "" leads to the union of finitely many sets treated in C; still a Borel set.
E. The condition "" leads to the complement of a set treated in D; still a Borel set.
F. The condition " for all k" leads to the intersection of countably many sets treated in E; still a Borel set. The same holds for the condition " for all " and, more generally, " for all " for given
G. The condition " 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 tends to infinity" leads to the intersection of countably many sets of the form treated in G ("7" being replaced with arbitrary 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 the corresponding set is Borel. However, A is the union of such sets over all ; 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.