So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of diagonalization to get non-recursive sets / classes. So there's a lot of existence proofs.

Are there "limits" to our applications of diagonalization? In other words, is there a point at which our diagonalizations fail to carry us from one class to another?


  • 1
    $\begingroup$ I think Kleene's fixed point theorem (aka the recursion theorem) was born out of an attempt to diagonalize out of the computable functions and can be used to argue that no such diagonalization is possible. $\endgroup$ – Quinn Culver Dec 27 '14 at 12:07
  • 1
    $\begingroup$ It is hard to answer your question as you have not defined a diagonalization formally. But most of the results about the existence of some classes of sets (degrees) are proved with the priority methods which do not use an explicit diagonalization and it would be hard to imagine to prove such results with the diagonalization techniques alone. C.f. Friedberg-Muchnik theorem, www1.maths.leeds.ac.uk/~pmt6sbc/3163/FMslides.pdf. $\endgroup$ – Dávid Natingga Dec 30 '14 at 22:52

If we consider the set $R_0$ of computable fonctions, you can obtain a new function by diagonalisation that will solve the halt problem of this set. Adding such a function as a atomic function (and get the closure by composition) will lead you to a new set of function $R_1$.

So basically we obtain $R_1$ from $R_0$ by adding the possibility to solve the halting problem on $R_0$. This is a called a jump.

Then from $R_1$ you can jump again, and again, and again. Once you get all $R_i$ for any $i\in\mathbb N$, you can jump again : $$R_\omega=\mbox{jump}\left(\bigcup_{i\in\mathbb N} R_i\right)$$

And go on jumping to compute $R_\alpha$ for a lots of ordinals $\alpha$. But you are stuck under $\omega_1^{CK}$ the first non computable ordinal. So by jumping, you can't define constructively any function not in $\bigcup_{i<\omega_1^{CK}} R_i$. As it is a countable union of countable sets, you only obtain a zero-measure set of all functions from $\mathbb N$ to $\mathbb N$. So most functions are unreachable using that kind of tools even if extensions exist to reach far beyond that...


One way to talk about the strength of diagonalizability is via diagonal nonrecursiveness; this is a family of notions of "diagonalization against computable functions." The simplest versions are the following:

  • Let $\{\varphi_e: e\in\omega\}$ be the usual effective listing of computable partial functions $\omega\rightarrow 2$. Then a total function $f:\omega\rightarrow 2$ is DNR$_2$ if for all $e$, $\varphi_e(e)\downarrow=n\implies f(e)\not=n$.

  • Let $\{\varphi_e: e\in\omega\}$ be the usual effective listing of computable partial functions $\omega\rightarrow \omega$. Then a total function $f:\omega\rightarrow\omega$ is DNR$_\omega$ if for all $e$, $\phi_e(e)\downarrow=n\implies f(e)\not=n$.

To be DNR$_{something}$ is to diagonalize against an appropriate list of computable functions. Notice that (unlike most presentations of normal diagonalization) there are degrees of freedom here. The most obvious one is that in both cases, if $\varphi_e(e)\uparrow$ then $f$ is free to do what it likes. More interestingly, in the case of DNR$_\omega$, we have even more freedom: even when $\varphi_e(e)\downarrow$ there are infinitely many "legal" options for $f$. By contrast, in the case of DNR$_2$ this is not true: if $\varphi_e(e)\downarrow$, then $f(e)$ is completely determined ($f(e)=1-\varphi_e(e)$).

Thinking about the difference in degrees of freedom suggests the following further notion of diagonal nonrecursiveness:

  • Let $\{\varphi:e\in\omega\}$ be the usual effective listing of computable partial functions $\omega\rightarrow k$ (for fixed $k>1$) Then $f:\omega\rightarrow k$ is DNR$_k$ if for each $e$ we have $\varphi_e(e)\downarrow=n\implies f(e)\not=n$.

And more generally we can replace "$n$" with any computable notion of codomain:

  • Fix $g$ computable total. Let $\{\varphi:e\in\omega\}$ be the usual effective listing of computable partial functions $\omega\rightarrow \omega$ such that $\varphi_e(k)\downarrow=n$ implies $n<g(k)$. Then we say $f:\omega\rightarrow \omega$ is DNR$_g$ if for each $e$ we have $\varphi_e(e)\downarrow=n\implies f(e)\not=n$ and $f(e)<g(e)$.

OK, now let's talk about your question. One way to ask about the power of diagonalization is to ask:

What computing power do DNR$_{something}$ functions have?

