## Contact Info

Pure MathematicsUniversity of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x43484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

Monday, May 13, 2019 — 10:00 AM EDT

**Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo**

"Degrees of Categoricity and the Isomorphism Problem"

In this thesis, we study notions of complexity related to computable structures. We first study degrees of categoricity for computable tree structures. We show that, for any computable ordinal $\alpha$, there exists a computable tree of rank $\alpha+1$ with strong degree of categoricity ${\bf 0}^{(2\alpha)}$ if $\alpha$ is finite, and with strong degree of categoricity ${\bf 0}^{(2\alpha+1)}$ if $\alpha$ is infinite. For a computable limit ordinal $\alpha$, we show that there is a computable tree of rank $\alpha$ with strong degree of categoricity ${\bf 0}^{(\alpha)}$ (which equals ${\bf 0}^{(2\alpha)}$).

In general, it is not the case that every Turing degree is the degree of categoricity of some structure. However, it is known that every degree c.e.\ in and above $\mathbf{0}^{(\alpha)}$, for $\alpha$ a successor ordinal, is a degree of categoricity. In this thesis, we include joint work with Csima, Deveau and Harrison-Trainor which shows that every degree c.e.\ in and above $\mathbf{0}^{(\alpha)}$, for $\alpha$ a limit ordinal, is a degree of categoricity. We also show that every degree c.e.\ in and above $\mathbf{0}^{(\omega)}$ is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.

After that, we study the isomorphism problem for tree structures. It follows from our proofs regarding the degrees of categoricity for these structures that, for every computable ordinal $\alpha>0$, the isomorphism problem for trees of rank $\alpha$ is $\Pi_{2\alpha}$-complete. We also discuss the isomorphism problem for pregeometries in which dependent elements are dense and the closure operator is relatively intrinsically computably enumerable. We show that, if $K$ is a class of such pregeometries, then the isomorphism problem for the class $K$ is $\Pi_3$-hard.

Finally, we study the Turing ordinal. We observed that the definition of the Turing ordinal has two parts each of which alone can define a specific ordinal which we call the upper and lower Turing ordinals. The Turing ordinal exists if and only if these two ordinals exist and are equal. We give examples of classes of computable structures such that the upper Turing ordinal is $\beta$ and the lower Turing ordinal is $\alpha$ for all computable ordinals $\alpha<\beta$.

MC 2009

University of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x43484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.