**Student Mathematical Library**

Volume: 88;
2019;
239 pp;
Softcover

MSC: Primary 11; 12;

**Print ISBN: 978-1-4704-4399-3
Product Code: STML/88**

List Price: $55.00

Individual Price: $44.00

MAA Member Price: $44.00

**Electronic ISBN: 978-1-4704-5261-2
Product Code: STML/88.E**

List Price: $55.00

Individual Price: $44.00

MAA Member Price: $44.00

#### Supplemental Materials

# Hilbert’s Tenth Problem: An Introduction to Logic, Number Theory, and Computability

Share this page
*M. Ram Murty; Brandon Fodden*

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 image by Jesse Jacobs.

#### Readership

Undergraduate and graduate students and researchers interested in number theory and logic.

#### Table of Contents

# Table of Contents

## Hilbert's Tenth Problem: An Introduction to Logic, Number Theory, and Computability

- Cover Cover11
- Title page iii4
- Preface xi12
- Acknowledgments xiii14
- Introduction 116
- Chapter 1. Cantor and Infinity 520
- Chapter 2. Axiomatic Set Theory 2338
- Chapter 3. Elementary Number Theory 4156
- Chapter 4. Computability and Provability 7186
- Chapter 5. Hilbert’s Tenth Problem 123138
- 5.1. Diophantine Sets and Functions 123138
- 5.2. The Brahmagupta–Pell Equation Revisited 131146
- 5.3. The Exponential Function Is Diophantine 137152
- 5.4. More Diophantine Functions 144159
- 5.5. The Bounded Universal Quantifier 149164
- 5.6. Recursive Functions Revisited 155170
- 5.7. Solution of Hilbert’s Tenth Problem 159174
- Further Reading 164179
- Exercises 165180

- Chapter 6. Applications of Hilbert’s Tenth Problem 167182
- Chapter 7. Hilbert’s Tenth Problem over Number Fields 201216
- Appendix A. Background Material 223238
- Bibliography 229244
- Index 233248
- Back Cover Back Cover1256