Show simple item record

dc.contributor.authorShafer, Paulen_US
dc.date.accessioned2012-12-17T13:53:11Z
dc.date.available2012-12-17T13:53:11Z
dc.date.issued2011-08-31en_US
dc.identifier.otherbibid: 7955521
dc.identifier.urihttps://hdl.handle.net/1813/30770
dc.description.abstractWe 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 ⊆. 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.en_US
dc.language.isoen_USen_US
dc.subjectmass problemsen_US
dc.subjectMedvedev degreesen_US
dc.subjectreverse mathematicsen_US
dc.titleOn The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematicsen_US
dc.typedissertation or thesisen_US
thesis.degree.disciplineMathematics
thesis.degree.grantorCornell Universityen_US
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Mathematics
dc.contributor.chairShore, Richard Aen_US
dc.contributor.committeeMemberNerode, Anilen_US
dc.contributor.committeeMemberKozen, Dexter Campbellen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics