skip to content

$On \forall\Sigma_1^b$ sentences provable in bounded arithmetic

Presented by: 
P Pudlak [Academy of Sciences, Prague]
Monday 10th April 2006 - 10:00 to 11:00
INI Seminar Room 1

We shall give a characterization of \forall\Sigma_1^b sentences provable in theories S_2^i. We shall consider also certain unrestricted versions of the principles that characterize these sentences and prove that they require iterated exponential time. This gives partial evidence that the hierarchy of \forall\Sigma_1^b sentences provable in S_2^i is strictly increasing.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons