Non-Borel set/Advanced: Difference between revisions

Revision as of 12:20, 20 June 2009

Main Article

Discussion

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

Citable Version ^[?]

Advanced ^[?]

An advanced level version of Non-Borel set.

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 $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.

@@ Line 1: / Line 1: @@
 {{subpages}}
-Usually, it is rather easy to prove that a given set is Borel (see
+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.
-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 <math> a_0=3 </math> is an
+A. The set of all numbers ''x'' such that <math> a_0=3 </math> is an interval, therefore a Borel set.
-interval, therefore a Borel set.
-B. The condition "<math> a_1=3 </math>" leads to a countable union of
+B. The condition "<math> a_1=3 </math>" leads to a countable union of intervals; still a Borel set.
-intervals; still a Borel set.
-C. The same holds for the condition "<math> a_2=3 </math>" and, more
+C. The same holds for the condition "<math> a_2=3 </math>" and, more generally, "<math> a_k=n </math>" for given ''k'' and ''n''.
-generally, "<math> a_k=n </math>" for given ''k'' and ''n''.
-D. The condition "<math> a_k<n </math>" leads to the union of finitely
+D. The condition "<math> a_k<n </math>" leads to the union of finitely many sets treated in C; still a Borel set.
-many sets treated in C; still a Borel set.
-E. The condition "<math> a_k>n </math>" leads to the complement of a set
+E. The condition "<math> a_k>n </math>" leads to the complement of a set treated in D; still a Borel set.
-treated in D; still a Borel set.
-F. The condition "<math> a_k>n </math> for all ''k''" leads to the
+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>
-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"
+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.
-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>
+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 arbitray natural
-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
+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!
-''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
+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.
-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.

Non-Borel set/Advanced: Difference between revisions

Revision as of 12:20, 20 June 2009

Navigation menu

Search