scientific article; zbMATH DE number 440485
The (first) finitisation principle considered in the paper says, roughly, that if \(\Theta(X)\) is a first order property with an infinite model, then there is a model \((M,{\mathcal X})\) of the second order weak fragment of arithmetic \(T^ 1_ 2(\alpha)\) such that \((M,A)\models\Theta(A)\), for some \(A\in{\mathcal X}\). The result is obtained by taking a representation of an infinite model of \(\Theta(X)\) of the form \(({\mathbf N},B)\), where \({\mathbf N}\) are the standard integers, taking a proper elementary extension \(({\mathbf N},B)\prec (M,C)\), and then mapping \((M,C)\) onto a nonstandard initial segment using a generic map. The main part of the proof concerns the amount of induction that holds in models constructed in this manner. The result is used to show that the inclusions \(T^ 1_ 2(\alpha)\subset S^ 2_ 2(\alpha)\subset T^ 2_ 2(\alpha)\) are proper -- the result proved earlier using different techniques by \textit{J. Krajiček}, \textit{P. Pudlak} and \textit{G. Takeuti} [Ann. Pure Appl. Logic 52, No. 1/2, 143-153 (1991; Zbl 0736.03022)]. Another finitisation principle, and interesting examples of second order statements not provable in \(S^ 2_ 2(\alpha)\) are also given. For the entire collection see [Zbl 0777.00008].
- Independence results for variants of sharply bounded induction
- An independence result on weak second order bounded arithmetic
- Bounded arithmetic and the polynomial hierarchy
- A constructive consistency proof of a fragment of set theory
- scientific article; zbMATH DE number 4043837
- TRACE EXPANSIONS OF INITIAL SEGMENTS
- On induction-free provability
- Separations of first and second order theories in bounded arithmetic
- Weakly compact cardinals in models of set theory
- Regular cuts in models of bounded arithmetic
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
- Circuit principles and weak pigeonhole variants
- Structures interpretable in models of bounded arithmetic
- Typical forcings, NP search problems and an extension of a theorem of Riis
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140642)