[FOM] PA with few symbols.

H. Enderton hbe at math.ucla.edu
Sun Jul 25 17:26:29 EDT 2004

Neil Tennant suggests that we "construct" variables as follows:
*,  #*,  ##*,  ...  (i.e., x_0,  x_1,  x_2, ... ), so that "every
quantified sentence of the language (of Peano arithmetic, say) would
be constructible from a genuinely *finite* lexicon."

I would put it more strongly:  This is exactly what the variables
*really are*, and the other version, x_0, x_1, ... , is merely a
constructed abbreviation.

The language of PA is a *language*, that is, a means of communication.
Those strings of symbols we talk about should be capable of being
transmitted between people or machines or whatever.  As Turing's 1936
paper points out, alphabets must always be finite, or else there will
be arbitrarily similar symbols.  (This is a theorem of analysis.
Define a symbol to be a Lebesgue measurable subset of the unit square.
Then for any infinite set of symbols and any positive epsilon, there
will be two symbols whose symmetric difference has measure less than

As Tim Chow pointed out, all this is not exactly what Bill Taylor was
asking about originally.

--Herb Enderton

More information about the FOM mailing list