Provable equality in primitive recursive arithmetic with and without induction

Pacific Journal of Mathematics 57 (2):379-392 (1975)
  Copy   BIBTEX

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 y≠0 → gx(S(x) = y) is added to PRE, then the set of identities provable become complete r.e. (with or without 1≠0). 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.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Intuitionistically provable recursive well-orderings.Harvey M. Friedman & Andre Scedrov - 1986 - Annals of Pure and Applied Logic 30 (2):165-171.
On a Theory for AC0 and the Strength of the Induction Scheme.Satoru Kuroda - 1998 - Mathematical Logic Quarterly 44 (3):417-426.
On the strength of könig's duality theorem for countable bipartite graphs.Stephen G. Simpson - 1994 - Journal of Symbolic Logic 59 (1):113-123.
Induction and foundation in the theory of hereditarily finite sets.Flavio Previale - 1994 - Archive for Mathematical Logic 33 (3):213-241.
Strictly Primitive Recursive Realizability, II. Completeness with Respect to Iterated Reflection and a Primitive Recursive $\omega$ -Rule.Zlatan Damnjanovic - 1998 - Notre Dame Journal of Formal Logic 39 (3):363-388.
Weak theories of nonstandard arithmetic and analysis.Jeremy Avigad - manuscript
Decidable Formulas Of Intuitionistic Primitive Recursive Arithmetic.Saeed Salehi - 2002 - Reports on Mathematical Logic 36 (1):55-61.
Induction rules, reflection principles, and provably recursive functions.Lev D. Beklemishev - 1997 - Annals of Pure and Applied Logic 85 (3):193-242.
Induction and Inductive Definitions in Fragments of Second Order Arithmetic.Klaus Aehlig - 2005 - Journal of Symbolic Logic 70 (4):1087 - 1107.
Strictly primitive recursive realizability, I.Zlatan Damnjanovic - 1994 - Journal of Symbolic Logic 59 (4):1210-1227.
Finite Arithmetic with Infinite Descent.Yvon Gauthier - 1989 - Dialectica 43 (4):329-337.
Markov's Rule revisited.Daniel Leivant - 1990 - Archive for Mathematical Logic 30 (2):125-127.
Periodic points and subsystems of second-order arithmetic.Harvey Friedman, Stephen G. Simpson & Xiaokang Yu - 1993 - Annals of Pure and Applied Logic 62 (1):51-64.
Universal Induction and True Universal Arithmetic.Teresa Bigorajska - 1994 - Mathematical Logic Quarterly 40 (1):103-105.
On the limit existence principles in elementary arithmetic and Σ n 0 -consequences of theories.Lev D. Beklemishev & Albert Visser - 2005 - Annals of Pure and Applied Logic 136 (1-2):56-74.

Analytics

Added to PP
2021-12-17

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Citations of this work

On Not Saying What We Shouldn't Have to Say.Shay Logan & Leach-Krouse Graham - 2021 - Australasian Journal of Logic 18 (5):524-568.

Add more citations

References found in this work

No references found.

Add more references