Completeness of the primitive recursive $$omega $$-rule

Archive for Mathematical Logic:1-17 (forthcoming)

Shoenfield’s completeness theorem states that every true first order arithmetical sentence has a recursive \-proof encodable by using recursive applications of the \-rule. For a suitable encoding of Gentzen style \-proofs, we show that Shoenfield’s completeness theorem applies to cut free \-proofs encodable by using primitive recursive applications of the \-rule. We also show that the set of codes of \-proofs, whether it is based on recursive or primitive recursive applications of the \-rule, is \ complete. The same \ completeness results apply to codes of cut free \-proofs.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/s00153-020-00716-9
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,355
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.
Term Rewriting Theory for the Primitive Recursive Functions. E. Cichon & A. Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Term Rewriting Theory for the Primitive Recursive Functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Unary Primitive Recursive Functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Classical Logic, Intuitionistic Logic, and the Peirce Rule.Henry Africk - 1992 - Notre Dame Journal of Formal Logic 33 (2):229-235.
The Ackermann Functions Are Not Optimal, but by How Much?H. Simmons - 2010 - Journal of Symbolic Logic 75 (1):289-313.
Fragments of $HA$ Based on $\Sigma_1$ -Induction.Kai F. Wehmeier - 1997 - Archive for Mathematical Logic 37 (1):37-49.
Program Extraction for 2-Random Reals.Alexander P. Kreuzer - 2013 - Archive for Mathematical Logic 52 (5-6):659-666.


Added to PP index

Total views
3 ( #1,218,701 of 2,286,123 )

Recent downloads (6 months)
3 ( #413,317 of 2,286,123 )

How can I increase my downloads?


My notes

Sign in to use this feature