Paul Shafer

Paul Shafer
Ph.D. (2011) Cornell University

First Position

Lecturer at Appalachian State University

Dissertation

On the Complexity of Mathematical Problems: Medvedev Degrees and Reverse Mathematics

Advisor:


Research Area:
logic

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 first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible 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.