Mathematical logic seminar – April 10, 2012
Time: 12:00 – 13:20
Room: Wean Hall 7201
Speaker: Stefan Hetzl
Institute of Discrete Mathematics and Geometry
Vienna University of Technology
Title: Which proofs can be computed by cut-elimination?
In classical logic, it is typically possible to compute significantly different cut-free proofs from a single proof with cuts using a non-deterministic algorithm like Gentzen’s procedure based on local proof rewriting steps. I will first speak about results that support this point by relating the number of cut-free proofs thus obtainable to the functions provably total in the system under consideration. Then I will turn towards recent work on characterising the cut-free proofs induced by a given proof with cuts.