Classical $\mathcal{A}$ quantifier: prove that $(\mathcal{A} \forall)_{1}$ relations and $\Sigma_1^1$ relations have the same expressive strength..

62 Views Asked by At

A quantifier on $\mathbb{N}$ is a set $Q$ such that $\emptyset \subsetneq Q \subsetneq P(\mathbb{N})$ and $Q$ is closed upwards, i.e. if $X \subseteq Y \subseteq \mathbb{N}$ and $X \in Q$, then $Y \in Q$.

Given a quantifier $Q$ on $\mathbb{N}$ we can expand a language $L$ to the language $L(Q)$ which has the additional symbols $Q$ and $\breve{Q}$, so that if $\phi$ is a formula of $L(Q)$, then so is $Q x \phi(x)$ and $\breve{Q} x \phi(x)$ with the following interpretation: $$ Q x \phi(x) \text { is true } \Leftrightarrow\{x: \phi(x)\} \in Q. $$

Suppose we also have a coding scheme in the language, such that we can code finite sequences of numbers as one natural number. $n = \langle n_1,\ldots,n_m\rangle$ is a single natural number and we can decode this too, thus we have that $(n)_i = n_i$. Now we define the classical $\mathcal{A}$ quantifier as $$ \mathcal{A}=\left\{Y \subseteq \mathbb{N}:\left(\exists x_{1} \exists x_{2} \ldots\right)(\forall n)\left(\left\langle x_{1}, x_{2}, \ldots, x_{n}\right\rangle \in Y\right)\right\} .$$ We say that a second-order relation $\varphi(\vec{x}, X)$ is $(\mathcal{A} \forall)_{1}$ on $\mathbb{N}$ if it is definable by a formula of the language $L(\mathcal{A})$ of the form $(\mathcal{A} y)(\forall z) \chi(\vec{x}, y, z, X)$ where $\chi$ only has bounded quantification and $\vec{x}$ and $X$ are free variables, $X$ being second-order.

In "Recursion, induction and quantifiers" in theorem 3.16 and subsequent notes, P. Kolaitis treats $(\mathcal{A} \forall)_{1}$ relations as if they are $\Sigma^1_1$ relations. $\Sigma_1^1$ relations are defineable by a formula of the form $\exists Y \forall z \psi(\vec{x}, Y, z, X)$, here $\exists Y$ is second-order quantification.

How does one prove that these do in fact play the same role? That for every $\Sigma_1^1$ relation $\varphi$ there exists a $(\mathcal{A} \forall)_{1}$ relations $\varphi'$ such that $$ \varphi(\vec{x},X) \Leftrightarrow \varphi'(\vec{x},X).$$ And vice versa? Or are they different in a subtle way?

I have already found that chapter 25 of Jech contains similar ideas by proving an normal form of $\Sigma_1^1$ sets through trees but this does not seem to generalise to the result I am searching for.

1

There are 1 best solutions below

0
On

Here's one direction (I'll add the other later) - namely, that every $(\mathcal{A}\forall_1)$-relation is $\Sigma^1_1$:

We have $$(\mathcal{A}y)(\forall z)\chi(\overline{x},y,z,X)\quad\equiv\quad \{y: \forall z\chi(\overline{x},y,z,X)\}\in\mathcal{A}$$ by the general definition of quantifiers. Now the right hand side can be rewritten, via the definition of $\mathcal{A}$ specifically, as $$\exists (y_i)_{i\in\mathbb{N}}\forall n(\langle y_1,...,y_n\rangle\in\{y: \forall z\chi(\overline{x},y,z,X)\}),$$ which itself can be rewritten as $$\exists (y_i)_{i\in\mathbb{n}}\forall n(\forall z\chi(\overline{x}, \langle y_1,...,y_n\rangle, z, X)).$$ This is clearly $\Sigma^1_1$, so every $(\mathcal{A}\forall_1)$-on-$\mathbb{N}$ formula is $\Sigma^1_1$.