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

Question

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.

Answer 1

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.

Answer 2

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.