2
$\begingroup$

Let $\mathbb{N}$ be the set of all positive integers and let $P(n),Q(n)$ be a pair of general recursive mappings of $\mathbb{N}$ into itself such that for all pairs $h,k$ of distinct positive integers, the absolute value of $(P(k)/(Q(k))-(P(h)/Q(h))$ does not exceed $(1/k)+(1/h).$

We have defined a general recursive Cauchy sequence of positive rational numbers which must converge to a unique non-negative real number.

The book "Foundations of Constructive Analysis" by E. Bishop uses Cauchy sequences of this type (which need not necessarily be general recursive) to illustrate how "constructive" mathematics can deal with the system of real numbers.

My question, however, belongs to classical mathematics. Let $r$ be any non-negative real number which is the limit of such a general recursive Cauchy sequence of positive rational numbers. Clearly there are many different Cauchy sequences of this sort which converge to $r.$

But does there always exist a Cauchy sequence converging to $r,$ whose mappings $P(n),Q(n)$ are both primitive recursive?

$\endgroup$
1
  • 2
    $\begingroup$ You could just ask: Is every real number that is the limit of a computable Cauchy sequence of rationals with a fixed rate of convergence also the limit of a primitive recursive such sequence? $\endgroup$ Commented Sep 6, 2015 at 18:07

1 Answer 1

6
$\begingroup$

No. Counterexample: consider a real number $0<x<1$ whose binary expansion is $$0.x_1x_2\dots$$ where $$x_{\langle i,j\rangle}=f_i(j)$$where $f_i$ is the $i$th function in a fixed computable list of the primitive recursive $\{0,1\}$-valued functions.

If $P$ and $Q$ for this $x$ are primitive recursive then we should be able to prove that the diagonalizing function $g(i):=1-f_i(i)$ is primitive recursive, which is a contradiction. Granted, we may have to fix some details such as turning $1/k+1/h$ into $2^{-(k+h)}$ or so.

$\endgroup$
1
  • $\begingroup$ This is a very nice approach which looks as if it would work, although I do not know if I would be able to fill out all the details of a rigorous proof. It would seem, then, that we could define an ascending chain of subsets of the set of computable functions-starting with the set of primitive recursive functions- and classify a computable real number r by the smallest set in the chain containing a function that determines a Cauchy sequence of rational numbers which converges to r. $\endgroup$ Commented Sep 7, 2015 at 19:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .