# Lightface Pointclasses

I know that a predicate $A\subset\mathcal{N}$ is said to be $\Sigma^0_1$ if there is a recursive ($\Delta^0_1$) monotone predicate $R\subset\omega$ s.t. $A(f)\iff\exists nR(f\restriction n)$.

Here $R$ is monotone iff $\forall s,s^\prime[[s\subset s^{\prime}\wedge R(s)]\implies R(s^\prime)]$.

And then to move up the lightface Borel hierarchy we take complements and projections along $\omega$.

The descriptive set theory sources I looked at didn't explain what hierarchy $A$ would belong to if instead $R$ were $\Sigma^0_n$ or $\Pi^0_n$ and monotone for $n>1$.

For instance, suppose we had a predicate $B\subset\mathcal{N}$ s.t. $B(f)\iff\exists nR(f\restriction n)$ where $R\subset\omega$ is a $\Sigma^0_2$ monotone predicate.

Would $B$ appear somewhere in the lightface Borel hierarchy?

Any help is appreciated, Thanks.

• To be sure, you mean the lightface Borel hierarchy? – Carl Mummert Sep 5 '14 at 2:54
• Yes, the lightface Borel hierarchy – user52534 Sep 5 '14 at 3:12

You are working with a less elegant definition of the lightface Borel hierarchy. Here is a more elegant one, and the relationship.

A set $A \subseteq \omega^\omega = \mathcal{N}$ is effectively open if it is the union of a computable enumerable sequence of basic open sets. This means there is a c.e. sequence $\langle \sigma_i : i \in \omega\rangle$ such that $A = \{ f : (\exists i)[\sigma_i \subseteq f]\}$. A code for $A$ is a pair $(1, i)$ where $i$ is an index of the c.e. enumeration.

The pointclass $\Sigma^0_1$ consists of the effectively open sets. More generally:

• The pointclass $\Pi^0_{n}$ consists of the complements of sets in $\Sigma^0_n$. The code for such a set is the same as the code for its complement.

• The pointclass $\Sigma^0_{n+1}$ consists of all effective countable unions of sets in $\Pi^0_{n}$. This means that a set $A$ is $\Sigma^0_{n+1}$ if there is a computable sequence of codes of $\Pi^0_n$ sets such that $A$ is the union of these sets. The code for the $\Sigma^0_{n+1}$ set is a pair $(n+1, i)$ where $i$ is an index of the c.e. enumeration of codes of $\Pi^0_n$ sets.

This coding scheme can be continued to define the classes $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ when $\alpha$ is a computable ordinal. But here we will stick to $\Sigma^0_n$ and $\Pi^0_n$ for $n$ in $\omega$.

The key fact is that these sets match up with the arithmetic hierarchy for formulas in second-order arithmetic:

Theorem. A subset of $\omega^\omega$ is lightface $\Sigma^0_n$ if and only if it is definable by a $\Sigma^0_n$ formula of second-order arithmetic (the formula will have one free function variable and no other free variables). The same holds for $\Pi^0_n$ sets, mutatis mutandis.

That answers your question, because if $R(m)$ is any arithmetically definable predicate then $\phi(f) \equiv (\exists n)R(f\upharpoonright n)$ is in the arithmetical hierarchy of formulas in second-order arithmetic, so the subset of $\omega^\omega$ that it defines is in the lightface Borel hierarchy.

The requirement that $R(f\upharpoonright n)$ be monotone is a consequence of the definition in the question using relations on $\omega$ instead of $\Sigma^0_1$ formulas of second-order arithmetic. There is a use principle for such formulas: if $f$ satisfies a $\Sigma^0_1$ formula $\phi(x)$ then there is a $k$ such that every $g$ with $g \upharpoonright k = f \upharpoonright k$ also satisfies $\phi$ (this is really just the claim that $\phi$ defines an open set).

The definition in the question avoids talking about formulas of second-order arithmetic, instead only talking about formulas of first-order arithmetic. This necessitates the assumption of monotonicity, because what the definition is really looking for is a definition of an effectively open set, although it avoids that terminology.

• Thanks a lot for your response! Can I ask what source you are getting your definitions from (or are they your own)? The effectively open definition you gave is similar to Moschovakis', but I haven't come across the notion of a "code for $A$" yet in his book. The less elegant definition was similar to ones I saw in Jech and also Mansfield/Weitkamp. I noticed Kanamori uses definability in second-order arithemetic. Also, you didn't mention anything about the bounded variables in your Theorem. So should your Theorem also include "without quantification over function variables"? Thanks again. – user52534 Sep 5 '14 at 23:43
• Also pages 504ff. of Jech's Set Theory third edition. The exact coding system varies a little by author. – Carl Mummert Sep 6 '14 at 2:01
• (Corrected) A $\Sigma^0_n$ formula never has function quantifiers, by definition. The definition of lightface Borel sets via codes is very well known; for example this set of lecture notes from Jan Reimann covers it personal.psu.edu/jsr25/Spring_11/Lecture_Notes/… . I believe it is on page 21 of Mansfield/Weitkamp, although that is from a Google books snippet. It is also seen in hyperarithmetic theory, or effective descriptive set theory, see e.g. Chapter 33 of Arnold Miller's book projecteuclid.org/euclid.lnl/1235423377 – Carl Mummert Sep 6 '14 at 2:07