[FOM] Cylindric Algebra and Consistency (again)

Dana Scott dana.scott at cs.cmu.edu
Sat May 28 13:41:14 EDT 2011

Re: FOM Digest, Vol 101, Issue 35
On May 28, 2011, Vaughan Pratt wrote:

> My understanding was that varieties are closed with respect to the 
> Zariski topology (as generated by the complements of the algebraic 
> sets).  Hence I don't see how this can work for more than the 
> sublanguage of PA consisting of those formulas whose matrix (assuming 
> prenex normal form) consists of atomic formulas all of the same sign; 
> equivalently a possibly negated monotone combination of atoms.  Since no 
> nontrivial induction hypothesis ?(x) ? ?(x+1) can have this form, it's 
> not clear to me how this sublanguage could bear on Con(PA)

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?   I would use these equivalences:

	a = b  <==>  a - b = 0

	a = 0 or b = 0  <==>  a b = 0

	a = 0 & b = 0  <==> a^2 + b^2 = 0

	not a = 0  <==> for some x,y,z,w. a^2 = 1 + x^2 + y^2 + z^2 + w^2

Did I make a mistake in what I previously asserted?

Vaughan continues:

> However I then made the point that this line of reasoning is 
> set-theoretic.  Without further qualification beyond the remark that 
> Replacement doesn't seem to be needed, it would appear to assume Con(Z).
(Here Z is Zermelo set theory -- or a version of 2nd order arithmetic.)

Of course.  I was not trying to be original.  I was just trying to be 
"non-logical" and avoid formal systems in favor of what I thought were 
mathematical concepts used every day.

By the way, I forgot to explain the meaning of "cylindrical".  In a space
like Z^n, a cylinder over the last coordinate means that if one vector
(x1,x2,x3,...,x(n-1),xn) belongs to the set V, then ALL the vectors
(x1,x2,x3,...,x(n-1),y) belong.  Every set has a SMALLEST cylinder which
contains it, and a LARGEST cylinder which is included in it.  If you then
intersect the first with the hyperplane Z^(n-1), you get P(V).  The second
gives you CPC(V).  It should be clear that the first corresponds to the
existential quantifier, while the second corresponds to the universal
quantifier.  Tarski's point was that first-order definable sets could be
obtained by using cylinders and/or projections.  He was trying to take out
the "mystery" some people feel in using the formal syntax of logic.  (And
I have met many over the years who very much dislike formal logic!)

More information about the FOM mailing list