Colloquium

Speaker: Russell Miller, CUNY

Title: Computability on $\mathbb R$ and other continuum-size structures

Abstract: We begin by recalling the notion of a computable function on the real numbers $\mathbb R$, developed independently by Gregorczyk and Lacombe over sixty years ago. Using this notion, we note that the real numbers that are themselves computable form a countable subfield of $\mathbb R$ with exactly the same first-order properties as $\mathbb R$ itself. (Logicians would therefore call it an \emph{elementary subfield}.) So, in a first-order sense, everything that happens in $\mathbb R$ is already exemplified in this much nicer subfield. However, even when one knows that an existential statement holds for all parameters, it may be impossible (both in $\mathbb R$ and in the subfield) to give a computable procedure for producing witnesses. Similar results hold in $\mathbb C$.

We will then turn to a different continuum-sized structure: the absolute Galois group $\operatorname{Gal}(\mathbb Q)$ of the rational numbers. Once again the computable elements of this group form a subgroup, but now it is an open problem whether the group and the subgroup have the same first-order theory, let alone whether this is an elementary subgroup. (If they do have the same theory, this would put nice upper bounds on the complexity of the theory of $\operatorname{Gal}(\mathbb Q)$.) However, using joint work with Kundu, we can show that once again there is no computable procedure for producing witnesses to the truth of (true) existential statements, either in the full group or in the subgroup.