zbMATH — the first resource for mathematics

Hanf number for Scott sentences of computable structures. (English) Zbl 07001423
Summary: The Hanf number for a set \(S\) of sentences in \(\mathcal {L}_{\omega _1,\omega }\) (or some other logic) is the least infinite cardinal \(\kappa \) such that for all \(\phi \in S\), if \(\phi \) has models in all infinite cardinalities less than \(\kappa \), then it has models of all infinite cardinalities. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is \(\beth _{\omega _1^{CK}}\). The same argument proves that \(\beth _{\omega _1^{CK}}\) is the Hanf number for Scott sentences of hyperarithmetical structures.
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03C75 Other infinitary logic
03C70 Logic on admissible sets
03C52 Properties of classes of models
Full Text: DOI
[1] Ash, C.J., Knight, J.F.: Computable Structures and the Hyperarithmetical Hierarchy. Elsevier, Amsterdam (2000) · Zbl 0960.03001
[2] Csima, B.; Harizanov, V.; Miller, R.; Montalbán, A., Computability of Fraïssé limits, J. Symb. Logic, 76, 66-93, (2011) · Zbl 1215.03053
[3] Goncharov, SS, Strong constructivizability of homogeneous models, Algebra i Logika, 17, 363-388, (1978) · Zbl 0441.03015
[4] Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997) · Zbl 0873.03036
[5] Keisler, H.J.: Model Theory for Infinitary Logic. North-Holland, Amsterdam (1971) · Zbl 0222.02064
[6] Nadel, M.; Barwise, KJ (ed.); Feferman, S. (ed.), \(L_{\omega _1,\omega }\) and admissible fragments, 271-316, (1985), New York
[7] Nadel, M., Scott sentences and admissible sets, Ann. Math. Logic, 7, 267-294, (1974) · Zbl 0301.02050
[8] Peretyat’kin, MG, A criterion of strong constructivizability of a homogeneous model, Algebra i Logika, 17, 436-454, (1978) · Zbl 0431.03021
[9] Ressayre, J-P, Boolean valued models and infinitary first order languages, Ann. Math. Logic, 6, 41-92, (1973) · Zbl 0288.02013
[10] Ressayre, J-P, Models with compactness properties relative to an admissible language, Ann. Math. Logic, 11, 31-55, (1977) · Zbl 0376.02032
[11] Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw Hill, New York (1967) · Zbl 0183.01401
[12] Scott, D.; Addison, J. (ed.); Henkin, L. (ed.); Tarski, A. (ed.), Logic with denumerably long formulas and finite strings of quantifiers, 329-341, (1965), Amsterdam
[13] Souldatos, I., Characterizing the power set by a complete Scott sentence, Fundam. Math., 6, 131-154, (2013) · Zbl 1285.03046
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.