76 found
Order:
  1.  15
    Degree Spectra and Computable Dimensions in Algebraic Structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
    Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   35 citations  
  2. Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
    We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  3.  31
    Combinatorial Principles Weaker Than Ramsey's Theorem for Pairs.Denis R. Hirschfeldt & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (1):171-206.
    We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  4.  26
    Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.
    In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  5. Reverse Mathematics: The Playground of Logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
    This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  6.  25
    Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
    The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  7. A Computably Stable Structure with No Scott Family of Finitary Formulas.Peter Cholak, Richard A. Shore & Reed Solomon - 2006 - Archive for Mathematical Logic 45 (5):519-538.
  8.  37
    Pseudo-Jump Operators. II: Transfinite Iterations, Hierarchies and Minimal Covers.Carl G. Jockusch & Richard A. Shore - 1984 - Journal of Symbolic Logic 49 (4):1205 - 1236.
  9.  19
    Direct and Local Definitions of the Turing Jump.Richard A. Shore - 2007 - Journal of Mathematical Logic 7 (2):229-262.
    We show that there are Π5 formulas in the language of the Turing degrees, [Formula: see text], with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L2 = x ≥ y|x″ = y″} in any jump ideal containing 0. There are also Σ6&Π6 and Π8 formulas that define the relations w = x″ and w = x', respectively, in any such ideal [Formula: see text]. In the language with just ≤ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  10.  15
    Then-Rea Enumeration Degrees Are Dense.Alistair H. Lachlan & Richard A. Shore - 1992 - Archive for Mathematical Logic 31 (4):277-285.
  11.  38
    Computably Categorical Structures and Expansions by Constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  12.  25
    Π 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.
  13.  72
    The Maximal Linear Extension Theorem in Second Order Arithmetic.Alberto Marcone & Richard A. Shore - 2011 - Archive for Mathematical Logic 50 (5-6):543-564.
    We show that the maximal linear extension theorem for well partial orders is equivalent over RCA 0 to ATR 0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR 0 over RCA 0.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  14.  26
    Working Below a Low2 Recursively Enumerably Degree.Richard A. Shore & Theodore A. Slaman - 1990 - Archive for Mathematical Logic 29 (3):201-211.
  15. Σn Sets Which Are Δn-Incomparable.Richard A. Shore - 1974 - Journal of Symbolic Logic 39 (2):295 - 304.
  16.  18
    Countable Thin Π01 Classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
    Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  17. A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension.Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (4):1199-1241.
    Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  18.  35
    Topological Aspects of the Medvedev Lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
    We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  61
    Degree Structures: Local and Global Investigations.Richard A. Shore - 2006 - Bulletin of Symbolic Logic 12 (3):369-389.
  20.  4
    A Non-Inversion Theorem for the Jump Operator.Richard A. Shore - 1988 - Annals of Pure and Applied Logic 40 (3):277-303.
  21. Definability in the Recursively Enumerable Degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
  22.  5
    Reducibility Orderings: Theories, Definability and Automorphisms.Anil Nerode & Richard A. Shore - 1980 - Annals of Mathematical Logic 18 (1):61-89.
  23.  20
    Working Below a High Recursively Enumerable Degree.Richard A. Shore & Theodore A. Slaman - 1993 - Journal of Symbolic Logic 58 (3):824-859.
  24.  29
    Highness and Bounding Minimal Pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  25. Decomposition and Infima in the Computably Enumerable Degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
    Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  26.  18
    Undecidability and 1-Types in the Recursively Enumerable Degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
    Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  27.  33
    The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
    We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  28.  87
    Nowhere Simple Sets and the Lattice of Recursively Enumerable Sets.Richard A. Shore - 1978 - Journal of Symbolic Logic 43 (2):322-330.
  29.  40
    The Prospects for Mathematical Logic in the Twenty-First Century.Samuel R. Buss, Alexander S. Kechris, Anand Pillay & Richard A. Shore - 2001 - Bulletin of Symbolic Logic 7 (2):169-196.
    The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  30. The Reviews.Richard A. Shore - 2003 - Bulletin of Symbolic Logic 9 (1):1-2.
  31.  28
    On Homogeneity and Definability in the First-Order Theory of the Turing Degrees.Richard A. Shore - 1982 - Journal of Symbolic Logic 47 (1):8-16.
  32.  44
    Degree Theoretic Definitions of the Low2 Recursively Enumerable Sets.Rod Downey & Richard A. Shore - 1995 - Journal of Symbolic Logic 60 (3):727 - 756.
  33.  17
    Recursion Theory.Anil Nerode & Richard A. Shore (eds.) - 1985 - American Mathematical Society.
    iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  34.  34
    Boolean Algebras, Tarski Invariants, and Index Sets.Barbara F. Csima, Antonio Montalbán & Richard A. Shore - 2006 - Notre Dame Journal of Formal Logic 47 (1):1-23.
    Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  35.  19
    The Theory of the Metarecursively Enumerable Degrees.Noam Greenberg, Richard A. Shore & Theodore A. Slaman - 2006 - Journal of Mathematical Logic 6 (1):49-68.
    Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as [Formula: see text] or, equivalently, that of the truth set of [Formula: see text].
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  36.  9
    Minimal Α-Degrees.Richard A. Shore - 1972 - Annals of Mathematical Logic 4 (4):393-414.
  37.  14
    Controlling the Dependence Degree of a Recursive Enumerable Vector Space.Richard A. Shore - 1978 - Journal of Symbolic Logic 43 (1):13-22.
  38.  21
    Lattice Initial Segments of the Hyperdegrees.Richard A. Shore & Bjørn Kjos-Hanssen - 2010 - Journal of Symbolic Logic 75 (1):103-130.
    We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $\scr{D}_{h}$ . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of $\scr{D}_{h}$ . Corollaries include the decidability of the two quantifier theory of $\scr{D}_{h}$ and the undecidability of its three quantifier theory. The key tool in the proof is a (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  39.  19
    Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
    . We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  40.  84
    The N-R.E. Degrees: Undecidability and Σ1 Substructures.Mingzhong Cai, Richard A. Shore & Theodore A. Slaman - 2012 - Journal of Mathematical Logic 12 (1):1250005-.
    We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  41.  27
    Some More Minimal Pairs of Α-Recursively Enumerable Degrees.Richard A. Shore - 1978 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 24 (25-30):409-418.
  42.  19
    Local Definitions in Degeree Structures: The Turing Jump, Hyperdegrees and Beyond.Richard A. Shore - 2007 - Bulletin of Symbolic Logic 13 (2):226-239.
    There are $\Pi_5$ formulas in the language of the Turing degrees, D, with ≤, ∨ and $\vedge$ , that define the relations $x" \leq y"$ , x" = y" and so $x \in L_{2}(y)=\{x\geqy|x"=y"\}$ in any jump ideal containing $0^(\omega)$ . There are also $\Sigma_6$ & $\Pi_6$ and $\Pi_8$ formulas that define the relations w = x" and w = x', respectively, in any such ideal I. In the language with just ≤ the quantifier complexity of each of these definitions (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  43.  21
    Types of Simple Α-Recursively Enumerable Sets.Anne Leggett & Richard A. Shore - 1976 - Journal of Symbolic Logic 41 (3):681-694.
  44.  8
    Interpreting True Arithmetic in the Theory of the R.E. Truth Table Degrees.André Nies & Richard A. Shore - 1995 - Annals of Pure and Applied Logic 75 (3):269-311.
    We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  45.  23
    Generalized High Degrees Have the Complementation Property.Noam Greenberg, Antonio Montalbán & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (4):1200-1220.
  46.  9
    The Settling-Time Reducibility Ordering.Barbara F. Csima & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (3):1055 - 1071.
    To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st A) if for every computable function f, for all but finitely many x, mB(x) > f(m₄(x)). This settling-time ordering, which is a natural extension to an ordering of the (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  23
    Undecidability and Initial Segments of the (R.E.) TT-Degrees.Christine Ann Haught & Richard A. Shore - 1990 - Journal of Symbolic Logic 55 (3):987-1006.
  48.  12
    Undecidability and 1-Types in Intervals of the Computably Enumerable Degrees.Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore - 2000 - Annals of Pure and Applied Logic 106 (1-3):1-47.
    We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  49.  18
    On the Jumps of the Degrees Below a Recursively Enumerable Degree.David R. Belanger & Richard A. Shore - 2018 - Notre Dame Journal of Formal Logic 59 (1):91-107.
    We consider the set of jumps below a Turing degree, given by JB={x':x≤a}, with a focus on the problem: Which recursively enumerable degrees a are uniquely determined by JB? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order R of r.e. degrees. Namely, we show that if every high2 r.e. degree a is determined by JB, then R cannot have a nontrivial automorphism. We then defeat the strategy—at least in the form presented—by constructing (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  50.  21
    The Turing Degrees Below Generics and Randoms.Richard A. Shore - 2014 - Journal of Symbolic Logic 79 (1):171-178.
    If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 76