University Seminar- Computability, Complexity, and Algebraic Structure- Why doesn’t Chevalley’s theorem solve the halting problem?

Time: Friday, January 24, 2:30 – 3:30pm

Place: Phillips Hall, Room 209

Speaker:  Henry Klatt, GWU

Title: Why doesn’t Chevalley’s theorem solve the halting problem?

Abstract:  A subset of a topological space is called constructible if it is the finite Boolean combination of open sets.  That is, the set can be expressed as the finite union and intersection of open and closed sets.  Chevalley’s theorem for schemes states that the image of a constructible set under a finitely presented morphism of schemes is itself a constructible set.  This generalizes, among other things, the result of Tarski that the theory of algebraically closed fields of characteristic 0 admits quantifier elimination.  One might naively expect that the result generalizes to arbitrary rings.  This, however, would contradict a century of mathematical logic: Turing’s negative result to the halting problem, the MRDP theorem, Tarski’s undefinability of truth, and Goedel’s incompleteness theorems, would all be falsified, to name a few.  Fortunately for mathematicians’ world, this misunderstanding is due to key structural differences between affine space over algebraically closed fields, and the integers.  In this talk, we dip our toes just far enough into the world of affine schemes to assure ourselves that mathematical logic is not built upon a massive contradiction.