Matthew Harrison-Trainor

Contact

Victoria University of Wellington.
Office: CO 430.
Email:

Curicculum Vitae

My CV.

About Me

I am currently a post-doctoral fellow working with Rod Downey at Victoria University of Wellington and Alexander Melnikov at Massey University. Previously I was a Banting post-doctoral fellow at the University of Waterloo working with Barbara Csima.

My main interests are in computability theory, and in particular, computable structure theory. I have also published work on model theory and differential algebra, modal logic, and probability theory.

I received my PhD under the supervision of Antonio Montalbán at the University of California, Berkeley. My thesis, The Complexity of Countable Structures, received the Sacks Prize from the Asociation for Symbolic Logic for the most outstanding thesis in mathematical logic worldwide and the Herb Alexander Prize for the most outstanding thesis in mathematics at UC Berkeley.

Teaching

In Semester 1 2019 I am teaching Set Theory (Math 434).

Papers

  1. Relationships between computability-theoretic properties of problems (with Rod Downey, Noam Greenberg, Ludovic Patey, and Dan Turetsky)
    Submitted for publication. [ pdf ]

  2. The tree of tuples of a structure (with Antonio Montalbán)
    Submitted for publication. [ pdf ]

  3. Describing finitely presented algebraic structures
    Submitted for publication. [ pdf ]

  4. Some questions of uniformity in algorithmic randomness (with Laurent Bienvenu and Barbara Csima)
    Submitted for publication. [ pdf ]

  5. Graphs are not universal for online computability (with Rod Downey, Iskander Kalimullin, Alexander Melnikov, and Daniel Turetsky)
    Submitted for publication. [ pdf ]

  6. The logic of comparative cardinality (with Yifeng Ding and Wesley Holliday)
    Submitted for publication. [ pdf ]

  7. Which classes of structures are both pseudo-elementary and \(\mathcal{L}_{\omega_1 \omega}\)-elementary? (with Barbara Csima and Nancy Day)
    Submitted for publication. [ pdf ]

  8. Optimal bounds for single-source Kolmogorov extractors (with Laurent Bienvenu and Barbara Csima)
    Submitted for publication. [ pdf ]

  9. Degrees of categoricity above limit ordinals (with Barbara Csima, Michael Deveau, and Mohammad Assem Mahmoud)
    Submitted for publication. [ pdf ]

  10. Automatic and polynomial-time algebraic structures (with Nikolay Bazhenov, Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng)
    Submitted for publication. [ pdf ]

  11. A short note on constructing decidable graphs from other structures (with Nikolay Bazhenov)
    Submitted for publication. [ pdf ]

  12. Finitely generated groups are universal (with Meng-Che "Turbo" Ho)
    Submitted for publication. [ pdf ]

  13. A representation theorem for possibility models
    Submitted for publication. [ pdf ]

  14. First-order possibility models and finitary completeness proofs
    Submitted for publication. [ pdf ]

  15. Characterizations of cancellable groups (with Meng-che Ho)
    Proceedings of the AMS, to appear. [ pdf ]

  16. A first-order theory of Ulm type
    Computability, to appear. [ pdf | DOI ]

  17. Effective aspects of algorithmically random structures (with Bakh Khoussainov and Daniel Turetsky)
    Computability, to appear. [ pdf | DOI ]

  18. There is no classification of the decidably presentable structures
    Journal of Mathematical Logic, 18 (2018), no. 2. [ pdf | DOI ]

  19. Borel functors and infinitary interpretations (with Russell Miller and Antonio Montalbán).
    Journal of Symbolic Logic, 83 (2018), no. 4, 1434–1456. [ pdf ]

  20. On optimal Scott sentences of finitely generated algebraic structures (with Meng-Che "Turbo" Ho)
    Proceedings of the AMS, 146 (2018), no. 10, 4473–4485. [ pdf | DOI ]

  21. Degree spectra of relations on a cone
    Memoirs of the AMS, 253 (2018), no. 1208. [ pdf | DOI ]

  22. Computable valued fields
    Archive for Mathematical Logic, 57 (2018), no. 5–6, 473–495. [ pdf | DOI ]

  23. Scott ranks of models of a theory
    Advances in Mathematics, 330 (2018), 109–147. [ pdf | DOI ]

  24. Some new computable structures of high rank (with Gregory Igusa and Julia Knight).
    Proceedings of the AMS, 146 (2018), no. 7, 3097–3109. [ pdf | DOI ]

  25. Left-orderable computable groups
    Journal of Symbolic Logic, 83 (2018), no. 1, 237–255. [ pdf | DOI ]

  26. Inferring probability comparisons (with Wesley Holliday and Thomas Icard)
    Mathematic Social Science, 91 (2018), 62–70. [ pdf | DOI ]

  27. On computable field embeddings and difference closed fields (with Alexander Melnikov and Russell Miller).
    Canadian Journal of Mathematics, 69 (2017), no. 6, 1338–1363. [ pdf | DOI ]

  28. The Gamma question for many-one degrees
    Annals of Pure and Applied Logic, 168 (2017), no. 7, 1396–1405. [ pdf | DOI ]

  29. Preferential structures for comparative probabilistic reasoning (with Wesley Holliday and Thomas Icard).
    AAAI, (2017), 1135–1141. [ pdf | DOI ]

  30. Computable functors and effective interpretability (with Alexander Melnikov, Russell Miller, and Antonio Montalbán).
    Journal of Symbolic Logic, 82 (2017), no. 1, 77–97. [ pdf | DOI ]

  31. Degrees of categoricity on a cone via \(\eta\)-systems (with Barbara Csima)
    Journal of Symbolic Logic, 82 (2017), no. 1, 325–346. [ pdf | DOI ]

  32. A note on cancellation axioms for comparative probability (with Wesley Holliday and Thomas Icard)
    Theory and Decision, 80 (2016), no. 1, 159–166. [ pdf | DOI ]

  33. Independence in computable algebra (with Alexander Melnikov and Antonio Montalbán).
    Journal of Algebra, 443 (2015), 441–468. [ pdf | DOI ]

  34. Differential-algebraic jet spaces preserve internality to the constants (with Zoé Chatzidakis and Rahim Moosa).
    Journal of Symbolic Logic, 80 (2015), no. 3, 1022–1034. [ pdf | DOI ]

  35. Nonstandard methods for bounds in differential polynomial rings (with Rahim Moosa and Jack Klys).
    Journal of Algebra, 360 (2012), 71–86. [ pdf | DOI ]

Talks and Slides

There is no natural construction of a structure of Scott rank \(\omega_1^{CK}\).
University of Wisconsin-Madison Logic Seminar, Madison, WI. March 2018.

When is a property expressed in infinitary logic also pseudo-elementary?
Oberwolfach, Germany. January 2018.

When is a property expressed in infinitary logic also pseudo-elementary? (slides)
Notre Dame Logic Seminar, South Bend, IN. November 2017.

Scott ranks of computable structures. (slides)
New England Recursion and Definability Seminar, Wellesley, MA. October 2017.

Some computable structure theory of finitely generated structures. (slides)
Mid-Atlantic Mathematical Logic Seminar, New York, NY. October 2017.

Some computable structure theory of finitely generated structures.
Scott ranks of computable structures.
Cornell Logic Seminar, Ithaca, NY. October 2017.

Some computable structure theory of finitely generated structures. (slides)
Aspects of Computation, Singapore. May 2017.

Describing finitely generated structures.
UCLA Logic Seminar, Los Angeles, CA. May 2017.

Optimal Scott sentences for finitely generated groups.
AMS Spring Central Sectional Meeting, Bloomington, IN. April 2017.

There is no classification of the decidably presentable structures.
University of Wisconsin-Madison Logic Seminar, Madison, WI. March 2017.

Some results on characterizing structures using infinitary formulas. (slides)
ASL North American Annual Meeting, Boise, ID. March 2017.

Extending automorphisms of normal algebraic fields. (slides)
AMS Spring Southeastern Sectional Meeting, Charleston, SC. March 2017.

Optimal Scott sentences for finitely generated groups.
Southeastern Logic Symposium, Gainesville, FL. March 2017.

Computable structures of high Scott rank. (slides)
Workshop on Computability, Ghent, Belgium. July 2016.

Borel functors and interpretations. (slides)
Computability in Europe, Paris, France. June 2016.

Scott ranks of models of a theory. (slides)
ASL North American Annual Meeting, Storrs, CT. May 2016.

Scott ranks of models of a theory.
CUNY Model Theory Seminar, New York, NY. December 2015.

Differential-algebraic jet spaces and internality.
Kolchin Seminar in Differential Algebra, New York, NY. December 2015.

Scott ranks of models of a theory.
Notre Dame Logic Seminar, South Bend, IN. September 2015.

First-order possibility models and worldizations. (slides)
CSLI Workshop on Logic, Rationality, and Intelligent Interaction, Stanford, CA. May 2015.

Computable structures on a cone. (slides)
Sets and Computations, Singapore. April 2015.

Computable categoricity on a cone. (slides)
ASL North American Annual Meeting, Urbana-Champaign, IL. March 2015.

Computable functors and effective interpretability. (slides)
AMS Sectional Meeting, Georgetown, DC. March 2015.

Independence in computable algebra. (slides)
CMS Annual Meeting, Hamilton, Canada. Dec 2014.

Degree spectra of relations on a cone. (slides)
ASL Logic Colloquium, Vienna, Austria. July 2014.

Degree spectra of relations on a cone..
ASL North American Annual Meeting, Boulder, CO. May 2014.

Degree spectra of relations on a cone..
Graduate Student Conference in Logic, Madison, WI. April 2014.

Jet spaces are C-Moishezon.
McMaster Model Theory Seminar, Hamilton, Canada. November 2011.

Non-standard methods for bounds in differential polynomial rings.
Kolchin Seminar in Differential Algebra, New York, NY. October 2011.