Contact Info
Pure MathematicsUniversity of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada
N2L 3G1
Departmental office: MC 5304
Phone: 519 888 4567 x33484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
Visit our COVID19 information website to learn how Warriors protect Warriors.
Please note: The University of Waterloo is closed for all events until further notice.
Michael Deveau, Department of Pure Mathematics, University of Waterloo
"Computability Theory and Some Applications"
In this thesis, we explore various areas of computability theory, ranging from applications in computable structure theory primarily focused on problems about computing isomorphisms, to a number of new results regarding the degreetheoretic notion of the bounded Turing hierarchy.
First, in joint work with Csima, HarrisonTrainor and Mahmoud, the set of degrees that are computably enumerable in and above $\mathbf{0}^{(\alpha)}$ are shown to be degrees of categoricity of a structure, where $\alpha$ is a computable limit ordinal. By restricting the construction to a particular case, we are able to produce a computable prime model with a degree of categoricity as high as is possible. This then shows that a particular upper bound on such degrees is exact.
Second, in joint work with Csima and Stephenson, a common trick in computable structure theory as it relates to degrees of categoricity is explored. In this trick, the degree of an isomorphism between computable copies of a rigid structure is often able to be witnessed by the clever choice of a computable set whose image or preimage through the isomorphism actually attains the degree of the isomorphism itself. We construct a pair of computable copies of $(\omega, <)$ where this trick will not work, examine some problems with decidability of the structures and work with $(\omega^2, <)$ to resolve them by proving a similar result.
Next, the effectivization of Walker's Cancellation Theorem in group theory is discussed in the context of uniformity. That is, if we have an indexed collection of instances of sums of finitely generated abelian groups $A_i \oplus G_i \cong A_i \oplus H_i$ and the code for the isomorphism between them, then we wish to know to what extent we can give a single procedure that, given an index $i$, produces an isomorphism between $G_i$ and $H_i$.
Finally, several results pertaining to the bounded Turing degrees (also known as the weak truthtable degrees) and the bounded jump are investigated. We investigate some open problems related to lowness and highness as it appears in this realm, and then generalize a characterization about reductions to iterated bounded jumps of arbitrary sets. We use this result to prove the nontriviality of the hierarchy of successive applications of the bounded jump above any set.
MC 5403
S  M  T  W  T  F  S 

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

13

14

15


16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

Departmental office: MC 5304
Phone: 519 888 4567 x33484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
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 Indigenous Initiatives Office.