[FOM] Generalizatons of the theorem that PA cannot be finitely axiomatized.

Vann McGee vmcgee at MIT.EDU
Mon Apr 30 09:00:51 EDT 2007

	I have a question about extensions of Ryll-Nardzewski's theorem that
PA isn't finitely axiomatizable, and hope I can get some help with it.
Tarski, Mostowski, and Robinson talk about interpreting an arithmetical
theory by finding a unary formula "Z," a binary formula"S," and ternary
formulas "A" and "M" to translate zero, successor, addition, and
multiplication, respectively, and translating arithmetical sentences into
the new language compositionally; in particular, the interpretation i will
set i((x)P) equal to (x)i(P). What they call a relative interpretation
employs a unary formula "N" to represent "natural number," setting i((x)P)
equal to (x)(Nx -> i(P)). Thus a relative interpretation restricts the
domain of quantification, but an interpretation does not. (Contemporary
usage is a little different.)

	Ryll-Nardzewski's argument shows that no consistent, finitely
axiomatizable theory into which you can interpret Robinson's Q entails all
the universal closures of formulas you can get by substituting a formula of
the interpreting language for the schematic letter "R" in the induction
axiom schema "((x)(Zx -> Rx) & (x)(y)((Sxy & Rx) -> Ry)) -> (x)Rx" (although
you can find  consistent, finitely axiomatizable theories that entail all
the induction axioms you get if you only allow interpretations of
arithmetical formulas to be substituted). My question is, does the same
result hold for relative interpretations? Is there a consistent, finitely
axiomatizable theory into which you can relatively interpret Q that entails
all instances of the schema "((x)((Nx & Zx) -> Rx) & (x)(y)((Nx & Ny & Sxy &
Rx) -> Ry)) -> (x)(Nx -> Rx)"? I know that there won't be such a theory if
you require the interpreting theory to contain, in addition to the
interpretation of Q, a wee bit of set theory, but I don't know whether this
further assumption is really needed. I would be grateful to find out.

More information about the FOM mailing list