25 found
Order:
  1.  19
    Pairs of Recursive Structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
  2.  1
    Pairs of Computable Structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
  3.  34
    Real Closed Fields and Models of Peano Arithmetic.P. D'Aquino, J. F. Knight & S. Starchenko - 2010 - Journal of Symbolic Logic 75 (1):1-11.
    Shepherdson [14] showed that for a discrete ordered ring I, I is a model of IOpen iff I is an integer part of a real closed ordered field. In this paper, we consider integer parts satisfying PA. We show that if a real closed ordered field R has an integer part I that is a nonstandard model of PA (or even IΣ₄), then R must be recursively saturated. In particular, the real closure of I, RC (I), is recursively saturated. We (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  42
    Classes of Ulm Type and Coding Rank-Homogeneous Trees in Other Structures.E. Fokina, J. F. Knight, A. Melnikov, S. M. Quinn & C. Safranski - 2011 - Journal of Symbolic Logic 76 (3):846 - 869.
    The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  5.  15
    Index Sets and Scott Sentences.J. F. Knight & C. McCoy - 2014 - Archive for Mathematical Logic 53 (5-6):519-524.
    For a computable structure A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{A}}$$\end{document}, there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}, then the complexity of the index set I\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I}$$\end{document} is bounded by that of φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}. There are results giving “optimal” Scott sentences for (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  8
    Ramified Systems.C. J. Ash & J. F. Knight - 1994 - Annals of Pure and Applied Logic 70 (3):205-221.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  7.  13
    Possible Degrees in Recursive Copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
    We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions on a pair (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  8.  9
    Permitting, Forcing, and Copying of a Given Recursive Relation.C. J. Ash, P. Cholak & J. F. Knight - 1997 - Annals of Pure and Applied Logic 86 (3):219-236.
  9.  9
    Possible Degrees in Recursive Copies.C. J. Ash & J. F. Knight - 1995 - Annals of Pure and Applied Logic 75 (3):215-221.
    Let be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this is not the case. Here (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  10.  9
    Computable Structures of Rank.J. F. Knight & J. Millar - 2010 - Journal of Mathematical Logic 10 (1):31-43.
    For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical example due to Makkai, and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  26
    Mixed Systems.C. J. Ash & J. F. Knight - 1994 - Journal of Symbolic Logic 59 (4):1383-1399.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  12.  16
    A Metatheorem for Constructions by Finitely Many Workers.J. F. Knight - 1990 - Journal of Symbolic Logic 55 (2):787-804.
  13.  22
    Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
    This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is m-complete $\Sigma _{2}^{0}$ relative to O.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  14.  15
    Quasi-Simple Relations in Copies of a Given Recursive Structure.C. J. Ash, J. F. Knight & J. B. Remmel - 1997 - Annals of Pure and Applied Logic 86 (3):203-218.
  15.  14
    Corrigendum To: “Real Closed Fields and Models of Arithmetic”.P. D'Aquino, J. F. Knight & S. Starchenko - 2012 - Journal of Symbolic Logic 77 (2):726-726.
  16. Computable Structures of Rank Omega (Ck)(1).J. F. Knight & J. Millar - 2010 - Journal of Mathematical Logic 10 (1):31-43.
    For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical example due to Makkai, and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  39
    Categoricity of Computable Infinitary Theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
    Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank ${\omega_1^{CK}}$ , which guarantee that the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  18.  14
    Hanf Number for Scott Sentences of Computable Structures.S. S. Goncharov, J. F. Knight & I. Souldatos - 2018 - Archive for Mathematical Logic 57 (7-8):889-907.
    The Hanf number for a set S of sentences in \ is the least infinite cardinal \ such that for all \, if \ has models in all infinite cardinalities less than \, 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 \. The same argument proves that \ is the Hanf number for Scott sentences of hyperarithmetical structures.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  24
    An Example Related to Gregory’s Theorem.J. Johnson, J. F. Knight, V. Ocasio & S. VanDenDriessche - 2013 - Archive for Mathematical Logic 52 (3-4):419-434.
    In this paper, we give an example of a complete computable infinitary theory T with countable models ${\mathcal{M}}$ and ${\mathcal{N}}$ , where ${\mathcal{N}}$ is a proper computable infinitary extension of ${\mathcal{M}}$ and T has no uncountable model. In fact, ${\mathcal{M}}$ and ${\mathcal{N}}$ are (up to isomorphism) the only models of T. Moreover, for all computable ordinals α, the computable ${\Sigma_\alpha}$ part of T is hyperarithmetical. It follows from a theorem of Gregory (JSL 38:460–470, 1972; Not Am Math Soc 17:967–968, 1970) (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  20.  7
    Comparing Two Versions of the Reals.G. Igusa & J. F. Knight - 2016 - Journal of Symbolic Logic 81 (3):1115-1123.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  9
    Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
    Here we prove that if T and T′ are strongly minimal theories, where T′ satisfies a certain property related to triviality and T does not, and T′ is model complete, then there is no computable embedding of Mod(T) into Mod(T′). Using this, we answer a question from [4], showing that there is no computable embedding of VS into ZS, where VS is the class of infinite vector spaces over Q, and ZS is the class of models of Th(Z, S). Similarly, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  22.  5
    Coding a Family of Sets.J. F. Knight - 1998 - Annals of Pure and Applied Logic 94 (1-3):127-142.
    In this paper, we state a metatheorem for constructions involving coding. Using the metatheorem, we obtain results on coding a family of sets into a family of relations, or into a single relation. For a concrete example, we show that the set of limit points in a recursive ordering of type ω 2 can have arbitrary 2-REA degree.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  23. Hella, L., Kolaitis, PG and Luosto, K., How to Define a Linear.C. J. Ash, J. F. Knight, B. Balcar, T. Jech, J. Zapletal & D. Rubric - 1997 - Annals of Pure and Applied Logic 87:269.
     
    Export citation  
     
    Bookmark  
  24. Real Closed Fields and Models of Arithmetic (Vol 75, Pg 1, 2010).P. D'Aquino, J. F. Knight & S. Starchenko - 2012 - Journal of Symbolic Logic 77 (2).
  25. Griffor, ER, See Rathjen, M.L. Harrington, R. I. Soare, J. F. Knight & M. Lerman - 1998 - Annals of Pure and Applied Logic 94:297.
    No categories
     
    Export citation  
     
    Bookmark