# How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined?

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.

• Just for my own peace of mind, $\exists^X$ and $\forall^X$ mean, essentially, quantifiers bounded in $X$, right? – Asaf Karagila Apr 23 '15 at 21:06
• @AsafKaragila That's right. – Trevor Wilson Apr 23 '15 at 21:06
• Thanks! (And huzzah! I can infer things from context!) – Asaf Karagila Apr 23 '15 at 21:07
• 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)$ – user52534 Apr 23 '15 at 22:48
• @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. – Trevor Wilson Apr 24 '15 at 0:17

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.

• 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? – Trevor Wilson Apr 24 '15 at 0:13
• $\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. – Rachid Atmai Apr 24 '15 at 0:31
• Sure, I would like to see the notes or your dissertation, whichever is convenient. Is your dissertation online? – Trevor Wilson Apr 24 '15 at 0:34
• No it's not online. I've sent you the notes. – Rachid Atmai Apr 24 '15 at 0:43
• I would be interested as well, please (and on your dissertation, if possible). – Andrés E. Caicedo Apr 24 '15 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.