9 found
Order:
  1.  47
    Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
    We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  2. Classification from a computable viewpoint.Wesley Calvert & Julia F. Knight - 2006 - Bulletin of Symbolic Logic 12 (2):191-218.
    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 (...)
    Direct download (14 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  3.  36
    The Isomorphism Problem for Computable Abelian p-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
    Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  4.  27
    The isomorphism problem for classes of computable fields.Wesley Calvert - 2004 - Archive for Mathematical Logic 43 (3):327-336.
    Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only computable members. We follow recent work (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  5.  30
    Effective categoricity of Abelian p -groups.Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov - 2009 - Annals of Pure and Applied Logic 159 (1-2):187-197.
    We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6. On three notions of effective computation over R.Wesley Calvert - unknown
     
    Export citation  
     
    Bookmark  
  7.  28
    Structural Highness Notions.Wesley Calvert, Johanna N. Y. Franklin & Dan Turetsky - 2023 - Journal of Symbolic Logic 88 (4):1692-1724.
    We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  15
    Interpreting a Field in its Heisenberg Group.Rachael Alvir, Wesley Calvert, Grant Goodman, Valentina Harizanov, Julia Knight, Russell Miller, Andrey Morozov, Alexandra Soskova & Rose Weisshaar - 2022 - Journal of Symbolic Logic 87 (3):1215-1230.
    We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  40
    PAC learning, VC dimension, and the arithmetic hierarchy.Wesley Calvert - 2015 - Archive for Mathematical Logic 54 (7-8):871-883.
    We compute that the index set of PAC-learnable concept classes is m-complete Σ30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{3}}$$\end{document} within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable Π10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^{0}_{1}}$$\end{document} classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark