Talk:Infinity-Borel set

(Formerly) Disputed

Um, so actually I wrote this article, and no one else has touched it, so really I'm arguing with myself here. But I thought about it and I'm not sure my definition is right. On the other hand, if it is right, it's (I think) easier to follow than any alternative I can think of, so I don't want to jump the gun. But I also don't want to mislead anyone.

Here's the issue; maybe someone can help me out: The ∞-Borel sets are the ones that have ∞-Borel codes. An ∞-Borel code is something that codes up the way you build an ∞-Borel set by starting with open sets (each basic open set gets a code), and then iterating the operations of complementation and wellordered union (there's a code for the complement of a coded set, and a code for the union of a sequence of coded sets).

Problem is--is the class of thus-coded sets in fact closed under wellordered union? To prove it, you'd seem to need AC_α, if your sequence of sets to be unioned up has length α, in order to choose a Borel code for each of the sets in the sequence, so you can form the new Borel code.

Any help appreciated. --Trovatore 04:21, 15 July 2005 (UTC)[reply]

Fixed

So the definition now in place is harder to follow, and it's got a lot of LaTeX that simply cannot be displayed if anyone is expected to read the thing. But it does have the advantage of being correct. --Trovatore 02:20, 16 July 2005 (UTC)[reply]

Alternative definition

So I thought of another approach: Dispense with the codes, and perform the transfinite iteration directly on the sets. Something like this:

For each ordinal α define by transfinite recursion B_α as follows:

B₀ is the collection of all open subsets of $X$ .
For a given even ordinal α, B_α+1 is the union of B_α with the set of all complements of sets in B_α.
For a given even ordinal α, B_α+2 is the set of all wellordered unions of sets in B_α+1.
For a given limit ordinal λ, B_λ is the union of all B_α for α<λ

It follows from the Burali-Forti paradox that there must be some ordinal α such that B_β equals B_α for every β>α. For this value of α, B_α is the collection of ∞-Borel sets.

