Analysis and Extension of Omega-Rule - Mathematics > LogicReport as inadecuate




Analysis and Extension of Omega-Rule - Mathematics > Logic - Download this document for free, or read online. Document in PDF available to download.

Abstract: $\Omega$-rule was introduced by W. Buchholz to give an ordinal-freecut-elimination proof for a subsystem of analysis with$\Pi^{1} {1}$-comprehension. His proof provides cut-free derivations byfamiliar rules only for arithmetical sequents. When second-order quantifiersare present, they are introduced by $\Omega$-rule and some residual cuts arenot eliminated. Using an extension of $\Omega$-rule we obtain by the samemethod as W. Buchholz complete cut-elimination: any derivation of arbitrarysequent is transformed into its cut-free derivation by the standard rules withinduction replaced by $\omega$-rule.W. Buchholz used $\Omega$-rule to explain how reductions of finitederivations used by G. Takeuti for subsystems of analysis are generated bycut-elimination steps applied to derivations with $\Omega$-rule. We show thatthe same steps generate standard cut-reduction steps for infinitary derivationswith familiar standard rules for second-order quantifiers. This provides ananalysis of $\Omega$-rule in terms of standard rules and ordinal-freecut-elimination proof for the system with the standard rules for second-orderquantifiers. In fact we treat the subsystem of $\Pi^{1} {1}$-CA of the samestrength as $ID {1}$ that W. Buchholz used for his explanation of finitereductions. Extension to full $\Pi^{1} {1}$-CA is forthcoming in another paper.



Author: R. Akiyoshi, G. Mints

Source: https://arxiv.org/







Related documents