1

Given $A$ - recursive set and function $f$ which is also recursive. Is $f(A)$ recursive?

I think that it isn't recursive, but how to prove it?

John Malick
  • 123
  • 1
    intuitively, I'd say that if $f$ is computable, and if you know how to enumerate $a_1,a_2,\ldots$ then you can enumerate $f(a_1),f(a_2),\ldots$, but you can't always enumerate $f(A)$ in the ascending order (because $g(n) = \min_{ k \ge n} f(a_k)$ isn't always computable) – reuns Mar 27 '16 at 20:16
  • Yes, I observed it too, but how to prove it formally? Proving that set is recursive is much easier than proving that it isn't. – John Malick Mar 27 '16 at 20:18
  • don't you have some examples of non recursive functions ? if you prove that for some $f$ and $A$ recursive, $g(n)$ is not recursive, it's good, no ? – reuns Mar 27 '16 at 20:21

1 Answers1

0

Do the usual sort of indexing of arithmetical sentences, and let our set $S$ be the (recursive) set of indices of proofs, say in first-order Peano arithmetic.

For any proof with index $n$, let $f(n)$ be the index of the last sentence in the proof (the theorem). Then $f(S)$ is not recursive.

André Nicolas
  • 507,029