Source author record

Noah Schweber

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Self-full ceers and the uniform join operator

A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$ then the range of $f$ intersects all $X$ -equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question from \cite{joinmeet} by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $X\oplus Y$ is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$ , $X\oplus Y$ is also self-full: we show that they are closed under uniform join, and that every non-universal degree in $\textrm{Ceers}_{/{\mathcal{I}}}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers which is closed under $\oplus$ .

preprint2020arXiv

The Theory of Ceers Computes True Arithmetic

We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of $\mathcal{I}$ -degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of $(\mathbb{N},+,\cdot)$ .

preprint2014arXiv

Computable structures in generic extensions

In this paper, we investigate connections between structures present in every generic extension of the universe $V$ and computability theory. We introduce the notion of {\em generic Muchnik reducibility} that can be used to to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of {\em generic presentability}, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making $ω_2$ countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentble by a forcing notion that does not make $ω_2$ countable has a copy in the ground model. We also show that any countable structure $\mathcal{A}$ that is generically presentable by a forcing notion not collapsing $ω_1$ has a countable copy in $V$ , as does any structure $\mathcal{B}$ generically Muchnik reducible to a structure $\mathcal{A}$ of cardinality $\aleph_1$ . The former positive result yields a new proof of Harrington's result that counterexamples to Vaught's conjecture have models of power $\aleph_1$ with Scott rank arbitrarily high below $ω_2$ . Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.

preprint2013arXiv

Transfinite Recursion in Higher Reverse Mathematics

In this paper we investigate the reverse mathematics of higher-order analogues of the theory \ATRz{} within the framework of higher order reverse mathematics developed by Kohlenbach \cite{Koh01}. We define a theory \RCAzthr, a close higher-type analogue of the classical base theory \RCAz, and show that it is essentially a conservative subtheory of Kohlenbach's base theory \RCAzo. Working over \RCAzthr, we study higher-type analogues of statements classically equivalent to \ATRz, including open and clopen determinacy, as well as two choice principles, and prove several equivalences and separations. Our main result is the separation of open and clopen determinacy for reals, using a variant of Steel forcing; in the presentation of this result, we develop a new, more flexible framework for Steel-type forcing.

preprint2011arXiv

Computably enumerable partial orders

We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the former is strictly stronger than the latter. We then show that every $\emptyset'$ -computable structure (or even just of c.e.\ degree) has the same degree spectrum as some computably enumerable (co-c.e.)\ partial order, and hence that there is a c.e.\ (co-c.e.)\ partial order with spectrum equal to the set of nonzero degrees.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.