I know no descriptive set theory. I've stumbled on something that must be well known, being so simple. But it contradicts something I've been told by smart people; the question is whether it's well known (or at least known).

A complete version of this post would be a little long. It seems clear to me that anyone who knows the answer is going to understand what I mean by the standard this and the usual that; if not I can clarify.

Context. Say $G$ is a group and $S\subset G$. There are at least three ways to say what $H$, the subgroup of $G$ generated by $S$, is:

  1. Let $S_0=S$, and let $S_{n+1}$ be $S_n$ together with all the $xy$ and $x^{-1}$ for $x,y\in S_n$. Then $H=\bigcup_{n=0}^\infty S_n$. (I call this the bottom-up construction.)

  2. $H$ is the set of all words in the elements of $S$.

  3. $H$ is the intersection of all the subgroups of $G$ containing $S$ (this I tend to think of as "top-down".)

Not that anyone would ever use (1) in this context. But now let's say $S\subset P(X)$, the powerset of $X$, and we want to describe $A$, the sigma-algebra generated by $S$. The analogue of (3) is what you see in every book on measure theory; some books include the transfinite-recursion analogue of (1) when they want to show that the Borel sets on the line have cardinality $c$. For some time I've speculated on whether there was something like (2) here.

There is.

(2') The elements of $A$ are exactly the roots of the trees $T$ such that $T$ is well-founded, every node of $T$ is a subset of $X$, every terminal node is an element of $S$, and every other node has either one or countably many subnodes; if a node $E$ has one subsnode $F$ then $E$ is the comlement of $F$, while if $E$ has countably many subnodes it is the union of the subnodes. (Taking advantage of the arity to avoid coloring the nodes to say which operation we're using is probably in poor taste, sorry.)

The proof that this works is totally elementary and straightforward from the definition of $A$ as the intersection of all sigma-algebras containing $S$ - no need to confuse the poor students with ordinals. And one can use it to show, for example, that the Borel sets on the line have cardinality $c$.

I'd be certain that this was perfectly well known except that smart people have told be that the only way to show the Borel sets have cardinality $c$ is transfinite induction. Hence the question: This actually is standard, those guys were just unaware of it as I was until yesterday, right?

  • $\begingroup$ Please let me know if this the answers to the suggested duplicate are not answering your question; in which case you might want to slightly edit and clarify how it's different from the suggested thread, and let me know so I can reopen. $\endgroup$ – Asaf Karagila Jun 16 '15 at 18:57
  • $\begingroup$ I want to answer this. Could someone reopen? I guess the question is asking about the literature on viewing Borel sets as nodes of certain well founded tree of countable rank. $\endgroup$ – hot_queen Jun 16 '15 at 19:09
  • 2
    $\begingroup$ You guys are right. This one is one me. No harm, no foul, I've used my mythical hammer that cracks the sky to crack open the closure of this. @hot_queen can post an answer. $\endgroup$ – Asaf Karagila Jun 16 '15 at 19:28
  • 1
    $\begingroup$ @NoahSchweber I figured he was talking about the fact that the class of Borel sets has cardinality no greater than $c,$ The fact that the cardinality is at least $c$ is, as you point out, trivial. $\endgroup$ – bof Jun 16 '15 at 19:31
  • 2
    $\begingroup$ @hot_queen: This is basically the notion of a Borel code, is it not? $\endgroup$ – Nate Eldredge Jun 16 '15 at 19:32

