FOM: correction

Harvey Friedman friedman at math.ohio-state.edu
Tue Sep 15 00:09:53 EDT 1998


In 6:44PM 9/14/98 I wrote:

THEOREM. For all k,p >= 1 there exists n so large that the following holds.
Let F:{1,...,n}^k into {1,...,n} be regressive in the sense that
F(x_1,...,x_k) <= min(x_1,...,x_k). Then there exists A contained in
{1,...,n} of cardinality p such that F[A^k] has cardinality <= k^k(p).

(This is independent of PA, and in fact equivalent to the 1-consistency of
PA over exponential function arithmetic).

I should have written:

THEOREM. For all k,r,p >= 1 there exists n so large that the following holds.
Let F:{1,...,n}^k into {1,...,n}^r be regressive in the sense that
max(F(x_1,...,x_k)) <= min(x_1,...,x_k). Then there exists A contained in
{1,...,n} of cardinality p such that F[A^k] has cardinality <= k^k(p).

(This is independent of PA, and in fact equivalent to the 1-consistency of
PA over exponential function arithmetic).








More information about the FOM mailing list