University Seminar- Computability, Complexity, and Algebraic Structure- Index sets in computable algebra

Time: Wednesday, April 15, 5:00–6:00 pm

Place: Phillips Hall, Room 108

Speaker: Jake Rhody, GWU

Title: Index sets in computable algebra

Abstract:  Many important properties of algebraic structures are definable, even in the first-order language, and there is a deep connection between definability and computability. This makes the index set problems a topic of study in computable algebra. Simply put, classifying the complexity of index sets for definable properties answers the question “what is the minimal number of quantifier alternations of formulas that can define a given property?” In this talk, we will provide a first-order definition of commutative semisimple rings (rings that are finite direct sums of fields). We will then prove that there is no first-order definition of a lower complexity.