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

Archive for Mathematical Logic 59 (5-6):715-731 (2020)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 92,168

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

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. 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.
Comparing Computational Power.Udi Boker & Nachum Dershowitz - 2006 - Logic Journal of the IGPL 14 (5):633-647.


Added to PP

14 (#993,927)

6 months
3 (#982,484)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Transfinite recursive progressions of axiomatic theories.Solomon Feferman - 1962 - Journal of Symbolic Logic 27 (3):259-316.
Transfinite Recursive Progressions of Axiomatic Theories.Solomon Feferman - 1967 - Journal of Symbolic Logic 32 (4):530-531.
Notation systems for infinitary derivations.Wilfried Buchholz - 1991 - Archive for Mathematical Logic 30 (5-6):277-296.
Transfinite Progressions: A Second Look At Completeness.Torkel Franzén - 2004 - Bulletin of Symbolic Logic 10 (3):367-389.

View all 6 references / Add more references