0

In this script of Lou van den Dries I encountered (total) functions $\mathbb N^n\to\mathbb N$ and relations $R\subseteq\mathbb N^n$ that are marked as computable.

They are introduced in section 5.1. on page 82.

Addition, multiplication, coördinate functions and relation $\leq$ are computable by definition and further the collection is closed under composition and a minimalisation restricted in such a way that it does not produce undefined values.

My question is the following:

If $R_n\subseteq\mathbb N$ is computable for every $n\in\mathbb N$ and $R\subseteq\mathbb N$ is defined as: $R(a)\iff\exists n<a[R_n(a)]$ then is $R$ computable?

If I look at it only on intuition then I would expect the answer to my question to by "yes". For a fixed $a$ we just have to check for a finite ($n<a$) number of algorithms whether they confirm or deny $R_n(a)$.

But intuition has deceived me many times and am eager to find a real proof (or counterexample).

Thank you very much for taking notice of this question.

drhab
  • 151,093

1 Answers1

1

You need some "uniformness" of computability of $R_n$. Otherwise, take any set $X$ and define $$R_n = \begin{cases}{\varnothing, \ n + 1 \notin X\\ \{n + 1\},\ n + 1 \in X} \end{cases}$$ Then every $R_n$ is computable, and (assuming $0 \notin X$), we get $R = X$. Taking $X$ to be non-computable, we get non-computable set that can be represented as you wrote.

If you require uniformness - ie function $f(n, m) = \chi_{R_n}(m)$ is computable, then your argument works.

Note that with your definition we necessary have $0 \notin R$, to fix that we can, for example, change right part to $\exists n \leq a (a \in R_n)$.

mihaild
  • 15,368
  • I understand that in this situation $X\subseteq R$. But it is unclear for me that also $X^c\subseteq R^c$. If $k+1\notin X$ then we conclude that $R_k=\varnothing$. But $k+1\notin R$ demands more. It demands that $\forall n<k+1[k+1\notin R_n]$. For that condition $R_k=\varnothing$ on its own is not enough. – drhab Apr 06 '23 at 17:08
  • I see now that also $X^c\subseteq R^c$. In the thinking that underlies my first comment I did not take into account that the $R_n$ are defined as singletons hence can only contain one element. Also it is clear for me that the existence of a function $f(n,m)$ as mentioned in your answer makes things different. Thank you very much. – drhab Apr 07 '23 at 07:50