The very notion of mathematical proof is founded upon the idea that a proof is ‘routine’ to check. While it may be difficult to actually prove a mathematical theorem, a proof should allow us to verify its truth . But exactly how much effort is required to check a proof, in terms of computational complexity?…
What proof mining is about, Part I
This is the first post in a series designed to introduce a working logician to the field of proof mining (for when you’ll want to know more than this hopefully gentle introduction will provide, the standard reference is the monograph of Kohlenbach). It will mainly focus on its motivations and logico-mathematical content, with historical information…
From cut elimination to reverse mathematics
This post explains how methods from ordinal analysis can be used to prove results in reverse mathematics. It may be surprising that this is possible, given that the traditional aims of the two areas are somewhat different: reverse mathematics proves implications between different statements about infinite sets, while ordinal analysis eliminates the infinite from proofs…
Lifting proofs: from Specker sequences to nets
This post provides an answer to the question: Can we somehow ‘lift’ proofs in a restricted language to interesting proofs in a richer language?