[FOM] Classical/Constructive Arithmetic

Rob Arthan rda at lemma-one.com
Sun Mar 19 11:48:00 EST 2006

On Saturday 18 Mar 2006 9:18 am, Harvey Friedman wrote:
> ...
> The aim is to concentrate on the following questions.
> 1. Examples where the known proofs are nonconstructive, and nobody knows if
> there are constructive proofs.
> 2. Examples where the known proofs are nonconstructive, and we know that
> all proofs are nonconstructive.

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).



More information about the FOM mailing list