How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined, when $A$ is a set of reals ($A \subset \omega^\omega$)? I assume that there is a standard definition, but I can't seem to find it in print.

I asked a question at mathoverflow about this pointclass, and then realized that I didn't know what I was talking about. Here is the definition I attempted to give there:

A $\Sigma^1_1(A)$ set is a set definable by a $\Sigma^1_1(A)$ formula, which is like a $\Sigma^1_1$ formula except that the language is expanded by a predicate symbol for $A$.

We define the class of $\Delta^0_1(A)$ formulas recursively by starting with atomic formulas (now including the formula $A(x)$) and applying $\neg$, $\wedge$, $\vee$, $\forall^\omega$, and $\exists^\omega$. Then the $\Sigma^1_1(A)$ formulas are obtained by adding blocks of real existential quantifiers $\exists^{\omega^\omega} x_1 \cdots \exists^{\omega^\omega} x_n$ in front of $\Delta^0_1(A)$ formulas.

However, I don't think this is the right definition. For example, I think that if $A$ is a binary relation on the reals then the statement "$A$ is ill-founded" should be $\Sigma^1_1(A)$, but the definition above doesn't seem to allow asking about membership of countably many ordered pairs of reals (as coded by a single real) in $A$. Also, it's not clear to me that the pointclass defined above is closed under recursive substitution.

  • $\begingroup$ Just for my own peace of mind, $\exists^X$ and $\forall^X$ mean, essentially, quantifiers bounded in $X$, right? $\endgroup$
    – Asaf Karagila
    Apr 23, 2015 at 21:06
  • $\begingroup$ @AsafKaragila That's right. $\endgroup$ Apr 23, 2015 at 21:06
  • 2
    $\begingroup$ Thanks! (And huzzah! I can infer things from context!) $\endgroup$
    – Asaf Karagila
    Apr 23, 2015 at 21:07
  • $\begingroup$ It's been a while since I've looked at DST, but the only natural thing that comes to mind is to define $\Sigma^1_1(A)=\bigcup_{f\in A}\Sigma^1_1(f)$; inspired from the fact that $\mathbf{\Sigma^1_1}=\bigcup_{f\in\omega^\omega}\Sigma^1_1(f)$ $\endgroup$
    – user52534
    Apr 23, 2015 at 22:48
  • $\begingroup$ @user52534 Then we wouldn't necessarily have $A \in \Sigma^1_1(A)$. That definition doesn't depend on the complexity of $A$ in the way I had in mind. $\endgroup$ Apr 24, 2015 at 0:17

2 Answers 2


The pointclasses $\Sigma^1_1(A)$ for some set $A\subseteq \mathbb{R}$ are defined as follows: a set $B$ is $\Sigma^1_1(A)$ iff there are $\Sigma^1_1$ sets $C$ and $D$ such that $B(x) \leftrightarrow C(x) \vee \exists y (\forall n (y)_n\in A \wedge D(\langle x,y\rangle))$. Notice that $A\in \Sigma^1_1(A)$ and the pointclass $\Sigma^1_1(A)$ is closed under $\exists^{\mathbb{R}}$, $\vee, \wedge$ and has a universal set (which can be defined using the universal $\Sigma^1_1$ sets $U$). The pointclasses $\Pi^1_1(A)$ and $\Sigma^1_n(A)$ are defined similarly.

  • $\begingroup$ This doesn't necessarily contain $\neg A$, right? (In that case I guess the pointclass I am after would be called $\Sigma^1_1(A,\neg A)$.) Do you have a reference for this definition in print? $\endgroup$ Apr 24, 2015 at 0:13
  • $\begingroup$ $\neg A$ is not necessarily in $\Sigma^1_1(A)$. If you want $\Sigma^1_1(A,\neg A)$ then you need to modify the definition accordingly. I don't know any references for this definition except for class notes from Steve Jackson (which I can send you if you want), and my dissertation. $\endgroup$ Apr 24, 2015 at 0:31
  • $\begingroup$ Sure, I would like to see the notes or your dissertation, whichever is convenient. Is your dissertation online? $\endgroup$ Apr 24, 2015 at 0:34
  • $\begingroup$ No it's not online. I've sent you the notes. $\endgroup$ Apr 24, 2015 at 0:43
  • $\begingroup$ I would be interested as well, please (and on your dissertation, if possible). $\endgroup$ Apr 24, 2015 at 16:09

EDIT: Taking the definition from Barwise "admissible sets and structures", the collection of $R$-positive formulas of the language $L^*\cup \{{R}\}$ is is the smallest class of formulas containing all formulas of $L^*$, all atomic formulas of $L^*\cup\{R\}$, and closed under $\vee$, $\wedge$, $\forall u \in v$, $\exists u \in v$, $\forall u$, $\exists u$. The Levy hierarchy of $R$-positive formulas can be defined as usual.

A subset $C\subseteq \omega^\omega$ is $\Sigma^1_1(A)$ iff there is a positive $\Sigma_1$ $R$-positive formula $\phi$ such that $C(x)$ iff $(\mathcal{P}(\omega),\omega,\in,A) \models \phi(x)$.

As reminded by Trevor, another approach is to go through Moschovakis set induction. $\text{pos}\Sigma^0_1(A)$ is the smallest monotone $\Sigma$-collection containing the evaluation-in-$A$ relation: $$E(w,x,B) \text{ iff } A(w).$$ Here $E$ is a set relation. All terminologies are according to Moschovakis's book. $\text{pos}\Sigma^0_n(A)$, $\text{pos}\Pi^0_n(A)$ are defined by alternating quantifiers in $\omega$. A set $C$ is $\Pi^1_1(A)$ iff $C$ is $\text{pos}\Sigma^0_\omega(A)$-inductive. According to 7C.2, $C$ is $\Pi^1_1(A)$ iff $C$ is $\text{pos}\Delta^0_2(A)$-inductive, or when the underlying space is the standard Baire space, $\text{pos}\Pi^0_1(A)$-inductive.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .