O struktuře modelů omezené -indukce
On elementary cuts in models of arithmetic
On interpretability in theories containing arithmetic. II.
On the weak pigeonhole principle
We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem. We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence...
On valued function fields III. Reductions of algebraic curves.
Order-types of models of arithmetic and a connection with arithmetic saturation.