Talk:Borel set

Countably generated

The concept of countably generated is in http://en.wikipedia.org/wiki/Countably_generated How to prove that Borel sets are countably generated? Jackzhp 20:44, 6 November 2006 (UTC)

from open sets?

A subset of X is a Borel set if and only if it can be obtained from open sets by using a countable series of the set operations union, intersection and complement.

Is this true in general? I know that for metrisable spaces, every Borel set is of the form F-sigma, G-delta, F-sigma-delta, G-delta-sigma, F-sigma-delta-sigma, etc., etc. But I don't think every Borel set is necessarily of this form in a general topological space. (Why else would metrisability be part of the hypothesis of the theorem I read?)

I was quite wrong here. I read the symbol for the first uncountable ordinal as the symbol for the first infinite ordinal. Whoops! Revolver 07:03, 16 Dec 2004 (UTC)

In any case, I'm not sure it's clear precisely what is meant by "using a countable series of the set operations union, intersection, and complement". Certainly this is meant to include the F-sigma, G-delta, F-sigma-delta, G-delta-sigma, F-sigma-delta-sigma, etc., etc., but what about taking countable unions/intersections of sets lying somewhere in this hierarchy? I'm not even sure if this gives more sets, but regardless, the way it's worded, it's not clear if this construction is intended or not. Revolver

I believe The article is true as it now stands with your correction. I may have been responsible for the original sloppy wording.CSTAR 13:14, 16 Dec 2004 (UTC)

I noticed that this article is virtually identical to [1]. Did they copy from us, or the other way around? If it's the latter, it would seem to be a violation. Revolver

Sorry...it was copied from us! We're given credit at the bottom of the page. My bad. Revolver

generation of Borel sets

I didn't mean iteration to any countable ordinal. I meant that any Borel set could be created by iteration to a countable ordinal, and that this countable ordinal may be arbitrarily large depending on the Borel set. Revolver 19:31, 14 Jun 2005 (UTC)

I just didn't want to give the impression that there is a Borel set whose existence requires one to iterate uncountably many times. To get the whole algebra, you must go to uncountably many times, but not for a fixed Borel set. Revolver 19:40, 14 Jun 2005 (UTC)

Is this true? In "Probability and Measure" by P. Billingsley (3rd ed.) pages 30-32, it is shown that there are Borel sets that are not generated by any finite n compositions of complements, countable unions (and countable intersections), no matter how large n is. It is also remarked, but not proved, that this holds even for countably infinite compositions. Unless Billingsley is wrong, this appears to contradict your claim.

Ah, yes.--CSTAR 20:17, 14 Jun 2005 (UTC)

Consider the revision [[2]]. I think the guy mistakenly inserted the sentence "There is a second way with which to generate the Borel algbra." since the algorithm of generating algebra was not complete before this point, ie., $T_{\delta \sigma }=(T_{\delta })_{\sigma }.\,$ is not the algebra yet. Is this talk page the right place for my remark? Matumba (talk) 16:12, 21 December 2008 (UTC)

Well, one may agree that the writing is not perfectly clear at that point, but the first way to generate the Borel sets is the one described in the intro of the article (by intersection). The sentence "there is a second way" could be as well moved to the beginning of the section "Generating the Borel sigma-algebra" I think. Bdmy (talk) 16:34, 21 December 2008 (UTC)

Hmm, I think I liked it better before, but just with the talk of the "second way" removed. It's odd to describe the description in the lede as "generating" the Borel sets. It defines them but doesn't construct them, whereas the recursive method does. I don't necessarily intend anything very precise by this; it's neither a mathematical nor a philosophical claim, but I think it's fairly clear what I'm talking about. --Trovatore (talk) 20:50, 21 December 2008 (UTC)

Serious mistake in article about the Borel algebra

Remark: Originally posted on Oleg Alexandrov's Talk page by anonymous user 129.70.85.106

