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?



Can a Boolean Set Algebra be Restricted in the Analytical hierarchy?
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**](https://en.wikipedia.org/wiki/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.*


