BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Paul Shafer

Paul Shafer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.LO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

7 published item(s)

preprint2020arXiv

Ekeland's variational principle in weak and strong systems of arithmetic

We analyze Ekeland's variational principle in the context of reverse mathematics. We find that that the full variational principle is equivalent to $Π^1_1$-${\sf CA}_0$, a strong theory of second-order arithmetic, while natural restrictions (e.g.~to compact spaces or continuous functions) yield statements equivalent to weak König's lemma (${\sf WKL}_0$) and to arithmetical comprehension (${\sf ACA}_0$). We also find that the localized version of Ekeland's variational principle is equivalent to $Π^1_1$-${\sf CA}_0$ even when restricting to continuous functions. This is a rare example of a statement about continuous functions having great logical strength.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Honest elementary degrees and degrees of relative provability without the cupping property

An element $a$ of a lattice cups to an element $b > a$ if there is a $c < b$ such that $a \cup c = b$. An element of a lattice has the cupping property if it cups to every element above it. We prove that there are non-zero honest elementary degrees that do not have the cupping property, which answers a question of Kristiansen, Schlage-Puchta, and Weiermann. In fact, we show that if $\mathbf b$ is a sufficiently large honest elementary degree, then there is a non-zero honest elementary degree $\mathbf a <_{\mathrm E} \mathbf b$ that does not cup to $\mathbf b$. For comparison, we modify a result of Cai to show that in several versions of the related degrees of relative provability the preceding property holds for all non-zero $\mathbf b$, not just sufficiently large $\mathbf b$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Comparing the strength of diagonally non-recursive functions in the absence of $Σ^0_2$ induction

We prove that the statement &#34;there is a $k$ such that for every $f$ there is a $k$-bounded diagonally non-recursive function relative to $f$&#34; does not imply weak König&#39;s lemma over $\mathrm{RCA}_0 + \mathrm{B}Σ^0_2$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every $k$-bounded diagonally non-recursive function computes a $2$-bounded diagonally non-recursive function may fail in the absence of $\mathrm{I}Σ^0_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On uniform relationships between combinatorial problems

The enterprise of comparing mathematical theorems according to their logical strength is an active area in mathematical logic. In this setting, called reverse mathematics, one investigates which theorems provably imply which others in a weak formal theory roughly corresponding to computable mathematics. Since the proofs of such implications take place in classical logic, they may in principle involve appeals to multiple applications of a particular theorem, or to non-uniform decisions about how to proceed in a given construction. In practice, however, if a theorem $\mathsf{Q}$ implies a theorem $\mathsf{P}$, it is usually because there is a direct uniform translation of the problems represented by $\mathsf{P}$ into the problems represented by $\mathsf{Q}$, in a precise sense. We study this notion of uniform reducibility in the context of several natural combinatorial problems, and compare and contrast it with the traditional notion of implication in reverse mathematics. We show, for instance, that for all $n,j,k \geq 1$, if $j < k$ then Ramsey&#39;s theorem for $n$-tuples and $k$ many colors does not uniformly reduce to Ramsey&#39;s theorem for $j$ many colors. The two theorems are classically equivalent, so our analysis gives a genuinely finer metric by which to gauge the relative strength of mathematical propositions. We also study Weak König&#39;s Lemma, the Thin Set Theorem, and the Rainbow Ramsey&#39;s Theorem, along with a number of their variants investigated in the literature. Uniform reducibility turns out to be connected with sequential forms of mathematical principles, where one wishes to solve infinitely many instances of a particular problem simultaneously. We exploit this connection to uncover new points of difference between combinatorial problems previously thought to be more closely related.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universality, optimality, and randomness deficiency

A Martin-Löf test $\mathcal U$ is universal if it captures all non-Martin-Löf random sequences, and it is optimal if for every ML-test $\mathcal V$ there is a $c \in ω$ such that $\forall n(\mathcal{V}_{n+c} \subseteq \mathcal{U}_n)$. We study the computational differences between universal and optimal ML-tests as well as the effects that these differences have on both the notion of layerwise computability and the Weihrauch degree of LAY, the function that produces a bound for a given Martin-Löf random sequence&#39;s randomness deficiency. We prove several robustness and idempotence results concerning the Weihrauch degree of LAY, and we show that layerwise computability is more restrictive than Weihrauch reducibility to LAY. Along similar lines we also study the principle RD, a variant of LAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAY.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Reverse Mathematics and Algebraic Field Extensions

This paper analyzes theorems about algebraic field extensions using the techniques of reverse mathematics. In section 2, we show that $\mathsf{WKL}_0$ is equivalent to the ability to extend $F$-automorphisms of field extensions to automorphisms of $\bar{F}$, the algebraic closure of $F$. Section 3 explores finitary conditions for embeddability. Normal and Galois extensions are discussed in section 4, and the Galois correspondence theorems for infinite field extensions are treated in section 5.

0 citations0 reviewsNo code linkedOpen access