[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