4
$\begingroup$

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.

1 Answers 1

3

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.

  • 1
    $\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}$.)2012-05-20