Syllabus for P. Pudlak's lectures at the
Godel's theorem holds for very weak theories, in particular, for fragments of Bounded Arithmetic. However, the statement that a theory T is consistent is very strong even for a fairly weak T. For example, the consistency of Robinson's arithmetic Q, which has no induction axioms at all, is not provable in Bounded Arithmetic. For strong theories the usual method of proving that a theory T is stronger than a theory S is to prove "S is consistent" in T. For the aforementioned reason this fails for fragments of Bounded Arithmetic. Therefore, restricted versions of the consistency statements have been studied. But it seems that without understanding the combinatorial substance of these sentences we cannot use them for separating fragments of Bounded Arithmetic.
Fall school(Sept.'03)
Godel's theorem in Bounded Arithmetic
The separation problem for fragments of Bounded Arithmetic is a proof-theoretical analog of the separation problem for complexity classes in computational complexity theory. Godel's theorem seems to correspond to the diagonal method of separating complexity classes. Since no formal relation is known, it is conceivable that the diagonal method may work in one setting while not in the other.