Computability Learning Seminar

Thursday, May 23, 2019 10:00 am - 10:00 am EDT (GMT -04:00)

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

"Degrees of Categoricity of Trees"

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)}$). These ranks are the smallest possible for realizing the corresponding degrees as degrees of categoricity.

MC 5479