56 found
Order:
  1.  37
    Degrees coded in jumps of orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
  2.  66
    Isomorphism relations on computable structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  3.  28
    Scott sentences for certain groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
    We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple as possible. We consider finitely generated groups and torsion-free abelian groups of finite rank. For both kinds of groups, the computable ones all have computable \ Scott sentences. Sometimes we can do better. In fact, the computable finitely generated groups that we have studied all have Scott sentences that are “computable d-\” sentence and a (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  4. Computable Boolean algebras.Julia F. Knight & Michael Stob - 2000 - Journal of Symbolic Logic 65 (4):1605-1623.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  5.  86
    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  
  6.  47
    Π 1 1 relations and paths through.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585-611.
  7.  57
    Computable Trees of Scott Rank [image] , and Computable Approximation.Wesley Calvert, Julia F. Knight & Jessica Millar - 2006 - Journal of Symbolic Logic 71 (1):283 - 298.
    Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  8. A complete L ω1ω-sentence characterizing ℵ1.Julia F. Knight - 1977 - Journal of Symbolic Logic 42 (1):59-62.
  9.  21
    Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
    Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δmath image sets, giving conditions under which a relation is intrinsically α-r. e.
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  10. Hanf numbers for omitting types over particular theories.Julia F. Knight - 1976 - Journal of Symbolic Logic 41 (3):583-588.
  11.  18
    Computing strength of structures related to the field of real numbers.Gregory Igusa, Julia F. Knight & Noah David Schweber - 2017 - Journal of Symbolic Logic 82 (1):137-150.
    In [8], the third author defined a reducibility$\le _w^{\rm{*}}$that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals${\cal R}$lies strictly above certain related structures. In the present paper, we show that$\left \equiv _w^{\rm{*}}{\cal R}$. More generally, for the weak-looking structure${\cal R}$ℚconsisting of the real numbers with just the ordering and constants naming the rationals, allo-minimal expansions of${\cal R}$ℚare equivalent to${\cal R}$. Using this, we show that (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  19
    Models and Types of Peano's Arithmetic.Haim Gaifman, Julia F. Knight, Fred G. Abramson & Leo A. Harrington - 1983 - Journal of Symbolic Logic 48 (2):484-485.
    Direct download  
     
    Export citation  
     
    Bookmark   5 citations  
  13. Barwise: Infinitary logic and admissible sets.H. Jerome Keisler & Julia F. Knight - 2004 - Bulletin of Symbolic Logic 10 (1):4-36.
    §0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46], and that of Platek [58], at Stanford, on admissible sets.Barwise's work on infinitary logic and admissible sets is described (...)
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  14.  18
    Coding in graphs and linear orderings.Julia F. Knight, Alexandra A. Soskova & Stefan V. Vatev - 2020 - Journal of Symbolic Logic 85 (2):673-690.
    There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  92
    Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.
    A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  16.  10
    Uniform procedures in uncountable structures.Noam Greenberg, Alexander G. Melnikov, Julia F. Knight & Daniel Turetsky - 2018 - Journal of Symbolic Logic 83 (2):529-550.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  67
    Decidability and Computability of Certain Torsion-Free Abelian Groups.Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky - 2010 - Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  18.  62
    Intrinsic bounds on complexity and definability at limit levels.John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn - 2009 - Journal of Symbolic Logic 74 (3):1047-1060.
    We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  19.  90
    Simple and immune relations on countable structures.Sergei S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Charles F. D. McCoy - 2003 - Archive for Mathematical Logic 42 (3):279-291.
    Let ???? be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of ???? in which the image of R (¬R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on ???? and R, a necessary and sufficient condition for the existence of a computable copy ℬ of ???? in which the image of R (¬R, resp.) (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  12
    Constructions by transfinitely many workers.Julia F. Knight - 1990 - Annals of Pure and Applied Logic 48 (3):237-259.
  21.  27
    Prime and atomic models.Julia F. Knight - 1978 - Journal of Symbolic Logic 43 (3):385-393.
  22. Nonarithmetical ℵ0-categorical theories with recursive models.Julia F. Knight - 1994 - Journal of Symbolic Logic 59 (1):106 - 112.
  23.  23
    Copying One of a Pair of Structures.Rachael Alvir, Hannah Burchfield & Julia F. Knight - 2022 - Journal of Symbolic Logic 87 (3):1201-1214.
    We ask when, for a pair of structures $\mathcal {A}_1,\mathcal {A}_2$, there is a uniform effective procedure that, given copies of the two structures, unlabeled, always produces a copy of $\mathcal {A}_1$. We give some conditions guaranteeing that there is such a procedure. The conditions might suggest that for the pair of orderings $\mathcal {A}_1$ of type $\omega _1^{CK}$ and $\mathcal {A}_2$ of Harrison type, there should not be any such procedure, but, in fact, there is one. We construct an (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  16
    Expanding the Reals by Continuous Functions Adds No Computational Power.Uri Andrews, Julia F. Knight, Rutger Kuyper, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1083-1102.
    We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  14
    Spectra of Atomic Theories.Uri Andrews & Julia F. Knight - 2009 - Journal of Symbolic Logic 78 (4):1189-1198.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  26.  14
    A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas.Christopher J. Ash & Julia F. Knight - 1994 - Mathematical Logic Quarterly 40 (2):173-181.
    We consider the following generalization of the notion of a structure recursive relative to a set X. A relational structure A is said to be a Γ-structure if for each relation symbol R, the interpretation of R in A is ∑math image relative to X, where β = Γ. We show that a certain, fairly obvious, description of classes ∑math image of recursive infinitary formulas has the property that if A is a Γ-structure and S is a further relation on (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  27.  27
    Meeting of the association for symbolic logic: Notre dame, indiana, 1984.John Baldwin, Matt Kaufmann & Julia F. Knight - 1985 - Journal of Symbolic Logic 50 (1):284-286.
  28.  16
    Representing Scott sets in algebraic settings.Alf Dolich, Julia F. Knight, Karen Lange & David Marker - 2015 - Archive for Mathematical Logic 54 (5-6):631-637.
    We prove that for every Scott set S there are S-saturated real closed fields and S-saturated models of Presburger arithmetic.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  29.  46
    Chains and antichains in partial orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - Archive for Mathematical Logic 48 (1):39-53.
    We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  30.  40
    Sequences of n-diagrams.Valentina S. Harizanov, Julia F. Knight & Andrei S. Morozov - 2002 - Journal of Symbolic Logic 67 (3):1227-1247.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  8
    Meeting of the Association for Symbolic Logic.Baldwin John, Matt Kaufmann & Julia F. Knight - 1985 - Journal of Symbolic Logic 50 (1):284-286.
  32.  10
    A Complete $L{omega 1omega}$-Sentence Characterizing $mathbf{aleph}1$.Julia F. Knight - 1977 - Journal of Symbolic Logic 42 (1):59-62.
  33.  17
    Algebraic independence.Julia F. Knight - 1981 - Journal of Symbolic Logic 46 (2):377-384.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  34.  12
    An inelastic model with indiscernibles.Julia F. Knight - 1978 - Journal of Symbolic Logic 43 (2):331-334.
  35.  26
    Additive structure in uncountable models for a fixed completion of P.Julia F. Knight - 1983 - Journal of Symbolic Logic 48 (3):623-628.
  36.  14
    Complete types and the natural numbers.Julia F. Knight - 1973 - Journal of Symbolic Logic 38 (3):413-415.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  37.  26
    Degrees of types and independent sequences.Julia F. Knight - 1983 - Journal of Symbolic Logic 48 (4):1074-1081.
  38.  24
    Generic expansions of structures.Julia F. Knight - 1973 - Journal of Symbolic Logic 38 (4):561-570.
  39.  43
    In memoriam: Christopher John Ash.Julia F. Knight - 1995 - Bulletin of Symbolic Logic 1 (2):202.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  40.  27
    Jon Barwise and John Schlipf. An introduction to recursively saturated and resplendent models. The journal of symbolic logic, vol. 41 , pp. 531–536.Julia F. Knight - 1982 - Journal of Symbolic Logic 47 (2):440.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  41.  18
    John Gregory. Uncountable models and infinitary elementary extensions. The journal of symbolic logic, vol. 38 , pp. 460–470.Julia F. Knight - 1982 - Journal of Symbolic Logic 47 (2):438-439.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  42.  34
    Minimality and completions of PA.Julia F. Knight - 2001 - Journal of Symbolic Logic 66 (3):1447-1457.
  43.  78
    Meeting of the association for symbolic logic: San Antonio, 1987.Julia F. Knight - 1988 - Journal of Symbolic Logic 53 (3):1000-1006.
  44.  4
    Meeting of the Association for Symbolic Logic.Julia F. Knight - 1988 - Journal of Symbolic Logic 53 (3):1000-1006.
  45.  33
    Omitting types in set theory and arithmetic.Julia F. Knight - 1976 - Journal of Symbolic Logic 41 (1):25-32.
  46.  26
    Requirement systems.Julia F. Knight - 1995 - Journal of Symbolic Logic 60 (1):222-245.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  31
    Skolem functions and elementary embeddings.Julia F. Knight - 1977 - Journal of Symbolic Logic 42 (1):94-98.
  48.  26
    Saturation of homogeneous resplendent models.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (1):222-224.
  49.  29
    Types omitted in uncountable models of arithmetic.Julia F. Knight - 1975 - Journal of Symbolic Logic 40 (3):317-320.
  50.  13
    University of California, San Diego, March 20–23, 1999.Julia F. Knight, Steffen Lempp, Toniann Pitassi, Hans Schoutens, Simon Thomas, Victor Vianu & Jindrich Zapletal - 1999 - Bulletin of Symbolic Logic 5 (3).
1 — 50 / 56