On Grzegorczyk induction (Q1892940)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On Grzegorczyk induction |
scientific article |
Statements
On Grzegorczyk induction (English)
0 references
28 November 1995
0 references
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.
0 references
Grzegorczyk hierarchy
0 references
quadratic reciprocity law
0 references
fragment of Peano arithmetic
0 references
Bertrand's postulate
0 references