[FOM] J. Robinson's dissertation
Andrew Arana
aarana at ksu.edu
Tue Sep 9 17:35:10 EDT 2008
I have some questions about Julia Robinson's dissertation
("Definability and decision problems in arithmetic", JSL 14 (1949)),
and hope somebody can help me with them.
In this paper, Robinson shows how to define addition and
multiplication for the natural numbers in terms of just successor and
divisibility, and in terms of just successor and multiplication. She
then describes how to translate the ordinary axioms of first-order
Peano Arithmetic (PA) so that the resulting axioms just use successor
and multiplication, avoiding arithmetic (a similar translation could
be carried out for successor and divisibility).
She then notes that these "translated'' axioms are obtained in a
"mechanical way'', resulting in axioms that are "complicated and
artificial'', and accordingly sets herself the goal of finding "a
simple and elegant axiom system'' for arithmetic in terms of just
successor and multiplication. Next, she proposes a candidate
"elegant'' axiom system, replacing three of the "translated'' axioms
with simpler ones.
Question 1. Robinson was able to show in this paper that her
"elegant'' axiom system proves the same propositions as PA only by
taking the induction axiom of both axiom systems to be second-order.
She says she does not know how to show that the two axiom systems are
equivalent when taking their induction axioms to be first-order. Has
anyone improved on Robinson's work here, in particular by showing the
equivalence of PA with her "elegant" system using first-order
induction axioms?
Question 2. Robinson shows how to define addition and multiplication
in terms of successor and divisibility, but does not address how to
axiomatize PA (elegantly) in terms of successor and divisibility. Do
any of you know of work on such a project? I am aware of some work on
this by Cegielski, but my recollection is that he included the
infinitude of primes as an axiom, which I would prefer to avoid.
Best wishes,
Andy
-----------------------------------------------------------------------
Andrew Arana
Assistant professor of philosophy, Kansas State University
http://www-personal.ksu.edu/~aarana
More information about the FOM
mailing list