Uniformity in Computable Structure Theory

Rod Downey, Denis R. Hirschfeldt & Bakhadyr Khoussainov

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). In computability theory, uniformity is usually defined in terms of indices. From a model-theoretic viewpoint, however, it seems more natural to consider effective procedures that take structures, rather than indices for structures, as input. We consider and compare these two different notions of uniformity, and discuss connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman [1] and Chisholm [3] and with previous work of Ash, Knight, and Slaman [2] on uniformity in a general computable structure-theoretical setting.

[1] C. Ash, J. Knight, M. Manasse, and T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic 42 (1989) 195–205.

[2] C. Ash, J. Knight, and T. Slaman, Relatively recursive expansions II, Fund. Math. 142 (1993) 147–161.

[3] J. Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990) 1168– 1191.

Addresses Rod Downey: School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand

Denis R. Hirschfeldt: School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand

Bakhadyr Khoussainov: Department of Computer Science, University of Auckland, New Zealand