The bulk of my mathematical research is on reverse mathematics and
on the degrees of unsolvability of mass problems.
Reverse Mathematics: Reverse mathematics is a study of
the logical strength of mathematical theorems in the context of
second-order arithmetic. The goal is to determine what axioms
are necessary and sufficient to prove a given theorem. To show
that certain axioms suffice to prove a given theorem, all we need is
a proof of that theorem from the axioms. To show that certain
axioms are necessary to prove a given theorem, we fix a set of weak
axioms once-and-for-all and show that if the given theorem is added
to these weak axioms, then we can prove each of the stronger axioms
we started with. This means that the strong axioms were indeed
necessary to prove the theorem. The proofs of the strong
axioms from the weak axioms and the given theorem are the "reverse"
in "reverse mathematics."
Degrees of unsolvability of mass problems: A mass
problem is simply a set of functions thought of as an abstract
mathematical problem, namely the problem of finding a function in
that set. The Medvedev and Muchnik degrees provide frameworks
for analyzing the computational relationships among mass problems
just as the classical Turing degrees provide a framework for
analyzing the computational relationships among functions.
Under the interpretation of mass problems as mathematical problems,
the Medvedev and Muchnik degrees formalize the "problem A is computationally harder
than problem B"
Papers (the versions hosted
here differ slightly from the official versions):
Paul Shafer. Effective powers of omega over Delta_2
cohesive sets, and an infinite Pi_1 set with no Delta_2
cohesive subset. preprint. pdfarXiv
Marta Fiori-Carones, Alberto Marcone, Paul Shafer, and
Giovanni Soldà. (Extra)ordinary equivalences with the
ascending/descending sequence principle.
Paul Shafer and Sebastiaan A. Terwijn. Ordinal
analysis of partial combinatory algebras. Journal of
Symbolic Logic 86 (2021). no. 3.
Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul
Shafer, Alexandra A. Soskova, and Stefan V. Vatev. On
cohesive powers of linear orders. preprint. pdfarXiv
Marta Fiori-Carones, Paul Shafer, and Giovanni Soldà. An
inside/outside Ramsey theorem and recursion theory.
Transactions of the American Mathematical Society 375
(2022). no. 3. 1977–2024. pdfarXiv
Paul Shafer. The strength of compactness for
countable complete linear orders. Computability 9
(2020). no. 1. 25–36. pdfarXiv
David Fernández-Duque, Paul Shafer, and Keita Yokoyama.
Ekeland's variational principle in weak and strong systems of
arithmetic. Selecta Mathematica, New Series 26
(2020). no. 5. Paper no. 68. 38pp. pdfarXiv
André Nies and Paul Shafer. Randomness notions and
reverse mathematics. Journal of Symbolic Logic 85
(2020). no. 1. 271–299. pdfarXiv
Paul Shafer and Andrea Sorbi. Comparing the degrees
of enumerability and the closed Medvedev degrees.
Archive for Mathematical Logic 58 (2019). no.
5-6. 527–542. pdfarXiv
Paul Shafer. Honest elementary degrees and degrees
of relative provability without the cupping property.
Annals of Pure and Applied Logic 168 (2017). no.
5. 1017–1031. pdfarXiv
Paul Shafer. The reverse mathematics of the Tietze
extension theorem. Proceedings of the American
Mathematical Society 144 (2016). no. 12.
Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul
Shafer, and Jeroen Van der Meeren. Reverse
mathematics, well-quasi-orders, and Noetherian spaces.
Archive for Mathematical Logic 55 (2016). no.
3-4. 431–459. pdfarXiv
Laurent Bienvenu, Ludovic Patey, and Paul Shafer. On
the logical strengths of partial solutions to mathematical
problems. Transactions of the London Mathematical
Society 4 (2017). no. 1. 30–71. pdfarXiv
Rupert Hölzl and Paul Shafer. Universality,
optimality, and randomness deficiency. Annals of
Pure and Applied Logic 166
(2015). no. 10. 1049–1069. pdfarXiv
François G. Dorais, Jeffry L. Hirst, and Paul Shafer. Comparing
the strength of diagonally non-recursive functions in the
absence of Sigma^0_2 induction. Journal of Symbolic
Logic 80 (2015). no. 4. 1211–1235. pdfarXiv
Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter, and
Paul Shafer. Randomness and semi-measures.
Notre Dame Journal of Formal Logic 58 (2017). no.
3. 301–328. pdfarXiv
François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst,
Joseph R. Mileti, and Paul Shafer. On uniform relationships between
combinatorial problems. Transactions of the
American Mathematical Society 368 (2016). no.
2. 1321–1359. pdfarXiv
François G. Dorais, Jeffry Hirst, and Paul Shafer. Reverse mathematics and algebraic
field extensions. Computability 2
(2013). no. 2. 75–92. pdfarXiv
François G. Dorais, Jeffry Hirst, and Paul Shafer. Reverse mathematics, trichotomy,
and dichotomy. Journal of Logic and Analysis 4 (2012). Paper no.
13. 14pp. pdf
Paul Shafer. Menger's
theorem in Pi^1_1-CA_0. Archive for Mathematical
Logic 51 (2012).
no. 3-4. 407–423. pdf
Paul Shafer. Coding
true arithmetic in the Medvedev degrees of Pi^0_1 classes.
Annals of Pure and Applied Logic 163 (2012). no. 3. 321–337. pdf
Paul Shafer. Coding
true arithmetic in the Medvedev and Muchnik degrees.
Journal of Symbolic Logic 76
(2011). no. 1. 267–288. pdf
Paul Shafer. Characterizing
the join-irreducible Medvedev degrees. Notre Dame
Journal of Formal Logic 52
(2011). no. 1. 21–38. pdf
Paul Shafer. On the
complexity of mathematical problems: Medvedev degrees and
reverse mathematics. PhD thesis. Cornell
University, 2011. pdf
An inside-outside Ramsey theorem in the Weihrauch degrees.
Given at the Swansea University Computer Science Seminar
on January 21, 2020.
Randomness notions and reverse mathematics. Given
at Proof Theory, Modal Logic, and Reflection Principles 2019
in Barcelona, Spain on November 6, 2019 and at the Computability
Theory and Applications Online Seminar / Midwest Computability
Seminar (virtual) on November 10, 2020.
Exploring the strength of Caristi's fixed point theorem and
Ekeland's variational principle. Given at the University
of Bristol Logic and Set Theory Seminar in Bristol, United
Kingdom on October 23, 2019.
Reverse mathematics of an inside/outside Ramsey theorem.
Given at Reverse Mathematics of Combinatorial Principles
in Oaxaca, Mexico on September 20, 2019.
Cohesive powers of linear orders. Given at Computability
in Europe 2019 in Durham, United Kingdom on July 15, 2019,
at Logic Colloquium 2019 in Prague, Czech Republic on
August 12, 2019, at the Computability Theory Seminar of
the MSRI program on Decidability, Definability and Computability
in Number Theory (virtual) on October 30, 2020, and at Joint
Mathematics Meetings 2021 (virtual) on January 7, 2021.
An introduction to computable functions and computable
structures. Given at the General Meeting of the
London Mathematical Society in London, United Kingdom on
June 28, 2019.
PhD short course on Medvedev and Muchnik degrees.
10-hour course given at the University of Udine during September
Reverse mathematics, a Ramsey theorem for graphs, and
complete linear orders. Given at the Workshop on
Ramsey Theory and Computability in Rome, Italy on July 9,
Reverse mathematics of Caristi's fixed point theorem and
Ekeland's variational principle. Given at ASL
North American Annual Meeting 2018 in Macomb, IL on May
19, 2018 and at Workshop: Proofs and Computation in
Bonn, Germany on July 2, 2018.
The reverse mathematics of Ekeland's variational principle.
Given at Proof Theory, Modal Logic, and Reflection
Principles 2017 in Moscow, Russia on October 17, 2017.
The reverse mathematics of Caristi's fixed point theorem.
Given at the 11th Panhellenic Logic
Symposium in Delphi, Greece on July 13, 2017 and at the University
of Manchester Logic Seminar in Manchester, United Kingdom
on November 29, 2017.
Honest elementary degrees without the cupping property.
Given at Computability in Europe 2016 in Paris, France
on June 28, 2016; at Proof Theory, Modal Logic, and
Reflection Principles Third International Wormshop in
Tbilisi, Georgia on September 8, 2016; and at the Conference
on Mathematical Logic in Gyolechitsa, Bulgaria in honor of
Dimiter Skordev's 80th birthday on October 8, 2016.
A tour of the mass problems. Given at The
Foundational Impact of Recursion Theory in Storrs, CT in
honor of Steve Simpson's 70th birthday on May 22, 2016.
Reverse mathematics and the strong Tietze extension
theorem. Given at the New Challenges in Reverse
Mathematics Workshop in Singapore on January 11, 2016 and
at Computability Theory and Foundations of Mathematics 2016
in Tokyo, Japan on September 20, 2016.
Universality, optimality, and randomness deficiency.
Given at Varieties of Algorithmic Information in
Heidelberg, Germany on June 18, 2015 and at Logic Colloquium
2015 in Helsinki, Finland on August 4, 2015.
Reverse mathematics, well-quasi-orders, and Noetherian
spaces. Given at the Sets and Computations
Workshop in Singapore on April 20, 2015 and at Computability
in Europe 2015 in Bucharest, Romania on July 2, 2015.
Exploring randomness, diagonally non-recursiveness, and
Ramsey-type combinatorial principles in reverse mathematics.
Given at ASL North American Annual Meeting 2014 in
Boulder, CO on May 21, 2014 and at Proof Theory, Modal
Logic, and Reflection Principles Second International Wormshop
in Mexico City, Mexico on September 30, 2014.
Studying the role of induction axioms in reverse
mathematics. Given at the Sendai Logic School
in Tokyo, Japan on February 21, 2014.
Separating the uniformly computably true from the
computably true via strong Weihrauch reducibility.
Given at Computability Theory and Foundations of Mathematics
2014 in Tokyo, Japan on February 17, 2014.
Examples of problems that cannot be solved by randomness
and examples of problems that can be solved by randomness.
Given at the University of Udine Department of Mathematics
and Computer Science Seminar in Udine, Italy on September
17, 2013 and at the Sendai Logic Seminar in Sendai,
Japan on February 14, 2014.
Reverse mathematics and Birkhoff’s problem 111.
Given at the Bundeswehr University Munich Seminar for
Theoretical Computer Science and Mathematical Logic in
Munich, Germany on August 21, 2013.
Comparing the strength of DNR(k) functions and DNR(2)
functions. Given at Logic Colloquium 2013 in
Évora, Portugal on July 22, 2013.
A low DNR(k) function that computes no DNR(2) function.
Given at the Workshop on Reverse Mathematics and Type Theory
in Seoul, South Korea on March 26, 2013 and at Journées
Calculabilités 2013 in Nancy, France on April 11, 2013.
Randomness from an
algorithmic perspective. Given at the ENS
Lyon Semaine Sport-Etudes 2012-2013 in Les 7 Laux, France
on January 26, 2013.
Logics and complexity in a
calculus of problems. Given at the Ghent
University Logic and Analysis Seminar in Ghent, Belgium on
October 24, 2012.
Presenting the effectively
closed Medvedev degrees requires 0'''. Given at
ASL North American Annual Meeting 2012 in Madison,
Wisconsin on March 31, 2012.
The Medvedev degrees as
semantics for propositional logic. Given at AMS
Spring Eastern Sectional Meeting 2012 in Washington, DC on
March 18, 2012.
Complexity in the degrees of
unsolvability of mass problems. Given at ASL
Winter Meeting 2012 in Boston, Massachusetts on January 6,
Complexity in the Medvedev
and Muchnik degrees. Given at the Penn State
Logic Seminar in State College, Pennsylvania on October
Describing the complexity of
the "problem B is
harder than problem A"
relation. Given at the Appalachian State
University Mathematical Sciences Colloquium in Boone,
North Carolina on October 7, 2011.
Complexity in the Medvedev
degrees of Pi^0_1 classes. Given at Workshop
on Computability Theory 2011, part 2 in Barcelona, Spain
on July 17, 2011.
Birkhoff's theorem and
reverse mathematics. Given at AMS Fall
Central Sectional Meeting 2010 in Notre Dame, Indiana on
November 7, 2010.
characterizing the first-order theory and the
join-irreducibles. Given at the Notre Dame
Logic Seminar in Notre Dame, Indiana on November 4, 2010.
Menger's theorem in
Pi^1_1-CA_0. Given at Logic Colloquium 2010
in Paris, France on July 27, 2010.
arithmetic into the closed Medvedev degrees.
Given at ASL North American Annual Meeting 2010 in
Washington, DC on March 17, 2010.
The first-order theory of the
Medvedev lattice is third-order arithmetic. Given
at Logic Colloquium 2009 in Sofia, Bulgaria on August 4,
A characterization of the
join-irreducible Medvedev degrees. Given at
Computability in Europe 2009 in Heidelberg, Germany on
July 22, 2009.
Menger's theorem and reverse
mathematics. Given at the MIT Logic Seminar
in Cambridge, Massachusetts on April 2, 2008.
My undergraduate research in computer science consisted of work on
several projects in computational biology and the Biozon database
led by Golan Yona.
Eric O. Williams, Yuanyuan Xiao, Heather M. Sickles, Paul
Shafer, Golan Yona, Jean YH Yang, and David M. Lin. Novel subdomains of the mouse
olfactory bulb defined by molecular heterogeneity in the
nascent external plexiform and glomerular layers.
BMC Developmental Biology 7:48
Paul Shafer, David M. Lin, and Golan Yona. EST2Prot: Mapping EST sequences to
proteins. BMC Genomics 7:41 (2006).
Paul Shafer, Timothy Isganitis, and Golan Yona. Hubs of knowledge: using the
functional link structure of Biozon to mine for biologically
significant entities. BMC Bioinformatics 7:71 (2006).
Paul Shafer and Timothy Isganitis. Hubs of Knowledge: using the
functional link structure in Biozon to mine for biologically
significant entities. Given at ISMB 2005
in Detroit, Michigan on June 28, 2005.