Matthew Harrison-Trainor

Contact

Victoria University of Wellington.
Office: CO 430.

Massey University Albany.
Office: The Institute of Natural and Mathematical Sciences.

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.

Papers

  1. Computing sets from all infinite subsets (with Noam Greenberg, Ludovic Patey, and Dan Turetsky)
    Submitted for publication. [ pdf ]

  2. Enumerations of families closed under finite differences (with Noam Greenberg, Joe Miller, and Dan Turetsky)
    Submitted for publication. [ pdf ]

  3. Non-density in punctual computability (with Noam Greenberg, Alexander Melnikov, and Dan Turetsky)
    Submitted for publication. [ pdf ]

  4. Computability up to homeomorphism (with Alexander Melnikov and Keng Meng Ng)
    Submitted for publication. [ pdf ]

  5. Relativizing computable categoricity (with Rod Downey and Alexander Melnikov)
    Submitted for publication. [ pdf ]

  6. The property “arithmetic-is-recursive” on a cone (with Uri Andrews and Noah Schweber)
    Submitted for publication. [ pdf ]

  7. Scott complexity of countable structures (with Rachel Alvir, Noam Grenberg, and Dan Turetsky)
    Submitted for publication. [ pdf ]

  8. There is a no simple characterization of the relatively decidable theories
    Submitted for publication. [ pdf ]

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

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

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

  12. 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 ]

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

  14. Finitely generated groups are universal (with Meng-Che "Turbo" Ho)
    Annals of Pure and Applied Logic, to appear. [ pdf | DOI ]

  15. The tree of tuples of a structure (with Antonio Montalbán)
    Journal of Symbolic Logic, to appear. [ pdf ]

  16. The logic of comparative cardinality (with Yifeng Ding and Wesley Holliday)
    Journal of Symbolic Logic, to appear. [ pdf ]

  17. Graphs are not universal for online computability (with Rod Downey, Iskander Kalimullin, Alexander Melnikov, and Daniel Turetsky)
    Journal of Computing and Systems Sciences, 112 (2020), 1–12. [ pdf | DOI ]

  18. Degrees of categoricity above limit ordinals (with Barbara Csima, Michael Deveau, and Mohammad Assem Mahmoud)
    Computability, 9 (2020), no. 2, 127–137. [ pdf | DOI ]

  19. Optimal bounds for single-source Kolmogorov extractors (with Laurent Bienvenu and Barbara Csima)
    Transactions of the AMS, 373 (2020), no. 3, 1983–2006. [ pdf | DOI ]

  20. First-order possibility models and finitary completeness proofs
    Review of Symbolic Logic, 12 (2019), no. 4, 637–662. [ pdf | DOI ]

  21. Automatic and polynomial-time algebraic structures (with Nikolay Bazhenov, Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng)
    Journal of Symbolic Logic, 84 (2019), no. 4, 1630–1669. [ pdf | DOI ]

  22. Constructing decidable graphs from decidable structures(with Nikolay Bazhenov)
    Algebra and Logic, 58 (2019), no. 5, 369–382. [ pdf | DOI ]

  23. Characterizations of cancellable groups (with Meng-che Ho)
    Proceedings of the AMS, 147 (2019), no. 8, 3533–3545. [ pdf | DOI ]

  24. Effective aspects of algorithmically random structures (with Bakh Khoussainov and Daniel Turetsky)
    Computability, 8 (2019), no. 3-4, 359–375. [ pdf | DOI ]

  25. A first-order theory of Ulm type
    Computability, 8 (2019), no. 3-4, 347–358. [ pdf | DOI ]

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

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

  28. 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 ]

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

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

  31. 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 ]

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

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

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

  35. 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 ]

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

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

  38. 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 ]

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

  40. 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 ]

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

  42. 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 ]

  43. 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

The tree of tuples of a structure.
Computability Theory and Applications Online Seminar. May 2020

Introreducibility.
Berkeley Computability Seminar, Berkeley, CA. October 2019.

Introreducibility.
University of Waterloo Logic Seminar, Waterloo, Canada. October 2019.

Describing countable structures. (slides)
Logic Colloquium, Prague, Czech Republic. August 2019.

The complexity of classifications and descriptions. (slides)
Maltsev Meeting, Novosibirsk, Russia. August 2018.

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.