[FOM] Re: PA with few symbols

Timothy Y. Chow tchow at alum.mit.edu
Wed Jul 21 10:06:27 EDT 2004


I wrote:
> I think Bill Taylor was asking a different question, namely whether it's
> possible to formulate a recursive set of axioms (in the first-order
> language of arithmetic) that is logically equivalent to PA but that uses
> only a finite number of variables.
> 
> The answer is surely no, and probably follows from the fact that the 
> arithmetical hierarchy is proper, but I don't see an immediate proof.

As Randall Holmes pointed out, this is wrong.  I was confusing the
number of variables with the quantifier depth, which is a particularly 
embarrassing mistake since in descriptive complexity---a topic I'm a 
little more familiar with---the distinction is fundamental.  Sorry for
any confusion I created.

Tim



More information about the FOM mailing list