5
$\begingroup$

Using the definitions given below, my question can be restated as

Does there exist a primitive recursive (PR) real $\{s_n\}$ such that for every scale $r \geq 2$ and every PR sequence $a_n$ with $0 \leq a_{n+1} \leq r-1$ it is NOT the case that $$ \{s_n\} = \{ \sum_{p \leq n} a_p r^{-p} \} $$

If $\{s_n\}$ is a PR real number and if $a_n$ is a PR sequence such that $$ 0 \leq a_{n+1} \leq r-1, r \geq 2 $$ and $$ \{s_n\} = \{ \sum_{p \leq n} a_p r^{-p} \} $$ then $\{s_n\}$ is said to have the PR expansion $\sum_{p \leq n} a_p r^{-p}$ in the scale of $r$.

A rational PR function which is PR convergent is called a PR real number.

PR real numbers $\{s_n\}$ and $\{t_n\}$ are equal, denoted $\{s_n\} = \{t_n\}$, if $\vert s_n - t_n \vert < 1/10^k$ for majorant $n$.

A rational PR function $f(x)$ is PR convergent if there is a PR $N(k)$ such that $N(k+1) \geq N(k) \geq k$ and $$ i,j \geq N(k) \rightarrow \vert f(i)-f(j) \vert < 1/10^k $$

$\endgroup$
8
  • $\begingroup$ Since I think the answer depends on the details, could you say exactly what you mean by "primitive recursively convergent"? I would guess a certain PR Cauchy property, namely, that there is a primitive recursive function $\epsilon\to N$ such that for $n,m\geq N$, we have $|s_n-s_m|<\epsilon$? Secondly, although you haven't stated a question in the post, there is a question in your title, but the quantifiers are not clear. Do you want that there is no expansive for any scale $r$, or that the expansion function is not uniformly PR in $r$, or what? $\endgroup$ Feb 18, 2016 at 1:04
  • $\begingroup$ I've included the definition of pr convergent at the end of the body of the question. I have also stated the question using the definitions in the question body. Thank you. $\endgroup$
    – John
    Feb 18, 2016 at 1:20
  • $\begingroup$ I have also edited the question body using your abbreviation of primitive recursive as PR. $\endgroup$
    – John
    Feb 18, 2016 at 1:22
  • $\begingroup$ I want that there is no expansive for any scale $r$. $\endgroup$
    – John
    Feb 18, 2016 at 1:24
  • 1
    $\begingroup$ Yes. An example is given in Goodstein's Recursive Analysis, and, as you can imagine, its construction and demonstration is considerably complex. I just attempted to write the construction in this comment and was cut off by the limit. Vaguely, using Rosza Péter's proof that all PRFs of one argument can be enumerated to build a PRF which is general but not PR to which Kleene Normal Form gives a PRF of 1 arg. and PR Pred of 2 args. which is used to prove E. Specker's theorem that there is a PR Pred of 1 arg. giving a GRF not PR, which is used to give a PR real without a PR decimal expansion. $\endgroup$
    – John
    Feb 18, 2016 at 2:11

1 Answer 1

4
$\begingroup$

I think it's useful to first consider an analogous situation in constructive mathematics. It is not possible to show constructively that every real number has a base $b$ expansion. This is because if the expansion starts $0.xxxx$, then we know the number is less than or equal to $1$, and if the expansion starts $1.xxxx$ we know the number is greater than or equal to $1$. But to be able to decide whether a number is $\leq 1$ or $\geq 1$ is equivalent to the principle LLPO, which is not constructive. Similarly it is impossible to find a base $n$ expansion of all computable reals in a uniformly computable way. We'll use this basic idea in the proof below.

There is one curious difference. For general computable functions, we can't find a expansion uniformly, but each computable real individually does have a computable expansion, because both rational and computable irriational numbers have computable expansions. For p.r. reals we can do something much better, which is to find one particular p.r. real with no p.r. expansion.

We basically do this by a diagonal argument. Assume that we are given a primitive recursive surjective pairing operation on $\mathbb{N}$, denoted $(,)$. Also say that we are given a p.r. enumeration of codes for all p.r. functions, represented as codes for Turing machines. We will define a p.r. real $s = (s_i)_{i \in \mathbb{N}}$ in a sequence of "blocks" where in the $n$th block we will ensure that if $n$ codes the pair $(e, r)$ then the $e$th p.r. function is not a p.r. expansion of $s$ in the scale $r$. Along the way we will ensure that for $j, k > i$, $|s_j - s_k| < \frac{1}{10^i}$. Together with defining $s_i$ in a p.r. manner, this will ensure that $s$ is in fact a p.r. real.

