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.

  • $\begingroup$ To be sure, you mean the lightface Borel hierarchy? $\endgroup$ – Carl Mummert Sep 5 '14 at 2:54
  • $\begingroup$ Yes, the lightface Borel hierarchy $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – user52534 Sep 5 '14 at 23:43
  • $\begingroup$ Also pages 504ff. of Jech's Set Theory third edition. The exact coding system varies a little by author. $\endgroup$ – Carl Mummert Sep 6 '14 at 2:01
  • 1
    $\begingroup$ (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 $\endgroup$ – Carl Mummert Sep 6 '14 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.