Paul Shafer
Paul Shafer

Ph.D. (2011) Cornell University

First Position
Dissertation
Advisor:
Research Area:
Abstract: We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its firstorder theory, and we also calculate the complexities of the firstorder theories of several related structures. We characterize the joinirreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under the subset ordering. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions.