University Seminar- Computability, Complexity, and Algebraic Structure-What is the "robust" Scott rank?

Time: Wednesday, March 4, 5:00–6:00 pm

Place: Phillips Hall, Room 108

Speaker:  de Lima Souza, Paula

Title: What is the "robust" Scott rank?

Abstract: In 1965, Dana Scott showed that for every countable structure A, there is a sentence $\Phi$ in infinitary logic $\mathcal{L}_{\omega_1 \omega}$ that characterizes A up to isomorphism among countable structures. Concretely, any countable B satisfies $\Phi$, if and only if, $\mathcal{A}\cong \mathcal{B}$. This is called the Scott sentence of A. Scott's proof gives rise to a new notion, the Scott Rank: an ordinal $\alpha$ that "counts" the quantifiers of the structure's description. Ever since, many different and non-equivalent definitions of such rank have been proposed. The most robust definition was presented by Antonio Montalbán (2015). In this talk, we will define these several notions, describe to what extent they differ, and explain why the latter is considered the right definition. In addition, we will discuss whether and how these results exist in the computable setting, in particular, how one can relate the Scott sentence of a structure to computable categoricity on a cone.