Source author record

Stephen G. Simpson

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

ResearcherUnclaimed source record

math.LO math.RA

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Pseudojump inversion in special r. b. $Π^0_1$ classes

The Jump Inversion Theorem says that for every real $A \ge_T 0'$ there is a real $B$ such that $A \equiv_T B' \equiv_T B \oplus 0'$ . A known refinement of this theorem says that we can choose $B$ to be a member of any special $Π^0_1$ subclass of $\{0,1\}^ω$ . We now consider the possibility of analogous refinements of two other well-known theorems: the Join Theorem -- for all reals $A$ and $Z$ such that $A \ge_T Z \oplus 0'$ and $Z >_T 0$ , there is a real $B$ such that $A \equiv_T B' \equiv_T B \oplus 0' \equiv_T B \oplus Z$ -- and the Pseudojump Inversion Theorem -- for all reals $A \ge_T 0'$ and every $e \in ω$ , there is a real $B$ such that $A \equiv_T B \oplus W_e^B \equiv_T B \oplus 0'$ . We show that in these theorems, $B$ can be found in some special $Π^0_1$ subclasses of $\{0,1\}^ω$ but not in others.

preprint2021arXiv

Very weak fragments of weak Kőnig's lemma

It is well-known that any finite $Π^{0}_{1}$ -class of $2^{\mathbb N}$ has a computable member. Then, how can we understand this in the context of reverse mathematics? In this note, we consider several very weak fragments of Kőnig's lemma to answer this qeustion.

preprint2015arXiv

Comparing WO $(ω^ω)$ with $Σ^0_2$ induction

Let WO $(ω^ω)$ be the statement that the ordinal number $ω^ω$ is well ordered. WO $(ω^ω)$ has occurred several times in the reverse-mathematical literature. The purpose of this expository note is to discuss the place of WO $(ω^ω)$ within the standard hierarchy of subsystems of second-order arithmetic. We prove that WO $(ω^ω)$ is implied by I $Σ^0_2$ and independent of B $Σ^0_2$ . We also prove that WO $(ω^ω)$ and B $Σ^0_2$ together do not imply I $Σ^0_2$ .

preprint2015arXiv

Reverse mathematics, Young diagrams, and the ascending chain condition

Let $S$ be the group of finitely supported permutations of a countably infinite set. Let $K[S]$ be the group algebra of $S$ over a field $K$ of characteristic $0$ . According to a theorem of Formanek and Lawrence, $K[S]$ satisfies the ascending chain condition for two-sided ideals. We study the reverse mathematics of this theorem, proving its equivalence over RCA $_0$ (or even over RCA $_0^*$ ) to the statement that $ω^ω$ is well ordered. Our equivalence proof proceeds via the statement that the Young diagrams form a well partial ordering.

preprint2014arXiv

Mass problems and intuitionistic higher-order logic

In this paper we study a model of intuitionistic higher-order logic which we call \emph{the Muchnik topos}. The Muchnik topos may be defined briefly as the category of sheaves of sets over the topological space consisting of the Turing degrees, where the Turing cones form a base for the topology. We note that our Muchnik topos interpretation of intuitionistic mathematics is an extension of the well known Kolmogorov/Muchnik interpretation of intuitionistic propositional calculus via Muchnik degrees, i.e., mass problems under weak reducibility. We introduce a new sheaf representation of the intuitionistic real numbers, \emph{the Muchnik reals}, which are different from the Cauchy reals and the Dedekind reals. Within the Muchnik topos we obtain a \emph{choice principle} $(\forall x\,\exists y\,A(x,y))\Rightarrow\exists w\,\forall x\,A(x,wx)$ and a \emph{bounding principle} $(\forall x\,\exists y\,A(x,y))\Rightarrow\exists z\,\forall x\,\exists y\,(y\le_{\mathrm{T}}(x,z)\land A(x,y))$ where $x,y,z$ range over Muchnik reals, $w$ ranges over functions from Muchnik reals to Muchnik reals, and $A(x,y)$ is a formula not containing $w$ or $z$ . For the convenience of the reader, we explain all of the essential background material on intuitionism, sheaf theory, intuitionistic higher-order logic, Turing degrees, mass problems, Muchnik degrees, and Kolmogorov's calculus of problems. We also provide an English translation of Muchnik's 1963 paper on Muchnik degrees.

preprint2013arXiv

Harrington's results on arithmetical singletons

We exposit two previously unpublished theorems of Leo Harrington. The first theorem says that there exist arithmetical singletons which are arithmetically incomparable. The second theorem says that there exists a ranked point which is not an arithmetical singleton. Unlike Harrington's proofs of these theorems, our proofs do not use the finite- or infinite-injury priority method. Instead they use an oracle construction adapted from the standard proof of the Friedberg Jump Theorem.

preprint2013arXiv

Propagation of partial randomness

Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-L"of random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.

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.

Stephen G. Simpson

Research overview

Is this your work?

7 publications

Pseudojump inversion in special r. b. $Π^0_1$ classes

Very weak fragments of weak Kőnig's lemma

Comparing WO $(ω^ω)$ with $Σ^0_2$ induction

Reverse mathematics, Young diagrams, and the ascending chain condition

Mass problems and intuitionistic higher-order logic

Harrington's results on arithmetical singletons

Propagation of partial randomness

See the researcher in context

Building this map preview

Stephen G. Simpson

Research overview

Is this your work?

7 publications

Pseudojump inversion in special r. b. Π10Π^0_1Π10​ classes

Very weak fragments of weak Kőnig's lemma

Comparing WO(ωω)(ω^ω)(ωω) with Σ20Σ^0_2Σ20​ induction

Reverse mathematics, Young diagrams, and the ascending chain condition

Mass problems and intuitionistic higher-order logic

Harrington's results on arithmetical singletons

Propagation of partial randomness

See the researcher in context

Building this map preview

Pseudojump inversion in special r. b. $Π^0_1$ classes

Comparing WO $(ω^ω)$ with $Σ^0_2$ induction