Some new computable structures of high rank

Harrison-Trainor, Matthew; Igusa, Gregory; Knight, Julia

doi:10.1090/proc/13967

Some new computable structures of high rank
HTML articles powered by AMS MathViewer

by Matthew Harrison-Trainor, Gregory Igusa and Julia F. Knight PDF

Proc. Amer. Math. Soc. 146 (2018), 3097-3109 Request permission

Abstract:

We give several new examples of computable structures of high Scott rank. For earlier known computable structures of Scott rank $\omega _1^{CK}$, the computable infinitary theory is $\aleph _0$-categorical. Millar and Sacks asked whether this was always the case. We answer this question by constructing an example whose computable infinitary theory has non-isomorphic countable models. The standard known computable structures of Scott rank $\omega _1^{CK}+1$ have infinite indiscernible sequences. We give two constructions with no indiscernible ordered triple.

References

W. Calvert, S. S. Goncharov, J. F. Knight, and Jessica Millar, Categoricity of computable infinitary theories, Arch. Math. Logic 48 (2009), no. 1, 25–38. MR 2480933, DOI 10.1007/s00153-008-0117-z
Wesley Calvert, Julia F. Knight, and Jessica Millar, Computable trees of Scott rank $\omega _1^{CK}$, and computable approximation, J. Symbolic Logic 71 (2006), no. 1, 283–298. MR 2210068, DOI 10.2178/jsl/1140641175
Barbara F. Csima, Valentina S. Harizanov, Russell Miller, and Antonio Montalbán, Computability of Fraïssé limits, J. Symbolic Logic 76 (2011), no. 1, 66–93. MR 2791338, DOI 10.2178/jsl/1294170990
Cameron Eric Freer, Models with high Scott rank, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–Harvard University. MR 2711681
Joseph Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526–543. MR 244049, DOI 10.1090/S0002-9947-1968-0244049-7
Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller, and Antonio Montalbán, Computable functors and effective interpretability, J. Symb. Log. 82 (2017), no. 1, 77–97. MR 3625736, DOI 10.1017/jsl.2016.12
C. Ward Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69–83. MR 304242, DOI 10.2140/pjm.1971.38.69
Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), no. 1-3, 71–113. MR 1897023, DOI 10.1016/S0168-0072(01)00087-2
Julia F. Knight, Computable structures of Scott rank $\omega _1^\textrm {CK}$, Models, logics, and higher-dimensional categories, CRM Proc. Lecture Notes, vol. 53, Amer. Math. Soc., Providence, RI, 2011, pp. 157–168. MR 2867968, DOI 10.1090/crmp/053/07
J. F. Knight and J. Millar, Computable structures of rank $\omega ^\textrm {CK}_1$, J. Math. Log. 10 (2010), no. 1-2, 31–43. MR 2802081, DOI 10.1142/S0219061310000912
M. Makkai, An example concerning Scott heights, J. Symbolic Logic 46 (1981), no. 2, 301–318. MR 613284, DOI 10.2307/2273623
J. Millar and G. E. Sacks, Atomic models higher up, Ann. Pure Appl. Logic 155 (2008), no. 3, 225–241. MR 2467433, DOI 10.1016/j.apal.2008.04.004
Mark Nadel, Scott sentences and admissible sets, Ann. Math. Logic 7 (1974), 267–294. MR 384471, DOI 10.1016/0003-4843(74)90017-5
Dana Scott, Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 329–341. MR 0200133