FOM: large cardinals and P vs NP

[Mitchell Steven Spector]

On Thu, Aug 02, 2001 at 11:33:17AM -0400, Stephen Cook wrote:
> Further to the question of whether large cardinals might help
> settle the P vs NP question, could someone answer the following
> question:
> 
> I suppose that a large cardinal axiom could be consistent with ZFC,
> but in some sense still false.  But in this case, could it imply
> a false statement of number theory?
> 
> More precisely, suppose C is a large cardinal axiom and A is a statement
> of first-order number theory.   Suppose that C + ZFC is consistent,
> and  C+ ZFC implies A.  Is A necessarily true?
> 
> Stephen Cook


   This brings up an interesting question regarding large
cardinal axioms.

   First of all, in the scenario above, as Joe Shipman pointed
out, the sentence A isn't necessarily true.  A might be false
if the theory ZFC + C were consistent but not omega-consistent.

   If the theory ZFC + C is omega-consistent, then A must be
true, even if A is not arithmetical but just Sigma-1-1.
(Alternatively, if A is a Pi-0-1 sentence of number theory,
then the consistency of the theory ZFC + C is sufficient to
prove that A is true.)

   But does anybody know any actual example of a sentence,
apparently and ostensibly of large cardinal character, that
turns out to be consistent but not omega-consistent?  (Even
better, can one find a consistent "large cardinal axiom"
which proves a false statement of number theory?)


   The closest I've thought of is the following large
cardinal property expressed as a countably infinite
collection {C0, C1, ...} of first-order sentences.
Add a constant symbol j to the language of ZF.  Consider
the theory consisting of ZFC together with the following
additional axioms (where V(alpha) denotes the set of all
sets of rank < alpha):

C0: There exist ordinals rho and beta such that j is an
elementary embedding, not the identity, of V(rho + 2)
into V(beta).

Cn for n > 0: If kappa is the least ordinal moved by j,
then (j^n)(kappa) < rho.
[Here j^1 = j and j^(n+1)(alpha) = j((j^n)(alpha)).]

   The theory T = ZFC + {Cn | n is less than omega} is
consistent (by the compactness theorem -- assuming that,
for every n, ZFC is consistent with the existence of an
n-huge cardinal).

   But T is omega-inconsistent:  In any omega-model of
T, we would have lambda <= rho, where lambda = 
sup {(j^n)(kappa) | n < omega}.  But then the restriction
of j to V(lambda + 2) would be an elementary embedding,
not the identity, mapping V(lambda + 2) to itself.  This
is well-known to be impossible (by Kunen's proof from ZFC
that there is no non-trivial elementary embedding of the
universe into itself).


   This isn't really a very nice example, since it requires
an infinite collection of axioms rather than a single large
cardinal axiom.  Also, one may doubt the consistency of T,
since that depends on the consistency of n-huge cardinals.

   In addition, T apparently proves only true sentences of
number theory.  (I say "apparently" since this fact depends
on the omega-consistency of n-hugeness for each integer n.)

Mitchell Spector

P.S.  I didn't change the Subject line, but I don't really
believe that this has anything to do with the P=NP question.