Degrees of Categorictiy of Trees of finite rank
Speaker:
Mohammad Mahmoud, University of Waterloo
Date and Time:
Friday, June 8, 2018 - 11:30am to 11:50am
Location:
University of Waterloo - MC 5501
Abstract:
For any natural number $n\geq 0$, it is easy to see that any computable tree of rank $n+1$ is ${\bf 0}^{(2n)}$-categorical. We show that ${\bf 0}^{(2n)}$ is the strong degree of categoricity for some computable tree of rank $n+1$. Our work also shows that the isomorphism problem for the class of trees of rank $n$, $n\geq 1$, is $\Pi^0_{2n}$-complete. The isomorphism problem for the class of trees of finite rank turns out to be interesting.