Logic Seminar-Index sets for structures

Time: Thursday, March 24, 11:00 am-12:00 noon

Place: zoom
https://gwu-edu.zoom.us/j/98191073403

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.