In the article "http://en.wikipedia.org/wiki/Borel_algebra" it is claimed, the borel algebra is the

"minimal σ-algebra containing the compact sets".

This is not correct. E.g. if you take some set E equipped with the indescrete topology (i.e. the only open sets are the empty set and E itself), then all sets are compact. Thus the minimal σ-algebra containing the compact sets is the powerset, while the borel algebra only consists of E and the empty set.

Other examples are

- any other non-Hausdorff space
- an uncountable space equipped with the discrete topology (every subset is open) --anon (129.70.85.106)

Very correct. However, please note that the article states at the beginning that

By Borel algebra one means either the the minimal σ-algebra containing the open sets or the minimal σ-algebra containing the compact sets.

And below that, it says that the two structures are not in general equivalent. So, you are very correct with the example above. But there is no mistake in the article. One can mean two different things by Borel algebra. In R^n those defintions are equivalent I think, in general they are not, and the article does state that. Oleg Alexandrov 15:29, 22 July 2005 (UTC)

Indeed the Borel algebra defined as generated by the compact sets is basically due to Halmos' book, Measure Theory. All differences disappear for locally compact sperable metric spaces. Maybe we should clarify the statement and say that these are two different definitions.--CSTAR 15:49, 22 July 2005 (UTC)

BTW, Oleg did you answer your own question, or was this someone else's objection?--CSTAR 15:53, 22 July 2005 (UTC)

Yes, it was somebody else's objection. I agree that maybe the statement would need clarification. Oleg Alexandrov 16:08, 22 July 2005 (UTC)

Construction of a Borel isomorphism

Can someone tell me how to construct an isomorphism between such Polish spaces as the unit ball in L^2[0,1] and the real line with the natural topology? Leocat 12 Oct 2006

Uh oh, construct? Do I know you? :) --CSTAR 19:24, 12 October 2006 (UTC)

You better worry about whether you know the answer to my question.Leocat 15 Oct 2006

Good answer. What I do know is that Kuratowski's theorem says there exists such an isomorphism. Whether this isomorphism is constructible, I don't know. Should I worry sone more? What me, worry?...about that? --CSTAR 14:52, 15 October 2006 (UTC)

To Leocat: See Example 2 in Schroeder-Bernstein_theorem_for_measurable_spaces; it is simpler than what you ask, but probably you can upgrade it as needed.Boris Tsirelson (talk) 21:02, 23 August 2008 (UTC)

Simple example

I would like to see a simple example what is and what is not a Borel set. TomyDuby 19:31, 31 December 2006 (UTC)

I think there is a simple example of what is a Borel set.

Specifically, I think it is the infinite series of 1/2, 1/4, 1/8, etc. of line segments. But I'm going here on my memory from a class taught by Gian-Carlo Rota in 1971 at MIT.

Here is a "simple" example of a Borel set -- and please comment/discuss if I'm wrong or correct since we are talking 35 years ago:

It is known that the number of rational numbers in countably infinite, and that there are "more" irrational numbers. In other words, we can prove that you can number all rational numbers via a grid with the whole numbers (p) across as column headers and whole numbers as row headers (q), and the intersection being the rational number p/q

Furthermore the diagonal method (same article, but there must be a better source) can show that there are more irrational numbers than rational.

But a Borel set can show this graphically by taking a line segment of length 2, and putting a line segment on each rational number there. The first line segment would be length 1/2, and the second would be length length 1/4, and then 1/8, etc. The sum of these line segments would be 1, since 1=1/2 + 1/4 + 1/8 + 1/16 + ....

Each line segment would have an infinite number of points. So, here you would have a mapping, that instead of one-to-one would be infinite-to-one of irrational numbers to whole numbers, and there are an infinite number of line segments that still would not be counted: the length of it equals 1 of the length 2 line segment.

Perhaps someone can a) verify that what I say is true, b) find the reference for it on the web.

--Peter10003 (talk) 12:01, 1 February 2010 (UTC)

