Richard A. Shore : Papers in Electronic Form

Most of the documents below have been compiled for optimum viewing in PDF format. However, some papers (for various reasons) look grainy as PDF files. Therefore, these papers are all also available in postscript and DVI format.

• Countable thin Pi₁⁰ classes, Annals of Pure and Applied Logic 59 (1993) 79-139 (with D. Cenzer, R. Downey and C. Jockusch).
  Also available in postscript or DVI format.

• Degree theoretic definitions of the low₂ r. e. sets, Journal of Symbolic Logic 60 (1995), 727-756 (with R. Downey).
  Also available in postscript or DVI format.

• Jumps of minimal degrees below 0', Journal of the London Mathematical Society 60 (1995), 727-756 (with R. Downey and S. Lempp).
  Also available in postscript or DVI format.

• Highness and bounding minimal pairs, Mathematical Logic Quarterly 39 (1993), 475-491 (with R. Downey and S. Lempp)
  Also available in postscript or DVI format.

• The theories of the T, tt and wtt r.e. degrees: undecidability and beyond, in Proc. IX Latin American Symposium on Mathematical Logic (part 1), Notas de Lo'gica Mathema'tica 38, Universidad Nacional del Sur, Bahia Blanca, Argentina, 1993, 61-70.
  Also available in postscript or DVI format.

• Conjectures and questions from Gerald Sacks's Degrees of Unsolvability, Archive for Mathematical Logic 36 (1997), 233-253.
  Also available in postscript or DVI format.

• Lattice embeddings below a nonlow₂ recursively enumerable degree, Israel Journal of Mathematics 94 (1996), 221-246 (with R. Downey).
  Also available in postscript or DVI format.

• Interpolating d-r.e. and REA degrees between r.e. degrees, Annals of Pure and Applied Logic 78 (1996), 29-56 (with M. Arslanov and S. Lempp).
  Also available in postscript or DVI format.

• On isolating r.e. and isolated d-r.e. degrees, in Computability, Enumerability, Unsolvability: Directions in Recursion Theory, S. B. Cooper, T. A. Slaman and S. S. Wainer eds., LMSLN 224, Cambridge University Press, Cambridge, England, 1996, 61-80 (with M. Arslanov and S. Lempp).
  Also available in postscript or DVI format.

• The recursively enumerable degrees, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, 1999, 169-197.
  Also available in postscript or DVI format.

• Intervals without critical triples, in Logic Colloquium '95, J. A. Makowsky and E. V. Ravve, eds., Lecture Notes in Logic 11, Springer-Verlag, Heidelberg, 1998, 17-43 (with P. Cholak and R. Downey).
  Also available in postscript or DVI format.

• Definability in the recursively enumerable degrees, Bulletin of Symbolic Logic 2 (1996), 392-404, (with A. Nies and T. Slaman).
  Also available in postscript or DVI format.

• Computably categorical structures and extensions by constants, Journal of Symbolic Logic, 64 (1999), 13-37 (with P. Cholak, S. Goncharov and B. Khoussainov).
  Also available in postscript or DVI format.

• Computable models of theories with few models, Notre Dame Journal of Formal Logic 38 (1997), 165-178 (with B. Khoussainov and A. Nies).
  Also available in postscript or DVI format.

• Splitting theorems and the jump operator, Annals of Pure and Applied Logic 94 (1997), 45-52 (with R. Downey).
  Also available in postscript or DVI format.

• There is no degree invariant half jump, Proc. Am Math. Soc. 125 (1997), 3033-3037 (with R. Downey).
  Also available in postscript or DVI format.

• Categoricity and Scott families, extended abstract, Combinatorics, Complexity and Logic, Proceedings of DMTCS '96, D. Bridges et al. eds., Springer-Verlag, Singapore, 1997, 299-308 (with B. Khoussainov).
  Also available in postscript or DVI format.

• Interpretability and definability in the recursively enumerable degrees, Proc. Lon. Math. Soc. (3) 77 (1998), 241-291 (with A. Nies and T. Slaman).
  Also available in postscript or DVI format.

• Computable Isomorphisms, Degree Spectra of Relations, and Scott Families, Annals of Pure and Applied Logic 93 (1998), 153-193 (with B. Khoussainov).
  Also available in postscript or DVI format.
  Revised version in postscript or DVI format.

