An arithmetical incompleteness in axiomatic arithmetic
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In 1931, Kurt Godel presented his historic proof that within any rigid logical system powerful enough to do basic arithmetic there exist statements that can neither be proved nor disproved. The statements constructed by Godel were considered unnatural, and for decades it was debated whether Godel's result applied to statements of "concrete" mathematical interest. Forty-six years later, Jeff Paris and Leo Harrington exhibited the first natural example of a statement that is true for the natural numbers, but unprovable in arithmetic. This statement was a refinement of the finite form of Ramsey's Theorem and has since come to be known as the Paris-Harrington Principle. The main argument used by Paris and Harrington involved intricate concepts from proof theory, including the inability of a theory to prove its own consistency. The authors stated that a simpler proof could be obtained using a model-theoretic approach. However, it wasn't until 2009 that Andrey Bovykin exhibited the first model-theoretic proof of the unprovability of the Paris-Harrington's Principle to appear in print. This thesis is intended as a self-contained exhibition of Bovykin's proof that should be accessible to anyone with sufficient mathematical maturity.