Can a Boolean Set Algebra be Restricted in the Analytical hierarchy?

Question

I want a comprehension principle to capture $\Pi^1_1$-sets from a domain as well as sets that are relative complements of or finite unions of sets already defined by comprehension. I want to use as little of the Analytical Hierarchy as possible, so is there a natural way to restrict comprehension to obtain such a set-algebra as I want?

Answer 1

Remember that $RCA_0$ already proves that the class of sets is closed under Boolean combinations:

• Given a set $A$, its complement is computable relative to $A$.

• Given sets $A$ and $B$, their union is computable relative to $A\oplus B$ (and $RCA_0$ stipulates closure under joins).

So if $M$ is any model of $RCA_0$, the class of sets in $M$ will be closed under Boolean combinations. In particular, $\Pi^1_1$-comprehension implies $\Sigma^1_1$-comprehension, $\Sigma^1_1\vee\Pi^1_1$-comprehension, etc.

---

The key here is definability relative to an existing set. This is similar to Separation or Replacement in ZF: we have an axiom (or many axioms) which assert the existence of sets which are definable in a certain way with parameters. Same deal here. The $\Pi^1_1$-comprehension scheme consists of, for each $\Pi^1_1$ formula $\varphi$, the axiom $$\forall x_1, ..., x_n, X_1, ..., X_k\exists Y\forall a(a\in Y\iff\varphi(a, x_1, ..., x_n, X_1, ..., X_k);$$ note the "$\forall X_1,...,X_k$" part. This is how parameters (or $\Pi^1_1$-definability relative to something) creep in:

Claim: $\Pi^1_1$ comprehension implies that every set has a complement.

Proof: Let $A$ be a set, and consider the formula $\varphi(x, X): x\not\in X$. $\varphi$ is $\Pi^1_1$ (in fact quantifier free), so by $\Pi^1_1$-comprehension we know: $$\forall X\exists Y\forall n(n\in Y\iff\varphi(n, X)).$$ Take $X=A$; the corresponding $Y$ is exactly the complement of $X$.

Boolean combinations can be justified similarly. And it gets better: $\Pi^1_1$-comprehension implies that for any set $A$, the relativized Kleene's $\mathcal{O}$, $\mathcal{O}^A$, exists, since the definition of $\mathcal{O}^A$ is $\Pi^1_1$ in a parameter for $A$: $\mathcal{O}$ is the set of naturals which code well-orderings. It's a bit messy to unwind this completely into the language of second-order arithmetic, but basically $\mathcal{O}$ is the set of $n$ such that for all sets $X$ (that's the $\Pi^1_1$ bit) $X$ is not a descending sequence through $\Phi_n$ (that bit is arithmetic). We can relativize this to an arbitrary $A$ by replacing "$\Phi_n$" with "$\Phi_n^A$" in the above.

Actually this isn't how $\mathcal{O}$ is defined, but it turns out to be equivalent since the $A$-computable ordinals are exactly the ones which have $A$-notations. This is a nontrivial theorem, though.

---

We can get a finer level of distinction by switching from boldface principles to lightface ( = parameter-free) ones: namely, get rid of the "$\forall X_1, ..., X_k$" clauses in the comprehension schemes above. (If we were interested in nonstandard models, we could also consider another dimension of lightfaceness: get rid of the whole "$\forall x_1, ..., x_n, X_1, ..., X_k$"! But in general this isn't as interesting.) This e.g. lets us prove that $\mathcal{O}$ exists, but not $\mathcal{O}^\mathcal{O}$. This doesn't really affect Boolean combinations, though - the relevant formulas there are quantifier free. So to get fineness on the level of Boolean combinations, you'd have to go all the way and make every comprehension axiom lightface; as far as I know, this hasn't really been looked into.

That said, there is a lightface version you might prefer to full $\Pi^1_1$ comprehension: let $T$ be the theory consisting of $RCA_0$ (the usual boldface version) + lightface $\Pi^1_1$-comprehension. $T$ proves closure under Boolean combinations, but not relativized $\Pi^1_1$-comprehension, so we'd get all finite Boolean combinations of $\Pi^1_1$ sets, but we wouldn't get e.g. $\mathcal{O}^\mathcal{O}$. Since $\mathcal{O}$ is $\Pi^1_1$-complete, $T$ is in fact equivalent to $RCA_0+$"$\mathcal{O}$ exists". (Similarly, $RCA_0$ + lightface $\Pi^0_1$-comprehension is just $RCA_0+$"$0'$ exists".)

---

One more comment:

It's worth pointing out that, unlike the arithmetic hierarchy, the analytic hierarchy is incredibly "spread out". $\Pi^1_1$-relative-to-$\Pi^1_1$ is not $\Pi^1_1$ ($\mathcal{O}^\mathcal{O}$ is not $\Pi^1_1$, just $\Pi^1_1$ *relative to $\mathcal{O}$), but it is still very very low in the $\Delta^1_2$ hierarchy. The gap between $\Delta^1_2$ and iterated $\Pi^1_1$ (basically, the sets you get from $\Pi^1_1$ comprehension) is mind-bogglingly vast, so vast that I actually don't have a good analogy at the moment.

This "gap" idea can be made precise via the Wadge hierarchy: there are many, many more Wadge degrees between $\Pi^1_1$ and $\Delta^1_2$ than there are between $\Pi^0_1$ and $\Delta^0_2$. Caveat: if you want the Wadge hierarchy to work properly, you probably want to assume some large cardinals. But the point I've made still stands without them.