• Undecidability and 1-types in intervals of the c.e. degrees, Annals of Pure and Applied Logic 106 (2000), 1-48 (with K. Ambos-Spies and D. Hirschfeldt).
  Also available in postscript or DVI format.

• Jumps of Sigma2-high e-degrees and properly Sigma2 e-degrees, in Recursion Theory and Complexity, M. Arslanov and S. Lempp eds., de Gruyter Series in Logic and its Applications 2, de Gruyter, Berlin, 1999, 157-172 (with A. Sorbi).
  Also available in postscript or DVI format.

• Effective model theory: the number of models and their compelxity in Models and Computability, Invited papers from Logic Colloquium '97, S. B. Cooper and J. K. Truss eds., LMSLNS 259, Cambridge University Press, Cambridge, England, 1999, 193-240 (with B. Khoussainov).
  Also available in postscript or DVI format.

• Every incomplete computably enumerable truth-table degree is branching, Archive for Mathematical Logic 40 (2001), 113-123 (with P. Fejer).
  Also available in postscript or DVI format.

• Reasoning about common knowledge with infinitely many agents, Information and Computation, 191 (2004), 1-40 (with J. Halpern).
  Also available in postscript as is the Extended abstract from the Proceedeings of LICS Meeting, Trento, Italy, July 1999 or DVI as is the Extended abstract from the Proceedeings of LICS Meeting, Trento, Italy, July 1999.

• Solutions of the Goncharov-Millar and degree spectra problems in the theory of computable models, Dokl. Akad. Nauk SSSR 371 (2000) 30--31 (Russian), English version: Doklady Mathematics 61 (2000), 178-179 (with B. Khoussainov).
  Also available in postscript or DVI format.

• Decomposition and infima in the computably enumerable degrees, Journal of Symbolic Logic, 68 (2003), 551-579 (with R. Downey and G. Laforte).
  Also available in postscript or DVI format.

• Degree spectra and computable dimension in algebraic structures, Annals of Pure and Applied Logic 115 (2002), 71-113 (with D. Hirschfeldt, B. Khoussainov and A. Slinko).
  Also available in postscript or DVI format.

• Natural definability in degree structures, in Computability Theory and Its Applications: Current Trends and Open Problems, P. Cholak, S. Lempp, M. Lerman and R. A. Shore eds., Contemporary Mathematics, AMS, Providence RI, 2000, 255-272.
  Also available in postscript or DVI format.

• A splitting theorem for n-REA degrees, Proc. American Mathematicl Society 129 (2001), 3721-3728 (with T. Slaman).
  Also available in postscript or DVI format.
  A follow up paper is A discrete splitting theorem for the 2-REA degrees (with T. Slaman).
  Also available in postscript or DVI format.

• Defining the Turing jump, Math. Research Letters 6 (1999), 711-722 (with T. Slaman).
  Also available in postscript or DVI format.

• Computable Structures: Presentations Matter, in In the scope of logic, methodology and the philosophy of science}, Int. Congress of LMPS, Cracow, August 1999, P. Gardenfors, J. Wolenski and K. Kijania-Placek eds., Synthese Library 315, Kluwer Academic Publishers, Dordrecht, 2002, vol. 1, 81-95.
  Also available in postscript or DVI format.

• A nonlow₂ r.e. degree with the extension of embeddings properties of a low₂ degree, Mathematical Logic Quarterly 6 (2002), no. 1 (with Y. Yang).
  Also available in postscript or DVI

• Intepreting arithmetic in the r.e. degrees under ISigma-4-induction, in Reverse Mathematics 2001, S. Simpson, ed., Lecture Notes in Logic 21, Association for Symbolic Logic, 2005 (with C. T. Chong and Y. Yang).
  Also available in postscript or DVI format.

• The prospects for mathematical logic in the twenty-first century, Bulletin of Symbolic Logic 7 (2001), 169-196 (with S. Buss, A. Kechris and A. Pillay).
  Also available in postscript or DVI format.

• The theory of the metarecursively enumerable degrees, Journal of Mathematical Logic, 6 (2006), 49-68 (with T. Slaman and N. Greenberg).
  Also available in postscript or DVI format.

• A computably categorical structure whose expansion by a constant has infinite computable dimension, Journal of Symbolic Logic 68 (2003), 1199-1241 (with D. Hirschfeldt and B. Khoussainov).
  Also available in postscript or DVI format.

• Undecidability of the AE-theory of $\mathcal{R}(\leq ,\vee ,\wedge ), Transactions of the American Mathematical Society 356 (2004), 3025-3067 (with A. Nies and R. Miller).
  Also available in postscript or DVI format.

