[FOM] recursion theory question

[Harvey Friedman]

On 3/19/06 11:48 AM, "Rob Arthan" <rda at lemma-one.com> wrote:

> This reminds me of a problem that I've been trying to forget because I can't
> solve it. Perhaps someone can put me out of my misery:
> 
> Any infinite r.e. set contains an infinite recursive set. Indeed, there is a
> recursive function, f, such that if k is the index of an infinite r.e. set
> W_k, then f(k) is the index of the characteristic function of an infinite
> subset of W_k. Can one arrange for f(k) be the index of a total recursive
> function for every k (and not just the k for which W_k is infinite)?
> 
> In the original problem, it would do for f(k) to be the characteristic
> function of a set of pairs of natural numbers, such that if k is infinite,
> then for some m, the set {n | {f(k)}(m, n) = 1} gives an infinite subset of
> W_k (with m not necessarily a recursive function of k).
> 

At first, I didn't see a real connection with this problem and
constructivity. While solving it, I did see a real connection - although at
present, not much connected with what this email was a reply to:
http://www.cs.nyu.edu/pipermail/fom/2006-March/010208.html

NOTE: I made some corrections to an earlier version thanks to Arthan.

*************************

As I was working to get a negative answer, I came across the following
problem in constructive mathematics.

First, we have Cantor's diagonal theorem.

THEOREM 1. The following is provable constructively. Let A_0,A_1,... be an
infinite sequence of subsets of N (decidable subsets). There exists a subset
B of N that differs somewhere from every one of the A's. I.e., for all i,
there exists n, such that n in B iff n notin A_i.

Now classically, there are some notable stronger conclusions one can draw.
The question is: which of these sharper statements are provable
constructively? 

a. B is infinite and B differs somewhere from every one of the A's.
b. B is infinite and B does not include any A_i. I.e., for all i, there
exists n such that n is in A_i but n is not in B.

It is trivial to extend Theorem 1 with a above. Just throw in all evens, and
work in the odds.

But what about b? Yes, it can be done constructively, with a little finesse.

THEOREM 2. The following is provable constructively. Let A_0,A_1,... be an
infinite sequence of decidable subsets of N. There exists an infinite
decidable subset B of N that does not include any of the infinite A's, in
the strong sense of "not included": for all i, if A_i is infinite, then
there exists n, such that n is in A_i and n is not in B.

We inductively define B. Suppose membership in B has been determined for the
integers 0,1,...,2n-1, n >= 0. We now determine membership in B for the
integers 2n,2n+1. 

Let k be least such that

i. k <= 2n.
ii. 2n is in A_k or 2n+1 is in A_k.
iii. B, so far, includes A_k intersect {0,...,2n-1}.

If there is no such k, then put 2n and 2n+1 in B.
If 2n is in A_k, then put 2n+1 in B and keep 2n out of B.
If 2n is not in A_k, then put 2n in B and keep 2n+1 out of B.

The above is the execution of "stage n" in the construction of B.

Obviously B is infinite. We write alpha(n) for the k in the construction. Of
course, alpha(n) might be undefined. But obviously alpha is one-one.

Let i >= 0. Now let's FIRST argue classically that B does not include Ai.

Suppose B includes A_k, where A_k is infinite. Let j be so large that the
alpha(j'), j' >= j, do not include any integers < i. Let p > j,k, where p
lies in A_k. Write p = 2n or 2n+1. Thus we are examining stage n in the
construction of B.

Obviously k <= 2n, 2n is in A_k or 2n+1 is in A_k, and B, so far, includes
A_k intersect {0,...,2n-1}. Therefore alpha(n) is defined and alpha(n) <= k.
Hence alpha(n) = k. But then by the construction, B does not include A_k.
This is a contradiction. This completes the verification that this
construction works CLASSICALLY; i.e., B is infinite and does not contain any
infinite A_i.

But now we show that this construction also works CONSTRUCTIVELY.

Let A_k be infinite. Let a_0 < a_1 < ... be the enumeration of the elements
of A_k that are greater than 2k. Write these as 2b_0 + i_0 < 2b_1 + i_1 <
... , where each at = 2b_t + i_t, and i_t is 0 or 1. (We might have some b_t
= b_t+1). 

Look at alpha(b_0),...,alpha(b_3k). If one of these is either greater than k
or undefined, then B does not include A_k, in the strong constructive sense.
So we can assume that they are all < k. Since the b's can at most occur
twice in b_0,...,b_3k, and alpha is one-one where defined, we have a
contradiction by counting. Hence at least one of these alpha's is k or
undefined. Say alpha(b_j) is k or undefined. From this, clearly 2b_j lies in
A_k but not in B, or 2b_j + 1 lies in A_k but not in B. Hence B does not
include A_k. QED

The construction in Theorem 2, even with the classical proof that it works,
trivially translates to the recursion theory domain to yield the following:

THEOREM 3. Let R be a recursive binary relation on N. There exists an
infinite recursive subset A of N that does not include any infinite cross
section of R. 

This answers the question from Arthan in the negative (including the form of
the question in his final paragraph). For suppose f is a recursive function
such that each f(n) is the index of a characteristic function such that for
all n, if W_n is infinite then phi_f(n) is the characteristic function of an
infinite subset of W_n. Let R(n,m) if and only if phi_f(n) at m is 1. Then
by hypothesis, R is recursive. Let A be an infinite recursive set which does
not include any cross section of R. Let W_n = A. Then phi_f(n) is the
characteristic function of an infinite subset of W_n. Hence W_n contains the
cross section R_n, contradicting the choice of A.

Harvey Friedman