Within each block $(e, r)$, we define $s_i$ as follows. Let $i_0$ be the first $i \in \mathbb{N}$ that lies in the block $(e, r)$. Define $q \in \mathbb{Q}$ to be $s_{i_0 - 1}$ if $i_0 > 0$ and $1$ otherwise. Now let $N$ be such that $r^{N} > 2 \times 10^{i_0}$. We can then find in a p.r. way, $k \in \mathbb{N}$ so that $|\frac{k}{r^N} - q| < \frac{1}{2\times 10^{i_0}}$. Let $s_{i_0} := \frac{k}{r^N}$. Now suppose that $(a_j)_{j \in \mathbb{N}}$ is some sequence such that $0 \leq a_j < r$ for all $j$. Then we have that for some $k'$, $\sum_{j = 0}^{N} a_j r^{-j} = \frac{k'}{r^N}$. Note that if $k' < k$, then $\sum_{j = 0}^\infty a_j r^{-j} \leq \frac{k}{r^N}$ and if $k' \geq k$ then $\sum_{j = 0}^\infty a_j r^{-j} \geq \frac{k}{r^N}$. We now ensure that the $e$th p.r. function is not an expansion of $s$ in scale $r$. We can't evaluate $\{e\}(j)$ for $j\leq N$ in a p.r. way, but what we can do is ask whether $\{e\}(j)$ has halted in less than $i$ steps for $j \leq N$. If $\{e\}(j)$ has not yet halted at stage $i$ for some $j \leq N$, we set $s_i := s_{i_0}$. If $\{e\}(j)$ has halted at stage $i$ for every $j \leq N$, we calculate $k'$ as above. If $k' < k$, we define $s_i := s_{i_0} + \frac{1}{3 \times 10^i}$ and from now on ensure that for future $i' > i$, we have $s_{i'} > s_{i_0} + \frac{1}{4 \times 10^i}$. This makes sure that $s > s_{i_0}$. If $k' \geq k$, then we similarly define $s_i := s_{i_0} - \frac{1}{3 \times 10^i}$ and ensure that for $i' > i$, we have $s_{i'} < s_{i_0} - \frac{1}{4 \times 10^i}$, to get $s < s_{i_0}$. However, by the above reasoning this has made sure that $e$ is not a p.r. expansion of $s$ of scale $r$ as required. Finally, note that

  1. Since $e$ is primitive recursive, we know that eventually $\{e\}(j)$ will halt for every $j \leq N$, so we will at some point be able to diagonalise and move on to the next block. This is the crucial difference to general recursive functions.

  2. We can't find the length of each block in a primitive recursive way, but also we don't need to for the argument to work.

$\endgroup$
6
  • $\begingroup$ Is their a bound on the search for the first $i$ that lies in the $(e,r)$-th block? Am I correct in saying that since we can not find the length of each block in a PR way then we can not place a bound on the search for the least $i$ such that $s_i$ belongs to the $(e,r)$-th block? Goodstein: "we may ask if a search without limit is really a search or not". $\endgroup$
    – John
    Feb 19, 2016 at 0:04
  • $\begingroup$ Perhaps I am missing something, but how is it known that $s_i$ is primitive recursive? $\endgroup$
    – John
    Feb 19, 2016 at 0:12
  • $\begingroup$ We set things up so that we don't need to compute $i_0$ from $(e,r)$. We need to compute $s_i$ from $i$, so what we need to know is which block the current $i$ is in, and where precisely in the block it is. This can be done by carrying out the computation of $s_{i'}$ for $i' < i$ and keeping track of how many times we have switched block and when was the last time we switched. I don't think I could give a full formal proof that $s_i$ is p.r., but it looks to me like everything used in the computation should be okay. $\endgroup$
    – aws
    Feb 19, 2016 at 0:24
  • $\begingroup$ I agree with you that it looks like $s_i$ is PR specifically because, as you stated, ${e}(j)$ will halt for every $j \leq N$. I'm going to try and see if I can't put your argument in line with Goodstein's proof that there is a PRF without a PR decimal expansion: both yours and his argument use a diagnolization, though his uses Rosza Péter's proof that all PRFs of one argument can be enumerated. I will try to translate your Turing code argument into one involving Péter's enumeration of PRFs of one variable. $\endgroup$
    – John
    Feb 19, 2016 at 1:07
  • $\begingroup$ Yes, it should be able to rephrase the argument along those lines. However, I don't think it's necessary to know that $e{j}$ halts eventually to show $s_i$ is defined; this is only used after $s$ is constructed, to show we never ended up in an infinitely long block. I think, constructing $s$, it's more important that we can decide in a p.r. way whether $e{j}$ has halted within $i$ steps, which follows from Kleene's T predicate being p.r.. $\endgroup$
    – aws
    Feb 19, 2016 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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