Hilbert's Tenth Problem: An Introduction to Logic, Number Theory, and Computability (Student Mathematical Library) (Student Mathematical Library, 88)

Hilbert's tenth problem is one of 23 problems proposed by David Hilbert in 1900 at the International Congress of Mathematicians in Paris. These problems gave focus for the exponential development of mathematical thought over the following century. The tenth problem asked for a general algorithm to determine if a given Diophantine equation has a solution in integers. It was finally resolved in a series of papers written by Julia Robinson, Martin Davis, Hilary Putnam, and finally Yuri Matiyasevich in 1970. They showed that no such algorithm exists. This book is an exposition of this remarkable achievement. Often, the solution to a famous problem involves formidable background. Surprisingly, the solution of Hilbert's tenth problem does not. What is needed is only some elementary number theory and rudimentary logic. In this book, the authors present the complete proof along with the romantic history that goes with it. Along the way, the reader is introduced to Cantor's transfinite numbers, axiomatic set theory, Turing machines, and Gödel's incompleteness theorems. Copious exercises are included at the end of each chapter to guide the student gently on this ascent. For the advanced student, the final chapter highlights recent developments and suggests future directions. The book is suitable for undergraduates and graduate students. It is essentially self-contained. Cover Title page Contents Preface Acknowledgments Introduction Chapter 1. Cantor and Infinity 1.1. Countable Sets 1.2. Uncountable Sets 1.3. The Schröder–Bernstein Theorem Exercises Chapter 2. Axiomatic Set Theory 2.1. The Axioms 2.2. Ordinal Numbers and Well Orderings 2.3. Cardinal Numbers and Cardinal Arithmetic Further Reading Exercises Chapter 3. Elementary Number Theory 3.1. Divisibility 3.2. The Sum of Two Squares 3.3. The Sum of Four Squares 3.4. The Brahmagupta–Pell Equation Further Reading Exercises Chapter 4. Computability and Provability 4.1. Turing Machines 4.2. Recursive Functions 4.3. Gödel’s Completeness Theorems 4.4. Gödel’s Incompleteness Theorems 4.5. Goodstein’s Theorem Further Reading Exercises Chapter 5. Hilbert’s Tenth Problem 5.1. Diophantine Sets and Functions 5.2. The Brahmagupta–Pell Equation Revisited 5.3. The Exponential Function Is Diophantine 5.4. More Diophantine Functions 5.5. The Bounded Universal Quantifier 5.6. Recursive Functions Revisited 5.7. Solution of Hilbert’s Tenth Problem Further Reading Exercises Chapter 6. Applications of Hilbert’s Tenth Problem 6.1. Related Problems 6.2. A Prime Representing Polynomial 6.3. Goldbach’s Conjecture and the Riemann Hypothesis 6.4. The Consistency of Axiomatized Theories Exercises Chapter 7. Hilbert’s Tenth Problem over Number Fields 7.1. Background on Algebraic Number Theory 7.2. Introduction to Zeta Functions and L-functions 7.3. A Brief Overview of Elliptic Curves and Their L-functions 7.4. Nonvanishing of L-functions and Hilbert’s Problem Exercises Appendix A. Background Material Bibliography Index Back Cover Hilbert's tenth problem is one of 23 problems proposed by David Hilbert in 1900 at the International Congress of Mathematicians in Paris. These problems gave focus for the exponential development of mathematical thought over the following century. The tenth problem asked for a general algorithm to determine if a given Diophantine equation has a solution in integers. It was finally resolved in a series of papers written by Julia Robinson, Martin Davis, Hilary Putnam, and finally Yuri Matiyasevich in 1970. They showed that no such algorithm exists. This book is an exposition of this remarkable achievement. Often, the solution to a famous problem involves formidable background. Surprisingly, the solution of Hilbert's tenth problem does not. What is needed is only some elementary number theory and rudimentary logic. In this book, the authors present the complete proof along with the romantic history that goes with it. Along the way, the reader is introduced to Cantor's transfinite numbers, axiomatic set theory, Turing machines, and Godel's incompleteness theorems. Copious exercises are included at the end of each chapter to guide the student gently on this ascent. For the advanced student, the final chapter highlights recent developments and suggests future directions. The book is suitable for undergraduates and graduate students. It is essentially self-contained