The computational content of arithmetical proofs (Q1762353)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The computational content of arithmetical proofs |
scientific article; zbMATH DE number 6110273
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The computational content of arithmetical proofs |
scientific article; zbMATH DE number 6110273 |
Statements
The computational content of arithmetical proofs (English)
0 references
23 November 2012
0 references
Natural deductions in intuitionistic arithmetic have a unique normal form. This is not true for Gentzen-style sequent derivations, especially in classical arithmetic. Using a special redundancy construction from a previous work with M. Baaz, the author proves that for a wide class of arithmetical theories \(T\) the number of possible cut-free forms of a single arithmetical derivation in \(T\) of a \(\Sigma^0_1\)-formula is not bounded by any function provably recursive in \(T\).
0 references
cut elimination
0 references
normal form
0 references
first-order arithmetic
0 references
arithmetical proofs
0 references
computational content
0 references
arithmetical theories
0 references
provably recursive function
0 references
0 references
