Graduate Student Seminar-Index sets for structures

Date and Time: Tuesday, March 29, 1-2pm

Place: Zoom
Zoom link:https://gwu-edu.zoom.us/j/92957649236?pwd=YmZIYytSUVVwcU1RdjZHYkNFak10U…

Speaker:  Dario Verta, GWU

Title: Index sets for structures

Abstract: We are interested in the computability-theoretic complexity of determining whether an algebraic structure has a certain property, relative to the algorithmic description that presents a structure. We study computable magmas, i.e., those structures that can be presented in terms of a computable domain with a computable binary operation. We establish that certain properties (such as Markov properties) are hard in a given class of computable structures. In particular, we show some examples of Markov properties at various levels of the arithmetical hierarchy and some involving more than one property.