Logic Seminar

Title: Complexity of relations and the arithmetical hierarchy

Speaker: Leah Marshall, George Washington University

Abstract: One way of examining computability-theoretic complexity of various natural properties (relations) of computable structures is to examine the complexity of the formulas that define the properties. In this talk, we will discuss some examples of the arithmetical complexity of various objects, pulling from the more standard and classic examples, as well as describing some examples from current research. We will review arithmetical hierarchy. The talk will be accessible to all graduate students.