University of Leeds
Calibrating the complexity of combinatorics: reverse mathematics and Weihrauch degrees of some principles related to Ramsey’s theorem
Abstract
dc:description.abstractIn this thesis, we study the proof-theoretical and computational strength of some combinatorial principles related to Ramsey's theorem: this will be accomplished chiefly by analyzing these principles from the points of view of reverse mathematics and Weihrauch complexity. We start by studying a combinatorial principle concerning graphs, introduced by Bill Rival and Ivan Sands as a form of ``inside-outside'' Ramsey's theorem: we will determine its reverse mathematical strength and present the result characterizing its Weihrauch degree. Moreover, we will study a natural restriction of this principle, proving that it is equivalent to Ramsey's theorem. We will then move to a related result, this time concerning countable partial orders, again introduced by Rival and Sands: we will give a thorough reverse mathematical investigation of the strength of this theorem and of its original proof. Moreover, we will be able to generalize it, and this generalization will itself be presented in the reverse mathematical perspective. After this, we will focus on two forms of Ramsey's theorem that can be considered asymmetric. First, we will focus on a restriction of Ramsey's theorem to instances whose solutions have a predetermined color, studying it in reverse mathematics and from the point of view of the complexity of the solutions in a computability theoretic sense. Next, we move to a classical result about partition ordinals, which will undergo the same type of analysis. Finally, we will present some results concerning a recently introduced operator on the Weihrauch degrees, namely the first-order part operator: after presenting an alternative characterization of it, we will embark on the study the result of its applications to jumps of Weak Kőnig's Lemma.
Degree
thesis:*- Name dc:type.qualificationname
- Ph.D
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- University of Leeds
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Solda, Giovanni
- Advisors dc:contributor.advisor
-
- Shafer, Paul
- Rathjen, Michael
Rights
- Language dc:language.dcterms_iso639_2
- eng
Identifiers
dc:identifier.*- Identifier
- uk.bl.ethos.839175