The most natural specific question to my mind is: does every DNR$_{something}$ compute the halting problem? It may seem like the answer should be "yes," since diagonalizing against the computable functions is one of the basic things ${\bf 0'}$ lets you do; however, the answer to this question is no. Very briefly, this is because for every computable total $g$ there is a computable tree $T_g$ such that $(i)$ for each $\sigma\in T_g$ and $n\in dom(\sigma)$ we have $\sigma(n)<g(n)$, and $(ii)$ the set of infinite paths through $T_g$ is exactly the set of DNR$_g$ functions. Now apply the low basis theorem.

Note that this omits the case of DNR$_\omega$ - the corresponding tree is infinitely branching, and so the low basis theorem doesn't apply. However, it turns out that DNR$_\omega$ is a weaker notion than the others. Indeed, DNR$_2$ is the strongest of the DNR notions. To see this, let me show that if you can compute a DNR$_2$ function then you can compute a DNR$_\omega$ function; the picture should then become clear. Let $h(n)=0$ if $n>0$ and $h(n)=1$ if $n=0$. Now using the recursion theorem, given an index $e$ for a computable partial function $\omega\rightarrow\omega$ I can computably find an index $\hat{e}$ for a computable partial function $\omega\rightarrow 2$ such that the $\varphi_e(e)\downarrow=n\iff\psi_{\hat{e}}(\hat{e})\downarrow=h(n)$ (note that this means that $\varphi_e(e)\uparrow\iff\psi_{\hat{e}}(\hat{e})\uparrow$). Now supposing $f$ is DNR$_2$, let $g(x)=f(\hat{x})$; then $g$ is DNR$_\omega$.

This shows that in a certain sense, the halting problem is well out of reach of diagonalization. Of course this may not match what you think of as "the strength of diagonalization," but it's an important aspect of it, and DNR-ness (and its relatives) plays an important role in computability theory.

  • $\begingroup$ Towards the end of first part (proof of second part is well-beyond my level of knowledge) of answer you wrote "usual effective listing of computable partial functions $\omega\rightarrow \omega$ such that $\varphi_e(k)\downarrow=n$ implies $n<g(e)$." ...... did you mean $\varphi_e(e)\downarrow=n$? Because otherwise, I can't understand what that means. The value of $\varphi_e(k)$ could increase arbitrarily with $k$ otherwise ... and then no single value $g(e)$ could be greater than it. And afterall, aren't we just concerned with $\varphi_e(e)$ (diagonalisation and all that)? $\endgroup$ – SSequence Feb 17 '18 at 22:44
  • $\begingroup$ @SSequence No, I didn't, although it is a typo - I meant "$\varphi_e(k)\downarrow=n\implies n<g(k)$. That is, the $\varphi_e$s are *bounded by $g$*. $\endgroup$ – Noah Schweber Feb 17 '18 at 22:46
  • $\begingroup$ Sorry to be bothersome but I have some trouble understanding the new condition "$\varphi_e(k)\downarrow=n$ implies $n<g(k)$" too. For example, suppose we set some specific value of $k$. Now as we vary/increase $e$ we can make $\varphi_e(k)$ arbitrarily large (programs outputting larger and larger constants for example). And hence $n$ can't be thought of a well-defined number (if we assume we can vary $e$ as we wish). But maybe the condition is supposed to mean something else and I should look at this again on different time. $\endgroup$ – SSequence Feb 17 '18 at 23:32
  • 1
    $\begingroup$ @SSequence "Now as we vary/increase $e$ we can make $\varphi_e(k)$ arbitrarily large (programs outputting larger and larger constants for example)." No, the point here is that we are looking at some reasonable listing of partial computable functions which are bounded by $g$. Just like there is a reasonable listing of partial computable functions $\omega\rightarrow \omega$, and a reasonable listing of partial computable functions $\omega\rightarrow 2$. $\endgroup$ – Noah Schweber Feb 17 '18 at 23:37
  • $\begingroup$ Oh OK, thanks for clarification $\endgroup$ – SSequence Feb 17 '18 at 23:40

The term "diagonalization" is used very broadly in computability theory, where even complicated priority arguments and forcing arguments might be called "diagonalization". So there is no firm line about when "diagonalization" has been used, and hence no firm line about when it can be used.

However, there are two ways in which, as a heuristic principle, diagonalization can be difficult to use:

1. Cardinality

In a certain kind of diagonalization argument, we have a particular number of opportunities to diagonalize, and a particular number of requirements that we want to diagonalize against. For example, we can make a total function $\mathbb{N}\to\mathbb{N}$ that is not computable by defining each $f(n)$ in a way to differ from the value of $\phi_n(n)$. Here we have a countable number of opportunities to diagonalize (the values of $f$ on each input) and a countable number of requirements ("$f \not = \phi_n$" for each $n$).

In an intuitive, non-formal sense, we cannot use this method to make a function $f \colon \mathbb{N}\to\mathbb{N}$ that differs from all functions $\mathbb{N}\to \mathbb{N}$ because then we have an uncountable set of requirements to meet, but still only a countable number of opportunities to diagonalize. Of course this is not a formal argument, just a methodological heuristic.

This kind of phenomenon is also related to the use of countable transitive models in the study of forcing in set theory (certain forcing arguments are just elaborate diagonalization arguments.) For example, to force the continuum hypothesis to fail, we can begin with a countable transitive model of ZFC and add a new real by diagonalizing against the reals in the model - the method of forcing allows us to build an entire larger model of ZFC including such a real. If we begin with an uncountable model of ZFC, we run into technical issues because we can't easily diagonalize against an uncountable set of reals in the same way.

2. Partiality

We can use diagonalization to make a partial computable function that differs from every total computable function. Namely, let $g(e) = \phi_e(e) + 1$. Then $g(e)$ is undefined if $\phi_e(e)$ is undefined, but $g(e) \not = \phi_e(e)$ if $\phi_e(e)$ is defined. So $g$ is partial computable but not total computable. We can't use this particular kind of effective diagonalization to make a partial computable function that differs from every partial computable function, because the partiality gets in the way. This phenomenon is closely related to the fact that any class of functions with a universal function and some weak closure properties must include partial functions.

This issue also arises in proof theory. For example, Tarski's theorem on the undefinability of truth in a model of arithmetic uses a kind of diagonalization argument. Gödel's incompleteness theorem is proved by a similar argument, but using provability instead of truth.

In Tarski's argument, there is a kind of totality to the satisfaction relation of a model: each sentence is either true or false in a model, and so if truth were definable we could translate the liar paradox into the satisfaction relation. In Gödel's argument, provability can be partial: a particular sentence may be neither provable nor disprovable from a theory. That difference is what allows the liar paradox to become a non-paradoxical incompleteness phenomenon.


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.