# expressiveness of computable infinitary logic

A language $L_{\omega_1\omega}$ generalizes an ordinary first-order language by allowing countably long disjunctions. If we take its nonlogical vocabulary to contain just a predicate for the successor relation, then every subset of $\mathbb N$ can be defined by some formula in the language.

How does the situation change if we consider the sublanguage which results from the extra requirement to form countable disjunctions only of r.e. sets of formulas?*

For example, is every $\Pi^1_1$ set definable?

Thankyou!

Max

*Note:

Let me try to clarify the extra requirement. (Please let me know if this doesn't work!)

Set up some reasonable coding of atomic formulas $A$ as $|A|$, of variables $v$ as $|v|$, and of pairs of integers $(a,b)$ as $\langle a,b\rangle$. Define a set of indices by induction as the smallest $I$ such that

$\langle 0,|A|\rangle\in I$ for every atomic $A$.

if $i\in I$, then $\langle 1,i\rangle\in I$

if $i\in I$, then $\langle 2,\langle|v|,i\rangle\rangle\in I$

if $W_e\subseteq I$, then $\langle 3,e\rangle\in I$.

Then obtain the corresponding subset of formulas of $L_{\omega_1\omega}$ in the natural way.

-

More generally than taking just one computable disjunction, you can define for $\alpha$ is a computable ordinal, the $\Sigma_{\alpha + 1}^c$ formulas as $$\bigvee_{i \in \omega} (\exists \bar{x}_i)\varphi_{f(i)}$$ where $f$ is computable, the length of $\bar{x}_i$ is given by another computable function, and $\varphi_{f(i)}$ is the $f(i)^\text{th}$ computable infinitary $\Pi_{\beta}^c$ formula where $\beta < \alpha$.

In terms of definability, hyperarithmetic sets are exactly those subsets of $\omega$ in the language of arithemtics that can be definable by computably infinitary formulas.

Hyperarithmetics sets are $\Delta_1^1$. Of the various many definition, a set is $\Delta_1^1$ if it is $\Sigma_1^0$ and $\Pi_1^1$ in the language of second order arithemtics. One can show that $\Sigma_1^1 \neq \Pi_1^1$ by exhibiting a complete $\Pi_1^1$ set, for example the index of computable well-orderings. Hence there is a $\Pi_1^1$ set that is not hyperarithmetic. This set would not be definable using a computably infinitary formula.

However, the computably infinitary language plays a very important role in computable model theory. For example, under certain conditions, if $\mathcal{A}$ is a computable structure, there is a single computable infinitary formula, such that $\mathcal{A}$ is the only computable structure that models the formula.

Check out the book $\textit{Computable Structures and the Hyperarithmetical Hierachy}$ by Knight and Ash for more on computably infinity languages and computable structures.

-
Thankyou! Just a further question: is there a direct argument for the result that the computable infinitary formulas define only hyperarithmetical sets? (More specifically, the set of formulas in the language of successor relation that is closed under negation, existential generalization, and r.e. disjunction)? For some reason, I can't find an argument of this sort (or, sorry, for the result you state, but this must be me not getting something) in the Knight and Ash. Thanks again! –  mmw May 19 '12 at 16:54
Look at chapter 5 of the book to how hyperarithmetics sets are defined. Roughly a hyper arithmetic set is one that is Turing below these $H$-sets which are like more generalized jumps. With some induction, you can shown $\emptyset^{(\alpha)}$ is $\Sigma_{\alpha}^c$ definable. –  William May 19 '12 at 20:57
....though I was wondering about the converse! i.e., that every $\Sigma^c_\alpha$ set is hyperarithmetic. –  mmw May 20 '12 at 14:50
$\Sigma_\alpha^c$ is clearly $\Delta_{\alpha + 1}^c$. That is, is is $\Sigma_{\alpha + 1}^c$ and $\Pi_{\alpha + 1}^c$. Thus it is clearly $\Sigma_1^1$ and $\Pi_1^1$. Hence it is $\Delta_1^1$. It is well known that hyper arithmetic and $\Delta_1^1$ are equivalent. (This you can find in Knight and Ash or Sacks $\textit{Higher Recursion Theory}$.) –  William May 20 '12 at 20:36