Noam Greenberg
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Noam Greenberg has a total of 59 co-authors. Here are the top co-authors by number of shared publications:
- André Nies
University of Auckland
13 shared publications - Joseph S. Miller
University of Wisconsin–Madison
10 shared publications - Dan Turetsky
Victoria University of Wellington
7 shared publications - Dan Turetsky
School of Mathematics and Statistics, Victoria University of Wellington, Wellington, New Zealand
6 shared publications - Rod Downey
Victoria University
6 shared publications - Daniel Turetsky
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITY OF VIENNA VIENNA, AUSTRIA
5 shared publications
Latest Publications
- 24 June 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-23
CHARACTERISING SJT REDUCIBILITY
SJT reducibility between sets $A,B \subseteq \mathbb N$ upper A comma upper B subset of or equal to double struck upper N is defined by $A \le _{SJT} B$ upper A less than or equals Subscript upper S upper J upper T Baseline upper B if for each computable function h that is unbounded and nondecreasing, there is an h -bounded uniformly B -c.e. trace $(T_n)_{n \in \mathbb N} $ left parenthesis upper T Subscript n Baseline right parenthesis Subscript n element of double struck upper N such that for each n , the value $J^A(n)$ upper J Superscript upper A Baseline left parenthesis n right parenthesis of the jump is in $T_n$ upper T Subscript n , if defined. This reducibility is slightly weaker than Turing reducibility. We study SJT reducibility, and as a main result give several characterisations of it on the K -trivial sets. This is the first case of extending the three lowness paradigms, weak as an oracle, computed by many, and inert, to the setting of weak reducibilities.- 24 June 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-23
CHARACTERISING SJT REDUCIBILITY
SJT reducibility between sets $A,B \subseteq \mathbb N$ upper A comma upper B subset of or equal to double struck upper N is defined by $A \le _{SJT} B$ upper A less than or equals Subscript upper S upper J upper T Baseline upper B if for each computable function h that is unbounded and nondecreasing, there is an h -bounded uniformly B -c.e. trace $(T_n)_{n \in \mathbb N} $ left parenthesis upper T Subscript n Baseline right parenthesis Subscript n element of double struck upper N such that for each n , the value $J^A(n)$ upper J Superscript upper A Baseline left parenthesis n right parenthesis of the jump is in $T_n$ upper T Subscript n , if defined. This reducibility is slightly weaker than Turing reducibility. We study SJT reducibility, and as a main result give several characterisations of it on the K -trivial sets. This is the first case of extending the three lowness paradigms, weak as an oracle, computed by many, and inert, to the setting of weak reducibilities.- Open Access
- 16 April 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-34
BOREL WADGE CLASSES AND SELIVANOV’S FINE HIERARCHY I: EXTENDING TO THE HYPERARITHMETIC
We show how to extend Selivanov’s fine hierarchy using descriptions of Borel Wadge classes. We give a game characterisation of containment between classes. We show that every class in the extended fine hierarchy has an admissible description, and use this to calculate heights in the hierarchy.
- 16 April 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-34
Open AccessBOREL WADGE CLASSES AND SELIVANOV’S FINE HIERARCHY I: EXTENDING TO THE HYPERARITHMETIC
We show how to extend Selivanov’s fine hierarchy using descriptions of Borel Wadge classes. We give a game characterisation of containment between classes. We show that every class in the extended fine hierarchy has an admissible description, and use this to calculate heights in the hierarchy.
- 27 March 2026
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Borel Wadge classes and Selivanov’s fine hierarchy II: Turing degrees
We answer the question: which levels of Selivanov’s fine hierarchy contain new Turing degrees?
- 27 March 2026
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Borel Wadge classes and Selivanov’s fine hierarchy II: Turing degrees
We answer the question: which levels of Selivanov’s fine hierarchy contain new Turing degrees?
- Open Access
- 6 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
The geometry of computable Banach spaces
- 6 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
Open AccessThe geometry of computable Banach spaces
- Open Access
Forcing and classes of $\mathsf{HYP}$-dominating functions
This paper is aimed at showing separations between three subsets of $ω^ω$, namely $\mathsf{HYP}\text{-}\mathsf{SNE}$, $\mathsf{HYP}\text{-}\mathsf{SME}$, and $\mathsf{HYP}\text{-}\mathsf{DOM}$. These classes are natural computational analogues of cardinal characteristics from Cichon's diagram and are known to satisfy $\mathsf{HYP}\text{-}\mathsf{SNE} \subseteq \mathsf{HYP}\text{-}\mathsf{SME} \subseteq \mathsf{HYP}\text{-}\mathsf{DOM}$. To show that both of these inclusions are strict we introduce effectivizations of Laver and Hechler forcing, which we believe are of independent interest. Our techniques allow us to show similar results relative to any Turing ideal closed under $\leq_{\mathsf{HYP}}$.Open AccessForcing and classes of $\mathsf{HYP}$-dominating functions
This paper is aimed at showing separations between three subsets of $ω^ω$, namely $\mathsf{HYP}\text{-}\mathsf{SNE}$, $\mathsf{HYP}\text{-}\mathsf{SME}$, and $\mathsf{HYP}\text{-}\mathsf{DOM}$. These classes are natural computational analogues of cardinal characteristics from Cichon's diagram and are known to satisfy $\mathsf{HYP}\text{-}\mathsf{SNE} \subseteq \mathsf{HYP}\text{-}\mathsf{SME} \subseteq \mathsf{HYP}\text{-}\mathsf{DOM}$. To show that both of these inclusions are strict we introduce effectivizations of Laver and Hechler forcing, which we believe are of independent interest. Our techniques allow us to show similar results relative to any Turing ideal closed under $\leq_{\mathsf{HYP}}$. - 28 August 2025
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Effective separation and reduction properties of Borel Wadge classes
In this paper, we use our descriptions of Borel Wadge classes from [A. R. Day, N. Greenberg, M. Harrison-Trainor and D. Turetsky, An effective classification of Borel Wadge classes] to characterize those Borel Wadge classes that have the separation property, and those that have the reduction property. Our analysis shows that both properties are equivalent to their effective versions. To do so, we give a characterization of containment between Borel Wadge classes based on their descriptions, and give a direct proof that all such classes admit admissible descriptions.
- 28 August 2025
- Published by World Scientific Pub Co Pte Ltd in Journal of Mathematical Logic
Effective separation and reduction properties of Borel Wadge classes
In this paper, we use our descriptions of Borel Wadge classes from [A. R. Day, N. Greenberg, M. Harrison-Trainor and D. Turetsky, An effective classification of Borel Wadge classes] to characterize those Borel Wadge classes that have the separation property, and those that have the reduction property. Our analysis shows that both properties are equivalent to their effective versions. To do so, we give a characterization of containment between Borel Wadge classes based on their descriptions, and give a direct proof that all such classes admit admissible descriptions.
- 20 May 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
An effective classification of Borel Wadge classes
We give a new and effective classification of all Borel Wadge classes of subsets of Baire space \mathcal{N} . This relies on the true stage machinery originally developed by Montalbán. We use this machinery to give a new proof of Louveau and Saint Raymond’s separation theorem for Borel Wadge classes. This gives a proof of Borel Wadge determinacy in the subsystem \mathsf{ATR}_{0}+\Pi^{1}_{1}\text{-}\mathsf{IND} of second-order arithmetic.
- 20 May 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
An effective classification of Borel Wadge classes
We give a new and effective classification of all Borel Wadge classes of subsets of Baire space \mathcal{N} . This relies on the true stage machinery originally developed by Montalbán. We use this machinery to give a new proof of Louveau and Saint Raymond’s separation theorem for Borel Wadge classes. This gives a proof of Borel Wadge determinacy in the subsystem \mathsf{ATR}_{0}+\Pi^{1}_{1}\text{-}\mathsf{IND} of second-order arithmetic.
- Open Access
- 7 April 2024
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 30 (2) , 199-226
ITERATED PRIORITY ARGUMENTS IN DESCRIPTIVE SET THEORY
We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff–Kuratowski and Wadge theorems on the structure of $\mathbf {\Delta }^0_\xi $ , Louveau and Saint Raymond’s separation theorem, and Louveau’s separation theorem.- 7 April 2024
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 30 (2) , 199-226
Open AccessITERATED PRIORITY ARGUMENTS IN DESCRIPTIVE SET THEORY
We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff–Kuratowski and Wadge theorems on the structure of $\mathbf {\Delta }^0_\xi $ , Louveau and Saint Raymond’s separation theorem, and Louveau’s separation theorem. - Open Access
- 13 November 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 260 (1) , 261-301
Martin–Löf reducibility and cost functions
Martin-Löf (ML)-reducibility compares the complexity of K-trivial sets of natural numbers by examining the Martin-Löf random sequences that compute them. One says that a K-trivial set A is ML-reducible to a K-trivial set B if every ML-random computing B also computes A. We show that every K-trivial set is computable from a c.e. set of the same ML-degree. We investigate the interplay between ML-reducibility and cost functions, which are used to both measure the number of changes in a computable approximation, and the type of null sets intended to capture ML-random sequences. We show that for every cost function there is a c.e. set that is ML-complete among the sets obeying it. We characterise the K-trivial sets computable from a fragment of the left-c.e. random real Ω given by a computable set of bit positions. This leads to a new characterisation of strong jump-traceability.
- 13 November 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 260 (1) , 261-301
Open AccessMartin–Löf reducibility and cost functions
Martin-Löf (ML)-reducibility compares the complexity of K-trivial sets of natural numbers by examining the Martin-Löf random sequences that compute them. One says that a K-trivial set A is ML-reducible to a K-trivial set B if every ML-random computing B also computes A. We show that every K-trivial set is computable from a c.e. set of the same ML-degree. We investigate the interplay between ML-reducibility and cost functions, which are used to both measure the number of changes in a computable approximation, and the type of null sets intended to capture ML-random sequences. We show that for every cost function there is a c.e. set that is ML-complete among the sets obeying it. We characterise the K-trivial sets computable from a fragment of the left-c.e. random real Ω given by a computable set of bit positions. This leads to a new characterisation of strong jump-traceability.
- Open Access
- 13 November 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 261 (1) , 1-44
Many forcing axioms for all regular uncountable cardinals
- 13 November 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 261 (1) , 1-44
Open AccessMany forcing axioms for all regular uncountable cardinals