Kurt Gödel Research Center

2017 seminar talk: Isomorphism and Classification for Countable Structures

Talk held by Russell Miller (Queens College, City University of New York (CUNY), USA) at the KGRC seminar on 2017-11-23.

Abstract

We describe methods of classifying the elements of certain classes of countable structures: algebraic fields, finite-branching trees, and torsion-free abelian groups of rank 1. The classifications are computable homeomorphisms onto known spaces of size continuum, such as Cantor space or Baire space, possibly modulo a standard equivalence relation. The classes involved have arithmetic isomorphism problems, making such classifications possible, and the results help suggest exactly which properties of their elements must be known in order to produce a nice classification.

For algebraic fields, this homeomorphism makes it natural to transfer Lebesgue measure from Cantor space onto the class of these fields, although there is another probability measure on the same class which seems in some ways more natural than Lebesgue measure. We will discuss how certain properties of these fields — notably, relative computable categoricity — interact with these measures: the basic result is that only measure-0-many of these fields fail to be relatively computably categorical. (The work on computable categoricity is joint with Johanna Franklin.)