[FOM] Cylindric Algebra and Consistency

Vaughan Pratt pratt at cs.stanford.edu
Mon May 30 02:25:15 EDT 2011

On May 28, 2011, Dana Scott wrote:
 > Perhaps there is a misunderstanding here?  Is it not well known that
 > every arithmetic formula over the ring of integers can be put into
 > prenex normal form with just one (mammoth) polynomial equation as the
 > matrix?

Ah, sorry, terminology snafu.  I took your "polynomial variety" too 
literally, when what you meant (obviously in retrospect) was 
"diophantine set."  I misunderstood you to be trying to make number 
theorists and algebraic geometers feel at home (diophantine sets and 
polynomial varieties over Q intermingle in algebraic number theory).

I hadn't seen (or had forgotten) that nice trick for making the PA 
matrix diophantine and hence r.e.  Without it the matrix could denote a 
more obscure set, though how much does this matter when the subsequent 
complementing and projecting is going to scramble things at least as 

I agree that cylindrification was a great way to make logic more 
appealing to mathematicians.  Which came first, that or Halmos's 
polyadic algebras?  (I encountered the latter while an undergraduate 
browsing the Sydney Uni. library stacks in 1965, I first encountered 
cylindric algebras more than a decade later.)


More information about the FOM mailing list