FOM: large cardinals and P vs NP
Mitchell Steven Spector
spector at seattleu.edu
Sat Aug 4 05:48:08 EDT 2001
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.
More information about the FOM
mailing list