FOM: A Natural(?) Nonrecursive Set of Integers
Harvey Friedman
friedman at math.ohio-state.edu
Thu Sep 6 08:20:31 EDT 2001
Natural(?) Nonrecursive Sets of Integers
by
Harvey M. Friedman
September 6, 2001
Here is a natural(?) nonrecursive set of integers.
For integers n,m, define R(n,m) if and only if n is the maximum value of
some polynomial P:Z^9 into Z with degree and coefficients of magnitude at
most m.
Let A be the set of all integers n which is the maximum value of some
polynomial P:Z^9 into Z with degree and coefficients of magnitude at most
log log log n.
For integers n,m, define S(n,m) if and only if n is the number of positive
values of some polynomial P:Z^9 into Z with degree and coefficients of
magnitude at most m.
Let B be the set of all integers n which is the number of positive values
of some polynomial P:Z^9 into Z with degree and coefficients of magnitude
at most log log log n.
THEOREM. A,B,R,S are of Turing degree <= 0'. A,B,R,S are are not Pi-0-1.
A,B meet every infinite r.e. set.
The expression log log log n is used as a particularly simple expression
that does the job. However, an interesting question is to figure out just
what expressions will make A and/or B nonrecursive.
More information about the FOM
mailing list