37 found
Order:
  1.  32
    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   9 citations  
  2.  41
    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   10 citations  
  3.  16
    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.
  4.  19
    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  
  5.  3
    Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  32
    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  
  7.  8
    A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
    We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees and the array noncomputable degrees. The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  12
    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   2 citations  
  9.  75
    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   5 citations  
  10.  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  
  11.  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  
  12.  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   2 citations  
  13.  29
    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   2 citations  
  14.  1
    Relationships Between Computability‐Theoretic Properties of Problems.Rod Downey, Noam Greenberg, Matthew Harrison‐Trainor, Ludovic Patey & Dan Turetsky - forthcoming - Journal of Symbolic Logic:1-26.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  44
    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  
  16.  26
    Embedding and Coding Below a 1-Generic Degree.Noam Greenberg & Antonio Montalbán - 2003 - Notre Dame Journal of Formal Logic 44 (4):200-216.
  17.  20
    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  
  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.  5
    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.  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.
  21. Scott Complexity of Countable Structures.Rachel Alvir, Noam Greenberg, Matthew Harrison-Trainor & Dan Turetsky - forthcoming - Journal of Symbolic Logic:1-16.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  31
    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  
  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.  10
    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  
  25.  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  
  26.  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).
  27.  14
    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.  10
    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  
  29.  31
    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 (6 more)  
     
    Export citation  
     
    Bookmark  
  30. Cupping and Jump Classes in the Computably Enumerable Degrees.Noam Greenberg, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (4):1499-1545.
    We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are ${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed ${\operatorname {\mathrm {low}}}_n$ cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the ${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  13
    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  
  32.  15
    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.
  33.  3
    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  
  34.  5
    Non-Density in Punctual Computability.Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov & Dan Turetsky - 2021 - Annals of Pure and Applied Logic 172 (9):102985.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35.  56
    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 (3 more)  
     
    Export citation  
     
    Bookmark  
  36.  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  
  37.  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