Efficient and Natural Proof Systems

Math is growing more complex each day, to the point that the assistance of computers is becoming necessary even for the most theoretically inclined among the mathematicians (see this recent article by Natalie Wolchover on Wired: http://is.gd/Qf2qpd ). After centuries of producing proofs in our heads and then describing them in papers, we are moving fast towards a future of proofs conceived by humans together with computers, which in turn will guarantee their correctness and availability.

But what is a proof? What could a common language between humans and computers be? A satisfying definition of mathematical proof has proved to be a very elusive concept. Suffice to say that the problem of deciding whether two formal proofs are the same has remained open since Hilbert formulated it more than one hundred years ago.

Finding efficient and natural proof systems is a fascinating problem that spans from philosophy, through math, to computer science. There is growing evidence that, at its core, good solutions can be provided by geometrical ideas. Indeed, many mathematicians interested in the foundations of mathematics have recently turned to geometry.

We propose a PhD in the context of the EPSRC project `Efficient and Natural Proof Systems´ (see at http://is.gd/7XYPbt ). In this project, we will define a new proof system which, essentially, will represent proofs as geometric shapes equivalent under continuous deformation. Three areas of mathematics and theoretical computer science concur in the definition of these proof systems: categorical semantics, proof theory and proof complexity. The result of this project will be the completion of three decades of efforts in proof theory that started with linear logic and continued with deep inference (see http://is.gd/leM81c [beware, there are jokes in that page]).