Automatic structures among computable structures

The project "Automatic structures among computable structures" is supported by the Elise Richter program of the Austrian Science Fund FWF under the number V 206.

Summary

The main directions of research for this project were:

  • the complexity of isomorphisms between copies of a structure, including questions about categoricity degrees and spectra, for computable copies and n-decidable copies;
  • the complexity of descriptions of various properties of computable structures and equivalence relations on computable structures;
  • existence of effectively given presentations satisfying structural restrictions given by an equivalence relation.

More precisely, we got the following results.

  • For a computable structure M, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of M. If the spectrum has a least degree, this degree is called the degree of categoricity of M. We investigated spectra of categoricity for computable rigid structures. In particular, we gave examples of rigid structures without degrees of categoricity.
  • We presented an example of a computable Fraïsse limit that is computably categorical but not relatively computably categorical. We also presented examples of \Delta^0_2 categorical but not relatively \Delta^0_2 categorical structures in natural classes such as trees of finite and infinite heights, abelian p-groups, and homogenous completely decomposable abelian groups. It is known that for structures from these classes computable categoricity and relative computable categoricity coincide. Furthermore, we computed degrees of categoricity for relatively \Delta^0_3 categorical Boolean algebras and relatively \Delta^0_2 categorical abelian p-groups.
  • We call a structure categorical relative to n-decidable presentations (or autostable relative to n-constructivizations) if any two n-decidable copies of A- are computably isomorphic. For n=0, we get the classical definition of a computably categorical (autostable) structure. We studied the complexity of index sets of structures that are n-decidable and categorical relative to m-decidable presentations, for various m,n\geq 0. If m\geq n\geq 0, then the index set is \Pi^1_1- complete, i.e., there is no nice description of the class of structures that are n-decidable, categorical relative to m-decidable presentations, for m\geq n\geq 0. In the case m = n-1\geq 0, the index set is \Sigma_0^4 complete, while if 0 \geq m \geq n-2, the index set is \Sigma_0^3 complete.
  • Let E,F be equivalence relations on N. We say that E is computably reducible to F, written E \leq F, if there is a computable function p: N \rightarrow N such that xEy \leftrightarrow p(x)Fp(y). We showed that several natural \Sigma_0^3 equivalence relations are in fact \Sigma_0^3 complete for this reducibility. Firstly, we showed that one-one equivalence of computably enumerable sets, as an equivalence relation on indices, was \Sigma_0^3 complete. Thereafter, we showed that this equivalence relation was below the computable isomorphism relation on computable structures from classes including predecessor trees, Boolean algebras, and metric spaces. This established the \Sigma_0^3 completeness of these isomorphism relations.
  • Let E be a computably enumerable (c.e.) equivalence relation on the set of natural numbers. We say that the relation E realizes a linearly ordered set L if there exists a c.e. order relation respecting E such that the induced quotient structure is isomorphic to L. We studied the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. We also studied the partially ordered set of lo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo-degrees.
  • We made some contribution to the computable structure theory in the setting of \omega_1. We proved that the isomorphism of computable structures lies on top among \Sigma^1_1 equivalence relations on \omega_1. In the standard setting, \Sigma^1_1 sets are characterized in terms of paths through trees. In the setting of \omega_1, we used a new characterization of \Sigma^1_1 sets that involves clubs in \omega_1. We also presented some new results about \omega_1-computable categoricity for fields.

List of publications supported by the project

  • E. Fokina, B. Khoussainov, P. Semukhin and D. Turetsky. Linear orders realized by c.e. equivalence relations, J. Symb. Logic, 81 (2016), 463-482, pdf
  • E. Fokina, A. Frolov, I. Kalimullin. Categoricity spectra for rigid structures, Notre Dame J. Formal Logic, 57 (2016), 45–57. pdf
  • E. Fokina, S. Goncharov, V. Harizanov, O. Kudinov, and D. Turetsky. Index sets for n-decidable structures categorical relative to m-decidable presentations, Algebra Logic, 54 (2015), 520-528 (in Russian), 336-341 (English translation). pdf
  • E. Fokina, S. Friedman, J. Knight, and R. Miller. Classes of structures with universe a subset of \omega_1, J. Logic Computation. 23 (2013) 6 1249–1265. pdf
  • E. Fokina, S. D. Friedman and A. Nies. Equivalence relations that are \Sigma_0^3 complete for computable reducibility, Lecture Notes in Computer Science 7456 (2012) 26–33. pdf
  • E. Fokina, V. Harizanov, A. Melnikov. Computable model theory, Turing's Legacy: Developments from Turing's Ideas in Logic (edited by R. Downey), ASL Lecture Notes in Logic 42 (2014), 124–194. pdf
  • E. Fokina, V. Harizanov and D. Turetsky. Effective categoricity and Scott Families, submitted. pdf