[FOM] Cylindric Algebra and Consistency

[Dana Scott]

Following an old plan of Tarski, let's do some
"formal syntax" without using logical syntax.  
And to make things seem more "mathematical", let's 
use the ring Z of integers, rather than the semiring
N.  (We recall that N is polynomially definable
in Z as those elements that are the sum of four
squares.)

Now, in a higher dimension, say Z^n, we also
know what is meant by a POLYNOMIAL VARIETY:
it is a subset V defined by a polynomial equation 
in n-variables:

	f(x1,x2,x3,...,xn) = 0.

And, it is easy to give a "code" to such varieties,
because every polynomial is writable as a linear 
combination of monomials, and a monomial is given
by the n-tuple of exponents, which can be taken as
a tuple in N^n.  A polynomial, then, is coded as
a map from a finite subset M of N^n to Z which
associates to each "monomial code" its coefficient
in the polynomial.  Such a code for a variety is thus
a very finite object.

Starting with the last variable, xn, we can choose
either to COMPLEMENT the variety (as a subset of
a higher dimension), or to PROJECT the subset down
to the next lower dimension.  We can notate such
a sequence of operations by symbolic combinations 
such as

	CPPCPPPCPCP...CPCP(V)

with at most n P's. (We work here from the inside out
projecting and complementing as directed, treating
the variables in the order xn, x(n-1),...,x2,x1.) 

If there are n-1 P's, then we get essentially just 
a subset of the ring Z. (Actually, a set of one-termed
vectors.)  If we have n P's, then we have a subset of

	Z^0 = {<>},

the set with one vector of length zero.  And there
are just two possible subsets: empty or full.  Call
such a result an "n-fold reduction" of the given V.

Given the code for V and the sequence of P's and
C's as above, would you care to GUESS whether the
n-fold reduction is empty or full?  The classical
insights of Gödel and Tarski tell us that there
can be no recursive decision method to answer this
question (i.e., recursive in the codes).  And indeed
the complexity of the question goes far, far beyond
the recursive level.

The (n-1)-fold reductions, as subsets of Z, give us
the "arithmetically definable" sets of integers.
And it is a fun (mathematical) exercise to show that
this family of subsets of Z forms a Boolean algebra of
sets.  And it will be of no surprise to find that
the sets obtained are much, much more than just the 
recursive subsets of Z.  (It is a little harder 
exercise, for instance, to show that ALL recursive 
subsets of Z are indeed included.)

Tarski also famously showed that if we start with
the field R of real numbers (or the field C of the
complex numbers), then the questions about the
n-fold reductions of varieties over R (or C) DO
have recursive answers.  (Again, polynomials at
the start have only integer coefficients.)  In the
case of the field Q of rational numbers, it took
Julia Robinson lots and lots of work to show that 
the situation is just as bad as that for Z (or N).

We agree, of course, that number theorists do not
tend to work with ARBITRARY varieties.  There are
many unsolved problems, I am sure, on the level
of cubic polynomials in just a few variables.  But
I see no MATHEMATICAL reason to say that the general
cases considered in my retelling of the story here
are not mathematical questions.

Returning to Z, we might want to ask whether there
are some systematic RULES to work with the monomial
and PC-codes to help decide whether an n-fold
reduction is empty or full?  And, yes, I know some
nice rules.  If you would like to come back to the
infant school another day, I could spell the rules
out for you, if you wish.  The rules are based on
a little algebra (of the kind that computer algebra
people have implemented many times), and some easy
Boolean algebra and properties of projections.  We
also need to invoke principles such that the non-empty
positive part of an arithmetically definable set
has a LEAST element.  Such a least element can
be picked out using this projection stuff.  (And
we need a "parametric" version of this principle.)

Perhaps a skeptical student might ask: "How do
you know that your rules of manipulation do not
lead to some incorrect results?"  "Good question,"
I will say, "but, when you see the rules, you will
agree that they are OBVIOUSLY correctness
preserving."  In other words, there is no problem
with the rules INDIVIDUALLY, but it is always hard
to guess whether a long sequence of applications
of the rules can lead to any desired conclusion.
We cannot get BAD conclusions, but we may not be
able to see how to find an INTERESTING conclusion.
The rules do not give us hints as to their most
effective uses.  Doing GOOD mathematics usually
requires years of experience and study.  But that
is not a criticism of the rules I have in mind.