Speaker: Russell Miller
CUNY
Will give a lecture entitled
Computability and the absolute Galois group of $\mathbb Q$
Abstract: Fix a computable presentation $\overline{\mathbb Q}$ of the algebraic closure of the field $\mathbb Q$ of rational numbers. With such a presentation, the automorphisms of $\overline{\mathbb Q}$ are naturally given as paths through a strongly computable finite-branching tree. The operations of composition and inversion on these automorphisms (i.e., on these paths) are both type-2 computable. Thus we have an effective way of considering $\text{Aut}(\overline{\mathbb Q})$, the absolute Galois group of $\mathbb Q$. In this context, one can discuss the computability of Skolem functions for $\text{Aut}(\overline{\mathbb Q})$. We show that for \emph{positive formulas} (not using the negation connective) with parameters, Skolem functions are close to computable: one can compute an approximation to the jump of a witness to an existential formula. (That is, these Skolem functions are \emph{superapproximable}, in the sense of Brattka, de Brecht, and Pauly in \cite{BdBP12}.) The same holds for Skolem functions for any $\Pi_2$ formula, positive or not, and for certain larger classes of formulas as well. However, joint work between Kundu and the speaker has shown that, even for positive existential formulas, Skolem functions are not always computable. We will describe these results and mention related results on the elementarity of countable subgroups defined by computability within $\text{Aut}(\overline{\mathbb Q})$, and also on the arithmetical complexity of subsets of $(\text{Aut}(\overline{\mathbb Q}))^n$ definable by such formulas.
Date: 04-25-2024
Time: 2:00 pm
Location: 229 Hayes-Healy Bldg