A note on theΠ 2 0 -induction rule

Archive for Mathematical Logic 34 (4):279-283 (1995)
  Copy   BIBTEX

Abstract

It is well-known (due to C. Parsons) that the extension of primitive recursive arithmeticPRA by first-order predicate logic and the rule ofΠ 2 0 -inductionΠ 2 0 -IR isΠ 2 0 -conservative overPRA. We show that this is no longer true in the presence of function quantifiers and quantifier-free choice for numbersAC 0,0-qf. More precisely we show that ℐ :=PRA 2 +Π 2 0 -IR+AC 0,0-qf proves the totality of the Ackermann function, wherePRA 2 is the extension ofPRA by number and function quantifiers andΠ 2 0 -IR may contain function parameters.This is true even forPRA 2 +∑ 1 0 -IR+Π 2 0 -IR −+AC 0,0-qf, whereΠ 2 0 -IR − is the restriction ofΠ 2 0 -IR without function parameters

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The role of parameters in bar rule and bar induction.Michael Rathjen - 1991 - Journal of Symbolic Logic 56 (2):715-730.
Remarks on Herbrand normal forms and Herbrand realizations.Ulrich Kohlenbach - 1992 - Archive for Mathematical Logic 31 (5):305-317.
A note on Spector's quantifier-free rule of extensionality.Ulrich Kohlenbach - 2001 - Archive for Mathematical Logic 40 (2):89-92.
Herbrand's theorem and term induction.Matthias Baaz & Georg Moser - 2006 - Archive for Mathematical Logic 45 (4):447-503.
The speed-optimality of Reichenbach's straight rule of induction.Cory F. Juhl - 1994 - British Journal for the Philosophy of Science 45 (3):857-863.
A new "feasible" arithmetic.Stephen Bellantoni & Martin Hofmann - 2002 - Journal of Symbolic Logic 67 (1):104-116.
Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.
On the induction schema for decidable predicates.Lev D. Beklemishev - 2003 - Journal of Symbolic Logic 68 (1):17-34.
A note on Goodman's theorem.Ulrich Kohlenbach - 1999 - Studia Logica 63 (1):1-5.
Emeralds are no chameleons — why “grue” is not projectible for induction.Rainer Gottlob - 1995 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 26 (2):259 - 268.

Analytics

Added to PP
2013-11-23

Downloads
33 (#419,057)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Fragments of arithmetic.Wilfried Sieg - 1985 - Annals of Pure and Applied Logic 28 (1):33-71.
On n-quantifier induction.Charles Parsons - 1972 - Journal of Symbolic Logic 37 (3):466-482.
On 퐧-Quantifier Induction.Charles Parsons - 1972 - Journal of Symbolic Logic 37 (3):466 - 482.

Add more references