Computable Structure and Non-Structure Theorems

S. S. Goncharov ; J. F. Knight

Algebra i logika, Tome 41 (2002) no. 6, pp. 639-681.

Résumé

In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures $\mathcal A$ of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify $\mathcal A$ with its atomic diagram $D(\mathcal A)$, which, via the Gödel numbering, may be treated as a subset of $\omega$. In particular, $\mathcal A$ is computable if $D(\mathcal A)$ is computable. If $K$ is some class, then $K^c$ denotes the set of computable members of $K$. A computable characterization for $K$ should separate the computable members of $K$ from other structures, that is, those that either are not in $K$ or are not computable. A computable classification (structure theorem) should describe each member of $K^c$ up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the “correct” answer for vector spaces over $Q$, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.

Bibliographie

[1] W. Hodges, “What is a structure theory?”, Bull. London Math. Soc., 19:3(78) (1987), 209–237 | DOI | MR | Zbl

[2] S. Shelah, “Classification of first order theories which have a structure theorem”, Bull. Am. Math. Soc., 12:2 (1985), 227–232 | DOI | MR | Zbl

[3] H. Friedman, L. Stanley, “On Borel reducibility theory for classes of computable structures”, J. Symb. Log., 54:3 (1989), 894–914 | DOI | MR | Zbl

[4] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Elsevier, Amsterdam, 2000 | MR

[5] D. Scott, “Logic with denumerably long formulas and finite strings of quantifiers”, The theory of models, eds. J. Addison, L. Henkin, A. Tarski, North-Holland, Amsterdam, 1970, 329–341 | MR

[6] H. J. Keisler, Model Theory for Infinitary Logic. Logic with countable conjunctions and finite quantifiers, North-Holland, Amsterdam, 1971 | MR | Zbl

[7] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York, 1967 | MR | Zbl

[8] J. Harrison, “Recursive pseudo well-orderings”, Trans. Am. Math. Soc., 131:2 (1968), 526–543 | DOI | MR | Zbl

[9] G. E. Sacks, Higher type recursion theory, Springer-Verlag, Berlin, 1990 | MR

[10] S. S. Goncharov, “Avtoustoichivost i vychislitelnye modeli”, Algebra i logika, 14:6 (1975), 647–680 | MR | Zbl

[11] S. S. Goncharov, “O chisle neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 16:6 (1977), 257–282 | MR | Zbl

[12] C. J. Ash, “Categoricity in hyperarithmetical degrees”, Ann. Pure Appl. Logic, 34:1 (1987), 1–14 | DOI | MR | Zbl

[13] E. Lopez-Escobar, “An addition to "On definable well-orderings”, Fund. Math., 59:3 (1966), 299–300 | MR | Zbl

[14] M. Morley, “Omitting classes of elements”, The theory of models, eds. M. Addison, L. Henkin, A. Tarski, North-Holland, Amsterdam, 1970, 265–273 | MR

[15] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinco, Degree spectra and computable dimensions in algebraic structures, preprint

[16] C. J. Ash, J. F. Knight, “Pairs of recursive structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | MR | Zbl

[17] C. J. Ash, C. G. Jockusch, J. F. Knight, “Jumps of orderings”, Trans. Am. Math. Soc., 319:2 (1990), 573–599 | DOI | MR | Zbl

[18] C. J. Ash, “A construction for recursive linear orderings”, J. Symb. Log., 56:2 (1991), 673–683 | DOI | MR | Zbl

[19] C. J. Ash, “Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc., 298:2 (1986), 497–514 ; “Corrections”, 310:2 (1988), 851 | DOI | MR | Zbl | DOI | MR

[20] A. T. Nurtazin, Vychislimye klassy i algebraicheskie kriterii avtoustoichivosti, diss. k.f.-m.n., In-t matem. mekhan. AN Kazakhskoi SSR, Alma-Ata, 1974 | Zbl

[21] C. G. Jockusch, R. I. Soare, “Degrees of orderings not isomorphic to recursive linear orderings”, Ann. Pure Appl. Logic, 52:1–2 (1991), 39–64 | DOI | MR | Zbl