Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-29T00:24:22.163Z Has data issue: false hasContentIssue false

Effective model theory: approach via σ-definability

Published online by Cambridge University Press:  05 December 2013

By
Alexey Stukachev
Edited by
Noam Greenberg ,
Denis Hirschfeldt ,
Joel David Hamkins  and
Russell Miller
Noam Greenberg
Affiliation:
Victoria University of Wellington
Denis Hirschfeldt
Affiliation:
University of Chicago
Joel David Hamkins
Affiliation:
College of Staten Island
Russell Miller
Affiliation:
Queens College, City University of New York
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Effective Mathematics of the Uncountable , pp. 164 - 197
Publisher: Cambridge University Press
Print publication year: 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Ash, C., Knight, J.F., Manasse, M. and Slaman, T. (1989) Generic copies of countable structures, Ann. Pure Appl. Logic 42, 195–205.Google Scholar
[2] Ashaev, I.V., Belyaev, V.Ya. and Myasnikov, A.G. (1993). Toward a generalized computability theory, Algebra Logic 32, 4, 183–205.Google Scholar
[3] Baleva, V. (2006) The jump operation for structure degrees, Arch. Math. Logic 45, 249–265.Google Scholar
[4] Barwise, J. (1975). Admissible Sets and Structures, Springer, Berlin–Heidelberg–New York.
[5] Blum, L., Shub, M. and Smale, S. (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Am. Math. Soc. 21, 1, 1–46.Google Scholar
[6] Chisholm, J. (1990). Effective model theory vs. recursive model theory, J. Symbolic Logic 55, 1168–1191.Google Scholar
[7] Ershov, Yu.L. (1980). Decidability Problems and Constructivizable Models, Nauka, Moscow.
[8] Ershov, Yu.L. (1985). Σ-definability in admissible sets, Sov. Math. Dokl. 32, 767–770.Google Scholar
[9] Ershov, Yu.L. (1995). Definability in hereditarily finite manifolds, Dokl. Math. 51, 1, 8–10.Google Scholar
[10] Ershov, Yu.L. (1996). Definability and Computability, Consultants Bureau, New York–London–Moscow.
[11] Ershov, Yu.L. (1998). Σ-definability of algebraic structures. In Handbook of Recursive Mathematics, Vol. 1, Yu.L., Ershov, S.S., Goncharov, A., Nerode, and J.B., Remmel (eds), Elsevier, 235–260.
[12] Ershov, Yu.L. (2000). Definability and Computability, Ekonomika, Nauch. Kniga, Moscow–Novosibirsk.
[13] Ershov, Yu.L. and Goncharov, S.S. (2000). Constructive Models, Consultants Bureau, New York–London–Moscow.
[14] Ershov, Yu.L., Goncharov, S.S. and Sviridenko, D.I. (1986). Semantic programming, Inform. Processing 86, 1093–1100.Google Scholar
[15] Ershov, Yu.L., Puzarenko, V.G. and Stukachev, A.I. (2011). HF-computability, In Computability in Context: Computation and Logic in the Real World, S.B., Cooper and A., Sorbi (eds.), Imperial College Press/World Scientific, 173–248.
[16] Goncharov, S.S. and Sviridenko, D.I. (1985). Σ-programming (Russian), Vychisl. Sist. 107, 3–29.Google Scholar
[17] Goncharov, S.S. and Khoussainov, B. (2004). Complexity of categorical theories with computable models, Algebra Logic 43, 6, 365–373.Google Scholar
[18] Gordon, C. (1970). Comparisons between some generalizations of recursion theory, Compos. Math. 22, 333–346.Google Scholar
[19] Hodges, W. (1993). Model Theory, Cambridge University Press, Cambridge.
[20] Kalimullin, I.S. (2006). The Dyment reducibility on the algebraic structures and on the families of subsets of ω, Logical Approaches to Computational Bariers, CiE2006, Report Series, Swansea, 150–159.
[21] Kalimullin, I.S. (2009). Uniform reducibility of representability problems for algebraic structures, Sib. Math. J. 50, 2, 265–271.Google Scholar
[22] Khisamiev, A.N. (1996). Σ-enumeration and Σ-definability in HFℳ (Russian), Vychisl. Sist. 156, 44–58.Google Scholar
[23] Khisamiev, A.N. (1997). Numberings and definability in the hereditarily finite superstructure of a model, Sib. Adv. Math. 7, 3, 63–74.Google Scholar
[24] Khisamiev, A.N. (1998). On definability of a model in a hereditarily finite admissible set (Russian), Vychisl. Sist. 161, 15–20.Google Scholar
[25] Khisamiev, A.N. (1998) Strong Δ1-definability of a model in an admissible set, Sib. Math. J. 39, 1, 168–175.Google Scholar
[26] Khisamiev, A.N. (1999). On resolvable and internally enumerable models (Russian), Vychisl. Sist. 165, 31–35.Google Scholar
[27] Khisamiev, A.N. (2000). The intrinsic enumerability of linear orders, Algebra Logic 39, 6, 423–428.Google Scholar
[28] Khisamiev, A.N. (2001). Quasiresolvable models and B-models, Algebra Logic 40, 4, 272–280.Google Scholar
[29] Khisamiev, A.N. (2004). Quasiresolvable models, Algebra Logic 43, 5, 346–354.Google Scholar
[30] Khisamiev, A.N. (2004). On the Ershov upper semilattice, Sib. Math. J. 45, 1, 173–187.Google Scholar
[31] Kierstead, H.A. and Remmel, J.B. (1983). Indiscernibles and decidable models, J. Symb. Logic 48, 1, 21–32.Google Scholar
[32] Kierstead, H.A. and Remmel, J.B. (1985). Degrees of indiscernibles in decidable models, Trans. Am. Math. Soc. 289, 1, 41–57.Google Scholar
[33] Korovina, M.V. (1992). Generalised computability of real functions, Sib. Adv. Math. 2, 4, 1–18.Google Scholar
[34] Korovina, M.V. (1996). On the universal recursive function and on abstract machines on real numbers with the list superstructure (Russian), Vychisl. Sist. 156, 24–43.Google Scholar
[35] Korovina, M.V. (2002). Fixed points on the real numbers without the equality test, Electron. Notes Theor. Comput. Sci. 66, 1.Google Scholar
[36] Korovina, M.V. (2003). Computational aspects of Sigma-definability over the real numbers without the equality test. In CSL; Lect. Notes Comput. Sci. 2803, 330–344.Google Scholar
[37] Korovina, M.V. (2003). Gandy's theorem for abstract structures without the equality test. In LPAR; Lect. Notes Comput. Sci. 2850, 290–301.Google Scholar
[38] Korovina, M.V. (2003). Recent advances in S-definability over continuous data types. In Ershov Memorial Conference; Lect. Notes Comput. Sci. 2890, 238–247.Google Scholar
[39] Korovina, M.V. and Kudinov, O.V. (1996). A new approach to computability of real-valued function (Russian), Vychisl. Sist. 156, 3–23.Google Scholar
[40] Korovina, M.V. and Kudinov, O.V. (1998). Characteristic properties of majorant-computability over the reals. In CSL; Lect. Notes Comput. Sci. 1584, 188–203.Google Scholar
[41] Korovina, M.V. and Kudinov, O.V. (1998). New approach to computability, Sib. Adv. Math. 8, 3, 59–73.Google Scholar
[42] Korovina, M.V. and Kudinov, O.V. (1999). A logical approach to specification of hybrid systems. In Ershov Memorial Conference; Lect. Notes Comput. Sci. 1755, 10–16.Google Scholar
[43] Korovina, M.V. and Kudinov, O.V. (2000). Formalisation of computability of operators and real-valued functionals via domain theory. In CCA; Lect. Notes Comput. Sci. 2064, 146–168.Google Scholar
[44] Korovina, M.V. and Kudinov, O.V. (2001). Semantic characterisations of second-order computability over the real numbers. In CSL; Lect. Notes Comput. Sci. 2142, 160–172.Google Scholar
[45] Korovina, M.V. and Kudinov, O.V. (2001). Generalised computability and applications to hybrid systems. In Ershov Memorial Conference; Lect. Notes Comput. Sci. 2244, 494–499.Google Scholar
[46] Korovina, M.V. and Kudinov, O.V. (2005). Towards computability of higher type continuous data. In CiE2005; Lect. Notes Comput. Sci. 3526, 235–241.Google Scholar
[47] Korovina, M.V. and Kudinov, O.V. (2008). Effectively enumerable topological spaces (Russian), Vestn. Novosib. Gos. Univ., Ser. Mat. Mech. Inform. 8, 2, 74–83.Google Scholar
[48] Korovina, M.V. and Kudinov, O.V. (2008). Basic principles of Σ-definability and abstract computability, Bericht Nr. 08-01, Fachbereich Mathematik, D-57068, Siegen.
[49] Korovina, M.V. and Vorobjov, N. (2004). Pfaffian hybrid systems. In CSL; Lect. Notes Comput. Sci. 3210, 430–441.Google Scholar
[50] Lacombe, D. (1964). Deux généralizations de la notion de récursivité relative, C. R. Acad. Sci., Paris 258, 3410–3413.Google Scholar
[51] Miller, R. (2007). Locally computable structures. In CiE2007, Lect. Notes Comput. Sci. 4497, 575–584.Google Scholar
[52] Miller, R. and Mulcahey, D. (2008). Perfect local computability and computable simulations. In CiE2008, Lect. Notes Comput. Sci. 5028, 388–397.Google Scholar
[53] Montague, R. (1967). Recursion theory as a branch of model theory. In Proceedings ofthe Third International Congress for Logic, Methodology and Philosophy of Science, North-Holland, Amsterdam-London, 63–86.
[54] Montalban, A. (2009). Notes on the jump of a structure. In CiE2009, Lect. Notes Comput. Sci. 5635, 372–378.Google Scholar
[55] Morozov, A.S. (2000). A Σ subset of natural numbers which is not enumerable by natural numbers, Sib. Math. J. 41, 6, 1162–1165.Google Scholar
[56] Morozov, A.S. (2002). Presentability of groups of Σ-presentable permutaions over admissible sets, Algebra Logic 41, 4, 254–266.Google Scholar
[57] Morozov, A.S. (2004). On the relation of Σ-reducibility between admissible sets, Sib. Math. J. 45, 3, 522–535.Google Scholar
[58] Morozov, A.S. (2006). Elementary submodels of parametrizable models, Sib. Math. J. 47, 3, 491–504.Google Scholar
[59] Morozov, A.S. (2008). On the index sets of Σ-subsets of the real numbers, Sib. Math. J. 49, 6, 1078–1084.Google Scholar
[60] Morozov, A.S. and Korovina, M.V. (2008) Σ-definability of countable structures over real numbers, complex numbers and quaternions, Algebra Logic 47, 3, 193–209.Google Scholar
[61] Morozov, A.S. and Puzarenko, V.G. (2004). Σ-subsets of natural numbers, Algebra Logic 43, 3, 162–178.Google Scholar
[62] Moschovakis, Y.N. (1969). Axioms for computation theories – first draft. In Logic Colloquium '69, R.O., Gandy and C.E.M., Yates (eds), North-Holland, Amsterdam, 199–255.
[63] Moschovakis, Y.N. (1969). Abstract computability and invariant definability, J. Symb. Log. 34, 605–633.Google Scholar
[64] Moschovakis, Y.N. (1969). Abstract first order computability I, Trans. Am. Math. Soc. 138, 427–464.Google Scholar
[65] Moschovakis, Y.N. (1969). Abstract first order computability II. Trans. Am. Math. Soc. 138, 465–504.Google Scholar
[66] Moschovakis, Y.N. (1974). Elementary Induction on Abstract Structures, North-Holland, Amsterdam–London.
[67] Puzarenko, V.G. (2000). On computability over models of decidable theories, Algebra Logic 39, 2, 98–113.Google Scholar
[68] Puzarenko, V.G. (2002). On model theory in hereditarily finite superstructures, Algebra Logic 41, 2, 111–122.Google Scholar
[69] Puzarenko, V.G. (2004). The Löwenheim–Skolem–Mal'tsev Theorem for ℍF-structures, Algebra Logic 43, 6, 418–423.Google Scholar
[70] Puzarenko, V.G. (2006). Definability of the field of reals in admissible sets, Logical Approaches to Computational Barriers, CiE2006, Report Series, Swansea, 236–240.
[71] Puzarenko, V.G. (2009). About a certain reducibility on admissible sets, Sib. Math. J. 50, 2, 330–340.Google Scholar
[72] Richter, L. (1981). Degrees of structures, J. Symb. Log. 46, 723–731.Google Scholar
[73] Romina, A.V. (1998). Hyperarithmetical stability of Boolean algebras (Russian), Vychisl. Sist. 161, 21–27.Google Scholar
[74] Romina, A.V. (2000). Autostability of hyperarithmetical models, Algebra Logic 39, 2, 114–118.Google Scholar
[75] Romina, A.V. (2000a). Definability of Boolean algebras in ℍF-superstructures, Algebra Logic 39, 6, 407–411.Google Scholar
[76] Rudnev, V.A. (1986). A universal recursive function on admissible sets, Algebra Logic 25, 4, 267–273.Google Scholar
[77] Rudnev, V.A. (1988). Existence of an inseparable pair in the recursive theory of admissible sets, Algebra Logic 27, 1, 33–39.Google Scholar
[78] Sacks, G.E. (1990). Higher Recursion Theory, Springer, Berlin–Heidelberg–New York.
[79] Schmerl, J.H. (1980). Decidability and ℵ0-categoricity of theories of partially ordered sets, J. Symb. Log. 45, 585–611.Google Scholar
[80] Slaman, T.A. (1998) Relative to any non-recursive set, Proc. Am. Math. Soc. 126, 2117–2122.Google Scholar
[81] Sorbi, A. (1996). The Medvedev lattice of degrees of difficulty, In Computability, Enumerability, Unsolvability: Directions in Recursion Theory. LMS Lecture Notes, 24, 289–312.
[82] Soskov, I.N. (2004). Degree spectra and co-spectra of structures, Ann. Univ. Sofia 96, 45–68.Google Scholar
[83] Soskova, A.A. (2007). A jump inversion theorem for the degree spectra. In CiE2007, Lect. Notes Comput. Sci. 4497, 716–726.Google Scholar
[84] Soskov, I.N. and Soskova, A.A. (2009). A jump inversion theorem for the degree spectra, J. Log. Comput. 19, 199–215.Google Scholar
[85] Stukachev, A.I. (1996). Uniformization Theorem for HF(R) (Russian). In Proceedings of the XXXIV International Scientific Student Conference ‘Student i Nauchno-Tehnicheskij Progress: Matematica’, Novosibirsk (1996), p. 83.
[86] Stukachev, A.I. (1997). Uniformization property in hereditary finite superstructures, Sib. Adv. Math. 7, 1, 123–132.Google Scholar
[87] Stukachev, A.I. (1998). Uniformization property in hereditary finite superstructures (Russian), Vychisl. Sist. 161, 3–14.Google Scholar
[88] Stukachev, A.I. (2002). Σ-admissible families over linear orders, Algebra Logic 41, 2, 127–139.Google Scholar
[89] Stukachev, A.I. (2004). Σ-definability in hereditary finite superstructures and pairs of models, Algebra Logic 43, 4, 258–270.Google Scholar
[90] Stukachev, A.I. (2005). On inner constructivizability of admissible sets (Russian), Vestn. Novosib. Gos. Univ., Ser. Mat. Mech. Inform. 5, 1, 69–76.Google Scholar
[91] Stukachev, A.I. (2005). Presentations of structures in admissible sets. In CiE2005, Lect. Notes Comput. Sci. 3526, 470–478.Google Scholar
[92] Stukachev, A.I. (2006). On mass problems of presentability. In TAMC2006, Lect. Notes Comput. Sci. 3959, 774–784.Google Scholar
[93] Stukachev, A.I. (2007). Degrees of presentability of structures, I, Algebra Logic 46, 6, 419–432.Google Scholar
[94] Stukachev, A.I. (2008). Degrees of presentability of structures, II, Algebra Logic 47, 1, 65–74.Google Scholar
[95] Stukachev, A.I. (2009). A jump inversion theorem for the semilattices of Σ-degrees (Russian), Sib. Elektron. Mat. Izv. 6, 182–190.Google Scholar
[96] Stukachev, A.I. (2010). A jump inversion theorem for the semilattices of Σ-degrees, Sib. Adv. Math. 20, 1, 68–74.Google Scholar
[97] Stukachev, A.I. (2010a). Σ-definability of uncountable structures of c-simple theories, Siberian Mathematical Journal 51, 515–524.Google Scholar
[98] Stukachev, A.I. (2013). On semilattices of Σ-degrees of structures. To appear in Algebra Logic.
[99] Vajtsenavichyus, R.Yu. (1989). On admissible sets with inner resolutions (Russian, English abstract), Mat. Logika Primen. 6, 9–20.Google Scholar
[100] Vajtsenavichyus, R.Yu. (1989). On necessary conditions for the existence of a universal function on an admissible set (Russian, English abstract), Mat. Logika Primen. 6, 21–37.Google Scholar
[101] Van den Dries, L. (1984). Algebraic theories with definable Skolem functions, J. Symbolic Logic 49, 625–630.Google Scholar
[102] Wehner, S. (1998). Enumerations, countable structures and Turing degrees, Proc. Am. Math. Soc. 126, 2131–2139.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×