Skip to main content
3 of 4
Joining separate MathJax for every character

How are Koepke's ordinal computability and E-recursion related?

In Koepke's paper, "Turing Computations On Ordinals", one has the following (well-known) result:

A set $x$ is ordinal computable from a finite set of ordinal parameters if an only if it is an element of the constructible universe.

In Sacks' survey article, "E-Recursive Intuitions", one finds these (possibly related) results:

Proposition 3.1. $V=L$ iff $L$ is E-recursively enumerable... Proposition 2.3. There exists a $\Delta_1$ definable class that is not E-recursively enumerable.

Now, since the above theorem of Koepke's characterizes the constructible sets as those ordinal computable from a finite set of ordinal parameters (note that the pure sets are sets of ordinals), one should be able to characterize the axiom $V=L$ as

'Every set of ordinals is ordinal computable from a finite set of ordinal parameters.'

Substituting this characterization for $V=L$ in Sacks' theorem, one has

'Every set of ordinals is ordinal computable from a finite set of ordinal parameters iff $L$ is E-recursively enumerable.'

It is interesting to note that Sacks' proof of Theorem 3.1 from his paper gives an indication of what must happen if $V\neq L$ (most set theorists do not believe that $V$=$L$ is an 'acceptable' axiom):

Proof of 3.1. Suppose $\forall x(x\in L\leftrightarrow\{e\}(x)\downarrow)$ and $V\neq L$. Then for some $b\notin L$, $\{e\}(b)\uparrow$. By Proposition 2.2 ["If $A$ is E-recursively enumerable, then $A$ is $\Delta_1$ definable."--my comment], divergence [$\uparrow$--my comment] is $\Sigma_1$ definable. Then by Levy-Shoenfield absoluteness, $\{e\}(x)\uparrow$ for some $x\in L$.

Hence the question asked in the title.

Three other questions:

  1. Can one 'force' $L$ to be not E-recursively enumerable?

  2. If $V\neq L$, are there constructible, non-E-recursively enumerable sets?

  3. Since $L$ is usually considered a 'class', is E-recursion defined for classes (since it is based on Normann's "Set recursion")? (Hope this is not too silly a question....)

Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39