Brief introduction to unprovability
Andrey Bovykin · Cambridge University Press eBooks · 2009
. The article starts with a brief survey of Unprovability Theory as of summer 2006. Then, as an illustration of the subject's model-theoretic methods, we re-prove threshold versions of unprovability results for the Paris-Harrington Principle and the Kanamori-McAloon Principle using indiscernibles. In addition, we obtain a short accessible proof of unprovability of the Paris-Harrington Principle. The proof employs old ideas but uses only one colouring and directly extracts the set of indiscernibles from its homogeneous set. We also present modified, abridged statements whose unprovability proofs are especially simple. These proofs were tailored for teaching purposes. The article is intended to be accessible to the widest possible audience of mathematicians, philosophers and computer scientists as a brief survey of the subject, a guide through the literature in the field, an introduction to its model-theoretic techniques and, finally, a model-theoretic proof of a modern theorem in the subject. However, some understanding of logic is assumed on the part of the readers. The intended audience of this paper consists of logicians, logic-aware mathematicians and thinkers of other backgrounds who are interested in unprovable mathematical statements. We start with a brief survey, listing many important achievements and directions of the subject. Most of the results speak for themselves and we omit a discussion of how they are interrelated as well as the story of the subject's big questions, philosophies, goals, exciting conjectures and dreams which is presumed to be partly known to the readers. The survey is biased towards the Paris-Harrington Principle and its exact versions (understanding this topic is an excellent first step for anyone who decides to study unprovability).