• Minimal degrees which are Sigma_2 but not Delta_2, Proc. American Mathematicl Society 132 (2004), 563-565.
  Also available in postscript or DVI format.

• Pi^1_1 relations and paths through O, Journal of Symbolic Logic 69 (2004), 585-611 (with S.S. Goncharov, V. Harizanov and J. Knight).
  Also available in postscript or DVI format.

• The AE theory of $\mathcal{D}(\leq ,\vee ,^{\prime })$ is undecidable, in Logic Colloquium '03, Viggo Stoltenberg-Hansen and Jouko Vaananen eds., Lecture Notes in Logic 24, ASL, ASL, 2006, 326-344 (with T.A. Slaman).
  Also available in postscript or DVI format.

• Generalized high degrees have the complementatation property, Journal of Symbolic Logic 69 (2004), 1200-1220 (with N. Greenberg and A. Montalban).
  Also available in postscript or DVI format.

• Invariants, Boolean algebras and ACA_0^+ , Transactions of the American Mathematical Society, 358 (2006), 989-1014.
  Also available in postscript or DVI format.

• A computably stable structure with no Scott family of finitary formulas, Archive for Mathematical Logic, 45 (2006), 519-538 (with P. Cholak and R. Solomon).
  Also available in postscript or DVI format.

• Boolean Algebras, Tarski Invariants, and Index Sets , Notre Dame Journal of Formal Logic, 47 (2006), 1-23 (with B. Csima and A. Montalban).
  Also available in postscript or DVI format.

• The low-n and low-m r.e. degrees are not elementarily equivalent, Science in China A-Mathematics, 47 (2004), 950-956.
  Also available in postscript or DVI format.

• Rigidity and biinterpretability in the hyperdegrees, in Recursion Theory Worksphop:Proceedings of the IMS Program, Computational Prospects of Infinity, C. T. Chong , F. Qi and Y. Yang eds., World Scientific Publishing Co., Singapore, 2008, 299-312.
  Also available in postscript or DVI format.

• Combinatorial principles weaker than Ramsey's theorem for pairs, Journal of Symbolic Logic 72 (2007), 171-206 (with D. Hirschfeldt).
  Also available in postscript or DVI format.

• Degree Structures: Local and Global Investigations, Bulletin of Symbolic Logic, 12 (2006), 369-389.
  Also available in postscript or DVI format.

• The settling-time reducibility ordering, Journal of Symbolic Logic, 72 (2007), 1055-71 (with B. Csima).
  Also available in postscript or DVI format.

• Direct and local defintions of the Turing jump, Journal of Mathematical Logic, 7 (2007), 229-262.
  Also available in postscript or DVI format.

• Local definability in degree structures: the Turing jump, hyperdegrees and beyond, Bulletin of Symbolic Logic, 13 (2007), 226-239.
  Also available in postscript or DVI format.

• Lattice initial segments of the hyperdegrees, Journal of Symbolic Logic 75 (2010), 103- 130 (with B. Kjos-Hanssen).
  Also available in postscript or DVI format.

• The atomic model theorem, Transactions of the American Mathematical Society, 361 (2009), 5805-5837 (with D. Hirschfeldt and T. Slaman).
  Also available in postscript or DVI format.

• Domination, forcing, array nonrecursiveness and relative recursive enumerability, Journal of Symbolic Logic, 77 (2012), 226-239. (with M. Cai).
  Also available in postscript or DVI format.

• Reverse mathematics, countable and uncountable: a computational approach, Effective Mathematics of the Uncountable, D. Hirschfeldt, N. Greenbergm J. D. Hamkins and R. Miller, eds., Lecture Notes in Logic, ASL and Cambridge University Press, New York, 2013, 150-163.
  Also available in postscript or DVI format.

• Topological aspects of the Medvedev lattice, Archive for Mathematical Logic 50 (2011), 319-340 (with A. E. M. Lewis and A. Sorbi).
  Also available in postscript or DVI format.

• The limits of determinacy in second order arithmetic Proceedings of the London Mathematical Society 104 (3) (2012), 223-252 (with A. Montalban).
  Also available in postscript or DVI format.

• Reverse Mathematics: the Playground of Logic, Bulletin of Symbolic Logic 16 (2010), 378-402.
  Also available in postscript or DVI format.

