[FOM] Can someone give me an example of...

[Rob Arthan]

On Saturday 18 Feb 2006 11:38 pm, Andrej Bauer wrote:
> Let me see if this time around I can get things right. There are two
> possible readings of what Giovanni Lagnese asked for:
>
> 1)...
> 2) A computable bounded rational sequence such that every computable
>    subsequence fails to be _classically_ Cauchy.
>...

More precisely, writing N for the set of natural numbers and Q for the set of 
rationals, I think he was looking for a total recursive function f : N -> Q 
with range contained in some interval [A, B] such that for any recursively 
enumerable (r.e.) infinite subset X = {x_1, x_2, ...} of N, the sequence of 
values f(x_1), f(x_2), ... is not a Cauchy sequence.

Here follows a sketch of how to construct such an f, which I think works. The 
basic idea is to assign to each Turing machine T representing some r.e. set X 
a digit position K in a suitable positional number system and to cook up a 
sequence of numbers f such that the values of the K-th digits in the numbers 
f(x) for x in X prevent the restriction of f to X from satisfying the Cauchy 
condition.

Note that the Cauchy condition for the sequence f(x_1), f(x_2) ... above only 
depends on the set X and not on the order of the x_m: if W is a countably 
infinite set of real numbers, then a sequence S whose range is W is not 
Cauchy iff. there is an E > 0, such that any cofinite subset of W contains 
real numbers x and y such that |x - y| >= E.

For this problem, it is pleasant to work with Knuth's balanced ternary number 
representation (BT) : i.e., base 3 numbers with  digits drawn from the set 
{-1, 0, +1}. (Any positional notation with base > 2 would also do, but BT is 
nicely symmetrical). The construction will only need numbers with no integer 
part in their BT representation: such numbers lie between A = -1/2 = 
[0].[-1][-1][-1]... and B = 1/2 = [0].[1][1][1]... . The expression "K-th BT 
digit" used below means the K-th digit after the point counting from 1.

The only property of the BT representation needed is this: if X and Y are real 
numbers such that the K-th BT digits of X and Y have opposite signs, then |X 
- Y| >= (1/2) 3^(-(K-1)). E.g., with K = 1, the smallest difference is with X 
1/3 = [0].[1][0][0][0]... and Y = -1/6 = [0].[-1][1][1][1]... .

Let Y = {y_1, y_2, ...} be any subset of N with the y_m given in strictly 
increasing order. Let D(Y) denote the sequence of BT digits such that D(Y)(n) 
= 0 if n is not in Y and D(Y)(y_m) = (-1)^m. I.e., the sequence D(Y) has 
zeroes off Y and alternates between 1 and -1 on Y. Let S be any sequence of 
real numbers such that for some K and every m, the K-th BT digit of S(m) is 
D(Y)(m).  I claim that if Y is infinite and if X is any set of indices 
containing Y, then the subsequence of S determined by X is not Cauchy. To see 
this observe that any cofinite subset of X contains indices y_(m+1) and y_m 
in Y, and then, by the remark of the previous paragraph, |S(y_(m+1)) - 
S(y_m)| >= 1/2 3^(-(K+1)), since the condition on S ensures that the K-th BT 
digits of S(y_(m+1)) and S(y_m) have opposite signs.

If Y_1, Y_2, is any infinite sequence of subsets of N, associate the set Y_K 
with the digit position K, and so construct the sequence S of rational 
numbers such that the BT representation of S(n) is 0.[D(Y_1)(n)][D(Y_1)(n)] 
... [D(Y_n)(n)]. By the above remarks, for each K, if X is any set of indices 
containing an infinite Y_K, the subsequence of S determined by X is not 
Cauchy.

It remains to enumerate a sequence Y_K of subsets of N, such that if X is any 
infinite r.e. set, then for some K, Y_K is an infinite subset of X. For this 
to yield the desired recursive f : N -> Q, we need to present the Y_K 
effectively, e.g., as a (total) recursive function g: N >< N -> {0, 1} such 
that n is in Y_K iff. g(n, K) = 1. This reduces to a scheduling problem: an 
arbitrary r.e. set X is recogised by some Turing machine, T, say; if one 
conducts a fair parallel simulation of T(1), T(2), T(3), ..., discarding 
members of X that are less than ones already encountered, then, if X is 
infinite, one will eventually enumerate an infinite subset Y of X in 
increasing order. A fair parallel simulation of these simulations for all 
possible Turing machines, T_m, gives an implementation of g and hence of f. 
(Note the Y_K will come out in an order which will be a by-product of the 
order of the T_m and of the scheduling algorithm, but the order of the Y_K 
does not matter).

Comments and corrections gratefully received.

Regards,

Rob.