Monographs
Yong Cheng. Incompleteness for Higher-Order Arithmetic: An Example Based on Harrington's Principle. SpringerBriefs in Mathematics, Springer, 2019.
About this book
Gödel's true-but-unprovable sentence from the first incompleteness theorem is purely logical in nature, i.e. not mathematically natural or interesting. An interesting problem is to find mathematically natural and interesting statements that are similarly unprovable. A lot of research has since been done in this direction, most notably by Harvey Friedman. A lot of examples of concrete incompleteness with real mathematical content have been found to date. This brief contributes to Harvey Friedman's research program on concrete incompleteness for higher-order arithmetic and gives a specific example of concrete mathematical theorems which is expressible in second-order arithmetic but the minimal system in higher-order arithmetic to prove it is fourth-order arithmetic. This book first examines the following foundational question: are all theorems in classic mathematics expressible in second-order arithmetic provable in second-order arithmetic? The author gives a counterexample for this question and isolates this counterexample from the Martin-Harrington Theorem in set theory. It shows that the statement “Harrington's principle implies zero sharp" is not provable in second-order arithmetic. This book further examines what is the minimal system in higher-order arithmetic to prove the theorem “Harrington's principle implies zero sharp" and shows that it is neither provable in second-order arithmetic or third-order arithmetic, but provable in fourth-order arithmetic. The book also examines the large cardinal strength of Harrington's principle and its strengthening over second-order arithmetic and third-order arithmetic.
Yong Cheng. The Landscape of Arithmetical Incompleteness: Gödel's Incompleteness Theorems and Their Limits. Forthcoming in the Synthese Library series, Springer, 2027.
About this book
This monograph offers a systematic map of arithmetical incompleteness and its boundary, one approached from logical, foundational, and philosophical perspectives. Nearly a century after Gödel's discovery, the literature remains organized around the classical theorems themselves---their proofs, their consequences, and their philosophical interpretation---while the limitative side of the phenomenon has been treated piecemeal. Drawing on more than two decades of research on arithmetical incompleteness, the book is not another introduction to the proofs of Gödel's theorems: it asks how far those theorems reach, how the phenomenon they describe can be classified, and where its limits lie.
Its organizing thesis is that arithmetical incompleteness is not a linear property fixed by a single threshold of expressive strength, but a multi-dimensional, abstractly limitless, and intensional phenomenon that is at the same time philosophically rich. The book develops this picture through five interconnected themes: a taxonomy of proofs, from proof-theoretic and recursion-theoretic arguments to concrete-combinatorial ones; a systematic taxonomy of the metamathematical properties that certify incompleteness, the implication relations among which form a partial order with incomparable elements rather than a linear hierarchy; the limits of the first incompleteness theorem, culminating in the result that with respect to interpretability the class of effectively inseparable---equivalently, effectively incomplete---theories has no minimal elements, so that effective incompleteness has no logical atom; and the limits of the second incompleteness theorem, including a systematic analysis of its intensionality. The fifth theme is a sustained philosophical reflection on the depth of Gödel's theorems, on mechanism, on arithmetical truth, and on arithmetical pluralism, closing with the proposal that different perspectives on incompleteness lead to different conclusions about its limits, and that, from the metamathematical perspective adopted here, those limits are normative rather than purely logical---shaped by the domain of theories we admit and by the representational demands we impose on consistency statements.
The treatment is self-contained, presupposing only first-order logic and the elements of computability theory, and parts of it can serve as the basis for a graduate course. It will be of interest to logicians, to philosophers of mathematics and logic, and to advanced students concerned with the incompleteness theorems and with their logical, foundational, and philosophical significance.