I don't think there are any simple examples of a set that is not a Borel set. Timhoooey 00:32, 14 October 2007 (UTC)

Good question, here is my follow up. How unconstructive relly are non-Borel sets? I know you need quite a strong choice, almost to well-order the reals, the get any non-Lebesgue or non-Baire sets, but do non-Borel ones provably exist even in ZF? Or you need some weak, like countable or dependent, choice? Thanks! Scineram (talk) 09:59, 14 July 2008 (UTC)

Actually there's a very concrete example of a non-Borel set, and I'm pretty sure it doesn't use any choice at all (though I do occasionally get surprised by the violent pathologies that can pop up in the absence of countable choice). Goes like this: first, specify some simple concrete scheme for coding an arbitrary linear order on the natural numbers by a single real. (This isn't too hard -- could be something like taking the fractional part of the real in binary, and if a 1 appears in position 2ⁿ3^m, that means that n is before m in the ordering. That gives a relation on the natural numbers; if the relation is not a linear order of the naturals, then you throw that real away.)

Now look at the set of all reals such that the linear order they code is a wellordering. This set is $\Pi _{1}^{1}$-complete, and therefore not Borel.

Which does invite two further questions: (1) Why is the set $\Pi _{1}^{1}$-complete, and (2) why can't a $\Pi _{1}^{1}$-complete set be Borel? I'm not going to try to answer those right now; if you're interested, I recommend Moschovakis's Descriptive Set Theory.

(Alternatively, you can short-circuit those questions by noting that every Borel set can be coded by a real, and then applying Cantor's diagonal argument to get a set that's not Borel. However that would be a much less important set than the one I described above.) --Trovatore (talk) 08:05, 18 August 2008 (UTC)

I've just implemented something like this, on a rather elementary level; please look:non-Borel set.Boris Tsirelson (talk) 11:14, 22 August 2008 (UTC)

Good. I think, this is an important point for the set theory and the computability, and hence should remain a distinct article, not to be merged with “Borel set”.

> though I do occasionally get surprised by the violent pathologies that can pop up in the absence of countable choice

Yes, it is consistent with ZF for R to be a countable union of countable sets, in which case every subset of R is Borel.

JumpDiscont (talk) 23:23, 30 September 2009 (UTC)

References

Ambiguous statement in the references section

The following statement appears in the references section but is immediately followed by a list of 4 references.
An excellent exposition of the machinery of Polish topology is given in Chapter 3 of the following reference:
I seriously doubt it applies to all 4. Does anyone know which one(s) its talking about? Timhoooey 00:40, 14 October 2007 (UTC)

First uncountable ordinal

Isn't that usually called $\omega _{1}$? Deepmath (talk) 07:00, 16 August 2008 (UTC)

Yes. The Ω notation is definitely attested, though (for example, Folland uses it, in this precise context).

Still, my preference would be to change it to ω₁, on the grounds that it's the less ambiguous, more commonly used, and more generalizable notation. Anyone else want to weigh in? --Trovatore (talk) 07:40, 18 August 2008 (UTC)

Whoops; I didn't bother to look at the actual article before responding — it doesn't say Ω; it just says the first uncountable ordinal. We should definitely add ω₁ to that, but first we should probably say a little more about just what it means to iterate the process up to an ordinal. Bringing in the notation from descriptive set theory mightn't be a bad idea. Of course this material is already treated at Borel hierarchy, and from my perspective, the best thing to do might just be to merge this article into that one. --Trovatore (talk) 07:53, 18 August 2008 (UTC)

Choice

"if m is an uncountable limit ordinal, Gm is closed under countable unions"

How is this proven without Countable Union Condition?

How is

Aleph_1 x 2^Aleph_0 = 2^Aleph_0

proven without AC? —Preceding unsigned comment added by JumpDiscont (talk • contribs) 03:39, 20 November 2009 (UTC)

