A construction of sigma-algebras - surely not new, right?
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:
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.)
$H$ is the set of all words in the elements of $S$.
$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?
Solution 1:
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.