[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).
Regards,
Robg.
More information about the FOM
mailing list