[FOM] J. Robinson's dissertation

[Andrew Arana]

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