zbMATH — the first resource for mathematics

Categoricity of computable infinitary theories. (English) Zbl 1161.03020
Summary: Computable structures of Scott rank \(\omega_1^{CK}\) are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of \(\mathcal{L}_{\omega_1 \omega}\), this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank \(\omega_1^{CK}\) whose computable infinitary theories are each \(\aleph_0\)-categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank \(\omega_1^{CK}\), which guarantee that the resulting structure is a model of an \(\aleph_0\)-categorical computable infinitary theory.

03C57 Computable structure theory, computable model theory
Full Text: DOI
[1] Calvert, W., Goncharov, S.S., Knight, J.F.: Computable structures of Scott rank \({\omega_1^{CK}}\) in familiar classes. In: Gao, S., Jackson, S., Zhang, Y. (eds.) Advances in Logic. Con. Math., pp. 43–66 (2007) · Zbl 1143.03016
[2] Calvert W., Knight J.F., Millar J.: Trees of Scott rank \({\omega_1^{CK}}\) , and computable approximability. J. Symb. Logic 71, 283–298 (2006) · Zbl 1112.03039
[3] Friedman H., Stanley L.: A Borel reducibility theory for classes of countable structures. J. Symb. Logic 54, 894–914 (1989) · Zbl 0692.03022
[4] Goncharov S.S., Harizanov V.S., Knight J.F., Shore R.: \({\Pi^1_1}\) relations and paths through \({\mathcal{O}}\) . J. Symb. Logic 69, 585–611 (2004) · Zbl 1107.03051
[5] Harrison J.: Recursive pseudo well-orderings. Trans. Am. Math. Soc. 131, 526–543 (1968) · Zbl 0186.01101
[6] Hirschfeldt D., Khoussainov B., Shore R., Slinko A.: Degree spectra and computable dimension in algebraic structures. Ann. Pure Appl. Logic 115, 71–113 (2002) · Zbl 1016.03034
[7] Keisler, J.H.: Model Theory for Infinitary Logic. North-Holland, Amsterdam (1971) · Zbl 0222.02064
[8] Knight, J.F., Millar, J.: Computable structures of Scott rank \({\omega_1^{CK}}\) . J. Math. Logic (submitted data) · Zbl 1112.03039
[9] Makkai M.: An example concerning Scott heights. J. Symb. Logic 46, 301–318 (1981) · Zbl 0501.03018
[10] Marker D.: Model Theory: An Introduction. Springer, Berlin (2002) · Zbl 1003.03034
[11] Millar, J., Sacks, G.: Atomic models higher up, pre-print · Zbl 1152.03024
[12] Nadel M.E.: Scott sentences for admissible sets. Ann. Math. Logic 7, 267–294 (1974) · Zbl 0301.02050
[13] Soskov I.N.: Intrinsically \({\Delta _{1}^{1}}\) relations. Math. Logic Q. 42, 469–480 (1996) · Zbl 0859.03016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.