FOM: theory-edge mailing list

[Harvey Friedman]

Schindler 8/1/01 wrote:

>It would be great if P?=NP were independent of ZF or would even have
>anything to do with large cardinals; but there is no indication
>whatsoever why this should be true. Easily, P=NP (or its negation)
>cannot imply the existence of transitive models with large cardinals; as a
>matter of fact, the construction of such models is *the* standard tool
>for showing that natural math statements (rather than consistency
>assertions) have a strength larger than ZF. I therefore wonder how Doria
>(or anybody else, for this matter) might support the claim that large
>cardinals are related to a natural arithmetical statement (like P=NP).
>I guess revolutionary new methods would be called for.

Here are two statements that have "strength larger than ZF". These had to
be shown without using transitive models, because of absoluteness
considerations.

THEOREM A (measurable cardinals). Let F be an isomorphically invariant
Borel measurable function from infinite sequences of finitely generated
groups into finitely generated groups. There exists an infinite sequence x
such that for all infinite subsequences y of x, F(y) is isomorphically
embeddable into a term of y.

THEOREM B (Mahlo cardinals of finite order). Let f,g be multivariate
functions from the integers into the integers of quadratic growth. There
exists bi-infinite sets of integers A,B,C such that fA is disjointly
covered by C,gB, and fB is disjointly covered by C,gC.

(Here fA = f[A^k]).

The techniques are expected to be extended to show that B is stronger than
ZF even for integral piecewise linear f,g, and A,B,C being integral
piecewise linear images of geometric progressions, resulting in an
explicitly Pi-0-1 sentence.