Vol. 57, No. 2, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 332: 1
Vol. 331: 1  2
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
ISSN 0030-8730 (print)
 
Special Issues
Author index
To appear
 
Other MSP journals
Provable equality in primitive recursive arithmetic with and without induction

Harvey Friedman

Vol. 57 (1975), No. 2, 379–392
Abstract

The set of identities provable in primitive recursive arithmetic without induction (PRE), with or without standard quantifier free successor axioms, is recursive. A finite number of identities can be added to PRE such that the set of identities provable become complete r.e. (with or without successor axioms). If the successor axiom y0 gx(S(x) = y) is added to PRE, then the set of identities provable become complete r.e. (with or without 10). If PRE is augmented by definition by cases, then the set of identities provable become complete r.e. (with or without successor axioms). Equivalents of primitive recursive arithmetic (PRA) are given, involving the rule of induction restricted to identities.

Mathematical Subject Classification
Primary: 02D99
Milestones
Received: 8 August 1974
Published: 1 April 1975
Authors
Harvey Friedman