32 found
Order:
  1.  28
    Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
    We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  2.  12
    Computing K-Trivial Sets by Incomplete Random Sets.Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies & Dan Turetsky - 2014 - Bulletin of Symbolic Logic 20 (1):80-90.
    EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  30
    Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
    We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity. We also consider Low(M, Kurtz), the class of degrees a such that every element of M is a-Kurtz random. These are characterised when M is the class of Martin-Löf random, computably random, or Schnorr random reals. (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  4.  26
    Uniform Almost Everywhere Domination.Peter Cholak, Noam Greenberg & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (3):1057 - 1072.
    We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  5.  14
    Anti-Complex Sets and Reducibilities with Tiny Use.Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan & Guohua Wu - 2013 - Journal of Symbolic Logic 78 (4):1307-1327.
  6.  8
    Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  74
    Totally Ω-Computably Enumerable Degrees and Bounding Critical Triples.Rod Downey, Noam Greenberg & Rebecca Weber - 2007 - Journal of Mathematical Logic 7 (2):145-171.
    We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  10
    Continuous Higher Randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
    We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see text]-trivial sets by higher (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  11
    Characterizing Lowness for Demuth Randomness.Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies & Dan Turetsky - 2014 - Journal of Symbolic Logic 79 (2):526-560.
    We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  46
    Two More Characterizations of K-Triviality.Noam Greenberg, Joseph S. Miller, Benoit Monin & Daniel Turetsky - 2018 - Notre Dame Journal of Formal Logic 59 (2):189-195.
    We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  38
    The Role of True Finiteness in the Admissible Recursively Enumerable Degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
    We show, however, that this is not always the case.
    Direct download (13 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  25
    Embedding and Coding Below a 1-Generic Degree.Noam Greenberg & Antonio Montalbán - 2003 - Notre Dame Journal of Formal Logic 44 (4):200-216.
  13.  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  
  14.  19
    Models of Cohen Measurability.Noam Greenberg & Saharon Shelah - 2014 - Annals of Pure and Applied Logic 165 (10):1557-1576.
    We show that in contrast with the Cohen version of Solovay's model, it is consistent for the continuum to be Cohen-measurable and for every function to be continuous on a non-meagre set.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  17
    Relative to Any Non-Hyperarithmetic Set.Noam Greenberg, Antonio Montalbán & Theodore A. Slaman - 2013 - Journal of Mathematical Logic 13 (1):1250007.
    We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  26
    A Random Set Which Only Computes Strongly Jump-Traceable C.E. Sets.Noam Greenberg - 2011 - Journal of Symbolic Logic 76 (2):700 - 718.
    We prove that there is a ${\mathrm{\Delta }}_{2}^{0}$ , 1-random set Y such that every computably enumerable set which is computable from Y is strongly jump-traceable. We also show that for every order function h there is an ω-c.e. random set Y such that every computably enumerable set which is computable from Y is h-jump-traceable. This establishes a correspondence between rates of jump-traceability and computability from ω-c.e. random sets.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  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.
  18.  11
    Models of Real-Valued Measurability.Sakae Fuchino, Noam Greenberg & Saharon Shelah - 2006 - Annals of Pure and Applied Logic 142 (1):380-397.
    Solovay’s random-real forcing [R.M. Solovay, Real-valued measurable cardinals, in: Axiomatic Set Theory , Amer. Math. Soc., Providence, R.I., 1971, pp. 397–428] is the standard way of producing real-valued measurable cardinals. Following questions of Fremlin, by giving a new construction, we show that there are combinatorial, measure-theoretic properties of Solovay’s model that do not follow from the existence of real-valued measurability.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  4
    The Upward Closure of a Perfect Thin Class.Rod Downey, Noam Greenberg & Joseph S. Miller - 2008 - Annals of Pure and Applied Logic 156 (1):51-58.
    There is a perfect thin class whose upward closure in the Turing degrees has full measure . Thus, in the Muchnik lattice of classes, the degree of 2-random reals is comparable with the degree of some perfect thin class. This solves a question of Simpson [S. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic 11 1–27].
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  30
    Galvin’s “Racing Pawns” Game, Internal Hyperarithmetic Comprehension, and the Law of Excluded Middle.Chris Conidis, Noam Greenberg & Daniel Turetsky - 2013 - Notre Dame Journal of Formal Logic 54 (2):233-252.
    We show that the fact that the first player wins every instance of Galvin’s “racing pawns” game is equivalent to arithmetic transfinite recursion. Along the way we analyze the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  21.  26
    Every 1-Generic Computes a Properly 1-Generic.Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1385 - 1393.
    A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  22.  8
    A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  18
    Conference on Computability, Complexity and Randomness.Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson - 2008 - Bulletin of Symbolic Logic 14 (4):548-549.
  24.  5
    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  
  25.  11
    Computability and Uncountable Linear Orders I: Computable Categoricity.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):116-144.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  26.  11
    Computability and Uncountable Linear Orders II: Degree Spectra.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):145-178.
  27.  12
    College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference “Bsl VII 376” Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW]Anuj Dawar Colyvan, Marcelo Fiore, Noam Greenberg, Hannes Leitgeb, Rahim Moosa, Ernest Schimmerling, Carsten Schürmann & Kai Wehmeier - 2011 - Bulletin of Symbolic Logic 17 (1).
    Direct download  
     
    Export citation  
     
    Bookmark  
  28.  9
    College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference “Bsl VII 376” Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW]Mark Colyvan Burgess, Anuj Dawar, Marcelo Fiore, Noam Greenberg, Hannes Leitgeb, Ernest Schimmerling, Carsten Schürmann & Kai Wehmeier - 2010 - Bulletin of Symbolic Logic 16 (3).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  8
    Ny 12604, Usa.Anuj Dawar Colyvan, Noam Greenberg, Rahim Moosa, Ernest Schimmerling & Alex Simp - 2012 - Bulletin of Symbolic Logic 18 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  30.  1
    Computing From Projections of Random Points.Noam Greenberg, Joseph S. Miller & André Nies - 2019 - Journal of Mathematical Logic 20 (1):1950014.
    We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  9
    Gainesville, Florida March 10–13, 2007.Michael Benedikt, Andreas Blass, Natasha Dobrinen, Noam Greenberg, Denis R. Hirschfeldt, Salma Kuhlmann, Hannes Leitgeb, William J. Mitchell & Thomas Wilke - 2007 - Bulletin of Symbolic Logic 13 (3).
    Direct download  
     
    Export citation  
     
    Bookmark  
  32.  5
    The Association for Symbolic Logic Publishes Analytical Reviews of Selected Books and Articles in the Field of Symbolic Logic. The Reviews Were Published in The Journal of Symbolic Logic From the Founding of the Journal in 1936 Until the End of 1999. The Association Moved the Reviews to This Bulletin, Beginning in 2000. The Reviews Section is Edited by Steve Awodey (Managing Editor), John Baldwin, John. [REVIEW]Mark Colyvan Burgess, Anuj Dawar, Marcelo Fiore, Noam Greenberg & Hannes Leitgeb - 2010 - Bulletin of Symbolic Logic 16 (1).