Who said it is? Choice is the default assumption; we don't have to mention it. If you want to discuss what can happen in models of ~AC, that might be an interesting sidelight, but it would come later in the article. --Trovatore (talk) 03:47, 20 November 2009 (UTC)

"any measure defined on open sets AND closed sets must also be defined on all Borel sets"

why is the above part of the wikipedia article true and can it be changed to ... OR ... --demus wiesbaden (talk) 14:44, 4 December 2009 (UTC)

Yes. — Carl (CBM · talk) 18:47, 4 December 2009 (UTC)

Cardinality

I'm not sure if the paragraph

In the construction by transfinite induction, it can be shown that, in each step, the number of sets is, at most, the power of the continuum. So, the total number of Borel sets is less than or equal to $\aleph _{1}\times 2^{\aleph _{0}}\,=2^{\aleph _{0}}\,$.

In the example section is meant for the borel algebra on the reals. If it is, then obvious the number of Borel sets is exactly continuum, because for any real number x, the set {x} is in the borel algebra (take the countable intersection of all open intervals (x-q,x+q) for q a positive rational number), and the defines an injection from the reals to the Borel algebra. Money is tight (talk) 09:02, 12 March 2010 (UTC)

There are exactly $2^{\aleph _{0}}$ Borel sets of reals, yes. Every Borel set can be coded by a real, which gives you the surjection. --Trovatore (talk) 09:06, 12 March 2010 (UTC)

Isn't this a consequence of axiom of countable choice? (In absence of any form of axiom of choice, it is consistent that all sets of real numbers are Borel sets.) [3] - Mike Rosoft (talk) 21:33, 16 January 2019 (UTC)

Um. Probably. I'd have to think about it, but yes, really really pathological things can happen if countable choice fails. But choice (especially countable choice) is part of the default context. For a while it was fashionable to be careful about calling out its dependencies specifically, but that is no longer true. --Trovatore (talk) 21:39, 16 January 2019 (UTC)

Borel set#Generating the Borel algebra

I'm not sure I'm very fond of a passage with the following structure:

To prove this claim, note that ... In particular, it is easy to show that ...

I'm not demanding a proof, but this is, in my opinion, worse than a totally absent proof, or a painfully detailed present proof.

What does an actual proof use b t w? Set theory version of De Morgan's laws? Some countability property of metric spaces? Open set = union of increasing sequence of closed sets is there, but what does "easy to show..." mean elsewhere? If the "proof" is to stay it needs a rewrite. YohanN7 (talk) 05:37, 16 December 2013 (UTC)

I think this may be useful: If α_n is a sequence in ω₁, then sup α_n is a limit an ordinal strictly less than ω₁. Put β = sup α_n + 1. Then, if B_n is a sequence of sets in the sigmas,

$\cup B_{n}\in \Sigma _{\beta }^{0}$

where α_n is the ordinal such that

$B_{n}\in \Sigma _{\alpha _{n}}^{0}.$

YohanN7 (talk) 08:02, 16 December 2013 (UTC)

Revised ambiguous use of "Borel space"

I revised the section Standard Borel spaces and Kuratowski theorems to give an unambiguous and modern definition of "Borel space".

The previous version said that Mackey used the term "Borel space" to mean what we now call a "measurable space", but that this is a misleading usage. However, it did not clearly state whether it was adopting Mackey's definition, nor did it offer another meaning for the term "Borel space". Yet it then proceeded to use the term several times!

The usage was consistent with the "obvious" definition of "Borel space", namely a set equipped with the sigma-algebra of Borel sets (of some topology). So I made this the official definition, at the top of the paragraph.

If someone thinks this is ahistorical, or not even correct usage, then I would suggest removing Mackey's no-longer-used definition (or putting it in a footnote) and also removing all usages of "Borel space", replacing them by "measurable space" (suitably qualified), except in the fixed expression "standard Borel space".

178.38.78.40 (talk) 10:07, 3 May 2015 (UTC)