Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Archive for Mathemat...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Archive for Mathematical Logic
Article . 1991 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1991
Data sources: zbMATH Open
DBLP
Article . 1991
Data sources: DBLP
versions View all 3 versions
addClaim

Herbrand analyses

Authors: Wilfried Sieg;

Herbrand analyses

Abstract

The Herbrand theorem shows that if an existential formula is provable, then so is a disjunction of substitution instances. The author first sharpens this condition to, for Herbrand theories, just one instance, and thus extracts a term t such that \(\phi\) (t) from a proof of \(\exists x\phi (x)\). Here, T(\({\mathfrak F})\) is said to be an Herbrand theory when it has QF(\({\mathfrak F})-IR\)- induction rule for quantifier-free formulas with function parameters from \({\mathfrak F}\)- where \({\mathfrak F}\) is closed under explicit definitions, definition by cases and bounded search. This is further sharpened for \(\exists \forall\)-formulas. [In this case a number of disjuncts are necessary.] He gives a number of interesting applications of these to the Grzegorczyk hierarchy, and the polynomial hierarchy [in bounded arithmetic of S. Buss et al.]. Here are two samples. (1) \(\Sigma^ 0_ 1({\mathfrak E})-IR\) is genuinely stronger than \(\Pi^ 0_ 1({\mathfrak E})-IR\), where \({\mathfrak E}\) is the Kalmar elementary class [Parsons]. (2) Elements of \({\mathfrak E}_ n\), \(n>2\), are exactly the functions provably total in \((\Pi^ 0_ 2({\mathfrak E})-IR)_{n-3}\), where the subscript indicates that the induction is applied at most n-3 times. The author's tool so far is nimble, and yet ``elementary'', transformations of proofs and extractions of relevant functions from proofs. By means of the same tool applied to second-order arithmetic, he gives a new proof of a Friedman's result that as to \(\Pi^ 0_ 2\)- formulas, PRA (primitive recursive arithmetic) is as strong as the second-order version of \(\Sigma^ 0_ 1-IR+\Sigma^ 0_ 1\)- AxCh\(+Weak\) König Lemma, among others. Towards the end of the paper, the author uses a more ``sophisticated'' method to prove powerful results like (a) QF(\({\mathfrak E}_{\infty})-IR+\Sigma^ 0_ 1-AC+\Pi^ 1_{\infty}-IR+WKL\) is conservative over (Hilbert's) Z, and (b) Provably total functions as of the second-order \(\Sigma^ 0_ n-IR\) are exactly the unnested \(<\omega_ n^{\omega}\)-recursive functionals. He first embeds the given proof in an infinitary system (with infinitary terms and the \(\omega\)-rule). This transformation is then formalized in the finitary system, and the reflection principle delivers the desired result. In the ``Concluding Remarks'', the author talks about possible directions of future research in proof theory.

Related Organizations
Keywords

Proof theory in general (including proof-theoretic semantics), First-order arithmetic and fragments, Provably total functions, second-order arithmetic, Herbrand theory, Kalmar elementary class, transformations of proofs, primitive recursive arithmetic, bounded arithmetic, recursive functionals, Herbrand theorem, PRA, polynomial hierarchy, reflection principle, Grzegorczyk hierarchy, extractions of relevant functions from proofs, Second- and higher-order arithmetic and fragments

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    39
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
39
Top 10%
Top 10%
Top 10%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!