• The n-r.e. degrees: undecidability and $\Sigma _{1}$ substructures, Journal of Mathematical Logic, 12 (2012), 1-30 (with M. Cai and T. Slaman).
  Also available in postscript or DVI format.

• The maximal linear extension theorem in second order arithmetic, Archive for Mathematical Logic 50 (2011), 543-564 (with A. Marcone).
  Also available in postscript or DVI format.

• Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame Journal of Formal Logic, 54 (2012), 215-232 (with B. F. Csima and J. Y. N. Franklin).
  Also available in postscript

• Computably enumerable partial orders, Computability, 1 (2012), 99-107 (with P. A. Cholak, D. D. Dzhafarov and N. Schweber).
  Also available in postscript or DVI format.

• Biinterpretability up to double jump in the degrees below 0', Proceedings of the American Mathematical Society, 142 (2014),351-360.
  Also available in postscript or DVI format.

• The Turing Degrees: An Introduction, in Forcing, Iterated Ultrapowers, and Turing Degrees, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore 29, eds. Chong Chi Tat, Feng Qi, Yang Yue, Theodore Slaman and Hugh Woodin, World Scientific Publishing, 2015, 39-121.
  Also available in postscript or DVI format.

• Computing maximal chains, Archive for Mathematical Logic 51 (2012), 651-660 (with A. Marcone and A. Montalban).
  Also available in postscript or DVI format.

• The complexity of ascendant sequences in locally nilpotent groups, International Journal of Algebra and Computation 24 (2014), 189-205 (with C. Conidis).
  Also available in DVI format.

• Low level nondefinability results: domination and recursive enumeration, Journal of Symbolic Logic 78 (2013), 1005-1024 (with M. Cai).
  Also available in postscript or DVI format.

• The Turing degrees below generics and randoms, Journal of Symbolic Logic, 79 (2014), 171-178..
  Also available in postscript or DVI format.

• The Limits of Determinacy in Second Order Arithmetic: Consistency and Complexity Strength, Israel Journal of Mathematics, 204 (2014), 477-508 (with A. Montalban).
  Also available in postscript or DVI format.

• The Strength of Turing Determinacy within Second Order Arithmetic, Fundamenta Mathematica, 232 (2016), 249-268 (with A. Montalban).
  Also available in postscript or DVI format.

• Induction, Bounding, Weak Combinatorial Principles, and The Homogeneous Model Theorem, Memoirs of the American Mathemactial Society 249, American Mathematical Society, Providence, R.I. 2107, vi + 101 (with D. Hirschfeldt and K. Lange). Also available in postscript or DVI format.

• On the jumps of the degrees below an r.e. degree, Notre Dame Journal of Formal Logic to appear (with D. Belanger).
  Also available in postscript or DVI format.

• The strength of the Graetzer-Schmidt theorem, Archive for Mathematical Logic, 55 (2016), 687-704 (with K. Brodhead, M. Khan, B. Kjos-Hansen, W A. Lampe and K. L. V. Nguyen).
  Also available in postscript or DVI format.

• Mass problems and density, Journal of Mathematical Logic 16 (2016), 1650006 (with S. Binns and S. Simpson).
  Also available in postscript or DVI format.

• Sigma ^1_1 in every real in a Sigma ^1_1 class of reals is Sigma ^1_1, in Computability and Complexity, Essays Dedicated to Rodney Downey on the Occasion of His 60th Birthday, A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov and F. Rosamond eds., Springer-Verlag, 2017, 455-468 (with L. Harrington and T. A. Slaman).
  Also available in postscript or DVI format.

• Conservativity of ultrafilters over subsystems of second order arithmetic, Journal of Symbolic Logic, 83 (2018), 740-765 (with A. Montalban).
  Also available in postscript or DVI format.

• Type omitting theorems for fragments of second order logics: classical and modal, to appear.
  

• Theorems of hyperarithmetic analysis and almost theorems of hyperarithmetic analysis, Bulletin of Symbolic Logic 28 (2022), 133-149 (with J. Barnes and J. L. Goh).
  

• Halin's infinite ray theorems: complexity and reverse mathmematics: Version E; this is a more leisurely prsentation the one to be published:
  Halin's infinite ray theorems: complexity and reverse mathmematics, Journal of Mathematical Logic, to appear (with J. Barnes and J. L. Goh).
  

• Almost theorems of hyperarithmetic analysis, Journal of Symbolic Logic, 88 (2023), 664-696.