70 found
Sort by:
  1. Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore (2013). Degrees of Categoricity and the Hyperarithmetic Hierarchy. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Mingzhong Cai & Richard A. Shore (2012). Domination, Forcing, Array Nonrecursiveness and Relative Recursive Enumerability. Journal of Symbolic Logic 77 (1):33-48.
    We present some abstract theorems showing how domination properties equivalent to being $\overline{GL}_{2}$ or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in $\overline{GL}_{2}$ is recursively enumerable in a 1-generic degree strictly below it. Our major new result is (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Mingzhong Cai, Richard A. Shore & Theodore A. Slaman (2012). The N-R.E. Degrees: Undecidability and Σ1substructures. Journal of Mathematical Logic 12 (01):1250005-.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Alberto Marcone, Antonio Montalbán & Richard A. Shore (2012). Computing Maximal Chains. Archive for Mathematical Logic 51 (5-6):651-660.
    In (Fund Math 60:175–186 1967), Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk’s original result (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Andrew Em Lewis, Richard A. Shore & Andrea Sorbi (2011). Topological Aspects of the Medvedev Lattice. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Alberto Marcone & Richard A. Shore (2011). The Maximal Linear Extension Theorem in Second Order Arithmetic. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Richard A. Shore (2010). Reverse Mathematics: The Playground of Logic. 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 (7 more)  
     
    My bibliography  
     
    Export citation  
  8. Richard A. Shore & Bjørn Kjos-Hanssen (2010). Lattice Initial Segments of the Hyperdegrees. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Barbara F. Csima & Richard A. Shore (2007). The Settling-Time Reducibility Ordering. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Denis R. Hirschfeldt & Richard A. Shore (2007). Combinatorial Principles Weaker Than Ramsey's Theorem for Pairs. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  11. Richard A. Shore (2007). Direct and Local Definitions of the Turing Jump. Journal of Mathematical Logic 7 (02):229-262.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12. Richard A. Shore (2007). Local Definitions in Degeree Structures: The Turing Jump, Hyperdegrees and Beyond. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  13. Peter Cholak, Richard A. Shore & Reed Solomon (2006). A Computably Stable Structure with No Scott Family of Finitary Formulas. Archive for Mathematical Logic 45 (5):519-538.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  14. Barbara F. Csima, Antonio Montalbán & Richard A. Shore (2006). Boolean Algebras, Tarski Invariants, and Index Sets. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  15. Noam Greenberg, Richard A. Shore & Theodore A. Slaman (2006). The Theory of the Metarecursively Enumerable Degrees. Journal of Mathematical Logic 6 (01):49-68.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  16. Richard A. Shore (2006). Degree Structures: Local and Global Investigations. Bulletin of Symbolic Logic 12 (3):369-389.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  17. Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore (2004). Π11 Relations and Paths Through. Journal of Symbolic Logic 69 (2):585-611.
    Direct download  
     
    My bibliography  
     
    Export citation  
  18. Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore (2004). Π 1 1 Relations and Paths Through. Journal of Symbolic Logic 69 (2):585-611.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Noam Greenberg, Antonio Montalb�N. & Richard A. Shore (2004). Generalized High Degrees Have the Complementation Property. Journal of Symbolic Logic 69 (4):1200 - 1220.
    We show that if d $\in GH_1$ then D( $\leq$ d) has the complementation property, i.e.. for all a < d there is some b < d such that a $\wedge$ b = 0 and a $\vee$ b = d.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  20. Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore (2003). Decomposition and Infima in the Computably Enumerable Degrees. 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 (7 more)  
     
    My bibliography  
     
    Export citation  
  21. Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore (2003). A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension. 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 (8 more)  
     
    My bibliography  
     
    Export citation  
  22. Richard A. Shore (2003). President, Association for Symbolic Logic Department of Mathematics Cornell University Ithaca, Ny 14853, Usa. Bulletin of Symbolic Logic 9 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  23. Richard A. Shore (2003). The Reviews. Bulletin of Symbolic Logic 9 (1):1-2.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  24. Richard A. Shore (2003). The Reviews, Bull. Symbolic Logic 9, Iss. 1 (2003). Bulletin of Symbolic Logic 9 (1):1-2.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  25. Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko (2002). Degree Spectra and Computable Dimensions in Algebraic Structures. Annals of Pure and Applied Logic 115 (1-3):71-113.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  26. Samuel R. Buss, Alexander S. Kechris, Anand Pillay & Richard A. Shore (2001). The Prospects for Mathematical Logic in the Twenty-First Century. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  27. Peter A. Fejer & Richard A. Shore (2001). Every Incomplete Computably Enumerable Truth-Table Degree is Branching. Archive for Mathematical Logic 40 (2):113-123.
    If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  28. Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore (2000). Undecidability and 1-Types in Intervals of the Computably Enumerable Degrees. Annals of Pure and Applied Logic 106 (1-3):1-47.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  29. Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore (1999). Computably Categorical Structures and Expansions by Constants. Journal of Symbolic Logic 64 (1):13-37.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  30. Bakhadyr Khoussainov & Richard A. Shore (1999). Erratum to “Computable Isomorphisms, Degree Spectra of Relations, and Scott Families” [Ann. Pure Appl. Logic 93 (1998) 153–193]. [REVIEW] Annals of Pure and Applied Logic 98 (1-3):297-298.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  31. R. G. Downey & Richard A. Shore (1998). Splitting Theorems and the Jump Operator. Annals of Pure and Applied Logic 94 (1-3):45-52.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  32. Bakhadyr Khoussainov & Richard A. Shore (1998). Computable Isomorphisms, Degree Spectra of Relations, and Scott Families. Annals of Pure and Applied Logic 93 (1-3):153-193.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. Bakhadyr Khoussainov, Andre Nies & Richard A. Shore (1997). Computable Models of Theories with Few Models. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  34. Richard A. Shore (1997). Alonzo Church. Bulletin of Symbolic Logic 3 (2):153.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  35. Richard A. Shore (1997). Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability. Archive for Mathematical Logic 36 (4-5):233-253.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  36. Richard A. Shore (1997). Preface. Annals of Pure and Applied Logic 87 (2):101-102.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  37. Marat Arslanov, Steffen Lempp & Richard A. Shore (1996). Interpolating D-R.E. And REA Degrees Between R.E. Degrees. Annals of Pure and Applied Logic 78 (1-3):29-56.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  38. Steffen Lemppl & Richard A. Shore (1996). On Isolating Re and Isolated Dr. E. Degrees. In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. 224--61.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  39. André Nies, Richard A. Shore & Theodore A. Slaman (1996). Definability in the Recursively Enumerable Degrees. Bulletin of Symbolic Logic 2 (4):392-404.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  40. Rod Downey & Richard A. Shore (1995). Degree Theoretic Definitions of the Low2 Recursively Enumerable Sets. Journal of Symbolic Logic 60 (3):727 - 756.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  41. André Nies & Richard A. Shore (1995). Interpreting True Arithmetic in the Theory of the R.E. Truth Table Degrees. Annals of Pure and Applied Logic 75 (3):269-311.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  42. Richard A. Shore (1995). 1994 European Summer Meeting of the Association for Symbolic Logic. Bulletin of Symbolic Logic 1 (2):203-268.
    Direct download  
     
    My bibliography  
     
    Export citation  
  43. Richard A. Shore (1995). The Bulletin of Symbolic Logic. Bulletin of Symbolic Logic 1 (1):1-3.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  44. Klaus Ambos-Spies & Richard A. Shore (1993). Undecidability and 1-Types in the Recursively Enumerable Degrees. Annals of Pure and Applied Logic 63 (1):3-37.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  45. Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore (1993). Countable Thin Π01 Classes. Annals of Pure and Applied Logic 59 (2):79-139.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  46. Rodney G. Downey, Steffen Lempp & Richard A. Shore (1993). Highness and Bounding Minimal Pairs. Mathematical Logic Quarterly 39 (1):475-491.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  47. Richard A. Shore (1993). Logical Methods in Mathematics and Computer Science: A Symposium in Honor of Anil Nerode's Sixtieth Birthday. Journal of Symbolic Logic 58 (3):1091-1092.
    Direct download  
     
    My bibliography  
     
    Export citation  
  48. Richard A. Shore & Theodore A. Slaman (1993). Working Below a High Recursively Enumerable Degree. Journal of Symbolic Logic 58 (3):824-859.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  49. Klaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 70