Whaddaya think? Is it clearer than the definition with codes? I did leave more out in this alternative version (e.g. I didn't really say what a wellordered union is, and it takes a little argument to see that clause 3. above gives you a set at all, rather than a proper class). Also the code notion is important. --Trovatore 02:49, 16 July 2005 (UTC)[reply]

Whoops. It is clearer, but it's wrong. Can't prove without AC that every set as defined above has an ∞-Borel code; same error as before. --Trovatore 03:06, 16 July 2005 (UTC)[reply]

Why Polish?

A beginners question: Why is "Polish" = "Separable + Completely Metrizable + Topological" used in the definition? Only the property "Countable Base" = "Second Countable" is used directly. What I mean is that the definition might make sense in any second countable space though it might not be "interesting" for all of them. (Historical reasons I guess)

Another thing I don't understand is the following: If c is a key then <0,c> is a key. Ok, but this leads to an "immediate explosion" of the keys c -> <0,c> -> <0,<0,c>> -> <0,<0,<0,c>>> -> <0,<0,<0,<0,c>>>> ... Are the ordered "nested triples", "nested quadruples", etc really necessary? Their respective interpretations doesn't add any new interpretations that aren't there already.

Maybe it should be pointed out that the recursion is set off rolling by the sequence denumerating the base and all it's subsequences of any length. Or do I get something wrong here?

I suppose the Axiom of Choice can be disposed of just because we could create an explicit rule for comparing two interpretations in terms of the sets of codes that have the interpretations in question. Now, being a programmer, I'd sure like for each interpretation to have a "pointer" to "it's" set of codes, as well as the rules for how to compare a set of codes with another set of codes (assuming all I can compare is natural numbers). I believe one could have intermediate steps in the definition with ordered pairs <interpretation, set of codes> and only in the end project the interpretations out of those pairs. (The second element of the ordered par is the "pointer" I am talking about). If ease of comprehension is an issue this might help. It might help describing the prevention of the (unintentional?) explosion of codes described above as well. Mathematically, of course, it would add nothing and it would make the definition a little longer.217.208.31.144 (talk) 08:31, 30 November 2007 (UTC)[reply]

Haven't digested the last paragraph. As for whether the definition makes sense in any second countable space, maybe it does; the question is whether anyone has bothered to use it in that context. I don't know of an example.

To be honest I wrote this article when I was still relatively new to WP and hadn't really internalized the importance of following the treatment in the references; the definition given is my own version. I'm almost certain that it's equivalent to the ones in the literature modulo irrelevant detail, but it really ought to be replaced with one that actually comes from the literature. Maybe I'll get to it this weekend, though I'm not making any firm promises.

The sad thing is that the section about the incorrect definition will probably have to be removed. It's too bad because it really is such an easy mistake to make and not notice that you've made it. But there are good reasons for the larger WP standards and I can't really argue that this is a special enough case to override them. --Trovatore 20:09, 30 November 2007 (UTC)[reply]

Oh leave that incorrect part in, It helpet me undersstand why the correct one is correct, and it's easier to se how we can live without AC. YohanN7 04:37, 1 December 2007 (UTC)[reply]

Well, I'd like to leave it, but I don't think I can without a source. Not sure what you mean by "how we can live without AC", though.

I'm afraid I'm not entirely sure what you're getting at in some of the above, so let me just make a few points that may or may not be relevant.

There is no canonical way of getting from an ∞-Borel set to an ∞-Borel code for that set, if that's what you mean by a "pointer". There are lots of different codes that code the same set. In fact literally speaking there's a proper class of codes for the same set, so there's not even a "set of codes", though I suppose we could restrict our ordinals to be below Θ without really losing anything.
So no, we can't build up ∞-Borel sets together with their "sets of codes".
A possibly useful analogy: For any particular output from a computer, there are many different programs that might have computed it (and by Rice's theorem there's no effective way to decide whether a given program does produce that output). So ∞-Borel sets are analogous to the outputs, whereas ∞-Borel codes are analogous to the programs. Roughly speaking.
But only roughly speakng, in part because in this context you can't limit yourself to natural numbers. An ∞-Borel code is more or less a set of ordinals, not of naturals. This is subject is really far outside the realm of computability -- no computer can deal with arbitrary ordinals. --Trovatore 08:23, 1 December 2007 (UTC)[reply]

You caught my idea of "pointer" precisely as I meant it. That is a (pointer to) a code, set of codes or - worse - proper class of codes that have the interpretaion in question. My whole point woul'd be that there then is a canonical well ordering of the interpretations at any stage sinse we can complare what their pointers point to. If you say it can't be done this saw I believe you. It was just an idea.

In my first note I mentioned the "explosion" of codes when taking complement. Is it supposed to be that way?YohanN7 21:48, 1 December 2007 (UTC)[reply]

Well, I suppose you could just disallow codes that take two complements in a row, but what would be the point? Yes, you get rid of one way in which two codes very obviously code the same set, but there are all sorts of more complicated ways for them to do so, and you'll never find them all working piecemeal like that. As far as I can see all it does is complicate the exposition, and you don't gain anything at all. --Trovatore 01:10, 2 December 2007 (UTC)[reply]

You are really good at explaining things to a layman Trovatore. I understand now that the "explosion of codes" is there, and that there is no point in trying to remove them - and that an explicit removal (of a few of them) would only complicate the definition.

I agree with that definitions should be taken from an "acknowledged source" and thereby be "verifiable", but I also feel that explanatory remarks should be put in as much as possible. The rationale is that even a direct quoute or rewording of a definition taken from a book can be misinterpreted because it is removed from it's context (i.e. the book). In short, a definition can be unambiguous in the reference itself, but ambiguous when removed from the reference.
I hold a masters degree in EE (and Engineering Physics too) which naturally means I know some math, but certainly not enough rigorous math to immediately grasp every math article in Wikipedia, especially those as complicated (or deep if you will) as the current article. I suppose people with even less background in math than me try to understand definitions they run across and they will run into the same kind of questions as me (or even worse ones) due to misinterpretation, so the more explanatory remarks the better, including the "incorrect definition" - with or without a reference. I can't see how that could break Wikipedia rules as long as it's explained clearly that it is an explanatory remark. (I can see, however, that it would potentially ruin a lot of your spare time;)
About that "how we can live without AC"-thing: I was referring to the article saying that Infinity-Borel is only interesting in contexts when AC is not assumed or can not be assumed together with the "incorrect definition" which I now understand, after your explanation, must assume AC. That might explain why, in the first place, I brought up the question of wether "the whole set of codes" somehow could be reverse-engineered from an Infinity-Borel set via that "pointer" and in that way one could guarantee closedness under wellordered union without AC. Given any set of codes, just pick the least code so to speak. I understand now the impossibility of this idea because we can not be given a set of codes. I am just trying to close the circle in my reasoning here and I hope that my earlier questions (all answered now) at least were "reasonable as questions about math" even if they weren't "reasonable as mathematical questions".

Thanks for your effort Trovatore! (YohanN7) 217.208.31.144 (talk) 07:36, 7 December 2007 (UTC)[reply]

Borel Code

Would it be okay to make 'borel code' redirect to this? There is no article for it, and this one with with a few changes should suffice to explain the notion. Chimpionspeak (talk) 14:48, 20 February 2011 (UTC)[reply]

Hmm, as a stopgap I suppose that would be OK, but it's not really an ideal solution. This article is too specialized to serve the burden of explaining Borel codes in general. It might be better to put a section on it into Borel hierarchy (or even Borel set) and then target the redirect to that section. --Trovatore (talk) 00:44, 22 February 2011 (UTC)[reply]

Oh okay. Thanks. Chimpionspeak (talk) 07:55, 26 February 2011 (UTC)[reply]

I have done some preliminary writing of it here. I am a little hesitant about what more to add/say for fear of getting it wrong though! If you think this is okay, maybe we can shift it. Also, if you think something needs to be added, feel free.Chimpionspeak (talk) 16:47, 14 March 2011 (UTC)[reply]

Honestly what we should do is use something from a published source. It was a mistake on my part to roll my own in this article; that's not supposed to be how we do things here. (I'm not going to actively remove it until I actually get around to finding one in a source, but if someone else did I couldn't really complain.) --Trovatore (talk) 18:27, 14 March 2011 (UTC)[reply]