First, a small technical point: in order to count them it's best to look at trees which are subsets of $\omega^{<\omega}$, explicitly. This actually matters if the axiom of choice fails: just because each successor set is countable, and the tree is well-founded, doesn't mean the tree is countable if the countable union of countable sets isn't countable! In fact, there are models of ZF in which every set of reals is Borel. See also Arnold Miller's wonderful paper "Long Borel Hierarchies" (http://arxiv.org/abs/0704.3998)

Your trees are Borel codes. Since a lot of descriptive set theory really does use transfinite induction in an essential way, we often don't talk about Borel codes; however, they are intuitively fundamental, even if often just implicit, and there are also many times when explicitly talking about codes is invaluable, such as effective descriptive set theory (https://en.wikipedia.org/wiki/Borel_hierarchy#Lightface_hierarchy), reverse mathematics (as in https://math.berkeley.edu/~antonio/papers/Delta4Det.pdf), and algebras of sets beyond the Borel (analytic sets - which contain the Borel sets - are defined in terms of tree representations, finding tree representations for classes of sets is a big tool in descriptive set theory, and als see https://en.wikipedia.org/wiki/Infinity-Borel_set).

As far as showing that Borel codes really do code the Borel sets, I think there is a bit of a subtlety actually: how do you show that there is no proper subset of $A$ which is the class of Borel sets? That is, you need to show that every countable well-founded tree yields a set which must be Borel; to do this it seems to me you need to use induction on the rank of the well-founded tree.

This can be done in a way which does not seem to use transfinite induction: given a well-founded tree, if the root is not Borel then we can find some node which is not Borel, but all of whose successors are Borel (otherwise we could build a path through the tree). This is of course a contradiction.

I would argue, though, that this is transfinite induction in disguise.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the technical point. (Assuming AC is fine. I'm told that without AC $\omega_1$ can have countable cofinality, in which case the induction isn't going to work either...) I didn't say anything about the proof - what I had in mind was what you say about otherwise we could find a descending infinite chain. No point in arguing about whether it's really transfinite induction. But my (ignorant!) impression is that what I'm calling (1') needs a certain amount of set theory, while (2') doesn't, largely because well foundedness is part of the definition of the class of trees. $\endgroup$ – David C. Ullrich Jun 16 '15 at 20:00
  • $\begingroup$ Or: Doing all the set theory that's needed for the transfinite induction, starting from essentially no serious set theory, takes some space - I know cuz I just wrote it all down, an appendix to something. But (2') really doesn't use that stuff, I can write it up from scratch in two medium paragraphs. At worst it's a pretty good disguise, heh... $\endgroup$ – David C. Ullrich Jun 16 '15 at 20:03
  • $\begingroup$ I didn't mean to come off as dismissive - Borel codes are certainly how I think about Borel sets! On the other hand, descriptive set theory really does need lots of transfinite induction, and building the Borel sets that way is a valuable thing to do in my opinion; for that matter, Borel rank is very important, and at that point you're looking at the ordinals. $\endgroup$ – Noah Schweber Jun 16 '15 at 20:05
  • $\begingroup$ Didn't take any of it as dismissive. And of course [everything you said just now]. Those Borel codes are cool, if only because they're my own invention - so I got scooped again, oh well. Seriously though, the more I look the more I can't find that hidden transfinite induction - if you were able to expose it for me that would be great. $\endgroup$ – David C. Ullrich Jun 16 '15 at 20:26
  • $\begingroup$ Just now discovered the notion of "accepting" an answer, if the delay seems curious... $\endgroup$ – David C. Ullrich Jun 22 '15 at 16:18

For a set of reals $X$, define $ord(X)$ to be the length of Borel hierarchy on $X$. What are the possible values of $ord(X)$? Arnold Miller proved a lot of interesting results on this in his thesis. In particular, he showed that for each $\alpha < \omega_1$ it is consistent to have a set of reals $X$ with $ord(X) = \alpha$. To construct this model, he made use of what he called $\alpha$-forcing to add a generic $\mathbf{\Pi}^0_{\alpha}$-set. See his book especially Section 7.

| cite | improve this answer | |
  • $\begingroup$ This is interesting, but does it answer the question? $\endgroup$ – Noah Schweber Jun 16 '15 at 19:46
  • $\begingroup$ You have to read Section 7 to see how trees are used to produce generic Borel sets. $\endgroup$ – hot_queen Jun 16 '15 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.