Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified.
I need to prove that set of Gödel numbers of all $\forall \exists$-formulas of signature $\sigma _0 = <+, \cdot, \le, s, 0>$ is recursive.
Main thoughts:
I need to prove that characteristic function $\chi$ of this set is recursive. Let's say that $\chi(n)$ returns 1 if the formula which has the Gödel number n is $\forall \exists$-formula, and 0 otherwise.
If formula $\phi$ is unquantified, then $\chi(GN(\phi))$ should return 1.
If $\phi = \forall x _i \phi _1$ and:
- $\phi _1 = \forall x _j \phi _2$ and $j = i + 1$ then return $\phi(GN(\phi _1))$.
- $\phi _1 = \exists x _j \phi _2$ and $j = i + 1$ then return $\phi(GN(\phi _1))$.
- $\phi _1$ is unquantified, then return 1.
If $\phi = \exists x _i \phi _1$ and:
- $\phi _1 = \exists x _j \phi _2$ and $j = i + 1$ then return $\phi(GN(\phi _1))$.
- $\phi _1$ is unquantified, then return 1.
Otherwise return zero.
Is this the valid description of function for this set?