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....)


1 Answer 1


I don't quite know what your main question is asking, or what (3) means, but (1) and (2) seem to have straightforward answers:

  • Any nontrivial forcing makes $L$ non-E-r.e.: if $M\models ZFC$ and $M[G]$ is a nontrivial forcing extension of $V$, then $M[G]\models \neg\mathsf{(V=L)}$, and so (from the perspective of $M[G]$) we have that $L$ is not $E$-r.e. (I've edited this bit to avoid some unfortunate abuse of the letter "V.")

  • And there are only countably many E-r.e. sets (every E-r.e. set is the domain of an E-recursive function, and there are only countably many indices for such), so even within $L$ there are constructible, non-E-r.e. sets - indeed, even sets of naturals. So I'm not sure if this was the question you meant to ask.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.