FOM: large cardinals and P vs NP

Robert M. Solovay solovay at ccrwest.org
Tue Aug 7 13:59:06 EDT 2001



On Sat, 4 Aug 2001, Mitchell Steven Spector wrote:

>    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.)
> 
	This is not correct. The statement "T is omega-consistent" is
arithmetic. 

	For a specific example, take "ZFC + 'ZFC is *not*
omega-consitent'.

	This theory is omega-consistent, but proves the arithmetically
false statement 'ZFC is omega-inconsistent'.

	I think you are confusing omega-consistent with "has an
omega-model".

	--Bob Solovay







More information about the FOM mailing list