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 '15 at 21:06
  • $\begingroup$ @AsafKaragila That's right. $\endgroup$ – Trevor Wilson Apr 23 '15 at 21:06
  • 2
    $\begingroup$ Thanks! (And huzzah! I can infer things from context!) $\endgroup$ – Asaf Karagila Apr 23 '15 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 '15 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$ – 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.

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


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.