Undecidability in Number Theory
In these lecture notes we give sketches of classical undecidability results in number theory, like Gödel’s first Incompleteness Theorem (that the first order theory of the integers in the language of rings is undecidable), Julia Robinson’s extensions of t
- PDF / 477,263 Bytes
- 37 Pages / 439.36 x 666.15 pts Page_size
- 117 Downloads / 215 Views
1 Introduction These lectures are variations on a theme that is faintly echoed in the following loosely connected counterpointing pairs: Euclid geometry decidability Tarski Hilbert
versus versus versus versus versus
Diophantos arithmetic undecidability Gödel Matiyasevich
Let me explain how. With his Elements which in the Middle Ages was the most popular ‘book’ after the Bible, Euclid laid a foundation for modern mathematics already around 300 BC. He introduced the axiomatic method according to which every mathematical statement has to be deduced from (very few) first principles (axioms) that have to be so evident that no further justification is required. The paradigm for this is Euclidean geometry. It wasn’t quite so easy for arithmetic (for good reasons as we know now). In the third century AD, Diophantos of Alexandria, often considered the greatest (if not only) algebraist of antique times, tackled what we call today diophantine equations, that is, polynomial equations over the integers, to be solved in integers. Diophantos was the first to use symbols for unknowns, for differences and for powers; in short, he invented the polynomial. He was the first to do arithmetic in its own right, not just embedded into geometry (like, e.g., Pythagorean triples). The goal was to find a systematic method, a procedure, an algorithm by which such diophantine equations
J. Koenigsmann () Mathematical Institute, Radcliff Observatory Quarter, Oxford OX2 6GG, UK e-mail: [email protected] L. van den Dries et al., Model Theory in Algebra, Analysis and Arithmetic, Lecture Notes in Mathematics 2111, DOI 10.1007/978-3-642-54936-6__5, © Springer-Verlag Berlin Heidelberg 2014
159
160
J. Koenigsmann
could be solved (like the well known formulas for quadratic equations). One of the oldest, very efficient such algorithm is the Euclidean (!) algorithm for finding the greatest common divisor gcd.a; b/ for two integers a; b. This is a diophantine problem: for any integers a; b; c, 8 < the three diophantine equations c D gcd.a; b/ , cu D a; cv D b and c D ax C by : are solvable (for even more surprising examples of mathematical problems that are diophantine problems ‘in disguise’, see Sect. 4.4). In his 10th problem from the famous list of 23 problems presented to the Congress of Mathematicians in Paris in 1900, David Hilbert, rather than asking for an algorithm to produce solutions to diophantine equations, asked for a more modest algorithm that decides whether or not a given diophantine equation has a solution. In modern logic terminology, such an algorithm would mean that the existential 1st-order theory of Z (in the language of rings, Lring WD fC; I 0; 1g) would be decidable (cf. Sect. 4.1). It would have been even more challenging—and quite in Hilbert’s spirit—to show that the full 1st-order theory of Z, often simply called arithmetic, would be decidable. However, in 1931, Gödel showed in the first of his two Incompleteness Theorems that this is not the case: no algorithm can answer every arithmetic YES/NO-question corre
Data Loading...
