Proof Theory

Credits 8 credit points
Instructors Iemhoff, R. (Universiteit Utrecht), 
Prerequisites Prerequisites: bachelor in Mathematics. Familiarity with the basics of logic (language, structures, formal proofs) helps, but is not required.

Description: Proof Theory is the study of combinatorial properties of formal proofs in Logic.
As such, the subject has relations with Combinatorics and Complexity Theory.
The subject arose out of "Hilbert's Programme", an attempt to establish the consistency (that is: being free of contradictions) of ordinary mathematical reasoning, by finitary methods. First major results were obtained by Hilbert himself, Goedel, and Hilbert's assistants Paul Bernays and Gerhard Gentzen.

In this course, we aim to acquaint the students with some basic results and techniques of the field. We shall start by working through the text "An Introduction to Proof Theory" by Samuel R. Buss. After that, there is a choice of additional topics we might discuss: Proof Complexity, Proof Theory of Arithmetic, Dialectica Interpretation and No-Counterexample Interpretation, Combinatorics of finite trees.

Examination Written exam.

Literature: Required is Buss's text "An Introduction to Proof Theory"; available here. By the same author, there are the texts "First-order Proof Theory of Arithmetic" and "Propositional Proof Complexity, An Introduction". We might also make use of "A course in Proof Theory" by Herman Ruge Jervell.

Background Literature: we recommend Troelstra & Schwichtenberg, Basic Proof Theory (CUP, 2d edition1999), Girard, Proof Theory and Logical Complexity (Bibliopolis 1987) and Kohlenbach, Applied Proof Theory (Springer 2008).


For more information, please visit this website.

  Last changed: 26-02-2015 15:39