Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-15T01:19:49.971Z Has data issue: false hasContentIssue false
  • English
  • Français

Classification from a Computable Viewpoint

Published online by Cambridge University Press:  15 January 2014

Wesley Calvert and
Julia F. Knight
Wesley Calvert
Affiliation:
Murray State University, Department of Mathematics and Statistics, Murray, Kentucky 42071, USA E-mail: wesley.calvert@murraystate.edu
Julia F. Knight
Affiliation:
University of Notre Dame, Department of Mathematics, Notre Dame, Indiana 46556, USA E-mail: Julia.F.Knight.1@nd.edu
Get accessRights & Permissions [Opens in a new window]

Extract

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we describe some recent work on classification in computable structure theory.

Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.

Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work.

Information

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 2 , June 2006, pp. 191 - 218
Copyright
Copyright © Association for Symbolic Logic 2007

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.)

Article purchase

Temporarily unavailable

References

REFERENCES

[1] Ash, C. J. and Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000.Google Scholar
[2] Baldwin, J. and Lachlan, A., On strongly minimal sets, The Journal of Symbolic Logic, vol. 36 (1971), pp. 79–96.Google Scholar
[3] Barker, E., Back and forth relations for reduced Abelian p-groups, Annals of Pure and Applied Logic, vol. 75 (1995), pp. 223–249.Google Scholar
[4] Barwise, J., Infinitary logic and admissible sets, The Journal of Symbolic Logic, vol. 34 (1969), pp. 226–252.Google Scholar
[5] Becker, H. and Kechris, A. S., The Descriptive Set Theory of Polish Group Actions, Cambridge, 1996.Google Scholar
[6] Buechler, S., Vaught's conjecture for superstable theories of finite rank, Annals of Pure and Applied Logic, to appear.Google Scholar
[7] Calvert, W., The isomorphism problem for classes of computable fields, Archive for Mathematical Logic, vol. 43 (2004), pp. 327–336.CrossRefGoogle Scholar
[8] Calvert, W., Algebraic Structure and Computable Structure, Ph.D. thesis, University of Notre Dame, 2005.Google Scholar
[9] Calvert, W., The isomorphism problem for computable Abelian p-groups of bounded length, The Journal of Symbolic Logic, vol. 70 (2005), pp. 331–345.Google Scholar
[10] Calvert, W., Cummins, D., Miller, S., and Knight, J. F., Comparing classes of finite structures, Algebra and Logic, vol. 43 (2004), pp. 365–373.CrossRefGoogle Scholar
[11] Calvert, W., Goncharov, S. S., and Knight, J. F., Computable structures of Scott rank in familiar classes, preprint.Google Scholar
[12] Calvert, W., Harizanov, V. S., Knight, J. F., and Miller, S., Index sets of computable structures, preprint.Google Scholar
[13] Calvert, W., Knight, J. F., and Millar, J., Computable trees of Scott rank and computable approximation, The Journal of Symbolic Logic, to appear.Google Scholar
[14] Csima, B., Montalban, A., and Shore, R., Boolean algebras, Tarski invariants, and index sets, preprint.Google Scholar
[15] Ershov, Y. L., Teoriya Numeratsii (Enumeration Theory), Nauka, 1977, in Russian.Google Scholar
[16] Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures, The Journal of Symbolic Logic, vol. 54 (1989), pp. 894–914.CrossRefGoogle Scholar
[17] Goncharov, S. S., Constructive Boolean algebras, Third All-Union Conference in Mathematical Logic, Novosibirsk, 1974.Google Scholar
[18] Goncharov, S. S., Countable Boolean Algebras, Siberian School of Algebra and Logic (Russian version), Kluwer (English version), 1996.Google Scholar
[19] Goncharov, S. S. and Dzgoev, V. D., Autostability of models, Algebra and Logic, vol. 19 (1980), pp. 28–37 (English), 45–58 (Russian).CrossRefGoogle Scholar
[20] Goncharov, S. S., Harizanov, V. S., Knight, J. F., and Shore, R., relations and paths through , The Journal of Symbolic Logic, vol. 69 (2004), pp. 585–611.Google Scholar
[21] Goncharov, S. S. and Knight, J. F., Computable structure and non-structure theorems, Algebra and Logic, vol. 41 (2002), pp. 351–373.Google Scholar
[22] Harrison, J., Recursive pseudo well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
[23] Hjorth, G., The isomorphism relation on countable torsion-free Abelian groups, Fundamenta Mathematicae, vol. 175 (2002), pp. 241–257.CrossRefGoogle Scholar
[24] Hjorth, G. and Kechris, A. S., Analytic equivalence relations and Ulm-type classifications, The Journal of Symbolic Logic, vol. 6 (1995), pp. 1273–1300.Google Scholar
[25] Hjorth, G. and Kechris, A. S., Recent developments in the theory of Borel reducibility, Fundamenta Mathematicae, vol. 170 (2001), pp. 21–52.CrossRefGoogle Scholar
[26] Hjorth, G. and Thomas, S., The classification problem for p-local torsion-free Abelian groups of rank two, preprint.Google Scholar
[27] Hodges, W. , What is a structure theory, Bulletin of the London Mathematical Society, vol. 19 (1987), pp. 209–237.CrossRefGoogle Scholar
[28] Jockusch, C. G., The degrees of bi-immune sets, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 135–140.CrossRefGoogle Scholar
[29] Kaplansky, I., Infinite Abelian Groups, University of Michigan Press, 1969.Google Scholar
[30] Keisler, H. J., Model Theory for Infinitary Logic, North-Holland, 1971.Google Scholar
[31] Ketonen, J., The structure of countable Boolean algebras, Annals of Mathematics, vol. 108 (1976), pp. 41–89.CrossRefGoogle Scholar
[32] Khisamiev, N. G., The arithmetic hierarchy of Abelian groups, Sibirskii Matematicheskii Zhurnal, vol. 29 (1988), pp. 144–159.Google Scholar
[33] Khisamiev, N. G., Constructive Abelian groups, Handbook of Recursive Mathematics, II (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Elsevier, 1998, pp. 1177–1231.Google Scholar
[34] Knight, J. F., Effective transfer of invariants, submitted to The Journal of Symbolic Logic.Google Scholar
[35] Knight, J. F. and Millar, J., Computable structures of rank , submitted to Journal of Mathematical Logic.Google Scholar
[36] Koppelberg, S., Handbook of Boolean Algebras, vol. 1, (Monk, J. D. and Bonnet, R., editors), North Holland, 1989.Google Scholar
[37] Kreisel, G., Set theoretic problems suggested by the notion of potential totality, Infinitistic Methods, Oxford, 1961, pp. 103–140.Google Scholar
[38] Makkai, M., An example concerning Scott heights, The Journal of Symbolic Logic, vol. 46 (1981), pp. 301–318.Google Scholar
[39] Miller, A. W., On the Borel classification of the isomorphism class of a countable model, Notre Dame Journal of Formal Logic, vol. 24 (1983), pp. 22–34.CrossRefGoogle Scholar
[40] Miller, D. E., The invariant separation principle, Transactions of the American Mathematical Society, vol. 242 (1978), pp. 185–204.Google Scholar
[41] Morley, M., Categoricity in power, Transactions of the American Mathematical Society, vol. 114 (1965), pp. 514–538.CrossRefGoogle Scholar
[42] Morley, M., The number of countable models, The Journal of Symbolic Logic, vol. 35 (1970), pp. 14–18.CrossRefGoogle Scholar
[43] Morozov, A. S., Groups of computable automorphisms, Handbook of Recursive Mathematics (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Elsevier, 1998, pp. 311–345.Google Scholar
[44] Nadel, M. E., Scott sentences and admissible sets, Annals of Mathematical Logic, vol. 7 (1974), pp. 267–294.Google Scholar
[45] Nadel, M. E., Lω1ω and admissible fragments, Model-Theoretic Logics (Barwise, K. J. and Feferman, S., editors), vol. 45, 1980, pp. 612–622.Google Scholar
[46] Pierce, R. S., Countable Boolean algebras, Handbook of Boolean Algebras, vol. 3 (Monk, J. D. and Bonnet, R., editors), North-Holland, 1989, pp. 775–876.Google Scholar
[47] Ressayre, J.-P., Models with compactness properties relative to an admissible language, Annals of Mathematical Logic, (now Annals of Pure and Applied Logic ), vol. 11 (1977), pp. 31–55.Google Scholar
[48] Rogers, H. Jr, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.Google Scholar
[49] Rubin, M., Theories of linear order, Israel Journal of Mathematics, vol. 17 (1974), pp. 392–443.Google Scholar
[50] Sacks, G. E., Bounds on weak scattering, Notre Dame Journal of Formal Logic, to appear, currently available at http://www.math.harvard.edu/~sacks/boundingws.pdf.Google Scholar
[51] Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, The Theory of Models (Addison, J., Henkin, L., and Tarski, A., editors), North-Holland, 1965, pp. 329–341.Google Scholar
[52] Shapiro, D. B., Composites of algebraically closed fields, Journal of Algebra, vol. 130 (1990), pp. 176–190.Google Scholar
[53] Shelah, S., The number of non-isomorphic models of an unstable first-order theory, Israel Journal of Mathematics, vol. 9 (1971), pp. 473–487.Google Scholar
[54] Shelah, S., Harrington, L., and Makkai, M., A proof of Vaught's Conjecture for totally transcendental theories, Israel Journal of Mathematics, vol. 49 (1984), pp. 259–278.Google Scholar
[55] Simpson, S., Subsystems of Second Order Arithmetic, Springer-Verlag, 1999.Google Scholar
[56] Steel, J., On Vaught's Conjecture, Cabal Seminar '76–'77: Proceedings of the Caltech–UCLA Logic Seminar 1976–'77 (Kechris, A. S. and Moschovakis, Y. N., editors), Springer-Verlag, 1978, pp. 193–208.Google Scholar
[57] Thomas, S., On the complexity of the classification problem for torsion-free Abelian groups of finite rank, this Bulletin, vol. 7 (2001), pp. 329–344.Google Scholar
[58] Vaught, R. L., Denumerable models of complete theories, Infinitistic Methods, Pergamon, 1961, pp. 303–321.Google Scholar
[59] Vaught, R. L., Invariant sets in topology and logic, Fundamenta Mathematicae, vol. 82 (1974/1975), pp. 269–294.Google Scholar