Hierarchy of subsets of $\mathbb{N}$

295 Views Asked by At

I was wondering if there is an interesting way to build an "hierarchy" of natural numbers subsets in a transfinite sequence: $$(U_\alpha)_{\alpha < \lambda} \quad \text{with } U_\alpha \subset\mathcal{P}(\mathbb{N})$$ and $$U_\alpha \subset U_{\alpha+1} \; \forall \alpha < \lambda$$ $$U_{\lambda} = \bigcup_{\alpha < \lambda} U_\alpha = \mathcal{P}(\mathbb{N})$$

where the subsets are ordered by some kind of complexity of construction (like for Borel sets). If it is correlated to their cardinality the better. By the way, would it be too much to ask for $\lambda \ge \omega_1$?

1

There are 1 best solutions below

4
On BEST ANSWER

There can indeed be ways of doing this, although I don't know of a natural one which works assuming only ZFC. I would say that they fall into two categories (and I suggest Kanamori's book as a great source on this sort of thing if you're interested):

  • Fine structural (ZFC + "restricted universe"). Assumptions like $V=L$ which say that the universe of sets is somehow "minimal" yield canonical hierarchies for the whole set-theoretic universe. We can look at how the set of sets of naturals in particular is stratified by this hierarchy, and the resulting 'sub-hierarchy' will have length $\omega_1$ (at least, in every case I'm aware of; certainly the length is $\ge\omega_1$). Especially when we take steps to refine the hierarchy in question, the resulting picture looks a lot like the hyperarithmetical hierarchy.

  • Descriptive set theoretic (ZF + DC + AD + maybe more). There is a natural way of comparing sets of reals in terms of topological complexity - namely, Wadge reducibility (and its variants). A priori the Wadge "hierarchy" is quite poorly behaved, but under AD it is quite nice (and vastly longer than $\omega_1$). Moreover, this partially reflects to ZFC in the sense that (under large cardinals) we have results of the form "The Wadge hierarchy restricted to 'nicely definable' sets of reals is well-behaved;" of course, the Wadge hierarchy no longer exhausts all of $\mathcal{P}(\mathbb{N})$.

An interesting aspect of this situation is the unification of fine structure and descriptive set theory in inner model theory; this is an extremely technical subject, but see this Mathoverflow question, and if that's interesting this paper of Sargsyan delves into the situation in more detail. Briefly, inner model theory studies the extent to which we can find inner models of the set-theoretic universe which are "$L$-like" in one sense (in particular, have good fine structure) but "$V$-like" in another (in particular, have as many large cardinals as possible - since $L$ can't have very large cardinals, this is nontrivial). Fine structure is a tool in inner model theory a priori, and it turns out that descriptive set theory plays a hugely important role as well.

But that's getting a bit far afield. The next two sections of this answer give a bit more detail about the two kinds of hierarchies above; let me just mention here that if you're interested in inner model theory, I recommend (after learning the basics of $L$ and relativized constructbility) Schimmerling's paper The ABC's of mice as a general introduction and this Mathoverflow question and this paper of Sargsyan for the role of descriptive set theory in the subject.


Fine structure.

Assumptions like $V=L$ which say the set-theoretic universe is "canonical" in some sense tend to yield explicit hierarchies for the universe; for example, if $V=L$ then we have the $L$-hierarchy $$L_0=\emptyset, \quad L_{\alpha+1}=\mathcal{P}_{def}(L_\alpha),\quad L_\lambda=\bigcup_{\beta<\lambda}L_\beta\mbox{ for $\lambda$ limit}.$$ Restricting to the reals yields the hierarchy of sets of reals $$U_\alpha:=L_\alpha\cap\mathcal{P}(\mathbb{R}).$$ Now $V=L$ is a very restrictive hypothesis - in particular, the existence of measurable cardinals is incompatible with $V=L$ - but there are other "$L$-like" situations which do incorporate large large cardinals.

Properly speaking, the $L$-hierarchy is rather coarse fine structure. Fine structure is really about finer hierarchies, which yield more detail about how the universe of sets is built up (and may have other nice properties as well). The hierarchies of sets of reals these finer hierarchies yield more closely resemble ones from computability theory - the idea being that successive levels in the hierarchy should be the analogues of Turing jumps, and this is driven by the (very successful) analogy between the Borel sets and the hyperarithmetic hierarchy.

For example, assuming $V=L$ we get the mastercode hierarchy (see also this old cs.stackexchange answer of mine). Note that going one step up in the mastercode hierarchy is basically like taking a single Turing jump, while going one step up in the $L$-hierarchy is more like taking $\omega$-many Turing jumps.


Descriptive set theory.

If we're willing to adopt determinacy - in which case we need to weaken choice to stay consistent - we have another very powerful approach available to us: the Wadge hierarchy (and its variants). Strictly speaking this isn't a fully linear hierarchy, but it's very close - basically, it consists of a well-ordered sequence of diamonds, and in particular there are no antichains of size $>2$. If you want to turn it into a genuinely well-ordered hierarchy you can simply let $U_\alpha$ be the set of all sets of naturals whose rank in the Wadge hierarchy is $<\alpha$.

The Wadge hierarchy has length $\Theta$, the sup of the cardinals onto which $\mathbb{R}$ surjects; this is the determinacy analogue of $(2^{\aleph_0})^+$. Obviously $\Theta\ge\omega_2$, but it turns out that $\Theta$ is quite large assuming AD - for instance, it's a fixed point of the map $\alpha\mapsto\omega_\alpha$ - with the key tool being Moschovakis' coding lemma - and Sargsyan showed that it is surprisingly inexpensive, consistency-strength-wise to make $\Theta$ very large (namely, regular) and strengthen AD substantially (to AD$_\mathbb{R}$).

In ZFC the Wadge hierarchy still makes sense, but is vastly more complicated, with even its well-founded part being hard to understand. Under large cardinals however we have large inner models satisfying determinacy hypotheses, and the motto becomes: "Assuming large cardinals, the nicely definable sets of reals have a good Wadge hierarchy."