On Grzegorczyk induction

DOI10.1016/0168-0072(94)00029-3MaRDI QIDQ1892940zbMATH OpenOpenAlexFDO

Authors Ch. Cornaros

Publication date 28 November 1995

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(94)00029-3

zbMATH Keywords

Bertrand's postulatefragment of Peano arithmeticGrzegorczyk hierarchyquadratic reciprocity law

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Review text

Let \(I {\mathcal E}^2_*\) denote the fragment of Peano arithmetic PA which allows induction on (a suitable representation of) the predicates whose characteristic function belongs to the class \({\mathcal E}^2\) of Grzegorczyk's hierarchy. \(I {\mathcal E}^2_*\) is one of the weakest fragments of \(I \Delta_0 + \text{exp}\). It is shown in the paper that \(I {\mathcal E}^2_*\) proves the quadratic reciprocity law and that a suitable fragment of \(I {\mathcal E}^2_*\) (which employs some well- known number-theoretic functions) proves Bertrand's postulate.

Recommendations

• Majorizing provably recursive functions in fragments of PA
• The prime number theorem and fragments of PA
• On the structure of models of bounded $E\sb 1$-induction
• Grzegorcyk's hierarchy and IepΣ₁
• Provably recursive functions in fragments of Peano arithmetic

Cites work

• Combinatorial principles in elementary number theory
• scientific article; zbMATH DE number 3813704 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• Provability of the pigeonhole principle and the existence of infinitely many primes

Cited in

(4)

• Pell Equations and Weak Regularity Principles
• Two (or three) notions of finitism
• Abelian groups and quadratic residues in weak arithmetic
• On bounded arithmetic augmented by the ability to count certain sets of primes

This page was built for publication: On Grzegorczyk induction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892940)